基于模拟退火算法的优化选修课程安排问题研究

摘要

模拟退火算法是一种用于求解大规模优化问题的随机搜索算法，它以优化问题求解过程与物理系统退火过程之间的相似性为基础，适合处理NP完全组合优化问题。与其他求解NP完全问题的智能算法相比，它复杂性较低，适合于本课题的研究与应用。
　　 排课处理，选课处理都是典型的NP完全组合优化问题。目前针对排课优化处理算法的研究比较多，而针对选修课程安排与处理的研究则比较少。本文根据选修课程问题的特性，以选课结果的优化处理为目标，介绍了目前选课处理的现状和常用方案，研究运用改进后的模拟退火算法优化选课处理过程。
　　 本文的主要内容如下：
　　 (1)对选课处理过程建立了数学模型；
　　 (2)比较了常用算法的实用性，提出了一种使用模拟退火算法进行优化的解决方案；
　　 (3)对模拟退火算法进行改进，利用优化的数据结构和初始解提高运算速度，建立了带性能约束的多目标优化数学模型；
　　 (4)证明了改进后的算法能显著提高收敛速度，改进了原算法执行时间过长，性能对初始值和参数选择过分依赖的问题，方便了算法的实际应用使用。

目录

文摘

英文文摘

第1章 选课问题及其改进思路

1.1 选课问题的起因

1.2 选课问题的现状

1.3 选课改进的思路

第2章 模拟退火算法

2.1 NP完全问题

2.2 模拟退火算法

2.2.1 Metroplis算法

2.2.2 参数控制

2.3 选择模拟退火算法的原因

第3章 选课的数学模型

3.1 选课的约束条件

3.2 数学模型

第4章 算法的实现

4.1 基本流程

4.2 参数定义

4.3 处理过程

4.3.1 创建初始解

4.3.2 优化过程

4.4 中间数据保存

第5章 优化处理系统的实现

5.1 系统功能需求

5.1.1 参数设置

5.1.2 数据管理

5.1.3 执行优化处理过程

5.2 架构设计

5.2.1 显示层user interface layer

5.2.2 业务逻辑层Bussiness logical layer

5.2.3 数据访问层data access layer

5.3 详细设计

5.3.1 数据转换接口

5.3.2 创建初始解模块

5.3.3 核心处理模块

5.3.4 数据访问层

5.3.5 输出与表现层

5.4 实现

5.4.1 开发工具的选择

5.4.2 表现层的实现

5.4.3 用户界面-主界面

5.4.4 用户界面-数据库参数

5.4.5 用户界面-操作界面

5.4.6 数据转换接口

5.4.7 优化处理核心

5.4.8 数据访问层的实现

第6章 运行分析

6.1 最终结果

6.2 S1选择模式对结果影响

6.3 参数对过程及结果影响

6.4 结束语

参考文献

致谢