一種基于遺傳算法在編排課程表中的應用

摘要：課程表排課安排和管理是每個學校教務活動中非常重要的工作，它依靠計算機來完成復雜的排課部分，避免了手工排課產生的老師上課時間沖突和教室沖突。該文運用遺傳算法的全局尋優對自動排課系統的設計構思和實現過程進行了研究，并利用遺傳算法對問題進行求解。在演化過程中采用一種新的遺傳策略，加速了群體的收斂速度。并得到了一個解決適合學校要求的課程表模型的好的算法。

關鍵詞：排課；遺傳算法；全局尋優；自動排課

中圖分類號：TP301.6文獻標識碼：A 文章編號：1009-3044(2008)33-1463-03

A Kind of Based on Genetic Algorithm the Application in Layout Course Table

QIAO An-hong

(Jiaxing University， Jiaxing 314001，China)

Abstract: Course table row lesson arrangement and management are every school campaign work of educational administration with frequently important Central Africa， it relies on computer to complete complex row lesson part， have avoided the teacher that handwork row lesson produces to attend class time conflict and classroom conflict. It is studied that this paper utilizes the overall situation of genetic algorithm to seek the good design conception for the system of automatic row lesson and the course of realizing and has gone on ， and beg to untie using genetic algorithm for problem. In evolution course have accelerated group with a kind of new hereditary strategy show restraint speed. And have gotten a good algorithm of the course table model that solves to suit school requirement.

Key words: queue up lesson; genetic algorithm; overall situation seek good; queue up lesson voluntarily

1 引言

學校課程表排課安排和管理是每個學校教務活動中非常重要的工作，它涉及面廣、限制條件多，而計算機自動排課系統設計就是根據教學計劃的內容以及一些限制條件自動生成課程表，從而減輕排課的工作量、提高排課的效率和科學性，其功能是可根據用戶需求進行如下的排課生成：設置上午、下午、晚上的上課節數，全校每天不排課的限制、上課周數。專業配課、年級配課、班級配課。課程信息設置，包含任課老師，性質、課時等。教室信息設置，包括性質、隸屬。教師的信息配置，包括教授的課程、特殊情況等自動排課生成各類課表手動編排。

目前最具科學性的方法：使用計算機軟件技術配合手工排課。就是將人腦和電腦的優勢結合在一起發揮作用——即具有“人工排課”的靈活、合理性，又具有“智能排課軟件”的便捷性。（也就是“計算機輔助排課”）使用計算機輔助排課系統的自動教師資源、教室資源和時間資源組成的效率與質量完全取決于時間表算法的設計。遺傳算法以其自適應尋優及良好的智能搜索技術，受到了廣泛的運用。Potts J C等人基于變異和人工選擇的遺傳算法對最優群體規模進行了論述；Hamilton M A等結合遺傳算法把其運用到神經網絡中，并取得了良好的效果；也有眾多的學者對保留最佳狀態的遺傳算法的收斂速度做了討論。通過理論推導和事實運用，發現遺傳算法在尋優和收斂性方面都是非常有效的、確實可行的一種解決方法。

2 問題描述

傳統的人工排課，最令人擔心的問題就是——出現教室資源沖突或教師資源沖突的情況。而且工作繁瑣，工作量巨大。況且我發現目前的排課軟件普遍存在——排課條件設置復雜，難以做到課程的合理分布（例如：數學、英語等主課多數要安排在上午上課）、出錯概率高、難以操作等缺點。計算機自動排課系統實際上是時間表的優化問題。如何根據班級的課程設置、課程的周內次數、現有教室資源、以及現有教師資源進行科學的合理安排，提供給學校的教務部門一個自動排課系統，在實際工作中具有一定的應用價值。

在進行計算機自動排課系統設計過程中，我考慮了三類資源：一類是教師資源，一類是教室資源，一類是時間資源。教師資源包括在編教師和每個教師歷年所上過的課程、以及所上過課程的評價值。同一課程可能有多名教師能開課，在資源分配允許的情況下，自然選擇評價值高的教師上這門課。多數情況下，在進行教學任務安排時，已經人為考慮了教師和課程之間的固定聯系。教室資源是指現有可用教室。時間資源是指允許可用的時間段。此外，按每學期教學大綱，本學期每個班(專業)所上課程和每門課的周學時數(次數)是預定的。同時，我還需要考慮不同時間段的上課效果。排課問題是根據現有教師資源、教室資源和時間資源，如何使排課結果最佳。適當定義相應的一些評價系數后，排課問題變成了一個時間表的優化問題。

而排課數據結構模型的產生和實現是計算機排課系統自動化或半自動化操作的核心目標之一，而如何保證生成的課程表能最大程度的滿足用戶的不同需要，并具有隨機性、科學性、合理性，這是實現中的一個難點。尤其在交互式環境下用戶對于生成課表速度要求較高，而一個理論上較完美的算法可能會以犧牲時間作為代價，往往不能達到預期的效果。因此，選擇一個高效、科學、合理的算法是自動排課的關鍵。

以往計算機排課系統算法的實現，大多采用隨機選取法和回溯試探法。兩種算法各有其優缺點，在限制條件狀態空間的控制下，隨機選取法有時能夠獲取一組令用戶滿意的課表。只不過由于它隨機選取時間表的的范圍太大，無法確定目前條件下哪些區域能夠抽取合適的時間表，反而可能在那些已經證明是無法抽取在合適課表的區域內反復選取，進行大量的無效操作進入死循環，最終導致課表生成失敗。回溯試探法用于課表生成的成功率較高，但它是以犧牲大量的搜索時間為代價的，已不適合應用要求。因此，必須結合以上兩種方法尋找一種新的改進算法，這種算法要具有全局尋優和收斂速度快的特點。遺傳算法以其具有自適應全局尋優和智能搜索技術，并且以收斂性好的特性很好的滿足課表自動生成的需求算法。

3 遺傳算法描述

3.1 遺傳算法基本思想

遺傳算法（Genetic Algorithm，縮寫為GA）是一種有效的解決最優化問題的方法。它是基于人類社會的進化過程，遺傳算法首先利用隨機方式產生一切始群體（祖先），群體中的每個個體稱為染色體，它對應著優化問題的一個可能解，染色體的最小組成元素應稱為基因，它對應可能解的某一特征，即設計變量。染色體的評價函數值反映可能解的優劣，按照優勝劣汰原則對染色體進行選擇，相對“好”的個體繁殖，相對“差”的個體將死亡，因此群體整體的性能，通過選擇、雜交、突變等過程將趨于改善，經過若干代繁衍進化就可使群體性能趨于最佳。其實質就是一種把自然界有機體的優勝劣汰的自然選擇、適者生存的進化機制與同一群體中個體與個體間的隨機信息交換機制相結合的搜索算法。

3.2 遺傳算法的基本步驟

1) 定義一個目標函數;2) 將可行解群體在一定的約束條件下初始化，每一個可行解用一個向量X來編碼，稱染色體，向里的分量代表基因，它對應可行解的某一決策變量；3) 計算群體中每條染色體Xi（i=1，2，……，n）所對應的目標函數值，并以此計算機適應值Fi，按Fi的大小來評價該可行解的好壞；4) 以優勝劣汰的機制，將適應值差的染色體淘汰掉，對幸存的染色體根據其適應值的好壞，按概率隨機選擇，進行繁殖，形成新的群體；5) 通過雜交和變異的操作，產生子代。雜交是隨機選擇兩條染色體（雙親），將某一點或多點的基因互換而產生兩個新個體，普通異是基因中的某一點或多點發生突變；6) 對子代群體重復步驟3）-5）的操作，進行新一輪遺傳進化過程，直到迭代收斂（適應值趨穩定）即找到了最優解或準最優解。

4 遺傳算法進行求解并優化應用

當我們對遺傳算法的基本原理有了一定的實踐和認識，利用其各種遺傳操作算子就可建立和產生課程表排課系統的結構模型，并進行求解和優化描述應用如下：

4.1 解的表示

表單元：一個班級的課程表為一個表單元。每周按7天計、每天按6個時間段計。如果周末和某些時間段不能排課，可以在初始約束時用一個布爾變量關閉。

時間段填充：單元中的時間段上用2元組（課程號，教室號）進行填充，當課程有重復次數時，固定課程號做重復填充。

原子碼：班級碼+課程碼+星期碼+時段碼+教室碼。

其中，班級碼和課程碼之間的關系是固定的。

表單元碼：相同班級碼的原子碼集合。

個體碼：假設有n個班，n個表單元碼構成的序形成一個個體碼。

可行解：滿足協調條件的個體碼。

4.2 選擇初始群體

1) 根據給定的班級、該班級本學期所要上的課程集合、以及每門課的重復次數。隨機產生星期碼、時段碼、教室碼。與班級碼和課程碼構成一個原子碼。

2) 由原子碼生成表單元碼。

3) 由表單元碼生成個體碼。

4) 根據初始群體大小，生成由個體組成的初始群體。

4.3 確定評價函數

評價函數在遺傳過程中起著環境的作用，根據評價函數產生每個個體的適應值。這里，我將時間段效率、時間間距約束、教室利用率等因素結合起來定義評價函數。時間段效率和時間間距約束涉及到上課的效果，教室利用率涉及到資源的利用問題。因此，應該優先考慮時間段效率和時間間距約束，在保證這兩者的前提下，再考慮教室利用率。在評價函數中，前兩者所占的比重相對較高。在每個個體中，每個三元組(星期碼，時段碼，教室碼)對應著時間段效率和教室利用率。對于每個班的重復課程，對應著一個時間間距約束問題。將這三個因素按比例進行累加，就可以得到每個個體的適應值。

4.4 遺傳策略

通常，我在遺傳過程中采用三種算子：復制、雜交、變異，三者概率分別為Pr，Pc，Pm。

1）復制算子(reproduction): 復制算子從群體中按照某一概率選擇個體，某個體si被選擇的概率Pi與其適應值成正比。通常，我用輪盤賭(roulette wheel)方法進行實現。輪盤賭方法的實現如下：設群體S：s1，s2，……，sn，每個個體的適應值分別為f(s1)，f(s2)，……，f(sn)，令sum＝f(s1)+f(s2)+……+f(sn)，某個體所si被選擇的概率Pi＝f(si)/sum (i=1，2，……，n)，在0與sum之間產生一個隨機數A，令B＝0，依概率p1，p2，……，pn在1到n之間隨機產生一個個體編號m，將f(sm)累加進B中，直到B>A，將此sm作為被選個體。

2）雜交算子(Crossover): 雜交算子將被選中的兩個個體的基因鏈按概率Pc進行雜交，即在某一確定段上，對等交換代碼，生成兩個新的個體，雜交位置是隨機的。

3）變異算子(Mutation): 變異算子將新個體的基因鏈的各位按概率Pm進行變異，對二進制基因鏈來說就是對某些隨機選取的位置取反。

這樣，對每一代群體，我首先用協調條件進行一次篩選，剔除不滿足協調條件的個體。然后才對個體進行演化計算產生下一代，從而加快了進化速度。

結合上述三種算子，采取了一種新的遺傳策略。在得到群體中每個個體的適應值后，首先用輪盤賭方法將群體選擇到交配池中，然后從交配池中每次取兩個個體依概率進行雜交或變異產生臨時新群體，此時，臨時新群體數目與父代群體數目相同。接著，再將臨時新群體中每個個體依概率選擇或直接復制到下一代，或與上一代對應個體進行競爭(即若其適應值比上一代對應個體差，則將上一代個體保留下來，否則將其保留至下一代)。另外，將每一代中最優個體進行保存，每次產生新群體后，判斷新群體中是否有比現有最優個體的適應值更好的，若有，則用其替換當前最優個體。通過父代和子代競爭，可以提高解的收斂速度。

4.5 停機準則

我可以采用多種方法來結束算法的執行，這里，我采用兩種方式相結合對停機加以控制：

1) 設定最大遺傳代數M，當遺傳進行到第M代時，讓其停機。

2) 預先定義評價函數的一個指標數，當某一代最優個體的適應值達到或超過該指標數時，讓其停機。

4.6 輸出結果

遺傳算法結束后，可以得到適應值（即綜合效率函數值）最好的個體。根據這個結果，我將對個體碼進行如下分解：

1) 分解個體碼成為表單元碼。

2) 分解每一個表單元碼成為：班級碼、課程碼、星期碼、時段碼、教室碼。

由分解后的班級碼、課程碼、星期碼、時段碼、教室碼分別生成如下表格：

1) 班級課程表。

2) 根據教師與課程的固定關系，生成教師工作表。

3) 每個教室的時間占用表。

4) 教學單位的課程總表。

5 結束語

本文基于遺傳算法建立和描述了排課的數學模型，實際上是對一個時間任務表的優化問題，研究了對問題的求解。利用遺傳算法的全局尋優和收斂速度快的特點，結合隨機選取法和回溯試探法的優點，設計了一種用于課表自動生成的好的算法，在排課的成功率和速度都得到了明顯的提高。實驗表明：本排課模型算法的構成結果能得到較滿意的課程表安排方案。然而要使課表自動生成的誤差精度和收斂速度進一步得到改進，還需要做出更深的研究。

參考文獻：

[1] Peter Brucker.Scheduling Algorithm. Berlin etc: Springer， 1998.

[2] J．H．Holland ，Adaptation in natural and artificial systems[M]，Ann arbor: University of Michigen press，1975.

[3] Hamilton M A. Java and the Shift to Net-centric Computing. IEEE Computer， 29(8)，1996.

[4] 劉勇，康立山，陳毓屏.非數值并行算法（第二冊）－遺傳算法[M].北京：科學出版社，1998.

[5] 余建橋，預測模型獲取的遺傳算法研究[J].計算機科學，1998，25(2):12-14.

[6] 王小平，曹立明.遺傳算法－理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

[7] 張宗華，張偉，趙霖.利用遺傳算法實現交通信號燈的控制[J].計算機科學，2002.29(9. 增刊): 178-181.

[8] 田奕，劉濤，李國杰.求解可滿足性問題的一種高效遺傳算法[J].模式識別與人工智能，1996.9:209-212.