一种基于高校排课问题的新型量子遗传进化算法

龙源期刊网 https://www.wendangku.net/doc/fc1199396.html,

一种基于高校排课问题的新型量子遗传进化算法

作者：沈微微华明正史洪玮

来源：《现代电子技术》2013年第20期

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

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

中图分类号： 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]。目前，这一领域的研究主要

集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法（Quantum Inspired Genetic Algorithm）；另一类是基于量子比特和量子态叠加特性的遗传量子算法（Genetic Quantum Algorithm，GQA）[3]。

2.1 量子位表示法