遺傳算法在多校區排課系統中的研究和應用

凌敏

摘 要 本文分析了造成多校區高校排課困難的各種因素，研究了如何應用遺傳算法來解決多校區高校排課困難的問題，并對該算法進行詳細設計，給出了一個基于該算法的排課模型。

關鍵詞 遺傳算法 排課系統 教務管理

中圖分類號：G71 文獻標識碼：A

排課問題是一個多約束、多目標的優化問題，是教務管理工作的一個重點和難點。尤其是多校區同時運行的高校格局增加了更多的約束條件，問題的復雜度也增加了許多。多校區排課是一個典型的多因素的優化決策問題，是組合規劃中的NP完全類問題，涉及信息較多且求解復雜性為課表規模的指數量級。遺傳算法被證明解決該類問題是最合適的。

1排課問題描述

課表要有利于教學設備的充分利用，要符合教學規律。將這個原則進行細化、清晰化，一般可以歸納為以下具體要求。

（1）課表中沒有硬性沖突，在排課過程中必須遵守如下約束條件：

①每位教師在同一時間段內只能安排一門課程；

②一個教室在某一時間只能安排一門課；

③教室的位置數量與每個自然班的人數應盡量匹配；

④必須根據核定的教學計劃所規定的學時數排課，不得任意增減；

⑤一個教師兩節課間路程不超過10分鐘，半天的工作必須安排在同一個校區。

（2）課表要求有較高質量，為了使排出的課表更優化、合理、排課還應考慮以下因素：

①一門課程在每個班的每兩天只能安排一次；

②專業必修課盡量安排在上午；

③同一門課的上課地點盡量安排在同一教室；

④體育課必須排在下午或者上午3-4節，體育課后避免安排講授課；

⑤實驗、操作、訓練、演示等課應排在下午；

⑥滿足個別教師的特殊上課時間要求；

⑦編排課表時，先排公共課，后排專業課；先排合班課，后排單班課；

先排多頭課（一個教師有多門課），后排獨頭課；先排多時課，后排少時課。

2排課問題的遺傳算法設計

首先，人工安排或計算機根據條件自動生成，集中安排實驗、實習、社會實踐等有固定時間和地點的課程。

其次，剩余課程按照院系為單位分為若干個子塊，用遺傳算法對每個子塊進行排課操作。

2.1染色體編碼

遺傳算法中首要考慮的是如何表現問題，即如何對其進行染色體編碼，使之適用于GA操作。一條染色體中應包含課程、老師、教室、學生、時間和校區等相關信息。但由于某一門課程信息里面已經包含了老師、學生和校區信息，故染色體中僅需要對課程、教室和節次采用可拼接的二進制編碼。若某院系一學期有40門課程，可編為X1=（a1，a2，a3，a4，a5，a6），ai∈{0，1}。每個院系一般有20 個教室不等，可編為X2=（b1，b2，b3，b4，b5），bi∈{0，1}。每周上五天課，每天4次，共20次，可編為X3=（c1，c2，c3，c4，c5……，c19，c20），ci∈{0，1}。所有課程的DNA分子拼接形成一條染色體。

2.2初始化群體

群體初始化的規模數n應取適中。一般，n取值為染色體長度的兩倍左右。根據上述的染色體編碼，一個DNA分子長度為31，40門課程的一個染色體碼長為1240，故n可取2480。每條染色體中的DNA分子之間由于教室、時間、學生、老師、校區等因素會產生沖突，比如一個老師不能在同一時間安排兩門或兩門以上的課程。產生初始群體時，在不產生沖突的情況下（滿足上述5條硬約束條件），隨機為基因塊賦0或1，直到滿足群體規模。

2.3適應度函數設計

遺傳算法根據適應度群體中個體的優良程度，適應度較高的個體遺傳到下一代的概率較大。因此，遺傳算法是在適應度函數的引導下運行的，適應度函數選擇的好壞直接影響算法的優劣。在適應度函數設計中，我們主要考慮以下沖突；

（1）教師沖突，教師安排是否沖突，同一時間段是否安排兩次課。

（2）教室沖突，同一教室同一時間段不能安排兩門課。

（3）班級沖突，同一班級同一時間的段不能安排兩門課。

（4）交通沖突：對于多校區或單校區教學樓分散情況，教師或學生相鄰時的教室間距不應超過10分鐘；

（5）教室大小與學生人數的沖突。

以上約束條件Pi∈{0，1}，0表示有沖突，1表示沒有沖突首先對一條染色體中的每個DNA分子（一門課程）計算適應度，然后計算一條染色體所有DNA分子適應度之和，將該值作為個體適應度，數學表達式如下：

fi=（P1譖2譖3譖4譖5？f譗1+j譗2+h譗3）

F=40i=1 %Lfi

f表示節次優先度，j表示課程類別優先度，h表示組合優先度。Q1、Q2、Q3代表相應權值，F為個體適應度。

2.4選擇算子

采用截斷選擇法，染色體按適應度函數值從高到低排序，只有最優秀的個體才能被選作父個體。其中，用于決定染色體被選作父個體的百分比的參數稱為截斷閥值，范圍取90%～80%。在該閥值之外的個體不能產生子個體。

2.5交叉算子

交叉只對復制產生的85%的個體進行，此時適當的選擇交換概率p，p過大或過小都不易收斂到最優解，設p為0.95（保留的15%不參加交換）。采用一點交換方式，在排課問題中，每周某一課程上課節次是固定的，隨機選擇第n個DNA分子時間節次碼中第m個基因位為1的基因。

2.6變異算子

排課系統中由于課表合法性問題，如果采用簡單的隨機變異，會出現大量的沖突，導致需要消耗大量精力去糾錯。因此，我們在研究中采用有條件的基因變異。變異操作的作用是防止丟失有用的可能解，保證搜索到空間的重要點，使算法具有全局收斂性，變異的概率較小，在本文中取0.01。和交叉算子一樣僅是時間節次碼參與交換，教室和課程碼保持不變。選擇兩個點進行變異，具體操作是：隨機選擇第n個DNA分子，再隨機選DNA分子中的時間碼第p、q個點進行變異。

2.7終止條件

采用迭代次數來決定，取2500。

參考文獻

[1] 肖俊.遺傳算法的工程應用[J].計算機科學，2005，11（32）：247-250