基于遺傳算法的排課系統的研究與實現

穆雪

摘 要：介紹是排課問題，分析了排課的數學模型，分析了基于遺傳算法的排課算法的基本原理及及其算法特點，利用時間模式，提出了基于遺傳算法解決排課問題的方法，并驗證了該方法的有效性。

關鍵詞：排課；遺傳算法；多目標優化；時間模式

1.引言

人工編排課程表是教務人員在進行教學管理中最為頭疼的工作之一。它涉及到很多的軟件 硬件資源和內外部因素，如：時間、地點、教師、學生及課程等。尤其是隨著高職院校的不斷擴招而軟硬件設備沒有及時更新和增加，造成了人多教室省、課程多時間少等狀況。這些問題使得學校的教學管理無法正常進行。傳統的人工排課方式存在有以下幾個方面的問題：人工編排課程表工作量大人工編排課程表依賴于人為因素；人工編排課程表可維護性差；人工編排課程表安全性差。

排課系統就是在教師、教室和時間這3大資源數量有限，約束不同的條件下，合理安排班級的課程，使得學生和教師獲得較為合理的上課時間和空間，是一個多目標的調度問題。如何實現課表的合理安排是當前高校教學管理人員值得研究的問題。

遺傳算法（Genetic Algorithm，簡稱GA）是一種自適應隨機搜索算法，具有全局收斂性和并行性，且對模型是否線性、連接、可微等不作限制，也不受優化數目、約束條件的束縛，所在工程優化、圖像處理和模式識別等領域取得廣泛的應用。本文將結合實際排課中所涉及到的各類約束、優化目標設計一種特定的基因編碼方法，和相應的目標評價函數，并在實際應用中取得了較好的效果。

2.數學模型分析

排課問題是求解三元組（Lecture，Time，Room）課程、時間和教室的統籌調度，即給指定的課程安排適應時間、空間等教學資源，使學校課程整體達到一個較為合理的狀態，其中課程又包含了（Classes，Lesson，Teacher）三個元素，即每個授課的班級、課程名稱和對應的老師是相關的，這些授課計劃數據是系統的輸入部分，而一個合理的排課結果是指使目標函數達到優值，表現為課程的時間安排均勻、教室利用率高、盡可能多滿足教師偏好等。實現此結果關鍵在于如何解決排課過程的眾多約束和有效目標函數的建立。

對于一個班級的某一個時刻不能上一門以上的課程，而在高校中由于資源緊張許多課程大班開課，因此對一次授課要求所有上該課的班級在該時刻沒有其他課程，則對于任何一門課程開設時間為t的課程lec有 =0

對于每個教師任何時刻只能參加一次授課，約束模型與班級約束相似，只是一次授課只有一個教師，沖突檢測只需對某個教師所授所有課程集合進行統計即可。

教學資源的約束，要求任何一個時刻作何一種類型的教學資源安排量不可超過學校擁有該類資源的總量；一個授課的安排要求該教學班級人數不可超過教室（或者其他教學資源）的容量，對于需要r類型教學資源，在t時刻授課的集合

3.時間模式

時間模式是一種上課時間的安排形式，由時間模式代碼表和時間模式明細表兩個表組成，其中時間模式代碼表是主表，定義了時間模式的基本信息，時間模式明細表是從表，定義時間模式所對應的上課時間。使用時間模式安排課表具有以下優點：

通過時間模式可以有效地安排課程，防止周學時較大的課程被安排在同一天或相鄰的兩天。

時間模式基本表中定義了優先級，可實現按照會優先級的順序安排班級的課表，可避免隨機安排班級課表所造成的課程上課時間的不合理問題。

時間模式的比較靈活，實現較容易，能滿足學校實際上課的需求，只定義較為合理上課時間的組合即可。

4.基于遺傳算法的排課算法

遺傳算法的基本原理：首先采用編碼方式將解空間映射到編碼空間，每個編碼對應問題的一個解（稱為染色體）。通過隨機方法確定初始的一群個體（稱為種群），在種群中根據適應度值或某種競爭機制選擇個體，利用各種遺傳操作算子（交叉、變異等）產生下一代，如此進化下去，直到滿足期望的終止條件。

4.1 染色體編碼

根據排課的實際情況，使用十進制來對的個體進行驗證碼，每個個體利用m*26 的數組表示。

4.2 初始種群生成

一個染色體就是一個可能的排課結果，是一個m*26 的數組，需處理的數據量較大，結構相對比較復雜。因此，如果初始種群中個體的分布不好，將很容易使整個排課結果陷入局部最優而得不到好的排課結果，因此初始種群的生成對整個算法的影響較大。

將時間模式引入到遺傳算法中進行初始種群的生成。基本思想：首先確定班級的數量及所要上的課程；接著隨機選取一個班所上的課程產生所需要的時間模式編號，判斷是否沖突，不沖突，則在個體相應的上課時間上記錄課程號，否則重新產生隨機模式編號；真至所有個體的所有班級的課程都安排完成。

算法：GAInit（T，W，n）

Input：時間模式T，教學任務W，初始種群大小n

Output：初始種群GAI

步驟1：定義初始種群GAI結構，確定班級個數m，種群大小n.。

步驟2：確定所有的上課班級及其所要上的課程CL，初始化i=1，j=1，p=1。

步驟3：初始化種群中第i個個體。

步驟4：取第j個班的課程ID（p），確定其周學時zxs。

步驟5：根據zxs隨機生成時間模式，確定一上課時間。

步驟6：判斷上課時間是否沖突，沒有沖突，則將課程號ID（p）記錄于第i個個體的相應的時間位置。否則，轉到步驟5。

步驟7：判斷第j個班的課程是否安排完成，如果沒有完成，p=p+1，轉到步驟4，直到j班的所有課程都安排完成。

步驟8：否則j=j+1，轉到步驟4，直到所有班級的課程安排完成。

步驟9：i=i+1，直到所有的個體的初始化完成。

4.3 適應度函數

根據排課的軟約束條件定義適應度函數，適應度值越小，個體越優。適應度由下面公式計算：F=a1×C1+a2×C2+a3×C3

其中C1為課程上課時間評價，C2 是一周多次課程的分布評價，C3教師課表分布評價。a1、a2和a3為評價系數，三者和為1。

4.4 選擇操作

采取輪盤選擇方法，根據個體適應度的大小，將種群中F值較小的個體以較大的概率保存到下一代中。

5.結論

以20個班級，120課程，課程的周學時為2和4兩種情況，基于MatLab平臺實現了排課系統。結果證明本文的算法能較快地收斂，且能得到較為理想的課表。

本文提出了時間模式的概念，并將其與遺傳算法結合，提出了新的基于遺傳算法的排課算法。在算法中利用時間模式求解了遺傳算法的初始種群，且根據軟約束設置了不同的課表的評價指標，避免了沖突，實現了課表的有效優化。

參考文獻

[1]楊宇.高校排課系統理論研究與開發---遺傳算法在課表問題中的應用.北京：北京理工大學，2003.

[2]沈麗榮，陳明磊.基于遺傳算法的高校排課系統研究.計算機科學與技術，2006（112）.

[3]膝姿，鄧輝文，楊久俊.基于遺傳算法的排課系統的設計與實現.計算機應用， 2007 （12）.

[4]謝勇，鄭金華.基于遺傳算法的綜合性大學排課系統研究.中國教育信息化， 2007 （11）.

[5]張春梅，行飛.用自適應的遺傳算法求解大學課表問題.內蒙古大學學報（自然科學版）， 2002.