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

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

0 引言

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

1 遺傳算法

1.1 遺傳算法的基本思想

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

步驟一：隨機(jī)生成初始化種群。

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

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

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

1.2 遺傳算法的基本操作

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

（1）選擇操作

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

（2）交叉操作

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

表1 單點(diǎn)交叉操作前后比較

（3）變異操作

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

表2 變異操作前后對(duì)比

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

2 排課問題制約條件

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

圖1 遺傳算法流程圖

（1）硬性制約

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

①一個(gè)班級(jí)不能同一個(gè)時(shí)間片安排兩門課程。

②一個(gè)教師不能同一個(gè)時(shí)間片教授兩門課程。

③一個(gè)教師不能同一個(gè)時(shí)間片教授兩個(gè)班級(jí)，合班授課除外。

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

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

⑥教室類型要與課程對(duì)教室要求的類型一致。

（2）軟性制約

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

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

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

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

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

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

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

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

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

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

3.1 基因編碼

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

3.2 生成初始種群

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

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

生成一個(gè)初始化班級(jí)課表，具體操作過程如下：

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

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

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

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

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

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

3.3 適應(yīng)度計(jì)算

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

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

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

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

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

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

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

（1）排課問題選擇操作

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

（2）排課問題交叉操作

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

（3）排課問題變異操作

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

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

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

3.5 遺傳算法終止條件

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

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

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

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

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

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

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

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

圖4 教師查看自己的課表

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

5 結(jié)語

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