基于遺傳算法的智能排課系統(tǒng)的設(shè)計

劉 莉,栗 超

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

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

1 問題分析

1.1 排課原則

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

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

1.2 排課約束條件

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

1)學(xué)生上課時間不發(fā)生沖突,即:

(1)

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

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

(2)

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

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

(3)

式中,H為教師人數(shù)的最大值。

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

2 模型構(gòu)建

2.1 課程編碼

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

圖1 課程編碼示意圖

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

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

(4)

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

(5)

智能排課模式適應(yīng)度函數(shù)f定義為:

(6)

式中:n為學(xué)生總數(shù);oi為第i個學(xué)生課程安排合理度。

2.3 選擇操作

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

圖2 輪盤賭法選擇示意

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

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

選擇操作方法為交叉變異產(chǎn)生新個體優(yōu),則接受產(chǎn)生的新個體;交叉變異產(chǎn)生的個體劣,以概率σ接受新個體,即蒙特卡洛概率接受法,概率σ稱為接受概率,其數(shù)學(xué)表達(dá)式為:

(7)

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

2.4 交叉變異

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

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

(8)

(9)

式中:Pc為交叉概率;Pm為變異概率;k1和k2為區(qū)間(0,1)上的隨機數(shù);fl為交叉?zhèn)€體適應(yīng)度值;favg為交叉?zhèn)€體適應(yīng)度平均值;f1為變異個體適應(yīng)度值;Navg為變異個體適應(yīng)度平均值。

2.5 智能排課系統(tǒng)

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

3 仿真分析

3.1 數(shù)據(jù)來源

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

3.2 仿真結(jié)果分析

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

圖3 智能排課系統(tǒng)流程

表1 算法參數(shù)

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

圖4 迭代次數(shù)和平均適應(yīng)度值關(guān)系

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

4 結(jié)論

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