文档介绍：用量子遗传算法求解大学排课问题
曹敏志
(湖南生物机电职业技术学院,湖南长沙410127)
摘要:作为典型的NP完全问题,大学排课问题在教务管理系统中非常重要。本文通过对大学排课问题的数学模型的分析,运用量子遗传算法进行求解。实验结果表明,利用量子遗传算法求解大学排课问题要优于使用遗传算法。
关键词:大学排课问题 NP难问题遗传算法量子遗传算法
中图分类号:TP301; 文献标识码:A
Application of Quantum-Inspired ic Algorithm in the University Timetable Problem
CAO Min-zhi
(Hunan Biological and Electromechanical Polytechnic, Changsha 410127, China)
Abstract: As the classic plete 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 ic algorithm is used to solve it. The results of experiments show that the quantum-inspired ic algorithm is more effective to ic algorithm in solving the university timetable problem.
Key Words: University Timetable Problem; NP-hard Problem; ic Algorithm; Quantum-Inspired ic Algorithm
引言
随着大学招生规模的扩大,而且大学的教学单位和课程众多,因此合理安排教师和教室的排课模型越来越复杂。大学排课问题(University Timetable Problem,UTP)成为大学教务处最棘手和最费时的工作之一,如何有效实现智能排课具有重要的实际意义[1-4]。由于UTP为典型的NP完全问题[5],随着问题规模的增长,传统的算法无法有效进行求解。作为计算智能的典型算法,遗传算法(ic Algorithm,GA)[6]在求解各类NP问题时表现出优异的定能,同时也存在收敛速度过慢等不足。本文针对UTP问题,通过采用量子遗传算法[7]进行有效的求解,实验结果表明用量子遗传算法求解UTP要优于遗传算法。
UTP问题及其数学模型
根据问题的描述,设立以下几个集合:
教师集合:T={Ti | i=1,2,…,t}
班级集合:S={Si | i=1,2,…,s}
课程集合:C={Ci | i=1,2,…,c}
教室集合:R={Ri | i=1,2,…,r}
时间集合:M={Mi | i=1,2,…,m}
以及以这五个集合为基础构建的
课元集:K={(