量子启发式进化算法的排课问题应用  

Quantum-inspired Evolutionary Algorithm for Course Timetabling

作　　者：郑玉[1,2] 马廷淮[1] 刘文杰[1] 宣文霞[1] 

机构地区：[1]南京信息工程大学计算机与软件学院,南京210044 [2]南京理工大学计算机学院,南京210094

出　　处：《武汉理工大学学报》2010年第16期19-22,共4页Journal of Wuhan University of Technology

基　　金：国家自然科学基金(60632050)

摘　　要：针对复杂的高校排课问题,应用量子启发式遗传进化算法(QEA)建立数学模型,提出并实现了高校自动排课算法。该算法采用传统遗传算法(GA)的基本框架,摒弃了GA中的选择、交叉、变异等遗传算子,充分利用量子比特的叠加性、并行性和纠缠性,通过量子旋转门更新遗传基因来获得下一代染色体。实验表明,该算法与传统的遗传算法相比更为高效,能更快地得到最优解。This paper is the first to propose a quantum-inspired evolutionary algorithm（QEA） for the heavily constrained course timetabling problems（CTP）.In the QEA,Qbits based representation is employed by updating operator of quantum gate which is introduced as a variation operator to drive the individuals toward better solutions.The experimental results show that a set of high quality timetables can be achieved.

关 键 词：量子启发式进化算法 遗传算法 量子旋转门 量子比特 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]