—种基于高校排课问题的新型量子遗传进化算法作者：沈微微华明正史洪玮摘耍：量子遗传进化算法是量子计算和遗传算法相结合的产物，量子比特是两个量子态的叠加态，在此，详细介绍了量子遗传进化算法。尝试使用量子遗传进化算法来解决高校排课问题，并进行了实验。实验结果表明，该算法获得了比较好的结果。关键字：高校排课问题；遗传算法；量子遗传进化算法；课程表：TN911734文献标识码：A：10047373X(2013)20?0007?04高校排课问题一直是很多人关注的一个问题，排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多冃标的调度问题，在运筹学中被称为时间表问题。1排课问题分析高校排课问题中实际上是时间表安排的问题［1］。在实际排课过程中，主耍涉及到：教室、班级、课程、时间和老师等5个因素的问题。在处理这5个因素关系的过程中会发生很多冲突，这就需耍有一些约束条件，这些约束条件可以大致分为硬约束和软约束，详见表1。根据以上的分析排课问题数学模型分为下面5个集合如下：教室集合：［R=｛rl,r2,•••,rm｝］；班级集合：［C二｛cl,c2,…，cn｝］；课程集合:［L=｛11,12,・lp｝］；教师集合：［S二表1排课问题的软硬约束条件上述5个元素是影响排课问题的主耍的因素，每个集合中取一个组成在某个时间某班上的课程由哪位老师来授课，在哪个教室上课，但必须满足一定的条件。2量子遗传进化算法量子遗传进化算法是量子计算与遗传算法相结合的产物［2］。冃前，这一领域的研究主要集中在两类模型上：一类是基丁量子多宁宙特征的多宁宙量子衍生遗传算法(QuantumInspiredGeneticAlgorithm)；另一类是基于量子比特和量子态叠加特性的遗传量子算法(GeneticQuantumAlgorithm,GQA)［3］。2.1量子位表示法在量子信息论中，信息的载体不再是经典的比特，而是个一般的二态量子体系，称为量子比特(qubit)。量子比特与经典位不同就在于它可以同时处在两个量子态的叠加态中［4］,比如：式中：［a,B］是两个复常数，满足：式中［0］和［1］分别表示自旋向下和自旋向上态。所以一个量子比特可同时包含态［0］和［1］的信息；［a］表示相应的qubit处于0状态的概率幅；［13］表示其处丁1状态的概率幅。［a2］表示处丁0状态的概率，［02］表示处于1状态的概率［3］。一个具有ni个量子比特位的系统可以描述为：其中［aj2+Bj2=l,j=l,2,…，m］o这种表示方法可以表示任意的线性叠加态，例如一个具有如下概率幅的量比特系统：---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---则系统的状态可以表示为：上面结果表示状态［00,001,010,011,100,101,］［110,111］出现的概率分别为［38,132,332,332,332,］［132,332,332,］即这个量子比特系统表示了8个状态叠加的信息而且随着趋于1或0,量子染色体收敛于一个状态,这时多样性消失，算法收敛［5］。2.2量子旋转门在遗传算法中，可以通过交叉，变异來得到新的个体，而在量子遗传进化算法中，是通过量子旋转门來进行更新的［6］。量子旋转门如下：比如对［aiBi］进行更新，可以用式(6)來进行更新：式中［△Oi］的取值对算法的执行效率有很大的影响，具体确定过程如表2所示。其中:［fx］和［fb］表示解的fitness,［x］为当前解,［b］为［btj］；［Xi］和［bj］分别表示解［x］和［b］的第i个bit位的取值;［saiBi］为［△0i］的符号⑺。例如，如果条件［fxMfb］成立，且［xi］和［bj］分别为1和0,贝ij［A0i］的取值为0.025nr,然后根据［ai］和［Bi］的值可将其符号设置为+1,-1和0來增加qubit处于1状态的概率。若［aiBi>0］,BP［A0i］为+0.025n,将［40i］代入式(6)中得到新的［ali］和［Dli］,使qubit处于1状态的概率增加，具体分析如图1所示。［△Oi］取值的大小会影响算法的收敛速度，如果取值过大会导致早熟收敛得不到最优解；［△0i］的符号决定解的收敛方向［8］。3量子遗传进化算法和遗传算法來解决高校排课问题3.1具体高校排课问题简介对丁一个具体的排课问题，分别采用量子遗传进化算法和遗传算法来解决，并对它们的结果进行分析［9］。简化的高校排课问题是针...