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

doi:10.3969/j.issn.1001-2400.2016.02.027

Abstract

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)

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.

References

［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]	DU Wenzhan,YU Zhiyong,YANG Jian,JIANG Haibin. Improved NSGA-II algorithm and research on monitoring antenna optimization deployment [J]. Journal of Xidian University, 2021, 48(5): 239-248.
[2]	WANG Yan. Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform [J]. Journal of Xidian University, 2019, 46(1): 130-136.
[3]	WANG Danqing;LI Ping. Expedited antenna multi-objective optimization method based on gradient-enhanced kriging surrogate model [J]. Journal of Xidian University, 2018, 45(2): 129-134+165.
[4]	WANG Mingzhao;WANG Yuping;WANG Xiaoli;WEI Zhen. Improved NSGA-Ⅱ algorithm based on the uniformly crowding distance [J]. Journal of Xidian University, 2016, 43(3): 49-54+130.
[5]	WEN Honghang;GE Jianhua;XU Tangwen. Low complexity method for PAPR reduction of OFDM signals [J]. J4, 2015, 42(5): 188-193.
[6]	DAI Cai;WANG Yuping;HE Xiaoguang. New ranking method for many-objective problems [J]. J4, 2014, 41(6): 89-94.
[7]	DONG Ning;WANG Yuping. Multi-objective evolutionary algorithm based on preference for constrained optimization problems [J]. J4, 2014, 41(1): 98-104+188.
[8]	PENG Yali;LIU Fang. Organizational evolutionary algorithm for occlusion recovery [J]. J4, 2013, 40(4): 137-141.
[9]	TONG Fei;WANG Jun;LI Hongwei. Novel passive radar location algorithm based on Memetic optimization by using the bearing-and-Doppler frequency [J]. J4, 2012, 39(4): 46-51+102.
[10]	CHENG Wei;SHI Haoshan;LI Dong. Novel localization algorithm based on evolutionary programming resampling in WSN [J]. J4, 2011, 38(4): 154-159.
[11]	LIU Ruochen;JIAO Licheng;LEI Qifeng;FANG Lingfen. New differential evolution constrained optimization algorithm [J]. J4, 2011, 38(1): 47-53.
[12]	MU Cai-hong;JIAO Li-cheng;LIU Yi. M-Elite coevolutionary algorithm for constrained optimization [J]. J4, 2010, 37(5): 852-861.
[13]	MA Jing-jing;YANG Dong-dong;JIAO Li-cheng. Immune nondominated adaptive particle swarm multi-objective optimization [J]. J4, 2010, 37(5): 846-851.
[14]	SHANG Rong-hua;JIAO Li-cheng;WU Jian-she;MA Wen-ping;LI Yang-yang. Immune clonal multi-objective algorithm for unsupervised feature selection [J]. J4, 2010, 37(1): 18-22.
[15]	SHANG Rong-hua;MA Wen-ping;JIAO Li-cheng;ZHANG Wei. Conal selection algorithm for multi-objective optimization problems [J]. J4, 2007, 34(5): 716-721.

Enhanced NNIA for multi-objective examination timetabling problems

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10