求解多目标考试时间表问题的NNIA改进算法

doi:10.3969/j.issn.1001-2400.2016.02.027

西安电子科技大学学报 ›› 2016, Vol. 43 ›› Issue (2): 157-161+192.doi: 10.3969/j.issn.1001-2400.2016.02.027

求解多目标考试时间表问题的NNIA改进算法

雷雨;焦李成;公茂果;李玲玲

(西安电子科技大学智能感知与图像理解教育部重点实验室，陕西西安 710071)

收稿日期:2015-01-08 出版日期:2016-04-20 发布日期:2016-05-27
通讯作者: 雷雨
作者简介:雷雨(1985-), 男，西安电子科技大学博士研究生，E-mail：xdleiyu@gmail.com．
基金资助:
国家自然科学基金资助项目(61273317)

Enhanced NNIA for multi-objective examination timetabling problems

LEI Yu;JIAO Licheng;GONG Maoguo;LI Lingling

(Ministry of Education Key Lab. of Intelligent Perception and Image Understanding, Xidian Univ., Xi'an 710071, China)

Received:2015-01-08 Online:2016-04-20 Published:2016-05-27
Contact: LEI Yu

摘要/Abstract

摘要：

针对多目标考试时间表问题，提出了一种用于求解多目标考试时间表问题的非支配邻域免疫改进算法．采用经典多目标进化算法非支配邻域免疫的算法框架，为改善该算法的收敛性和多样性，利用超启发方法生成初始种群，同时采用一种新的资源分配模型，在克隆过程中动态调节优秀个体的克隆比例，来改善算法的性能．采用10组标准测试数据对算法的性能进行测试．实验结果表明，该算法对多目标考试时间表问题十分有效，并且在某些测试数据上可得到令人满意的结果．

关键词: 多目标优化, 考试时间表, 进化算法, 资源分配模型, 非支配邻域免疫算法

Abstract:

Based on the nondominated neighbor immune algorithm(NNIA), an enhanced NNIA is introduced for multi-objective examination timetabling problems. With the framework of NNIA, the hyper-heuristic approach is utilized to generate the initial population. In addition, the resource allocation model is designed to dynamically adjust the clone percentage of potential individuals. Experimental results on ten benchmark datasets prove that the proposed algorithm can solve examination timetabling problems effectively and obtaine competitive results.

Key words: multi-objective optimization, examination timetabling, evolutionary algorithm, resource allocation model, nondominated neighbor immune algorithm(NNIA)

雷雨;焦李成;公茂果;李玲玲. 求解多目标考试时间表问题的NNIA改进算法[J]. 西安电子科技大学学报, 2016, 43(2): 157-161+192.

LEI Yu;JIAO Licheng;GONG Maoguo;LI Lingling. Enhanced NNIA for multi-objective examination timetabling problems[J]. Journal of Xidian University, 2016, 43(2): 157-161+192.

参考文献

［1］ BURKE E K, MCCOLLUM B, MEISELS A, et al. A Graph-based Hyper-heuristic for Educational Timetabling Problems［J］. European Journal of Operational Research, 2007, 176(1): 177-192.
［2］ ALZAQEBAH M, ABDULLAH S. An Adaptive Artificial Bee Colony and Late-acceptance Hill-climbing Algorithm for Examination Timetabling［J］. Journal of Scheduling, 2014, 17(3): 249-262.
［3］ THEPPHAKORN T, PONGCHAROEN P, HICKS C. An Ant Colony Based Timetabling Tool［J］. International Journal of Production Economics, 2014, 149: 131-144.
［4］ BURKE E, BYKOV Y, NEWALL J, et al. A Time-predefined Local Search Approach to Exam Timetabling Problems［J］. IIE Transactions, 2004, 36(6): 509-528.
［5］ THOMPSON J M, DOWSLAND K A. A Robust Simulated Annealing Based Examination Timetabling System［J］. Computers ＆ Operations Research, 1998, 25(7): 637-648.
［6］ BURKE E K, ECKERSLEY A J, MCCOLLUM B, et al. Hybrid Variable Neighbourhood Approaches to University Exam Timetabling［J］. European Journal of Operational Research, 2010, 206(1): 46-53.
［7］ SORIA-ALCARAZ J A, OCHOA G, SWAN J, et al. Effective Learning Hyper-heuristics for the Course Timetabling Problem［J］. European Journal of Operational Research, 2014, 238(1): 77-86.
［8］ GONG M, JIAO L, DU H, et al. Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection［J］. Evolutionary Computation, 2008, 16(2): 225-255.
［9］ ZHANG Q, LI H. MOEA/D: a Multi-objective Evolutionary Algorithm Based on Decomposition［J］. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
［10］董宁, 王宇平. 求解约束优化问题的偏好多目标进化算法［J］. 西安电子科技大学学报, 2014, 41(1): 98-104.
DONG Ning, WANG Yuping. Multi-objective Evolutionary Algorithm Based on Preference for Constrained Optimization Problems［J］. Journal of Xidian University, 2014, 41(1): 98-104.
［11］ CHEONG C Y, TAN K C, VEERAVALLI B. A Multi-objective Evolutionary Algorithm for Examination Timetabling［J］. Journal of Scheduling, 2009, 12(2): 121-146.
［12］康姝. 基于NNIA的多目标时间表调度问题研究［D］. 西安: 西安电子科技大学, 2014.
［13］孙娜娜. 基于MOEA/D的多目标考试时间表调度算法研究［D］. 西安: 西安电子科技大学, 2014.
［14］ CARTER M W, LAPORTE G, LEE S Y. Examination Timetabling: Algorithmic Strategies and Applications［J］. Journal of the Operational Research Society, 1996, 47(3): 373-383.
［15］ CARAMIA M, DELL'OLMO P, ITALIANO G F. Novel Local-search-based Approaches to University Examination Timetabling［J］. INFORMS-Informs Journal on Computing, 2008, 20(1): 86-99.
［16］ BURKE E K, BYKOV Y. Solving Exam Timetabling Problems with the Flex-deluge Algorithm［EB/OL］. ［2014-12-20］. http://www.docin.com/p-85694528.html.
［17］ ABDULLAH S, TURABIEH H, MCCOLLUM B. A Hybridization of Electromagnetic-like Mechanism and Great Deluge for Examination Timetabling Problems［C］//Lecture Notes in Computer Science: 5818 LNCS. Heiderlberg: Springer Verlage, 2009: 60-72.

[1]	张宇鹏,吴自力,陈鸣,张璐璐. 面向交叉微服务链的任务调度优化[J]. 西安电子科技大学学报, 2021, 48(6): 32-39.
[2]	杜文占,余志勇,杨剑,姜海滨. 改进NSGA-II算法及监测天线部署优化研究[J]. 西安电子科技大学学报, 2021, 48(5): 239-248.
[3]	杨五四,陈莉,王毅,张茂省. 一种适应度排序的高维多目标粒子群优化算法[J]. 西安电子科技大学学报, 2021, 48(3): 78-84.
[4]	刘天宇,王翥. 一种多样性控制的多目标粒子群算法[J]. 西安电子科技大学学报, 2021, 48(3): 106-114.
[5]	周杰,徐梦颖,王娇娇,卢毅. 认知无线传感器网络频谱分配的一种改进方法[J]. 西安电子科技大学学报, 2020, 47(3): 80-85.
[6]	杜振鑫,刘广钟,赵学华. 集成学习人工蜂群算法[J]. 西安电子科技大学学报, 2019, 46(2): 124-131.
[7]	王燕. 改进多目标进化算法的云工作流调度[J]. 西安电子科技大学学报, 2019, 46(1): 130-136.
[8]	宋嘉奇, 陶海红. 一种稀布阵列天线的近场波束综合算法[J]. 西安电子科技大学学报, 2018, 45(6): 14-18.
[9]	李枫, 王紫阳, 王乐, 李蕊, 冯罡, 尹应增. 抗干扰阵列天线的小型化及波束形成技术分析[J]. 西安电子科技大学学报, 2018, 45(6): 51-56.
[10]	韩亚敏;柴争义;李亚伦;朱思峰. 长尾群组推荐的免疫多目标优化实现[J]. 西安电子科技大学学报, 2018, 45(3): 109-116.
[11]	王丹青;李萍. 利用GEK代理模型的天线快速多目标优化设计[J]. 西安电子科技大学学报, 2018, 45(2): 129-134+165.
[12]	杨国平;刘三阳;张建科. 极小极大问题的生物地理学优化邻近点算法[J]. 西安电子科技大学学报, 2016, 43(5): 88-92+182.
[13]	王明昭;王宇平;王晓丽;卫珍. 一种均匀聚集距离的改进NSGA-Ⅱ算法[J]. 西安电子科技大学学报, 2016, 43(3): 49-54+130.
[14]	温鸿航;葛建华;许唐雯. 一种低复杂度OFDM峰均比降低方法[J]. J4, 2015, 42(5): 188-193.
[15]	代才;王宇平;何晓光. 高维多目标问题的排序新方法[J]. J4, 2014, 41(6): 89-94.

求解多目标考试时间表问题的NNIA改进算法

Enhanced NNIA for multi-objective examination timetabling problems

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10