基于蒙特卡洛遺傳算法的排課問題研究

張貴軍, 陳 安, 胡 俊

(浙江工業(yè)大學(xué) 信息工程學(xué)院, 浙江 杭州 310014)

隨著高等院校招生規(guī)模擴大和專業(yè)的發(fā)展,教學(xué)資源不足的問題被放大,合理的教學(xué)安排變得尤為重要。排課已經(jīng)成為教學(xué)管理中的一項重要工作[1]。

排課問題實質(zhì)上屬于調(diào)度問題的研究范疇,即將班級、教師、課程等資源根據(jù)約束條件安排在特定的時間和教室中,并使結(jié)果達(dá)到最優(yōu)。由于該問題具有多約束、多目標(biāo)和非線性的屬性[2],難以用經(jīng)典優(yōu)化方法求解,因此通常采用啟發(fā)式優(yōu)化算法,例如模擬退火算法、遺傳算法、禁忌搜索算法等來求解該類問題[3]。

筆者對傳統(tǒng)遺傳算法做了改進(jìn),提出一種基于蒙特卡洛的遺傳算法,對交叉和變異階段產(chǎn)生的個體采用蒙特卡洛概率接受的方法,彌補傳統(tǒng)遺傳算法的早熟、收斂速度慢等缺點,避免算法陷入局部極值解,提高種群的質(zhì)量。最后,采用ReactJS+NodeJS+MongoDB框架開發(fā)出一套智能排課系統(tǒng)。

1 排課問題的數(shù)學(xué)模型

排課問題的主要內(nèi)容是將班級、課程、教師和教室安排在不沖突的時間內(nèi)。然而在排課過程中,課表的合理性會受課程時間安排均勻度、教室利用率以及不同類型課程在不同時間段上課效率等方面的影響。因此,排課需要解決的問題是：確定每個班級的課表在滿足各種約束的條件下目標(biāo)達(dá)到最優(yōu)。

1.1 變量描述

排課問題的數(shù)學(xué)模型變量描述為：

(1) 班級集合：C={c1,c2, …,cn}；

(3) 教師集合：T={t1,t2,…,tk}；

(5) 教室集合：R={r1r2,…,rp}；

(6) 教師對上課時間的滿意度集合：W={w1,w2,w3,w4,w5}。

1.2 約束條件

在建立排課問題數(shù)學(xué)模型之前,考慮如下約束條件[4-6]：

(1) 同一個班級在同一個時間段只能安排一門課程,即：

(1)

表示同一個班級cn在同一時間dm只能安排同一門課程kl,在教室rp由教師th授課；其中L表示最多有L個課程,H表示最多有H個教師,P表示最多有P個教室；

(2) 同一個教師在同一時間段只能安排一門課程,即：

(2)

表示同一個教師th在同一時間dm只能安排同一門課程kl,在教室rp授課班級cn；其中L表示最多有L個課程,N表示最多有N個班級,P表示最多有P個教室；

(3) 同一個教室在同一時間段只能安排一門課程,即：

(3)

表示同一個教室rp在同一時間dm只能安排同一門課程kl,在教室中由教師th在授課班級cn；其中L表示最多有L個課程,N表示最多有N個班級,H表示最多有H個教師；

(4) 教室容量須大于班級學(xué)生人數(shù),即：

rnum≥cnum

(4)

rnum表示教室容量,cnum表示班級學(xué)生數(shù)量。

(5) 每個課程的上課時間盡量滿足教師的要求；

(6) 同一門課程的上課安排不能過于緊湊；

(7) 合理利用教室的利用率與上課地點的關(guān)系。

上述(1)—(4)為排課的硬約束條件,(5)—(7)為軟約束條件。滿足硬約束條件的方案便是排課的可行解,軟約束條件則是作為評判排課方案好壞的標(biāo)準(zhǔn)。本文的排課方法是在對班級、課程、教師、教室和學(xué)生五元數(shù)組求解過程中,滿足上課地點和上課時間不沖突的條件下,經(jīng)過一步步的優(yōu)化最終找到最優(yōu)的排課方案。

2 編碼方案

2.1 編碼

編碼方式不同,排課效率也會不同,好的編碼方式能夠讓排課變得更高效。本文中,排課問題的研究對象為班級、課程、教師、時間和教室,采用十進(jìn)制的編碼方式對課表編碼。

將課表看作個體,將班級、課程、教師、時間和教室信息編碼作為染色體,編碼結(jié)構(gòu)形式為班級編號-課程編號-教師編號-上課時間編號-教室編號(見圖1)[7]。例如編碼為0113-0301-0202-1135-1204,表示班級編號為0113的班級,由編號為0202的教師來授課編號為0301的課程,“1135”表示上課時間,規(guī)定一門課程一周上2個課時,將一天劃分為5個上課時間段,所以“1135”表示為周一的第1段時間(即上午第1、第2節(jié)課),以及周三的第5段時間(即晚上第9、第10節(jié)課)。

圖1 基因編碼圖

2.2 適應(yīng)度評價函數(shù)

在遺傳算法中,適應(yīng)度評價函數(shù)是衡量一個個體好壞程度的重要標(biāo)準(zhǔn)。本文將從3個方面對排課問題定義評價函數(shù)。

2.2.1 課程間隔

對于同一門課程的安排,合適的時間間隔有助于學(xué)生學(xué)習(xí)和鞏固課程知識,保持學(xué)習(xí)的積極性,同時給予教師充分的時間備課,避免學(xué)生與教師因密集的課程而過度勞累。

(5)

(6)

(7)

(8)

2.2.2 教室間隔

一天內(nèi)相鄰時間的上課教室安排對學(xué)生和教師也有一定的影響,合理安排上課教室能夠使學(xué)生在上課之前有充裕的時間休息和預(yù)習(xí)下一節(jié)課程內(nèi)容,讓教師有充足的時間休息并且準(zhǔn)備上課內(nèi)容。因此針對教室間隔的安排,具體方式如下：

(9)

(10)

(11)

2.2.3 教師要求

課程安排的時間和地點應(yīng)盡可能滿足教師的要求,如果上課時間和地點與教師的個人安排有沖突,會導(dǎo)致教學(xué)進(jìn)程緩慢、教學(xué)效率降低。因此,滿足教師對上課時間和地點的要求是教學(xué)排課中一個重要的環(huán)節(jié)。教師合理度要求表達(dá)為

(12)

其中,f3表示總的教師合理度,q表示一個班級的教師合理度,θ1表示根據(jù)第一次上課時間段從教師-時間滿意表中查詢其對應(yīng)的滿意值,θ2表示根據(jù)第二次上課時間段從教師-時間滿意表中查詢其對應(yīng)的滿意值,如表1表示教師A的時間滿意表；α表示教師對安排的授課教室的滿意度,其值也是通過查找教師-教室滿意表得到,如表2表示教師A、B、C對教室A、B、C、D、E的滿意表。

表1 教師-時間滿意表

表2 教師-教室滿意表

綜上所述,本文的適應(yīng)度評價函數(shù)F定義如下：

(13)

其中ωi表示適應(yīng)度函數(shù)評價值fi對應(yīng)的權(quán)值,其中i=1,2,3,因此目標(biāo)函數(shù)為f=max(F)。

3 蒙特卡洛遺傳算法

3.1 蒙特卡洛

本文的排課問題實質(zhì)可定性為一個離散非線性規(guī)劃問題。在排課中,蒙特卡洛[8-10]采樣過程如下：

首先,設(shè)定馬爾可夫鏈狀態(tài)轉(zhuǎn)移概率ρ與當(dāng)前種群最優(yōu)個體狀態(tài)值x0以及新生成個體狀態(tài)值x1有關(guān),平穩(wěn)分布π(x)設(shè)定狀態(tài)轉(zhuǎn)移次數(shù)的閾值為n1。

然后,在每一次遺傳算法排課的迭代過程中,進(jìn)行n1次轉(zhuǎn)移：

(1) 從均勻分布中u～uniform[0,1]中隨機采樣得到u；

(2) 若u<ρ,則接受轉(zhuǎn)移x1→x0并且結(jié)束本次轉(zhuǎn)移,則x1=x2,其中x2表示下一代新個體的狀態(tài)值；否則不接受轉(zhuǎn)移。

3.2 種群初始化

傳統(tǒng)遺傳算法在初始化種群過程中,通常采用隨機方案來生成種群?？紤]排課的特殊性,本文在初始化過程中加入約束條件生成初始化種群。

根據(jù)教學(xué)任務(wù),班級的專業(yè)課和授課教師已經(jīng)提前安排,只需對上課時間和上課地點初始化。首先,對于每個班級隨機生成一組課程的上課時間和地點。若分配的上課時間、教室位置以及教室容量沒有發(fā)生沖突,那么將信息保存下來作為個體中的一條染色體；若產(chǎn)生沖突,則按照上述規(guī)則重新初始化,依次完成每個班級的編碼直到全部成功編碼,最終根據(jù)種群規(guī)模來生成相應(yīng)個體,從而達(dá)到種群初始化。

3.3 選擇

選擇操作是對種群中個體進(jìn)行去劣存優(yōu)的一種自然選擇過程,從舊種群中選取適應(yīng)性強的個體。個體適應(yīng)度越高,被選擇的可能性越大[11]。本文采用蒙特卡洛概率接受的方法進(jìn)行選擇,若交叉變異產(chǎn)生的新個體優(yōu)于舊個體,則接受該個體,否則以一定的概率來接受該個體,其中接受概率為

(14)

其中σ為接受概率,E1為舊個體的適應(yīng)度,E2為新個體的適應(yīng)度,KT為常量；

3.4 交叉

染色體的交叉保證了種群的多樣性,防止遺傳的單一化[12],在進(jìn)行交叉之前要選擇雙親。本文中選取當(dāng)代種群中適應(yīng)度最優(yōu)的個體S1作為父代,在剩余個體中隨機選擇個體S2作為母代。交叉的方法為：

(1) 從雙親中隨機選取2段相同片段的染色體,將染色體中的“時間”和“教室”基因如圖2方式進(jìn)行交換；

(2) 判斷交換成功之后的個體S1是否發(fā)生課表沖突,若不沖突,則表示交叉完成,否則恢復(fù)染色體片段并且回到步驟(1)中繼續(xù)交叉,直到不沖突。

圖2 交叉

3.5 變異

變異操作是自然選擇中的突發(fā)過程,它的出現(xiàn)擴大了種群的多樣性[13]。本文中的變異方式有3種：對染色體中的“時間”進(jìn)行變異；對染色體中的“教室”進(jìn)行變異；對染色體中的“時間”和“教室”基因一起變異[14]。具體變異操作如下：

(1) 首先通過生成隨機數(shù)來判斷執(zhí)行上述變異方式中的一種；

(2) 從個體中隨機選取一條染色體進(jìn)行變異,其中變異的方式如圖3所示,從時間集合D或者教室集合R中隨機選取時間和教室編號信息,替換該染色體中的時間和教室編號；

(3) 判斷變異之后的個體是否發(fā)生課表沖突,若不沖突,則表示變異完成,否則轉(zhuǎn)到步驟(2),并且恢復(fù)該染色體片段。

圖3 變異

4 仿真測試與分析

為了驗證排課問題中蒙特卡洛遺傳算法的性能,選取某高校某學(xué)院27個班級、55位教師的實驗數(shù)據(jù)。將教師對于時間和教室的滿意值均設(shè)為1,設(shè)置種群規(guī)模20,交換概率0.5,變異概率0.01,遺傳代數(shù)1 400代。將傳統(tǒng)遺傳算法與基于蒙特卡洛遺傳算法作對比測試,運行結(jié)果如圖4所示。從圖4中可知,在1～400代期間,傳統(tǒng)的遺傳算法對適應(yīng)度的提升穩(wěn)定,而蒙特卡洛遺傳算法對適應(yīng)度的影響影響較大,適應(yīng)度的變化體現(xiàn)出蒙特卡洛方法中對較差適應(yīng)度個體進(jìn)行概率接受的特點,在400～1600代的時候,基于蒙特卡洛的遺傳算法收斂速度優(yōu)于傳統(tǒng)遺傳算法。實驗結(jié)果表明：基于蒙特卡洛的遺傳算法得到的最優(yōu)解優(yōu)于傳統(tǒng)遺傳算法,說明加入蒙特卡洛方法可以避免局部極值解,得到問題最優(yōu)可行性方案。

圖4 蒙特卡洛遺傳算法收斂性能對比圖

5 結(jié)語

排課是教學(xué)管理中非常重要的一部分,傳統(tǒng)的排課方法效率低、排課沖突率高,影響教學(xué)秩序。本文采用基于蒙特卡洛的遺傳算法進(jìn)行排課,統(tǒng)計學(xué)生、教師、課程等信息,將排課問題轉(zhuǎn)化成多約束、多目標(biāo)的模型優(yōu)化問題,將蒙特卡洛與遺傳算法結(jié)合,啟發(fā)式搜索排課問題的最優(yōu)可行性方案,在滿足上課時間、地點不沖突,兼顧學(xué)生、教師和教室容量需求的情況下得到比較人性化、合理化的課表。