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

張貴軍, 陳 安, 胡 俊

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

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

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

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

1 排課問題的數學模型

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

1.1 變量描述

排課問題的數學模型變量描述為：

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

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

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

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

1.2 約束條件

在建立排課問題數學模型之前,考慮如下約束條件[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) 教室容量須大于班級學生人數,即：

rnum≥cnum

(4)

rnum表示教室容量,cnum表示班級學生數量。

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

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

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

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

2 編碼方案

2.1 編碼

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

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

圖1 基因編碼圖

2.2 適應度評價函數

在遺傳算法中,適應度評價函數是衡量一個個體好壞程度的重要標準。本文將從3個方面對排課問題定義評價函數。

2.2.1 課程間隔

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

(5)

(6)

(7)

(8)

2.2.2 教室間隔

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

(9)

(10)

(11)

2.2.3 教師要求

課程安排的時間和地點應盡可能滿足教師的要求,如果上課時間和地點與教師的個人安排有沖突,會導致教學進程緩慢、教學效率降低。因此,滿足教師對上課時間和地點的要求是教學排課中一個重要的環節。教師合理度要求表達為

(12)

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

表1 教師-時間滿意表

表2 教師-教室滿意表

綜上所述,本文的適應度評價函數F定義如下：

(13)

其中ωi表示適應度函數評價值fi對應的權值,其中i=1,2,3,因此目標函數為f=max(F)。

3 蒙特卡洛遺傳算法

3.1 蒙特卡洛

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

首先,設定馬爾可夫鏈狀態轉移概率ρ與當前種群最優個體狀態值x0以及新生成個體狀態值x1有關,平穩分布π(x)設定狀態轉移次數的閾值為n1。

然后,在每一次遺傳算法排課的迭代過程中,進行n1次轉移：

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

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

3.2 種群初始化

傳統遺傳算法在初始化種群過程中,通常采用隨機方案來生成種群。考慮排課的特殊性,本文在初始化過程中加入約束條件生成初始化種群。

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

3.3 選擇

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

(14)

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

3.4 交叉

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

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

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

圖2 交叉

3.5 變異

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

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

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

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

圖3 變異

4 仿真測試與分析

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

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

5 結語

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