基于遺傳算法的高校教務系統排課問題的應用研究

蔣正鋒，呂佩佩，覃韓，龔瓊珍

（1.廣西民族師范學院數學與計算機科學學院，崇左532200；2.武漢大學計算機學院，武漢430072）

0 引言

二十世紀五十年代就有學者對自動排課問題進行研究，如Gotlieb 在1963 年時第一次就提出了自動排課的數學模型，而我國對排課問題的研究起步比較晚，始于80 年代初，并且取得了一定的成效，一些學校都有自己的排課系統[1,5]，但是這些排課系統都是依賴各個學校的具體情況，有自己的特殊性[2]，不宜推廣。考慮廣西民族師范學院的教學體制，模擬人工排課過程，制定一份相對能夠統籌兼顧學校教學資源的課表，將提高排課的效率，減少了排課工作量，提高學校教學質量，對推動學校信息化管理也起著重大的作用。

1 遺傳算法

1.1 遺傳算法的基本思想

遺傳算法（Genetic Algorithms，簡稱GA 或GAs）[3]是在二十世紀七十年代初由美國密歇根大學的Joho H.Holland 教授首先提出來的，是一種模擬生物界的進化規律演化而來的隨機化搜索方法，它剛被提出時便吸引了大量學者進行研究，并迅速得到推廣到搜索、優化等領域。遺傳算法是一種基于群優化的方法，在初始解集種群生成后，種群中的每個個體都會根據適應度函數[4]來評估優劣，將剔除種群部分個體，最后得到最優個體，就是待求解的最優解。具體優化步驟如下：

步驟一：隨機生成初始化種群。

步驟二：根據求解問題的目標函數構造適應度函數。適應度函數用于評估種群中每個個體對其生存環境的適應性。

步驟三：根據適應度函數對種群個體的評估值，選擇適應性強的種群個體，然后通過交叉和變異更新種群個體編碼。

步驟四：循環執行步驟二、三多代后獲得待求解的最優解。

1.2 遺傳算法的基本操作

遺傳算法主要包括三個基本操作[3]，分別為選擇操作、交叉操作和變異操作，這三個基本操作是按順序執行的，并且可以重復執行多次。

（1）選擇操作

選擇操作以種群個體適應度計算為前提，隨機選擇30%到60%的種群個體參與下一輪遺傳操作。本文選擇個體采用輪盤賭算法，基本思路是種群中每個個體被選中的概率與其計算出來的適合度成正比，然后以積累概率的形式分布在轉盤上，通過轉動轉盤，選擇指針落在某個扇區對應的個體。

（2）交叉操作

交叉操作是遺傳算法的核心部分，它將兩個父代個體以一定概率對基因編碼[5]部分進行互相交叉重組，產生新的子代個體。交叉的方式有單點交叉、多點交叉和均勻交叉等，以單點交叉為例，兩個二進制編碼的個體分別為P1：10101101，P2：11010110，交叉前隨機生成交叉位置n 和0 到1 之間的浮點數q。假設n=3，q=0.6，且0＜q＜0.8，則進行P1 和P2 的交叉操作，從P1和P2 從第四位開始交換所有后續的編碼，生成新的個體為NP1:10100110，NP2:11011101，單點交叉操作前后如表1 所示。

表1 單點交叉操作前后比較

（3）變異操作

變異操作是指以一定突變概率在一個父代個體基因編碼的某個位置進行變異，生成新的子代個體。二進制編碼的變異操作是0 變成1 或1 變成0。變異前隨機生成變異位置n 和0 到1 之間的突變概率q。假設變異概率為0.06，n=4，q=0.03，且0＜q＜0.06，則對P3:11010011 進行變異操作，生成新的個體為NP3:10100110，變異操作前后對比如表2 所示。

表2 變異操作前后對比

遺傳算法三個基本操作選擇操作、交叉操作和變異操作如圖1 所示。

2 排課問題制約條件

排課需要解決的問題，就是如何協調好時間與空間的關系[9]。課程表主要由五個要素組成，分別為班級、課程、教師、教室和時間。排課問題的五要素用集合形式表示，如班級CLASS={CL1,CL2,CL3,…,CLN}，課程COURSE={CO1,CO2,CO3,…,COL}，教師TEACHER={TE1,TE2,TE3,…,TEK}，教室CLASSROOM={CR1,CR2,CR3,…,CRP}，時間TIME={TI1,TI2,TI3,…,TIQ}，五要素之間存在一定的約束，排課問題就是在硬性制約和軟性制約條件[3]下，尋找一個五要素之間的最優的組合。

圖1 遺傳算法流程圖

（1）硬性制約

硬性制約是為了排除五要素之間出現沖突的情況，課程安排必須要滿足的，如下列的情況：

①一個班級不能同一個時間片安排兩門課程。

②一個教師不能同一個時間片教授兩門課程。

③一個教師不能同一個時間片教授兩個班級，合班授課除外。

④一個教室不能同一個時間片有兩個班級上課，合班上課除外，但只能是一位教師授課。

⑤授課教室的容量要大于等于在此上課班級的學生人數。

⑥教室類型要與課程對教室要求的類型一致。

（2）軟性制約

軟性制約是在硬性制約的基礎上人為設定的約束條件，是為了課程安排更加科學與合理，常見的軟性制約如下：

①一個班級的上課時間不能過于密集，應均勻分散在一周內。

②同一門課程不同班級，授課教師在一天內完成相同的授課內容，以保證教學的連貫性。

③同一門課程同班級兩次課時間間隔至少一天，但也不能超過兩天。

④選修課安裝在晚上或者周末。

⑤盡量滿足教師對課程安排的特殊需求。

⑥連續上課或授課時，教室之間的距離不能太遠。

⑦專業課和邏輯思維性強的課程，盡量安排在上午，體育課一般安排在下午。

⑧教師的授課任務不能過于集中，為保證授課質量，應均勻分散在一周內。

3 基于遺傳算法的自動排課模型設計

3.1 基因編碼

基因編碼[6,7]是排課問題的五要素集合中元素的結構化組合。時間要素TIME 是由時間片TIi 組成的，每個時間片就是兩節課，每天上午2 個時間片，下午2 個時間片，晚上1 個時間片，一周排課5 天，總共25 個時間片，排課問題就是基因編碼分布在25 個時間片里，所以基因編碼不包含時間要素。

3.2 生成初始種群

初始化種群就是隨機生成一定數量滿足硬性制約可用的全校課表的過程，一定數量是種群的大小，即個體的數量為M。

下學期要開設哪些課程是教研室主任根據培養方案來制定合理的任課計劃表，而任課計劃表中教師的授課任務是確定的，即在哪些班級開設了什么課程是確定的，所以班級、課程和教師的組合編碼排課前就綁定好了。初始化種群是在滿足硬性制約條件下把由班級、課程、教師、教室和時間組合基因編碼保存下來，把班級、課程和教師看成一個新的組合要素，排課問題的五要素就轉成了新的組合要素、教室和時間三要素，即新的組合要素和合適的教室構成的基因編碼分布在某個時間片里。

生成一個初始化班級課表，具體操作過程如下：

步驟一：一個班級任課計劃表中存在還沒有安排的課程，轉到步驟二，否則轉到步驟五。

步驟二：選擇其中一門課程，任課計劃表中組合編碼分成班級編碼和新的課程和教師的組合編碼，其中班級編碼確定要初始化個體行的位置。

步驟三：隨機選擇一個滿足硬性要求的教室，由課程、教師和教室構成基因編碼。

步驟四：隨機選擇一個空閑的時間片，把基因編碼寫到時間片里，轉到步驟一。

步驟五：班級課表初始化結束。

上述操作過程是初始化一個班級課表，循環操作初始化全校所有班級課表就生成一個種群個體，循環操作初始化M 個個體，就生成初始種群。

3.3 適應度計算

初始化種群后，對種群中個體的優化[4]，需用到適度函數來評估每個個體的適應度值。本文定義的適應度函數是基于加分原則的，滿足不同軟性制約條件則加上不同的分數，最后得到個體的適應度值。適應度的計算包括班級適應度、課程適應度和教師適應度。

（1）班級適應度考慮連續兩門課程上課教室分布情況，如同一上課教室、同一樓層不同教室、不同樓層教室和不同教學樓的教室。

（2）課程適應度考慮課程分布在25 個時間片里的均勻程度，同一門課程兩次課的間隔、不同類型課程如專業課和邏輯思維性強的課程、體育課等課程的安排、不同時間片對上課效果的影響等。

（3）教師適應度考慮授課分布在25 個時間片里的均勻程度、連續時間片授課不同教室的轉移、同課程不同班級課程安排是否為同一天等。

對于一個班級來說，綜合計算班級適應度和課程適應度，而對于一個個體來說，還需考慮教師適應度。

3.4 遺傳算法優化課程表

遺傳算法優化課程表就是循環選擇操作、交叉操作和變異操作[6,8]三個基本操作，直到滿足遺傳算法結束條件。在排課問題中交叉操作和變異操作后都可能發生沖突，所以要進行沖突檢測和調整，使交叉操作和變異操作后生成新個體滿足硬性制約[3]條件。

（1）排課問題選擇操作

根據種群中個體的適應度值使用輪盤賭算法選擇種群中50%的個體進行下一步操作。

（2）排課問題交叉操作

本文成對發生交叉的概率設定為0.6，如發生交叉操作，排課問題的交叉操作有兩種，一種個體與個體之間，隨機互相交換某個位置后續班級的課程表，另一種是個體中同一時間片里基因編碼中教室編碼的互換，生成新的個體，加入到種群。

（3）排課問題變異操作

變異操作在優化種群極為關鍵，本文變異概率設定為0.5。排課問題的變異是指兩個方面的變異操作，一是基因編碼在時間片上的位置變化，另一個是基因編碼中教室編碼的改變。

（4）淘汰適應度低的個體

個體的適應度值是班級適應度、課程適應度和教師適應度值之和，計算出每個個體適應度，對種群中個體按適應度進行排序，淘汰掉適應度值低的個體，使種群大小為M，準備下一代的遺傳操作。

3.5 遺傳算法終止條件

淘汰適應度低的個體后，判斷是否滿足遺傳算法的終止條件。本文遺傳算法的終止條件有兩種，一是進化迭代次數達到一定值后就結束遺傳算法；二是連續進化迭代五次，種群中個體的最高適應度幾乎沒有變化。

4 基于遺傳算法的排課系統

本排課系統采用B/S 結構，基于Java 語言開發的，采用JSP 技術和MySQL 數據庫，開發出一個基于遺傳算法的排課系統。

排課系統面向的學校管理人員、教師和學生，所以根據使用系統用戶對象的不同，整個系統分管理員操作模塊、教師操作模塊和學生操作模塊，用戶登錄界面如下圖2 所示。不同用戶登錄進入不同的操作模塊，管理員操作模塊是自動排課系統最重要的部分，操作權限屬于管理員。

圖2 基于遺傳算法的排課系統登錄界面

管理員成功登錄后，進入管理員操作界面，主要有排課管理、課程管理、課表管理、人員管理和基礎數據管理等功能，系統功能主界面如圖3 所示。

圖3 排課系統功能界面

自動排課保存到數據庫中的課表是班級課表，課表分班級課表、教師課表和教室課表三種，但教師課表和教室課表可由班級課表變換得到。某教師登錄排課系統查看自己授課任務的課表如圖4 所示。

圖4 教師查看自己的課表

自動排課是本系統最為核心的部分，以班級、課程、教師和教室數據為基礎，生成一定數量滿足硬性制約可用的全校課表，然后使用遺傳算法優化課表，可對生成的課表進行查看、修改、檢查等操作，最終將課表數據保存到系統數據庫中，能快速地自動編排成較科學與合理的課程表，符合教學規律，對于提高學校教務管理水平具有重要意義。

5 結語

如何合理配置有限的教學資源已成為每個高校[5,6]避不開的問題，其中編排全校科學與合理的課程表是這個問題的核心部分。本文簡單介紹了遺傳算法的基本思想，對排課問題的制約條件進行了分析，針對廣西民族師范學院的具體情況，結合遺傳算法中選擇、交叉和變異策略進行分析，設計了一個基于遺傳算法的智能的自動排課數學模型，由測試結果表明了該智能排課模型能快速地自動編排成較科學與合理的課程表，省時又省力，但隨著學?？焖侔l展及招生規模的進一步擴大，學校教務管理工作的變化，排課問題需求也會發生變化，因此排課問題的算法有待于進一步優化和研究[7,10]。