基于遺傳算法的高校教務(wù)系統(tǒng)排課問題的應(yīng)用研究

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

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

0 引言

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

1 遺傳算法

1.1 遺傳算法的基本思想

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

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

步驟二：根據(jù)求解問題的目標函數(shù)構(gòu)造適應(yīng)度函數(shù)。適應(yīng)度函數(shù)用于評估種群中每個個體對其生存環(huán)境的適應(yīng)性。

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

步驟四：循環(huán)執(zhí)行步驟二、三多代后獲得待求解的最優(yōu)解。

1.2 遺傳算法的基本操作

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

（1）選擇操作

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

（2）交叉操作

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

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

（3）變異操作

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

表2 變異操作前后對比

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

2 排課問題制約條件

排課需要解決的問題，就是如何協(xié)調(diào)好時間與空間的關(guān)系[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]下，尋找一個五要素之間的最優(yōu)的組合。

圖1 遺傳算法流程圖

（1）硬性制約

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

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

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

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

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

⑤授課教室的容量要大于等于在此上課班級的學(xué)生人數(shù)。

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

（2）軟性制約

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

①一個班級的上課時間不能過于密集，應(yīng)均勻分散在一周內(nèi)。

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

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

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

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

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

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

⑧教師的授課任務(wù)不能過于集中，為保證授課質(zhì)量，應(yīng)均勻分散在一周內(nèi)。

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

3.1 基因編碼

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

3.2 生成初始種群

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

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

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

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

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

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

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

步驟五：班級課表初始化結(jié)束。

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

3.3 適應(yīng)度計算

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

（1）班級適應(yīng)度考慮連續(xù)兩門課程上課教室分布情況，如同一上課教室、同一樓層不同教室、不同樓層教室和不同教學(xué)樓的教室。

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

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

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

3.4 遺傳算法優(yōu)化課程表

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

（1）排課問題選擇操作

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

（2）排課問題交叉操作

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

（3）排課問題變異操作

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

（4）淘汰適應(yīng)度低的個體

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

3.5 遺傳算法終止條件

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

4 基于遺傳算法的排課系統(tǒng)

本排課系統(tǒng)采用B/S 結(jié)構(gòu)，基于Java 語言開發(fā)的，采用JSP 技術(shù)和MySQL 數(shù)據(jù)庫，開發(fā)出一個基于遺傳算法的排課系統(tǒng)。

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

圖2 基于遺傳算法的排課系統(tǒng)登錄界面

管理員成功登錄后，進入管理員操作界面，主要有排課管理、課程管理、課表管理、人員管理和基礎(chǔ)數(shù)據(jù)管理等功能，系統(tǒng)功能主界面如圖3 所示。

圖3 排課系統(tǒng)功能界面

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

圖4 教師查看自己的課表

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

5 結(jié)語

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