资源描述：
《用量子遗传算法求解大学排课问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、科学技术与工程用量子遗传算法求解大学排课问题曹敏志（湖南生物机电职业技术学院，湖南长沙410127）摘要：作为典型的NP完全问题，大学排课问题在教务管理系统中非常重要。本文通过对大学排课问题的数学模型的分析，运用量子遗传算法进行求解。实验结果表明，利用量子遗传算法求解大学排课问题要优于使用遗传算法。关键词：大学排课问题NP难问题遗传算法量子遗传算法中图分类号：TP301;文献标识码:AApplicationofQuantum-InspiredGeneticAlgorithmintheUniversityTi
2、metableProblemCAOMin-zhi(HunanBiologicalandElectromechanicalPolytechnic,Changsha410127,China)Abstract:AstheclassicNP-CompleteProblem,UniversityTimetableProblemisveryimportanttotheacademiccourseschedulingmanagementsystem.Inthispaper,themathematicmodelofuniv
3、ersitytimetableproblemisanalyzed,andthequantum-inspiredgeneticalgorithmisusedtosolveit.Theresultsofexperimentsshowthatthequantum-inspiredgeneticalgorithmismoreeffectivetogeneticalgorithminsolvingtheuniversitytimetableproblem.KeyWords:UniversityTimetablePro
4、blem;NP-hardProblem;GeneticAlgorithm;Quantum-InspiredGeneticAlgorithm科学技术与工程1.引言随着大学招生规模的扩大，而且大学的教学单位和课程众多，因此合理安排教师和教室的排课模型越来越复杂。大学排课问题（UniversityTimetableProblem，UTP）成为大学教务处最棘手和最费时的工作之一，如何有效实现智能排课具有重要的实际意义[1-4]。由于UTP为典型的NP完全问题[5]，随着问题规模的增长，传统的算法无法有效进行求解。作
5、为计算智能的典型算法，遗传算法（GeneticAlgorithm，GA）[6]在求解各类NP问题时表现出优异的定能，同时也存在收敛速度过慢等不足。本文针对UTP问题，通过采用量子遗传算法[7]进行有效的求解，实验结果表明用量子遗传算法求解UTP要优于遗传算法。2.UTP问题及其数学模型根据问题的描述，设立以下几个集合：教师集合：T={Ti
6、i=1,2,…,t}班级集合：S={Si
7、i=1,2,…,s}课程集合：C={Ci
8、i=1,2,…,c}教室集合：R={Ri
9、i=1,2,…,r}时间集合：M={Mi
10、i
11、=1,2,…,m}以及以这五个集合为基础构建的课元集：K={(t,s,c)
12、t∈T,s∈C,c∈C}资源集：Z={(r,m)
13、r∈R,m∈M}通过以上定义，可以讲UTP问题转化为求映射集F:K→Z的问题。3.量子遗传算法量子遗传算法（Quantum-InspiredGeneticAlgorithm，QGA）[7]是量子计算与遗传算法相结合的产物。QGA科学技术与工程建立在量子的态矢量表述基础上，用量子比特编码来表示染色体，用量子旋转门和量子非门来实现染色体的更新，从而实现对目标问题的优化求解。1.1量子位的
14、表示在QGA中，染色体不是用确定性的值（如二进制数、浮点数或符号等）表示，而是用量子位表示，一个量子位不仅仅表示0或1两种状态，而且同时表示这两种状态之间的任意中间态。一般地，用n个量子位就可以同时表示2n个状态，因而对于相同的优化问题，QGA的种群大小可比传统GA小很多。在QGA中，一个量子位可能处于或，或者处于和之间的中间态，即和的不同叠加态，因此一个量子位的状态可表示为：(1)其中和可以是复数，表示相应状态的概率幅，且满足下列归一化条件：(2)其中，表示的概率，表示的概率。1.2量子旋转门在QGA中，
15、由于染色体的状态处于叠加或纠缠状态，因而采用将量子门分别作用于各叠加态或纠缠态的方式；子代个体的产生不是由父代群体决定，而是由父代的最优个体及其状态的概率幅决定。遗传操作主要是将构造的量子门作用于量子叠加态或纠缠态的基态，使其相互干涉，相位发生改变，从而改变各基态的概率幅。因此，量子门的构造既是量子遗传操作要解决的主要问题，也是QGA的关键问题，因为它直接关系到QGA的性能好坏。在QGA中，主要采用量子旋转门，即
