用量子遺傳算法求解大學排課問題

摘要:作為典型的NP完全問題，大學排課問題在教務管理系統中非常重要。該文通過對大學排課問題的數學模型的分析，運用量子遺傳算法進行求解。實驗結果表明，利用量子遺傳算法求解大學排課問題要優于使用遺傳算法。

關鍵詞:大學排課問題;NP難問題;遺傳算法;量子遺傳算法

中圖分類號:G434文獻標識碼:A文章編號:1009-3044(2010)05-1174-02

Application of Quantum-Inspired Genetic Algorithm in the University Timetable Problem

CAO Min-zhi

(Hunan Biological and Electromechanical Polytechnic， Changsha 410127， China)

Abstract: As the classic NP-Complete Problem， University Timetable Problem is very important to the academic course scheduling management system. In this paper， the mathematic model of university timetable problem is analyzed， and the quantum-inspired genetic algorithm is used to solve it. The results of experiments show that the quantum-inspired genetic algorithm is more effective to genetic algorithm in solving the university timetable problem.

Key words: university timetable problem; NP-hard problem; genetic algorithm; quantum-inspired genetic algorithm

隨著大學招生規模的擴大，而且大學的教學單位和課程眾多，因此合理安排教師和教室的排課模型越來越復雜。大學排課問題(University Timetable Problem，UTP)成為大學教務處最棘手和最費時的工作之一，如何有效實現智能排課具有重要的實際意義[1-4]。由于UTP為典型的NP完全問題[5]，隨著問題規模的增長，傳統的算法無法有效進行求解。作為計算智能的典型算法，遺傳算法(Genetic Algorithm，GA)[6]在求解各類NP問題時表現出優異的定能，同時也存在收斂速度過慢等不足。本文針對UTP問題，通過采用量子遺傳算法[7]進行有效的求解，實驗結果表明用量子遺傳算法求解UTP要優于遺傳算法。

1 UTP問題及其數學模型

根據問題的描述，設立以下幾個集合:

教師集合:T={Ti | i=1，2，…，t}

班級集合:S={Si | i=1，2，…，s}

課程集合:C={Ci | i=1，2，…，c}

教室集合:R={Ri | i=1，2，…，r}

時間集合:M={Mi | i=1，2，…，m}

以及以這五個集合為基礎構建的

課元集:K={(t， s， c) | t∈T， s∈C， c∈C}

資源集:Z={(r， m) | r∈R， m∈M}

通過以上定義，可以講UTP問題轉化為求映射集F:K→Z的問題。

2 量子遺傳算法

量子遺傳算法(Quantum-Inspired Genetic Algorithm，QGA)[7]是量子計算與遺傳算法相結合的產物。QGA建立在量子的態矢量表述基礎上，用量子比特編碼來表示染色體，用量子旋轉門和量子非門來實現染色體的更新，從而實現對目標問題的優化求解。

2.1 量子位的表示

在QGA中，染色體不是用確定性的值(如二進制數、浮點數或符號等)表示，而是用量子位表示，一個量子位不僅僅表示0或1兩種狀態，而且同時表示這兩種狀態之間的任意中間態。一般地，用n個量子位就可以同時表示2n個狀態，因而對于相同的優化問題，QGA的種群大小可比傳統GA小很多。在QGA中，一個量子位可能處于|0>或|1>，或者處于|0>和|1>之間的中間態，即|0>和|1>的不同疊加態，因此一個量子位的狀態可表示為:

|φ>=α|0>+β|1> (1)

其中α和β可以是復數，表示相應狀態的概率幅，且滿足下列歸一化條件:

|α|2+|β|2=1(2)

其中，|α|2表示|0>的概率，|β|2表示|1>的概率。

2.2 量子旋轉門

在QGA中，由于染色體的狀態處于疊加或糾纏狀態，因而采用將量子門分別作用于各疊加態或糾纏態的方式;子代個體的產生不是由父代群體決定，而是由父代的最優個體及其狀態的概率幅決定。遺傳操作主要是將構造的量子門作用于量子疊加態或糾纏態的基態，使其相互干涉，相位發生改變，從而改變各基態的概率幅。因此，量子門的構造既是量子遺傳操作要解決的主要問題，也是QGA的關鍵問題，因為它直接關系到QGA的性能好壞。在QGA中，主要采用量子旋轉門，即:

其中，θ為旋轉角。

2.3 QGA算法

QGA算法的基本流程如下:

1) 初始化:產生初始種群P(t)={p1t，p2t，…pnt}，其中n是種群的規模，pjt(j=1，2，…，n)為種群第t代的一個體，其中pjt=[α1t， α2t，…αmt; β1t， β2t，…βmt]，m為量子位數目，即染色體的長度，在初始化時，α和β都取1/。

2) 根據P(t)中概率幅的取值情況構造出R(t)，R(t)={ α1t， α2t，…αnt }。

3) 用適應值評價函數對R(t)中的每個個體進行評價，并保留此代中的最優個體。若獲得了滿意解，則算法終止，否則，轉人4)繼續進行。

4) 使用恰當的量子門U(t)更新P(t)。

5) 遺傳代數t=t+1，算法轉至2)繼續進行。

3 求解UTP問題的量子遺傳算法

UTP問題可以分為兩個部分，第一部分為確定教師、班級和課程組成的課元集K，第二部分為將課元集K中的元素安排到對應的時間和教室組成的資源集Z。第一部分為經典的組合問題，可以直接采用遺傳算法進行求解。本文主要針對第二部分，即在課元集已確定的情況下求解課元集和資源集的對應關系。

3.1 編碼

在建立UTP問題的數學模型時，為了簡化問題，我們假設每周的授課計劃為:每周一至周五上課，共五天;每天安排8節課，上午下午各四節，每兩節課為一個授課單元。因此對于每周排課而言，每個教室最多可以安排20次授課。因此資源集的描述如圖1所示。

我們按照教室、日期和節次的順序將資源集中數據進行編碼，即按照{教室1星期一第1、2節;教室1星期一第3、4節;…;教室n星期五第7、8節}的順序進行編碼。對于課元集則直接采用將所有課元根據順序轉換成相同長度的二進制序列。通過將課元集二進制序列填入到對應的資源集編碼段中，從而形成染色體個體。

3.2 適應度函數

適應度函數用于評估種群中個體的優劣程度，從而指導算法朝著最優解的方向進化。基于UTP問題的軟約束和硬約束特點，本文中采用如下適應度函數:當個體出現硬約束沖突時，硬約束適應度值設置為0，此時個體的適應度值最低;當不存在硬約束沖突時，相應的硬約束適應度值設置為1，此時個體的適應度值較高。在硬約束適應度值都為1的情況下，適應度值由軟約束條件決定。例如，當一門課程兩次上課時間間隔越長，軟約束適應度值越大，表明排課效果越好。因此，適應度函數主要對種群中的個體即排課方案進行評估，其值越大，方案的排課效果好。

3.3 算法流程

求解UTP問題的量子遺傳算法的基本流程如圖2所示。首先算法對具體UTP問題進行編碼，之后進行種群初始化，算法的核心是一個迭代過程，由量子觀測、評估、量子門旋轉以及再一次量子觀測過程組成。在達到結束條件后對最優解進行解碼，即得到問題的最優解。

3.4 實驗結果

為檢驗本文設計的算法，本文將其與遺傳算法進行了對比實驗。在課元集元素個數為100，400和800時，對兩種算法各測試10組數據，并取平均值，實驗結果如表1所示。

從表1中可以看到，量子遺傳算法在求解的適應度上要優于遺傳算法，對比實驗表明，本文采用的量子遺傳算法在求解UTP問題中，獲得了優于遺傳算法的結果。

4 結論

量子遺傳算法相比于遺傳算法具有收斂速度快，不容易陷入局部最優等優點，是一種成功的遺傳算法改進算法。本文通過將量子遺傳算法應用到求解UTP問題中，獲得了較好的效果。相比于遺傳算法，本文采用的算法求解的結果具有更好的適應度。同時，由于本文對UTP模型的約束條件設計較為簡單，因此很多復雜功能有待于進一步改進和開發。

參考文獻:

[1] 張晶，李廣軍，唐遠翔.智能排課算法綜述[J].長春大學學報，2009，19(8):38-41

[2] 譚保華，彭偉.基于蟻群遺傳算法的高校排課系統[J].計算機仿真，2008，25(12):294-297.

[3] 陳章輝，黃小暉，任文藝，等.基于雙倍體遺傳算法求解大學排課問題[J].計算機應用，2008，28(12):3074-3076，3104.

[4] 滕姿，鄧輝文，楊久俊.基于遺傳算法的排課系統的設計與實現[J].計算機應用，2007，27(12):199-204.

[5] 李悅喬.用演化算法求解高校排課的問題[J].電腦知識與技術，2009，6(5):4257-4259.

[6] 王耀南.計算智能信息處理技術及其應用[M].長沙:湖南大學出版社，1999.

[7] Tony H.Quantum computing: all introductions[J].Computing Control Engineering Journal，1996，10(3):105-112.