基于遺傳算法的智能排課系統的設計

劉 莉,栗 超

(1.煙臺職業學院 交通工程系,山東 煙臺 264670;2.山東理工大學 計算機科學與技術學院,山東 淄博 255000)

高校課程多、學生多,排課是組合數學理論中所稱的非確定性多項式(Non-deterministic Polynomial,NP)問題,具有難解性、復雜性特點[1]?？茖W合理的課程安排不僅能夠提高教師和學生的滿意度,同時在提升高校辦學質量方面也發揮著極為重要的作用。智能化排課系統不僅能夠降低高校教務部門的工作量,還使得排課方案更加科學、合理。宗薇[2]構建了多約束條件下的排課數學模型,采用遺傳算法對可行排課方案進行優化,獲得最佳的排課方案,使得排課的成功率大大提升,避免了課程之間出現沖突。劉明[3]以“實驗室智能管理平臺”為基礎,采用遺傳算法開展智能實驗排課,智能優化算法在排課中的應用使得有限資源得到了科學合理利用,提高了教學資源的利用率以及師生的滿意度。王運成等[4]指出排課問題可以轉化為多約束、多目標優化問題,并采用二叉樹知識推理設計了可拓展智能排課系統,有效解決了動態大規模排課需求。盡管各種智能算法在排課中得到了廣泛應用,但是實際排課方案還存在較大優化空間。遺傳算法作為一種模擬生物進化過程的優化算法,在許多優化問題中具有突出的表現,但是存在受參數設置影響大、易陷入局部最優解的問題。本文構建智能排課的求解優化模型,同時對傳統遺傳算法進行改進,應用于所構建的優化模型中,得到智能化的排課結果。

1 問題分析

1.1 排課原則

不同專業學生既有相同的課程,也有大量不同的課程,排課是一個多對多的問題。只有堅持排課的基本原則,才能使學生和任課教師滿意,同時也能夠達到良好的優化效果,使有限的教育資源得到科學、合理地分配。課程排課應該堅持4個基本原則,即沒有時間沖突、滿足課程最佳上課時間、課程盡量均衡、保持合理間隔[5]。

沒有時間沖突是基本要求,同時也是硬性要求,即不能給同一個任課教師在同一個時間安排2門課程,也不能給同一名學生在同一個時間安排2門課程。不同性質的課程有其最佳的上課時間,如英語課安排在上午1～2節相對比較合理,這樣能夠提高學生學習的積極性和主動性,教務部門在排課時應該給予考慮;數學課難度較大,對學生的腦力消耗較多,不宜讓學生連續上,應該保持合理的時間間隔。另外,為確保教師具有良好的講課狀態,排課盡量避免教師連續上4節課。這將直接影響教師的上課質量,進而影響課程的教學效果。在進行排課的過程中應該盡量做到難易結合,確保教師和學生的休息時間,不能過于集中。

1.2 排課約束條件

智能排課問題屬于優化調度問題,即學生、教師、課程等在滿足排課約束條件下被安排在特定的時間、特定的場所上課,使得資源得到充分利用,上課效果最佳。按照課程排課的原則,構造排課約束條件:

1)學生上課時間不發生沖突,即:

(1)

式中:L為課程類別數;H為課程教師人數;P為場地數;cn為學生;dm為時間;kl為課程;th為教師;rp為教學場所。

2)教師上課時間不發生沖突,即:

(2)

式中,N為班級所能容納的學生最大值。

3)上課場所不發生沖突,即:

(3)

式中,H為教師人數的最大值。

排課不沖突,即學生上課時間不沖突、教師上課時間不沖突、上課場所不沖突,這是智能排課的硬約束,滿足硬約束的排課方案是可行方案,但未必是最優排課方案[6]。為了使智能排課方案最優,課程的上課時間要盡量滿足學生和教師的要求,均勻分布,同時要對上課的場所充分利用,避免有的場所使用過于頻繁,而有的場所長期被閑置。

2 模型構建

2.1 課程編碼

不同的課程編碼方式導致智能排課的效率存在較大的差別。傳統遺傳算法采用二進制編碼方式,效率較低[7]。本文采用十進制對課程進行編碼,如圖1所示。

圖1 課程編碼示意圖

例如:編碼1120-1021-0403-1125-1024,其中1120為學生編號;0403為教師編號;1021為課程的類別編號;1125為上課時間;1024為上課的教室編號。

2.2 適應度函數

(4)

式中:gi(i=1,2)為上課時間;mi(i=1,2)為上課時間段;μ1和μ2為對應的權重系數;δfit為理想評價值。課程安排合理度o定義為:

(5)

智能排課模式適應度函數f定義為:

(6)

式中:n為學生總數;oi為第i個學生課程安排合理度。

2.3 選擇操作

選擇操作是遺傳算法中體現“適者生存”的關鍵一步,傳統遺傳算法采用輪盤賭法進行選擇操作,即將個體輪盤劃分為不同比例的區域,區域的大小由個體的適應度來確定[8]。個體適應度值越大,在輪盤中所占的比例越高,生存的概率越大,進入下一代群體的概率也越大,具體如圖2所示。

圖2 輪盤賭法選擇示意

由于輪盤賭法只考慮舊種群個體,導致種群個體的多樣性減少。為增加種群個體的多樣性,采用蒙特卡洛概率接受法進行選擇操作。蒙特卡洛采樣過程為[9]:

假設馬爾科夫鏈的狀態轉移概率ρ和當前種群中的最優個體x0、新生個體x1有關,平穩分布π(x)狀態轉移次數閾值為n1,在每一次迭代過程中進行n1狀態轉移。從矩形分布U(0,1)中隨機采樣獲得u,如果u<ρ,那么接受最優個體x0、新生個體x1;如果u≥ρ,那么不接受狀態轉移。

選擇操作方法為交叉變異產生新個體優,則接受產生的新個體;交叉變異產生的個體劣,以概率σ接受新個體,即蒙特卡洛概率接受法,概率σ稱為接受概率,其數學表達式為:

(7)

式中:Ei(i=1,2)為個體適應度,1為舊個體,2為新個體;KT為常量。

2.4 交叉變異

交叉與變異操作直接影響遺傳算法的性能,通過個體的交叉組合來獲得優異個體,同時通過個體的變異操作來獲得新的優異個體。遺傳算法染色體交叉操作確保種群的多樣性,避免遺傳單一化,一般選擇交叉概率大于0.9。遺傳算法變異操作是自然界在物種選擇過程中出現的突發情況,變異使得種群的多樣性擴大,一般選擇變異概率小于0.1。

由于傳統遺傳算法交叉與變異概率是固定值,導致在進化的后期個體變得比較單一,缺乏多樣性,進而算法陷入局部最優的狀態。為避免這種情況的出現,采用自適應交叉與變異操作,即:

(8)

(9)

式中:Pc為交叉概率;Pm為變異概率;k1和k2為區間(0,1)上的隨機數;fl為交叉個體適應度值;favg為交叉個體適應度平均值;f1為變異個體適應度值;Navg為變異個體適應度平均值。

2.5 智能排課系統

基于遺傳算法的智能排課系統首先對排課問題初始化,產生遺傳算法的初始化種群,采用十進制對課程進行編碼,計算每一種排課方案的適應度值,并判斷當前排課方案是否為最優排課方案。如果是最優排課方案,那么直接輸出;如果不是最優排課方案,繼續迭代。計算新一代種群的個體適應度值,直到該方案為最優排課方案,輸出結果即為智能排課的結果?；谶z傳算法的智能排課系統流程如圖3所示。

3 仿真分析

3.1 數據來源

以浙江省某職業院校為例,大二年級學生數量為3 620人,教師人數為42人,涉及的教學任務共96個,其中專業基礎課共12門,專業選修課為20門,提供課程教學的場所共28個。

3.2 仿真結果分析

為了對比改進遺傳算法和傳統遺傳算法在智能排課方面的性能,分別采用傳統遺傳算法和改進遺傳算法進行排課分析,參數設置見表1。

圖3 智能排課系統流程

表1 算法參數

為了消除參數選擇過程中各種隨機因素的影響,采用傳統遺傳算法和改進遺傳算法進行6次仿真試驗,取6次仿真結果的平均值進行對比,其迭代次數和平均適應度值關系如圖4所示。

圖4 迭代次數和平均適應度值關系

由圖4可知,對遺傳算法進行改進后獲得最優排課方案所需要的迭代次數減少。將傳統遺傳算法得到的排課方案和改進遺傳算法得到的排課方案進行對比,結果表明改進遺傳算法得到的排課方案對教學資源的利用率更高。

4 結論

本文對傳統遺傳算法的選擇操作采用蒙特卡洛概率接受法改進,交叉和變異操作采用自適應概率改進,提出且構建了基于改進遺傳算法的智能排課模型,應用于浙江省某職業院校,與傳統遺傳算法排課模型進行對比。結果表明,基于改進遺傳算法的智能排課模型在解決排課問題上更具優勢,提高資源利用率。這對促進高校教學質量的提升具有一定的實際意義。