遗传算法在求解时间表问题中的应用研究

摘要

本文以大学课程安排时间表问题为研究对象，分析了其约束条件，建立了数学模型，提出了基于班级课表的主染色体和教室课表、教师课表的辅助染色体，从而方便了问题的求解。针对标准遗传算法局部搜索能力弱、收敛速度慢的缺点，将一些传统的启发式算法引入到遗传算法中，提出了两阶段启发式混合遗传算法，实际的应用结果表明该算法的改进是非常有效的。在已有的遗传算法求解大学课程时间表问题中，普遍采用了线性加权的方法将各优化目标转化为单目标来进行求解，但由于各优化目标之间存在着相互冲突和矛盾，加权系数难以确定，求解的结果收敛于单一的特定值。因此，根据多目标优化基本理论，本文将基于多目标优化的向量评价遗传算法(VEGA)应用到大学课程时间表问题中，算法运行一次就具有多种优化的结果，表现出了较好的多样性。

目录

文摘

英文文摘

浙江工业大学学位论文原创性声明和版权使用授权书

第一章绪论

1.1研究背景

1.2研究内容和特色

第二章时间表问题

2.1时间表问题

2.1.1时间表问题概述

2.1.2时间表问题的一般数学模型

2.1.3时间表问题的求解难度

2.2排课时间表问题

2.2.1排课问题概述

2.2.2人工排课的思维过程

2.2.3人工排课的特点

2.2.4排课时间表问题是NP完全问题

2.3排课时间表问题求解模型

2.3.1符号约定

2.3.2优化模型

2.4排课时间表问题常用求解方法

第三章遗传算法的基本原理和方法

3.1遗传算法发展历史

3.2遗传算法的基本思想

3.3遗传算法的基本过程

3.3.1编码

3.3.2群体设定

3.3.3适应度函数

3.3.4遗传操作

3.4遗传算法的收敛性

3.5遗传算法机理的简要分析

3.5.1模式定理

3.6遗传算法的特点

第四章基于遗传算法的排课时间表问题求解

4.1排课时间表的资源集合

4.2排课时间表问题的优化目标

4.2.1节次优先度

4.2.2上课周次组合优先度

4.2.3教师期望时间优先度

4.2.4班级日课时分布均匀度

4.3基于遗传算法的排课时间表求解算法设计

4.3.1算法总体思想

4.3.2算法总体框架

4.3.3遗传算法设计

4.4基于单目标优化的排课时间表求解

4.4.1适应度函数设计

4.4.2遗传操作

4.4.4运算结果与分析

4.5启发式算法在排课时间表中的应用

4.5.1启发式遗传算法的基本原理

4.5.2运算结果及分析

4.6本章小结

第五章多目标遗传算法在排课时间表问题中的应用

5.1多目标优化遗传算法

5.1.1多目标优化的基本概念

5.1.2 MOP的基本求解方法

5.1.3多目标优化遗传算法

5.1.4多目标优化遗传算法框架

5.2向量评价方法在排课时间表问题中应用

5.2.1各单目标的排课遗传算法优化

5.2.2向量评价遗传算法(VEGA)

5.2.3基于VEGA的排课时间表算法框架图

5.2.4遗传操作

5.2.5运算结果及分析

5.3本章小结

第六章总结与展望

6.1全文总结

6.2研究展望

参考文献

攻读硕士学位期间参加的科研项目和发表的论文

参加的科研项目

发表的论文

致 谢