一種基于高校排課問題的新型量子遺傳進化算法

摘 要： 量子遺傳進化算法是量子計算和遺傳算法相結合的產物，量子比特是兩個量子態的疊加態，在此，詳細介紹了量子遺傳進化算法。嘗試使用量子遺傳進化算法來解決高校排課問題，并進行了實驗。實驗結果表明，該算法獲得了比較好的結果。

關鍵字： 高校排課問題； 遺傳算法； 量子遺傳進化算法； 課程表

中圖分類號： 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 量子位表示法

在量子信息論中， 信息的載體不再是經典的比特，而是個一般的二態量子體系，稱為量子比特（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]。

圖1 量子門坐標圖

排課時的一些要求，其中一周上兩次的課，不能排在同一天或者相鄰兩天，至少相差一天。項目中主要牽涉到的數據，每門課程的重要性，將它們存放在一個數組中，其中，無課也放在了數組中，則最終的數組應該是一個一維數組，包括8個元素。

int classWeights[] ={0，70，60，55，75，80，90，85}

對應的課程為無課，體育，計算機基礎，政治，數據結構，高數，英語，操作系統。其中，classWeight[0]無課的重要性，沒有課程 ，那重要性當然為0，后面依次是第幾們課程的重要性。下標為幾，即為第幾們課程的重要性。各個時間段的重要性存放在一個二維數組中，數組中共有25個元素，因為這里討論的排課問題，一個星期共有五天上課，一天共有五節課，其中上午兩節課，下午兩節課，晚上一節課，這里的一節課包括兩個學時。第一個下標加1后的值表示的是星期幾，第二個下標加1后的值表示的是第幾節課，如timeWeights[2][3]表示的是星期三第四節課。有：

double[][] timeWeights =

{ { 0.65， 0.90， 0.85， 0.60， 0.50 }，

{ 0.90， 0.85， 0.80， 0.75， 0.70 }，

{ 0.95， 0.90， 0.85， 0.80， 0.65 }，

{ 0.90， 0.80， 0.75， 0.70， 0.60 }，

{ 0.85， 0.90， 0.70， 0.60， 0.50 } }

Fitness函數如下：

[fx=i=0i=4j=0j=4timeWeightsij?classWeightsk，0≤k≤7]

函數[f（x）]是評價排出課表好壞的函數，[f（x）]值越大，則排出的課表越好。

3.2 兩種算法的測試結果

在項目中還有一些輔助的類就在此不做詳細介紹，WriteFile.java中方法的作用是將運行的結果輸入到Excel文件中。test.java是一個主函數的類，最終采用進化1 000代，種群規模為10，每種算法運行25次，最終分別對它們的1次運行和25次求的平均畫圖，比較兩種算法，可看出量子遺傳進化算法在求具體的高校排課問題的優越性。在控制臺中也會輸出每次運行中的最優解的課表。其中第1次到第25次運行的是量子遺傳進化算法，第26次到第50次運行的是遺傳算法。運行結果的截圖如圖2，圖3所示。

圖2 QEA與CGA一次運行最好解的fitness值

圖3 QEA與CGA運行25次的最好解的平均fitness值

從圖2和圖3中可以很明顯的看出量子遺傳進化算法求出的解要比遺傳算法求出的解要好，下面給出兩種算法排出的具體課表，這里取出某次運行中的最優解的課表。

表3是量子遺傳進化算法排出的課表，表4是遺傳算法排出的課表。它們的fitness值可以從圖2中看出，量子遺傳進化算法排出的課表的fitness值明顯大于遺傳算法排出的課表的fitness值。

表3 量子遺傳進化算法第10次運行排出的課表

表4 遺傳算法第10次運行排出的課表

4 結 語

通過對高校排課問題的分析，對高校排課問題中主要的影響因素進行比較深入的了解，并根據量子啟發式進發算法優點，采用量子遺傳進化算法來解決高校排課問題。從最終的結果對比可以看出，量子遺傳進化算法得出的解比遺傳算法得出的解要好很多，收斂速度上，量子遺傳進化算法和遺傳算法的收斂速度差不多。所以，采用量子遺傳進化算法來解決高校排課問題比較高效，能得到很好的解。

參考文獻

[1] HAN K H， KIM J H. Quantum?inspired evolutionary algorithm fora class of combinatorial optimization [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（6）： 580?593.

[2] 楊俊安，莊鎮泉.量子遺傳算法研究現狀[J].計算機科學，2003，30（11）：13?15.

[3] NARAYANAN A， MOORE M. Quantum?inspired genetic algorithm [C]// Proceedings of IEEE Congress on Evolutionary Computation. Nogama： IEEE， 1996： 61?66.

[4] HART K H，PARK K H.Parallel quantum?inspired genetic algorithm for combinatorial optimization problems [C]// Proceedings of the IEEE Conference on Evolutionary Computation.Piscataway： IEEE Press， 2001： 1422?1429.

[5] TONY H.Quantum computing： all introduction [J].Computing Control Engineering Journal，1996， 10（3）： 105?112.

[6] LIU Wen?jie， CHEN Han?wu， YAN Qiao?qiao，et al. A novel quantum?inspired evolutionary algorithm based on variable angle?distance rotation [C]// 2010 IEEE Congress on Evolutionary Computation. Barcelona： IEEE， 2010： 1?7.

[7] RECHENBERG I. Evolutionsstrategie： optimierung technischer systemenach prinzipien der biologishen evolution stuttgart [M]. Germany： From?mann?Holzbog， 1973.

[8] 雷英杰，張善文，李續武，等.Matlab遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.

[9] 王小平，曹立明.遺傳算法[M].西安：西安交通大學出版社，2002.

[10] 蘭慧.基于遺傳算法的排課系統的設計與實現[D].北京：華北電力大學，2005.