摘要：量子遗传进化算法是量子计算和遗传算法相结合的产物，量子比特是两个量子态的叠加态，在此，详细介绍了量子遗传进化算法。尝试使用量子遗传进化算法来解决高校排课问题，并进行了实验。实验结果表明，该算法获得了比较好的结果。

　　关键字：高校排课问题；遗传算法；量子遗传进化算法；课程表

　　中图分类号：TN911?34文献标识码：A文章编号：1004?373X（2013）20?0007?04

　　高校排课问题一直是很多人关注的一个问题，排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，在运筹学中被称为时间表问题。

　　1排课问题分析

　　高校排课问题中实际上是时间表安排的问题[1]。在实际排课过程中，主要涉及到：教室、班级、课程、时间和老师等5个因素的问题。在处理这5个因素关系的过程中会发生很多冲突，这就需要有一些约束条件，这些约束条件可以大致分为硬约束和软约束，详见表1。

　　根据以上的分析排课问题数学模型分为下面5个集合如下：教室集合：[R={r1，r2，…，rm}]；班级集合：[C={c1，c2，…，cn}]；课程集合：[L={l1，l2，…，lp}]；教师集合：[S=表1排课问题的软硬约束条件

　　上述5个元素是影响排课问题的主要的因素，每个集合中取一个组成在某个时间某班上的课程由哪位老师来授课，在哪个教室上课，但必须满足一定的条件。

　　2量子遗传进化算法

　　量子遗传进化算法是量子计算与遗传算法相结合的产物[2]。目前，这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法（QuantumInspiredGeneticAlgorithm）；另一类是基于量子比特和量子态叠加特性的遗传量子算法（GeneticQuantumAlgorithm，GQA）[3]。

　　2.1量子位表示法

　　在量子信息论中，信息的载体不再是经典的比特，而是个一般的二态量子体系，称为量子比特（qubit）。量子比特与经典位不同就在于它可以同时处在两个量子态的叠加态中[4]，比如：

　　式中：[α，β]是两个复常数，满足：

　　式中[0]和[1]分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态[0]和[1]的信息；[α]表示相应的qubit处于0状态的概率幅；[β]表示其处于1状态的概率幅。[α2]表示处于0状态的概率，[β2]表示处于1状态的概率[3]。一个具有m个量子比特位的系统可以描述为：

　　其中[αj2+βj2=1，j=1，2，…，m]。这种表示方法可以表示任意的线性叠加态，例如一个具有如下概率幅的量比特系统：

　　则系统的状态可以表示为：

　　上面结果表示状态[00，001，010，011，100，101，][110，111]出现的概率分别为[38，132，332，332，332，][132，332，332，]即这个量子比特系统表示了8个状态叠加的信息而且随着趋于1或0，量子染色体收敛于一个状态，这时多样性消失，算法收敛[5]。

　　2.2量子旋转门

　　在遗传算法中，可以通过交叉，变异来得到新的个体，而在量子遗传进化算法中，是通过量子旋转门来进行更新的[6]。

　　量子旋转门如下：

　　比如对[αiβi]进行更新，可以用式（6）来进行更新：

　　式中[Δθi]的取值对算法的执行效率有很大的影响，具体确定过程如表2所示。其中：[fx]和[fb]表示解的fitness，[x]为当前解，[b]为[btj]；[Xi]和[bj]分别表示解[x]和[b]的第i个bit位的取值；[sαiβi]为[Δθi]的符号[7]。

　　例如，如果条件[fx≥fb]成立，且[xi]和[bj]分别为1和0，则[Δθi]的取值为0.025π，然后根据[αi]和[βi]的值可将其符号设置为+1，-1和0来增加qubit处于1状态的概率。若[αiβi>0]，即[Δθi]为+0.025π，将[Δθi]代入式（6）中得到新的[αli]和[βli]，使qubit处于1状态的概率增加，具体分析如图1所示。

　　[Δθi]取值的大小会影响算法的收敛速度，如果取值过大会导致早熟收敛得不到最优解；[Δθi]的符号决定解的收敛方向[8]。

　　3量子遗传进化算法和遗传算法来解决高校

　　排课问题

　　3.1具体高校排课问题简介

　　对于一个具体的排课问题，分别采用量子遗传进化算法和遗传算法来解决，并对它们的结果进行分析[9]。简化的高校排课问题是针对一个班级来排课，有7门课程，其中，有部分课程是一周上一次，还有部分课程是一周上两次，每门课程都有各自的重要性，每个时间段，都有不同的听课效率，为了排出合格课表。下面先通过量子遗传进化算法来排课表，最终得到的课表通过课程的重要性乘以时间段的听课效率的总和来比较课表的优劣，最终的值越大，且不存在冲突，则课表越好[10]。

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。