基于遺傳算法的排課系統(tǒng)的研究與實現(xiàn)

穆雪

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

關(guān)鍵詞：排課；遺傳算法；多目標(biāo)優(yōu)化；時間模式

1.引言

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

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

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

2.數(shù)學(xué)模型分析

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

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

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

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

3.時間模式

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

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

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

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

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

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

4.1 染色體編碼

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

4.2 初始種群生成

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

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

算法：GAInit（T，W，n）

Input：時間模式T，教學(xué)任務(wù)W，初始種群大小n

Output：初始種群GAI

步驟1：定義初始種群GAI結(jié)構(gòu)，確定班級個數(shù)m，種群大小n.。

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

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

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

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

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

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

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

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

4.3 適應(yīng)度函數(shù)

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

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

4.4 選擇操作

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

5.結(jié)論

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

本文提出了時間模式的概念，并將其與遺傳算法結(jié)合，提出了新的基于遺傳算法的排課算法。在算法中利用時間模式求解了遺傳算法的初始種群，且根據(jù)軟約束設(shè)置了不同的課表的評價指標(biāo)，避免了沖突，實現(xiàn)了課表的有效優(yōu)化。

參考文獻

[1]楊宇.高校排課系統(tǒng)理論研究與開發(fā)---遺傳算法在課表問題中的應(yīng)用.北京：北京理工大學(xué)，2003.

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

[3]膝姿，鄧輝文，楊久俊.基于遺傳算法的排課系統(tǒng)的設(shè)計與實現(xiàn).計算機應(yīng)用， 2007 （12）.

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

[5]張春梅，行飛.用自適應(yīng)的遺傳算法求解大學(xué)課表問題.內(nèi)蒙古大學(xué)學(xué)報（自然科學(xué)版）， 2002.