用量子遗传算法求解大学排课问题.doc

用量子遗传算法求解大学排课问题
　　摘要:作为典型的NP完全问题,大学排课问题在教务管理系统中非常重要。该文通过对大学排课问题的数学模型的分析,运用量子遗传算法进行求解。实验结果表明,利用量子遗传算法求解大学排课问题要优于使用遗传算法。
　　关键词:大学排课问题;NP难问题;遗传算法;量子遗传算法
　　中图分类号:G434文献标识码:A文章编号:1009-3044(2010)05-1174-02
　　Application of Quantum-Inspired Genetic Algorithm in the University Timetable Problem
　　CAO Min-zhi
　　(Hunan Biological and Electromechanical Polytechnic, Changsha 410127, China)
　　Abstract: As the classic NP-Complete Problem, University Timetable Problem is very important to the academic course scheduling management system. In this paper, the mathematic model of university timetable problem is analyzed, and the quantum-inspired genetic algorithm is used to solve it. The results of experiments show that the quantum-inspired genetic algorithm is more effective to genetic algorithm in solving the university timetable problem.
　　Key words: university timetable problem; NP-hard problem; genetic algorithm; quantum-inspired genetic algorithm
　　随着大学招生规模的扩大,而且大学的教学单位和课程众多,因此合理安排教师和教室的排课模型越来越复杂。大学排课问题(University Timetable Problem,UTP)成为大学教务处最棘手和最费时的工作之一,如何有效实现智能排课具有重要的实际意义[1-4]。由于UTP为典型的NP完全问题[5],随着问题规模的增长,传统的算法无法有效进行求解。作为计算智能的典型算法,遗传算法(Genetic Algorithm,GA)[6]在求解各类NP问题时表现出优异的定能,同时也存在收敛速度过慢等不足。本文针对UTP问题,通过采用量子遗传算法[7]进行有效的求解,实验结果表明用量子遗传算法求解UTP要优于遗传算法。
　　1 UTP问题及其数学模型
　　根据问题的描述,设立以下几个集合:
　　教师集合:T={Ti | i=1,2,…,t}
　　班级集合:S={Si | i=1,2,…,s}
　　课程集合:C={Ci | i=1,