基于遺傳算法高校排課系統(tǒng)

1、基于遺傳算法高校排課系統(tǒng)    摘  要   提出并實現(xiàn)了一種高校自動排課算法,利用遺傳算法建立數(shù)據(jù)模型,定義一個包含教師編號、班級編號、課程編號、教室編號、上課時間段的染色體編碼方案和適應度函數(shù)，通過初始化種群、選擇、交叉、變異等過程不斷進化，最后得到最優(yōu)解。利用該算法對某高校的真實數(shù)據(jù)進行實驗，結果顯示無一例教室、教師、班級沖突，算法具有合理性和可行性。     關鍵詞  遺傳算法； 排課問題； 適應度函數(shù)      1 

2、 前言     每個學期對本校教學任務進行合理安排是教務科的重要任務。其中排課是最為關鍵的環(huán)節(jié)。排課問題的本質(zhì)是將課程、教師和學生在合適的時間段內(nèi)分配到合適的教室中，涉及到的因素較多，是一個多目標的調(diào)度問題，在運籌學中被稱為時間表問題（Timetable Problem，簡稱TTP）。目前由于學校擴招，學生和課程數(shù)量比以往大大增加，教室資源明顯不足，在這種情況下排課人員很難在同時兼顧多重條件限制的情況下用人工方式排出令教師和學生都滿意的課表。     排課問題很早以前就成為眾多科研人員和軟件公司的研究課題，但是真正投入使用的排課軟件卻

3、很少。原因是多方面的，其中算法的選擇是最關鍵的一個問題，S.Even等人在1975年的研究中證明了排課問題是一個NP-Complete問題，即若是用“窮舉法”之外的算法找出最佳解是不可能的。然而由于窮舉法成本太高，時間太長，根本無法在計算機上實現(xiàn)。因為假設一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節(jié)課，在不考慮其他限制的情況下，能夠推出的可能組合就有nm*k種，如此高的復雜度是目前計算機所無法承受的。因此眾多研究者提出了多種其他排課算法，如模擬退火,列表尋優(yōu)搜索,約束滿意等1。其中，遺傳算法(Genetic Algorithm, 簡稱GA)是很有效的求解最優(yōu)解的

4、算法。     遺傳算法是一種通過模擬自然界生物進化過程求解極值的自適應人工智能技術，是由美國芝加哥大學Holland教授于1962年首先提出的。遺傳算法借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制來提高各個個體的適應性，體現(xiàn)了自然界中“物競天擇、適者生存”的進化過程。遺傳算法也因此吸引了一大批的研究者，并廣泛應用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、機器學習、圖像處理、模式識別等多個領域。 2  排課問題描述     在排課問題中，我們的主要任務是將班級、教室、課程、教師安排在一周內(nèi)且不發(fā)生時間沖突2。據(jù)此，我們給

5、出如下描述：     學校有R間教室，C個班，S門課程，T位教師，P個時間段。     教室集合R（R1,R2,Rn），每間教室分別可容納（X1,X2Xr）人；     班級集合C（C1,C2,Cn），每個班級分別有（K1,K2,Kc）人，其中有x個班級上合班課；     課程集合S（S1,S2,Sn），每門課對應Ci個班，1位教師，（1 Ci <Cn）；     教師集合T（T1,T2,Tn），每位教師對應Sm門課，Cn個班，（1 Sm

6、<Sn,1 Cn <Cn），在初始設置時設定教師的排課要求。     時間集合P(P1，P2，Pn)，假設一周上五天課，每天分為五個教學單元，每個單元為2個課時，即上午2個，下午2個,晚上1個，則時間集合包含25個時間段。如11代表周一第一個教學單元，即周一1、2節(jié)，12代表周一第二個教學單元，即周一3、4節(jié)，以此類推，這些時間段構成一個時間集合P(11,12,13,.55)。     一張正確的課表應至少滿足以下硬約束條件：3     一個教師或者一個班級或者一個教室在同一時間段內(nèi)只能安排一

7、門課程；     分配的教室可容納人數(shù)應該大于學生數(shù)。     除了上述的硬性約束，還有些軟約束，這些軟約束有助于使得課表更加合理，更加人性化。這些軟約束條件可能是4：     盡量在早上安排必修課，而下午安排選修課，晚上盡量不排課；     盡可能滿足個別教師的特殊上課時間要求；     一門課盡量分散在一個星期中，即某天上完某一門課后，要隔一天以上再上這門課，以使教師有充足的時間備課和批改作業(yè)，而學生也有足夠的時間復習消化；  &#

8、160;  (4)一個教師的課不能排滿一整天；     (5)學生課表中的上課時間不能過分集中，應避免一天課程很滿而另一天卻一整天沒課的情況。 這些軟約束條件各院校有所不同，在我們的研究中，旨在我們定義的約束范圍內(nèi)給出一個遺傳算法的解決方法，并對其進行優(yōu)化操作。 3   遺傳算法          遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下：     1）隨機產(chǎn)生一定數(shù)目的初始種群    

9、 2）對個體適應度進行評估，如果個體的適應度符合優(yōu)化準則，則輸出最佳個體及其代表的最優(yōu)解，并結束計算，否則轉向第3步。     3）依據(jù)適應度選擇再生個體     4）按照一定的交叉概率和交叉方法生成新的個體     5）按照一定的變異概率和變異方法生成新的個體     6）由交叉和變異產(chǎn)生新一代的種群，然后返回第2步。如圖1所示：    圖1 遺傳算法示意圖     以下是遺傳算法的偽代碼。  

10、   BEGIN:         I = 0;         Initialize P(I);         Fitness P(I);         While(not Terminate-Condition)       

11、60;             I +;             GA-Operation P(I);             Fitness P(I);           &#

12、160;  END. 4  設計 4.1  染色體編碼     GA中首要考慮的是如何表現(xiàn)其問題，即如何對染色體編碼，使之適用于GA操作。在經(jīng)典的遺傳算法中，常采用浮點數(shù)或二進制的編碼方法，而研究中，每條染色體代表每位教師的課表，其結構表示如下：    教師ID    班級ID    課程ID    教室    上課時間安排  

13、   染色體在程序中可用十進制數(shù)編碼，例如：某一教師編號為1247，要教授“數(shù)據(jù)庫原理”這門課，“數(shù)據(jù)庫原理”課程編號為8017，周學時為4，班級為01811、01812，隨機產(chǎn)生上課時間，隨機選擇大于兩班總人數(shù)的教室，則可生成染色體如：“124701811018128017024012241”其中02401，2241分別代表教室及上課時間星期二第二個教學單元（即上午3、4節(jié)）和星期四第一個教學單元（即上午1、2節(jié)）。     按如上編碼，兩條染色體對后9位作交叉操作，不會影響到每位教師所教授的課程，也不會造成教師課表內(nèi)含其他教師的教授課程或每

14、代演化后染色體結構不合理等問題。 每一條染色體表示一種可能的排課結果，至于排課結果的優(yōu)劣，則由適應度函數(shù)評估染色體的適應值來決定。 適應度函數(shù)        遺傳算法在進化中是以每個個體的適應度值為依據(jù)來選取下一代種群的。適應度函數(shù)設定的好壞直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解。在本系統(tǒng)中，適應度函數(shù)的設計思想是對每條染色體中存在的沖突類型進行加權求和，其中權值Wi代表的是第i條規(guī)則的重要程度，若某條染色體違反了某條規(guī)則i，則將其值Pi置為1（若沒有違反規(guī)則i，則Pi值為0），其受到的懲罰值為Wi*Pi，對染色體中存在的沖突進

15、行加權求和并加上1后，再求其倒數(shù)，如以下公式所示。染色體適應度函數(shù)值越大，則表示其擁有較好的授課時段和教室，其在下一代的演化中的生存概率就較大。    4.2  遺傳操作     （1）初始化Initialize     初始化的目的在于為后面的遺傳操作提供初始種群。     在我們的算法中，由于每次對一位教師進行遺傳操作，初始化時就需要考慮到教室及時間的設定，這其中包括教室可容人數(shù)的最優(yōu)逼近（即避免一個30人的班級占用可容200人的教室這種情況），以及上

16、課時間安排的合理性，這在排課問題描述中已有解釋。     （2）選擇Select     選擇運算用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它從舊種群中選擇出適應度高的某種染色體，放入配對集合中，為染色體交叉和變異運算產(chǎn)生新種群做準備。適應度越高的染色體被選擇的可能性越大，     選擇操作的方法有許多，如輪盤賭選擇法（roulette wheel selection），局部選擇法（local selection），錦標賽選擇法（tournament selection）等。 研究中，我們選用了局部選擇法中的

17、一種：截斷選擇法（truncation selection）。 在截斷選擇法中，染色體按適應度函數(shù)值由高到低排序，只有最優(yōu)秀的個體才能被選作父個體。其中，用于決定染色體被選作父個體的百分比的參數(shù)稱為截斷閥值Trunc，其取值范圍為50%10%。在該閥值之外的個體不能產(chǎn)生子個體。算法中選擇強度與截斷閥值的關系如表1所示。 表1 選擇強度與截斷閥值的關系5    截斷閥值    1%  10% 20% 40% 50%    80%   &#

18、160;選擇強度    2.66 1.76 1.2  0.97  0.8    0.34     其中選擇強度是將正規(guī)高斯分布應用于選擇方法，期望平均適應度。     選擇強度表示為： SelIntTrunc(Trunc) = 式中fc為下列高斯分布的積分下限： Trunc =     （3）交叉Crossover     交叉是根據(jù)選擇操作的結果，選取兩條染色體作為父個體，再

19、取一隨機值（設為r）與系統(tǒng)預設的交叉率值（設為t）比較，若r<t則進行交換基因。     （4）變異Mutate     變異是隨機改變?nèi)旧w中任一授課時段，將時段隨機抽取一點在設定范圍內(nèi)改變。變異運算模仿了生物在自然遺傳環(huán)境中由于各種偶然因素引起的基因突變，通過變異，染色體適應度有可能加強也有可能降低，但它確保了種群中遺傳基因類型的多樣性，使搜索能在盡可能大的空間中進行，獲得最優(yōu)解的可能性大大加強。     變異操作與交叉操作類似，即定義一個變異概率pm，在變異時先產(chǎn)生一個隨機數(shù)r，當r<p

20、m時，執(zhí)行變異操作，否則不執(zhí)行。      例如：有一染色體編碼為：“087201211100504201 2122”，它表示星期二的第一、二教學單元節(jié)有編號為“1005”的課程，經(jīng)變異，該染色體變成：“087201211100504201 2152”，染色體的適應度大大提高。 5  沖突問題解決     排課問題是一個NP-Complete問題，無論采用哪種方法都無法避免各種沖突問題的出現(xiàn)，同一位教師在同一時段內(nèi)排了兩門課是沖突問題中最明顯的一個。為了避免這種沖突產(chǎn)生，在本系統(tǒng)開發(fā)中引進了一個沖突檢測函數(shù)fCon

21、flict()，當排完一位教師的所有課程之后，系統(tǒng)就會用該函數(shù)對此教師課程安排的沖突情況進行檢測并作修正。 6  結果評估     本系統(tǒng)用Visual C+ 6.0軟件實現(xiàn)上述遺傳排課算法，并對某高校的真實數(shù)據(jù)作了測試。該校20022003學年上學期共有686個排課單元，上課教師356名，共有160間教室，412個行政班。圖2顯示了一代染色體在演化過程中最高適應值和平均適應值的變化情況，其中染色體為30條，交叉率為0.8，變異率為0.02，演化的代數(shù)為1000代。    圖2算例最高適應值-平均適應值曲線

22、60;   由適應值曲線圖可以看出，該算法具有較好的收斂性，也說明了本文中提到的染色體編碼方案和適應度函數(shù)能夠較好地反映排課要求，染色體經(jīng)過世代進化后可以得到令人滿意的最優(yōu)解。圖3是利用遺傳算法排出的01811,01812兩個班級某個學期的課表，從課表中可以看出該課表不存在教師、教室、班級沖突，同一門課程兩次上課時間間隔都達到一天以上，并且沒有課程被安排在晚上，因此不管是硬約束條件還是軟約束條件都得到較好的滿足。 7  結論     本文論述了利用遺傳算法求解高校課表的安排問題，實驗證明文中提出的染色體編碼方案和適應度函數(shù)是可行的，適應度函