面向考试时间表问题的启发式进化算法研究

发布时间：2017-08-07 05:03

  本文关键词：面向考试时间表问题的启发式进化算法研究

  更多相关文章： 进化算法 Memetic算法 单目标优化 多目标优化 考试时间表问题

【摘要】：时间表优化问题作为调度领域的研究热点问题,涉及范围大到军事国防,小到医院学校的时间安排,在现实世界中的应用领域十分广泛。开展时间表优化问题的高效进化算法研究对国家、社会和个人都具有重大的意义。本论文以考试时间表问题作为研究背景,分析现有解决该问题的进化算法所面临的主要问题,比如：传统的直接编码方式不利于算法的搜索；同样的进化操作算子及适应度函数不利于同时优化硬约束条件和软约束条件；传统单目标建模方式的运算效率较低等。通过对超启发技术、协同进化理论、多目标优化理论的深入研究,本论文提出了多种解决该问题的启发式进化算法,主要成果包括以下五部分内容：第一,借鉴超启发技术和进化的思想,提出一种基于超启发的Memetic算法(Memetic Algorithm based on Hyper-Heuristics, MAHH)用于求解单目标考试时间表优化问题。MAHH是一种结合了超启发技术和进化策略的混合算法。超启发技术的引入改变了传统进化算法直接对个体进行搜索的模式,采用一种间接的搜索模式,即通过传统进化策略搜索启发式链表的方式寻找潜在个体。这种搜索方式可有效避免在处理考试时间表优化问题时直接编码方式对算法搜索性能的影响。除此之外,一种特殊的邻域变异方式被用于有效的指导MAHH算法进行局部搜索。算法的仿真实验表明：MAHH的实验结果在11个测试问题中的整体表现较为出色,且3个测试问题的结果比其他7种传统的超启发解决方法更加优秀。第二,提出一种基于双进化策略的Memetic算法用于求解单目标考试时间表问题(Memetic Algorithm based on Double Evolutionary Strategies, MADES)。考试时间表中存在两类需要优化的子问题,即硬约束条件优化和软约束条件优化,两类子问题并不适用于相同的进化算子和适应度函数进行处理。MADES采用直接编码方式,在两个进化空间中分别采用两种不同的进化算子和适应度函数。此外,克隆算子的应用能有效改善考试时间表问题中可行个体不足的情况。MADES的仿真试验表明：MADES中的各算子都对算法的搜索产生积极的影响；算法的运行结果与其它多种经典的考试时间表问题优化算法相比具有一定的竞争性。第三,借鉴第一章超启发与进化混合的思想,以及第二章提出的双进化策略,提出一种求解单目标考试时间表问题的自适应协同进化Memetic算法(Adaptive Co-evolutionary Memetic Algorithm, ACMA)。ACMA采用启发式搜索空间和解空间两个进化空间,利用基于超启发的进化策略和传统的进化策略分别进行硬约束条件优化和软约束条件优化。此外,为了更合理的分配算法的计算资源,设计了一种自适应协同进化算子。该算子可根据种群中个体的实际情况,动态控制算法的搜索空间。同时,两空间的个体能够通过协同进化策略进行协作。随后的仿真实验表明：超启发进化策略的引入有利于算法更好的处理硬约束条件优化,而传统的进化策略则能够较好的保持种群的多样性；自适应参数能够指导算法在更加合适的空间进行搜索；协同进化算子则进一步减少了因搜索方式的固定搜索易于陷入局部最优的可能。与接近20种解决该问题的常见算法相比,ACN MA的结果仅次于当前效果最好的四种算法,明显优于其他方法。第四,为了给多目标考试时间表问题提供高效的进化算法,本工作进行多目标优化算法的理论研究,并提出一种新的多目标免疫算法(Enhanced Multi-Objective Immune Algorithm, EMIA)。EMIA算法借鉴了经典多目标优化算法NNIA的算法思路,构建了一种资源分配模型,并在此模型的基础上,结合NNIA的克隆策略,设计了一种可动态调节不同个体克隆比例的的新型克隆算子。此外一种新的拥挤距离度量方法的设计可有效改善原有方法在处理二目标以上问题上的不足,同时辅以拥挤距离动态更新策略,可使个体分布密度的估计更为准确。针对10个测试问题,EMIA与三种经典的多目标进化算法NNIA、NSGA-Ⅱ, MOEA/D进行比较,其结果表明EMIA在绝大多数问题中其收敛性和多样性均好于NNIA、 NSGA-II,在某些问题上EMIA的收敛性比MOEA/D更佳。第五,本工作首先构建了一种新的多目标考试时间表模型。随后根据此模型的特点,同时参考之前提出的EMIA算法,设计了一种解决该问题的EMIA改进算法。多目标考试时间表模型是在原有单目标时间表模型的基础上,增加一个时间表长度最小化的目标函数。EMIA的改进算法采用一种混合初始化方法,并且舍弃了EMIA中原有的拥挤距离度量方法,采用一种简单的新方法保证种群的多样性；同时采用一种特殊的局部搜索方法进一步优化个体。最终的仿真结果表明：EMIA的改进算法在处理多目标考试时间表问题时能够得到多样性和收敛性较好的非支配解集,并且在大部分问题上,与其它传统单目标优化算法的结果相差不大。
【关键词】：进化算法 Memetic算法 单目标优化 多目标优化 考试时间表问题
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18
【目录】：

• 摘要5-7
• ABSTRACT7-13
• 符号对照表13-14
• 缩略语对照表14-19
• 第一章 绪论19-31
• 1.1 研究背景与意义19-20
• 1.2 进化算法的分类和基本框架20-22
• 1.2.1 进化算法的分类20-22
• 1.2.2 进化算法的基本框架22
• 1.3 进化算法的最新进展22-25
• 1.3.1 免疫进化算法23
• 1.3.2 量子进化算法23
• 1.3.3 Memetic算法23-24
• 1.3.4 群智能算法24
• 1.3.5 协同进化算法24-25
• 1.4 考试时间表问题25
• 1.5 考试时间表问题相关技术的最新进展25-29
• 1.5.1 图启发技术25-26
• 1.5.2 基于局部搜索的技术26-27
• 1.5.3 基于种群的技术27-28
• 1.5.4 超启发方法28-29
• 1.6 本论文的主要工作29-31
• 第二章 求解考试时间表问题的MAHH算法31-47
• 2.1 引言31
• 2.2 考试时间表问题的数学描述31-32
• 2.3 MAHH的算法设计32-38
• 2.3.1 算法框架与主要流程32-33
• 2.3.2 超启发编码方式33-36
• 2.3.3 种群初始化方法36-37
• 2.3.4 局部搜索算子设计37-38
• 2.4 实验结果与分析38-45
• 2.4.1 实验设置38-39
• 2.4.2 测试数据39
• 2.4.3 初始化方法的性能分析39-41
• 2.4.4 不同图启发算法的性能分析41-42
• 2.4.5 局部搜索算子的性能分析42-44
• 2.4.6 算法最终结果的对比分析44-45
• 2.5 本章小结45-47
• 第三章 求解考试时间表问题的MADES算法47-59
• 3.1 引言47
• 3.2 MADES的算法设计47-52
• 3.2.1 算法框架与流程47-48
• 3.2.2 适应度值评价函数48-49
• 3.2.3 初始化方法49
• 3.2.4 交叉操作和变异操作49-50
• 3.2.5 局部搜索算子(第一进化空间)50-51
• 3.2.6 局部搜索算子(第二进化空间)51-52
• 3.3 实验结果与分析52-58
• 3.3.1 第二进化空间种群规模n的设定52-53
• 3.3.2 操作算子的性能分析53-56
• 3.3.3 算法最终结果对比与分析56-58
• 3.4 小结58-59
• 第四章 求解考试时间表问题的ACMA算法59-73
• 4.1 引言59
• 4.2 ACMA的算法设计59-64
• 4.2.1 算法框架与流程59-60
• 4.2.2 进化策略分析60-62
• 4.2.3 自适应协同进化策略62-64
• 4.3 实验结果与分析64-71
• 4.3.1 算法性能评价64-66
• 4.3.2 自适应协同进化策略性能分析66-69
• 4.3.3 局部搜索策略的性能分析69-71
• 4.4 小结71-73
• 第五章 一种改进的多目标免疫算法73-103
• 5.1 引言73
• 5.2 多目标优化问题的数学描述73-74
• 5.3 三种经典的进化多目标优化算法74-79
• 5.3.1 NSGA-Ⅱ74-76
• 5.3.2 MOEA/D76-77
• 5.3.3 NNIA77-79
• 5.4 EMIA的算法设计79-85
• 5.4.1 算法框架与流程79
• 5.4.2 一种新型的克隆算子79-83
• 5.4.3 一种新的拥挤距离度量方法83-84
• 5.4.4 重组操作与变异操作84-85
• 5.4.5 算法复杂度分析85
• 5.5 实验结果与分析85-101
• 5.5.1 测试问题85-87
• 5.5.2 性能评价指标87-88
• 5.5.3 拥挤距离算子的性能测试88-91
• 5.5.4 算法收敛性结果分析91-99
• 5.5.5 扩展性实验分析99-101
• 5.6 本章小结101-103
• 第六章 求解多目标考试时间表问题的EMIA改进算法103-121
• 6.1 引言103
• 6.2 多目标考试时间表问题103
• 6.3 EMIA改进算法的算法设计103-108
• 6.3.1 算法初始化104-105
• 6.3.2 局部搜索算子105-107
• 6.3.3 交叉和变异操作107-108
• 6.4 实验结果与分析108-119
• 6.4.1 实验设置108-109
• 6.4.2 初始化方法性能测试109-112
• 6.4.3 克隆操作算子的性能指标112-114
• 6.4.4 局部搜索算子的性能分析114-116
• 6.4.5 算法最终结果分析116-119
• 6.5 小结119-121
• 第七章 结论和展望121-123
• 7.1 总结与讨论121-122
• 7.2 进一步研究展望122-123
• 参考文献123-135
• 致谢135-137
• 作者简介137-138

【相似文献】

中国期刊全文数据库 前10条

1 葛磊;武芳;王鹏波;张冬林;;3维建筑综合中基于最小特征的面平移算法[J];测绘科学技术学报;2009年02期

2 骆雯,孙延明,陈振威,陈锦昌;判断点与封闭多边形相对关系的改进算法[J];机械;1999年03期

3 李林;卢显良;;一种基于切割映射的规则冲突消除算法[J];电子学报;2008年02期

4 刘巧玲;张红英;林茂松;;一种简单快速的图像去雾算法[J];计算机应用与软件;2013年07期

5 林亚平,杨小林;快速概率分析进化算法及其性能研究[J];电子学报;2001年02期

6 章郡锋;吴晓红;黄晓强;何小海;;基于暗原色先验去雾的改进算法[J];电视技术;2013年23期

7 杨铁军;靳婷;;一种动态整周模糊值求解算法及其仿真分析[J];系统工程与电子技术;2007年01期

8 周秀玲;郭平;陈宝维;王静;;几种计算超体积算法的比较研究[J];计算机工程;2011年03期

9 吴一戎,胡东辉,彭海良;Chirp Scaling SAR成象算法及其实现[J];电子科学学刊;1995年03期

10 王贵竹;一种产生单向分解值的算法[J];安徽大学学报(自然科学版);2001年03期

中国重要会议论文全文数据库 前10条

1 尹冀锋;;一种新的图象自适应增强算法[A];四川省通信学会一九九二年学术年会论文集[C];1992年

2 宁春平;田家玮;郭延辉;王影;张英涛;郑桂霞;刘研;;计算机辅助增强、分割算法在鉴别乳腺良、恶性肿块中的应用价值[A];中华医学会第十次全国超声医学学术会议论文汇编[C];2009年

3 谢丽聪;;SVB查询改写算法的改进[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

4 郑存红;;复杂背景下相关跟踪算法研究及DSP实现[A];中国光学学会2010年光学大会论文集[C];2010年

5 杨文杰;吴军;;RFID抗冲突算法研究[A];2008通信理论与技术新进展——第十三届全国青年通信学术会议论文集（上）[C];2008年

6 高山;毕笃彦;魏娜;;一种基于UPF的小目标TBD算法[A];第十四届全国图象图形学学术会议论文集[C];2008年

7 周磊;张卫华;王晓奇;张军;;基于流水算法的智能路障机器人设计[A];2011年全国电子信息技术与应用学术会议论文集[C];2011年

8 潘巍;李战怀;陈群;索博;李卫榜;;面向MapReduce的非对称分片复制连接算法优化技术研究[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

9 李伟伟;蔡康颖;郑新;王文成;;3D模型中重复结构的多尺度快速检测算法[A];第六届和谐人机环境联合学术会议（HHME2010)、第19届全国多媒体学术会议（NCMT2010）、第6届全国人机交互学术会议（CHCI2010）、第5届全国普适计算学术会议（PCC2010）论文集[C];2010年

10 杨任尔;陈恳;励金祥;;基于棱边方向检测的运动自适应去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中国重要报纸全文数据库 前1条

1 国泰君安资产管理部;“算法交易”是道指暴跌罪魁祸首?[N];上海证券报;2010年

中国博士学位论文全文数据库 前10条

1 冯辉;网络化的并行与分布式优化算法研究及应用[D];复旦大学;2013年

2 许玉杰;云计算环境下海量数据的并行聚类算法研究[D];大连海事大学;2014年

3 李琰;基于猫群算法的高光谱遥感森林类型识别研究[D];东北林业大学;2015年

4 陈加顺;海洋环境下聚类算法的研究[D];南京航空航天大学;2014年

5 王洋;基于群体智能的通信网络告警关联规则挖掘算法研究[D];太原理工大学;2015年

6 雷雨;面向考试时间表问题的启发式进化算法研究[D];西安电子科技大学;2015年

7 张冬丽;人工蜂群算法的改进及相关应用研究[D];燕山大学;2014年

8 徐悦竹;机会发现算法及其应用研究[D];哈尔滨工程大学;2010年

9 王征;分布式互斥算法的研究与实现[D];电子科技大学;2007年

10 王艳娇;人工蜂群算法的研究与应用[D];哈尔滨工程大学;2013年

中国硕士学位论文全文数据库 前10条

1 姚鑫宇;EMD去噪与MUSIC算法在DOA估计中的联合应用[D];昆明理工大学;2015年

2 陆进;面向含噪数据聚类相关算法的研究[D];复旦大学;2014年

3 李家昌;基于能量约束的超声图像自动分割算法[D];华南理工大学;2015年

4 陈坚;基于密度和约束的数据流聚类算法研究[D];兰州大学;2015年

5 高健;基于Zynq7000平台的去雾算法研究及实现[D];南京理工大学;2015年

6 顾磊;基于Hadoop的聚类算法的数据优化及其应用研究[D];南京信息工程大学;2015年

7 杨燕霞;基于Hadoop平台的并行关联规则挖掘算法研究[D];四川师范大学;2015年

8 王羽;基于MapReduce的社区发现算法的设计与实现[D];南京理工大学;2015年

9 许振佳;流式数据的并行聚类算法研究[D];曲阜师范大学;2015年

10 董琴;人工蜂群算法的改进与应用[D];大连海事大学;2015年

，

本文编号：632895