基于MOEA/D的多目标考试时间表调度算法研究

摘要

调度问题自上世纪中后期便引起了大量学者的广泛关注,其中,时间表调度作为一类特殊的资源调度问题,广泛应用在学校课程和考试的时间安排、航班时刻表的制定、体育比赛等活动中,与人们的日常生活息息相关。本文以大学考试时间表问题作为研究对象进行了研究。
　　大学考试时间表问题作为一个NP完全问题,因其会随着问题规模的扩大,求解难度也会随着增大。近年来,用进化算法解决这类问题已经成为一个研究热点,得到了广泛的研究。对于大学考试时间表的研究目前主要还是集中在单目标方面,即在固定时间段的前提下,将一系列考试无冲突的安排到这些固定的时间段内。但是在实际的应用中,学校每学期的考试时间长度安排是不一样的,这也就导致决策者需要更多不同时间段的考试时间表来进行决策。同时,也有学者提出,如果时间段长度可以设定的很大,那很有可能会使冲突数变为零。从上可以得出,无论是实际需要还是理论研究,对多目标考试时间表的研究都是必须的。
　　在本文中,第一次使用基于分解的多目标进化算法(MOEA/D)解决多目标考试时间表问题,同时优化时间表的时间段长度和人均冲突数。首先针对多目标考试时间表问题的特殊性,本文设计了两种混合初始化方式、交叉和变异算子以及针对MOEA/D算法的邻域选择算子。通过在11个数据集上的对比实验,验证了本文提出的算法的有效性,能够解决多目标考试时间表这一问题。然后为了提高算法的收敛性以及 Pareto前沿面的均匀分布,本人提出了改进的 MOEA/D算法,即结合 Memetic算法,来解决多目标考试时间表问题。用两方向的局部搜索算子来提高收敛性,用时间段补充算子来改善Pareto前沿面的分布情况。在11个数据集上的实验结果验证了本文提出的这两个局部搜索算子的有效性。通过与其它算法的比较,也证明了本文算法的有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 引言

1.2 研究现状

1.3 本文的主要工作

第二章 大学考试时间表问题

2.1 大学考试时间表问题的相关概念

2.2 没有座位容量限制的大学考试时间表调度问题标准测试数据集

2.3 大学考试时间表问题的解决方案

2.4 本章小结

第三章 基于MOEA/D的多目标考试时间表调度算法

3.1 多目标优化问题的基本理论

3.2 基于MOEA/D的多目标考试时间表调度算法

3.3 实验结果

3.4 本章小结

第四章 基于改进的MOEA/D的多目标考试时间表调度算法

4.1 memetic算法概述

4.2 Memetic算法在多目标考试时间表问题中的应用

4.3 实验结果与分析

4.4 本章小结

第五章 总结和展望

5.1 本文主要工作总结

5.2 展望

致谢

参考文献

硕士期间研究成果