基于改進(jìn)GWO算法的高校教學(xué)管理系統(tǒng)排課算法研究

田方

摘要：高校辦學(xué)規(guī)模的擴(kuò)大使得高校排課面臨巨大挑戰(zhàn)，對(duì)此采用改進(jìn)的GWO算法對(duì)高校教學(xué)管理系統(tǒng)排課算法進(jìn)行了研究。分析了GWO算法的原理和流程，在此基礎(chǔ)上運(yùn)用混沌理論，采用Chebyshev混沌序列生成GWO算法的初始化灰狼種群，同時(shí)采用萊維飛行來(lái)改進(jìn)灰狼位置的更新公式，得到了改進(jìn)的GWO算法。通過(guò)對(duì)A大學(xué)排課的優(yōu)化仿真試驗(yàn)，驗(yàn)證了改進(jìn)的GWO算法避免了算法陷入局部最優(yōu)，達(dá)到了良好的排課優(yōu)化效果。該研究對(duì)排課系統(tǒng)的優(yōu)化具有一定的參考價(jià)值。

關(guān)鍵詞：排課問(wèn)題;改進(jìn)GWO算法;Chebyshev混沌序列

中圖分類號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：A

ResearchontheCourseArrangementAlgorithmofUniversityTeaching

ManagementSystemBasedonImprovedGWOAlgorithm

TIANFang

（SchoolofContinuingEducation，ShanxiUniversityofTraditionalChineseMedicine，Xianyang712000，China）

Abstract：Theexpansionofthescaleofauniversitymakesthecoursearrangementoftheuniversityfaceagreatchallenge.Inthispaper，theimprovedGWOalgorithmisusedtostudythecoursearrangementalgorithmofuniversityteachingmanagementsystem.TheprincipleandflowofGWOalgorithmareanalyzed.Basedonthechaostheory，ChebyshevchaoticsequenceisusedtogeneratetheinitialgraywolfpopulationofGWOalgorithm.Atthesametime，Levyflightisusedtoimprovetheupdateformulaofgraywolfposition，andtheimprovedGWOalgorithmisobtained.Throughthesimulationexperimentofauniversitycoursearrangement，itisverifiedthattheimprovedGWOalgorithmcanavoidthealgorithmfallingintothelocaloptimumandachieveagoodeffectofcoursearrangementoptimization.Theresearchofthispaperhascertainreferencevaluetotheoptimizationofthecoursearrangementsystem.

Keywords：classschedulingproblem;improvedGWOalgorithm;Chebyshevchaoticsequence

0引言

國(guó)民經(jīng)濟(jì)的快速發(fā)展促進(jìn)了我國(guó)高等教育的快速發(fā)展，各個(gè)高等院校紛紛擴(kuò)招，在校大學(xué)生的數(shù)量快速增加，同時(shí)高校辦學(xué)規(guī)模的不斷擴(kuò)大，其所開設(shè)的專業(yè)課程數(shù)目也在不斷地增多。高校學(xué)生人數(shù)和開設(shè)專業(yè)課程數(shù)目的增加使得高校教務(wù)管理面臨一個(gè)巨大的難題，即排課。采用手工排課的方式去排課要耗費(fèi)大量的人力資源，且容易出現(xiàn)錯(cuò)誤，特別是在當(dāng)前高校學(xué)生人數(shù)和課程持續(xù)增多的環(huán)境下，這種排課的方式變得不現(xiàn)實(shí)。為了解決教學(xué)資源沖突，提高排課的效率，目前各大高校都采用了排課軟件。高校教務(wù)部門采用排課軟件可以解決一般的排課問(wèn)題，但是依舊無(wú)法避免師生沖突、資源與課程沖突，因此在排課之后還需要手工調(diào)整，浪費(fèi)了大量人力資源[1]。采用遺傳算法、灰狼優(yōu)化算法（GWO）能夠解決高校教學(xué)管理系統(tǒng)排課問(wèn)題，但是也存在一些缺陷?；诖?，本文對(duì)GWO算法進(jìn)行改進(jìn)，同時(shí)將改進(jìn)的GWO算法應(yīng)用于高校教學(xué)管理系統(tǒng)排課中去，期待對(duì)解決比較復(fù)雜的排課問(wèn)題提供參考。

1GWO算法

1.1GWO算法原理

2014年，Mirjalili等人受到受到大自然灰狼捕食獵物活動(dòng)啟發(fā)提出了灰狼優(yōu)化算法，即GWO算法。相對(duì)于其它的智能優(yōu)化算法，GWO算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)設(shè)置少等優(yōu)點(diǎn)，被廣泛應(yīng)用于參數(shù)優(yōu)化、車間調(diào)度、系統(tǒng)排課等問(wèn)題中?；依鞘堑湫偷娜馐硠?dòng)物，主要是群居生活。在一個(gè)狼群中包含有10只左右的灰狼，而最厲害的狼僅有一只。在一個(gè)小型的狼群中，最厲害的那只大灰狼負(fù)責(zé)整個(gè)狼群中的各項(xiàng)事務(wù)，處于核心地位。對(duì)于灰狼群[2]而言，其遵循社會(huì)支配等級(jí)關(guān)系，可以分為四層，如圖1所示。

α處于社會(huì)等級(jí)的第一層，為頭狼，在整個(gè)灰狼群中處于領(lǐng)袖地位，其對(duì)整個(gè)灰狼群的捕食、棲息等活動(dòng)做出決策，是管理層。也許在整個(gè)灰狼群中頭狼捕食最厲害的，但是頭狼的管理能力一定是最厲害的，其它的狼都必須服從頭狼的管理，按照頭狼的命令開展各種活動(dòng)。

β處于社會(huì)等級(jí)的第二層，其協(xié)助頭狼α做決策和處理灰狼群中的各種活動(dòng)。在灰狼群中，如果頭狼不在、生病、死亡，那么β就轉(zhuǎn)變?yōu)轭^狼，承擔(dān)頭狼的各種任務(wù)。對(duì)于β灰狼而言，其一方面要向灰狼群中的其它狼下達(dá)頭狼的命令，同時(shí)還要將其它狼執(zhí)行頭狼α的命令情況反饋給頭狼。

δ處于社會(huì)等級(jí)的第三層，其開展各種活動(dòng)必須聽從于α狼和β狼，同時(shí)指揮底層的狼。對(duì)于δ狼而言，其往往是從事放哨、偵查、狩獵、護(hù)理等工作。對(duì)于α狼和β狼而言，當(dāng)其年紀(jì)比較大時(shí)，也會(huì)轉(zhuǎn)變?yōu)棣睦恰?/p>

ω處于社會(huì)等級(jí)的第四層，其各項(xiàng)工作的開展必須服從于α狼、β狼和δ狼。從表面上來(lái)看，ω狼在整個(gè)狼群中處于可有可無(wú)的地位。實(shí)際上，ω狼在整個(gè)狼群中的地位至關(guān)重要，由ω狼來(lái)負(fù)者整個(gè)狼群各個(gè)階層之間的平衡。如果在整個(gè)狼群中沒(méi)有ω狼的存在，那么就會(huì)出現(xiàn)自相殘殺的情況。

1.2GWO算法流程

采用GWO算法必須構(gòu)建灰狼群的社會(huì)等級(jí)層次模型。對(duì)灰狼群中的灰狼個(gè)體計(jì)算適應(yīng)度，依據(jù)適應(yīng)度的大小來(lái)選擇適應(yīng)度比較大的三只灰狼，

記為α狼、β狼和δ狼，其余的灰狼記為ω狼。大灰狼在大自然中搜索獵物時(shí)會(huì)采取逐步靠近再包圍獵物的方式，其數(shù)學(xué)模型如式（1）—式（4）。

D=C·xp（t）-x（t）（1）

x（t+1）=xp（t）-A·D（2）

A=2ar1-a（3）

C=2r2（4）

式中，D為最優(yōu)灰狼和候選灰狼之間的距離，A、C為協(xié)同系數(shù)向量，t為迭代次數(shù)，x為灰狼的位置向量，xp為獵物的位置向量，a在整個(gè)迭代過(guò)程中從2線性遞減到0，r1、r2為閉區(qū)間[0，1]上的隨機(jī)向量。

在自然界中，灰狼只有具有識(shí)別潛在獵物位置的能力，才能確保狼群的生存，整個(gè)灰狼群搜索獵物完全是在α狼、β狼和δ狼的命令下完成的。為了更好地對(duì)灰狼搜索獵物行為進(jìn)行模擬，在GWO算法的每次迭代中均保留當(dāng)前適應(yīng)度值最好的三只灰狼，結(jié)合α狼、β狼和δ狼的位置信息來(lái)更新ω狼的位置信息?；依侨旱尼鳙C行為數(shù)學(xué)模型如式（5）—式（7）

Dα=C1·xα-x

Dβ=C2·xβ-x

Dδ=C3·xδ-x（5）

x1=xα-A1Dα

x2=xβ-A2Dβ

x3=xδ-A3Dδ（6）

x（t+1）=x1+x2+x33（7）

式中，Dα、Dβ、Dδ分別為候選灰狼和最優(yōu)灰狼α、β、δ之間的距離，A1、A2、A3、C1、C2、C3為協(xié)同系數(shù)向量，xα、xβ、xδ分別為最優(yōu)灰狼α、β、δ的位置向量，x為灰狼的位置向量。

對(duì)于GWO優(yōu)化算法而言，其首先是設(shè)置最大迭代次數(shù)tmax，灰狼種群的規(guī)模N，結(jié)合隨機(jī)參數(shù)生成初始化灰狼種群的位置，并計(jì)算灰狼個(gè)體的適應(yīng)度，按照適應(yīng)度值的大小來(lái)找出在灰狼種群中最優(yōu)的三種灰狼，分別記為α狼、β狼和δ狼，保存α狼、β狼和δ狼的位置xα、xβ、xδ。其次是采用公式（5）～（7）對(duì)ω狼的位置進(jìn)行更新，對(duì)更新后的位置采用公式（3）、（4）更新參數(shù)，并計(jì)算所有個(gè)體的適應(yīng)度值，將其和上一次迭代的適應(yīng)度值進(jìn)行比較，選擇適應(yīng)度值最大的三只灰狼，繼續(xù)尋找獵物。最后是判斷迭代是否達(dá)到了最大值，如果達(dá)到了最大值，那么停止迭代，輸出頭狼xα的位置作為最優(yōu)值。GWO算法流程[3]，如圖2所示。

2改進(jìn)的GWO算法

2.1混沌初始化種群

傳統(tǒng)的GWO算法產(chǎn)生初始的灰狼種群是隨機(jī)的，這使得灰狼種群的多樣性受到影響，進(jìn)而影響到GWO算法的迭代效率。混沌是自然科學(xué)中行為不可預(yù)測(cè)的確定性系統(tǒng)，可以借助混沌來(lái)對(duì)GWO算法的灰狼種群進(jìn)行初始化，這樣就可以在很大程度上提高初始灰狼種群個(gè)體的多樣性，使得GWO算法的計(jì)算效率得到大大提升。在數(shù)學(xué)中，各種混沌行為往往借助于迭代函數(shù)來(lái)檢測(cè)。對(duì)于不同的初始值，混沌函數(shù)所產(chǎn)生的序列不同，但是比較有趣的事情是伴隨著迭代次數(shù)的不斷增大，混沌函數(shù)所產(chǎn)生的序列極限值是一樣的。在GWO群智能算法中，各種隨機(jī)性對(duì)搜索產(chǎn)生巨大的影響?；煦缧蛄心壳氨粡V泛應(yīng)用于各種群智能算法中，同時(shí)取得了良好的效果。針對(duì)GWO算法的改進(jìn)，采用Chebyshev混沌序列來(lái)生成GWO算法的初始化灰狼種群，使得種群個(gè)體多樣性增加，改進(jìn)算法的計(jì)算效率大大提升。Chebyshev的映射方程如

式（8）。

xk+1=cos（kcos-1（xk））（8）

2.2萊維飛行改進(jìn)位置更新

采用傳統(tǒng)的GWO算法可能存在優(yōu)化陷入局部最優(yōu)的情況，在對(duì)GWO算法進(jìn)行改進(jìn)時(shí)采用萊維飛行對(duì)GWO算法種群位置更新的公式進(jìn)行改進(jìn)，從而在一定程度上擴(kuò)大GWO算法的搜索范圍[4]。采用萊維飛行改進(jìn)GWO算法位置更新公式如式（9）

xα（t+1）=xα（t）+alpha⊕Levy（β）

xβ（t+1）=xβ（t）+alpha⊕Levy（β）

xδ（t+1）=xδ（t）+alpha⊕Levy（β）（9）

式中，alpha為步長(zhǎng)控制量，一般取值為0.01;⊕為點(diǎn)對(duì)點(diǎn)乘法運(yùn)算規(guī)則;Levy（β）為GWO算法的隨機(jī)搜索路徑

如式（10）。

Levy（β）=uv1/β·（x（t）-xm（t））·randn（10）

式中，β的取值范圍為[1，3]，v服從正態(tài)分布u∶N（0，1），x（t）為灰狼群t次迭代更新以后的位置，

xm（t）為灰狼群t次迭代時(shí)α狼、β狼和δ狼的位置，randn為服從正態(tài)分布的隨機(jī)數(shù)，u服從正態(tài)分布

N（0，δ2），其中δ如式（11）。

δ=Γ（1+β）·sinπ·β2

Γ1+β2·β·2（β-1）/2

1/β（11）

通過(guò)對(duì)GWO算法位置更新的公式進(jìn)行改進(jìn)使得搜索的范圍擴(kuò)大，避免在迭代的過(guò)程中陷入局部最優(yōu)。采用改進(jìn)的GWO算法可以在很大程度上使得整個(gè)算法搜索的靈活性增強(qiáng)，提升了算法的魯棒性。

3改進(jìn)GWO算法在高校排課中的應(yīng)用

3.1排課問(wèn)題概述

高校的快速擴(kuò)招使得高校的辦學(xué)規(guī)?？焖贁U(kuò)大，保證高校教學(xué)質(zhì)量必須確保各種軟硬件設(shè)施的同步發(fā)展。高校學(xué)生和高校開設(shè)專業(yè)的增多使得排課問(wèn)題變得十分復(fù)雜，高校排課必須確保班級(jí)、教師、課程、教師安排等不發(fā)生沖突。排課問(wèn)題必須滿足以下五個(gè)硬約束[5]：

（1）在同一個(gè)時(shí)間段內(nèi)不能為同一個(gè)教師安排兩門課程的教學(xué)任務(wù)，否則就會(huì)出現(xiàn)教師上課時(shí)間的沖突，出現(xiàn)教學(xué)事故;

（2）在同一個(gè)時(shí)間段內(nèi)不能為同一個(gè)學(xué)生安排兩門課程的學(xué)習(xí)任務(wù)，否則就會(huì)出現(xiàn)學(xué)生上課時(shí)間的沖突，學(xué)生不知道應(yīng)該去上什么課程，出現(xiàn)嚴(yán)重教學(xué)事故;

（3）在同一個(gè)時(shí)間內(nèi)的同一個(gè)教室不能安排兩門課程，否則就會(huì)在該教室出現(xiàn)多個(gè)班級(jí)和多個(gè)教室來(lái)同一個(gè)教室上課，出現(xiàn)教學(xué)混亂，影響正常教學(xué)工作的開展;

（4）安排課程的上課時(shí)間不能夠少于課程規(guī)定的時(shí)間，如果安排課程的上課時(shí)間少于規(guī)定課程規(guī)定的時(shí)間，那么就有可能出現(xiàn)這門課程還沒(méi)有下課，而下一門課程已經(jīng)上課，造成教學(xué)沖突，影響正常教學(xué);

（5）教室的座位數(shù)不能夠少于上課的學(xué)生數(shù)，如果教室的座位數(shù)不足，那么學(xué)生就無(wú)法正常上課。

采用GWO算法對(duì)高校教學(xué)管理系統(tǒng)進(jìn)行排課，構(gòu)造編碼是算法設(shè)計(jì)的關(guān)鍵所在。對(duì)于高校排課問(wèn)題而言，其涉及五個(gè)方面的因素，分別為教師、教室、班級(jí)、課程和時(shí)間。高校教學(xué)管理系統(tǒng)排課的基因構(gòu)造，如圖3所示。

排課基因構(gòu)造完成之后，可以采用改進(jìn)的GWO算法將適應(yīng)度高的保留下來(lái)，反復(fù)循環(huán)，直到算法終止，找到問(wèn)題的最優(yōu)解。

3.2GWO算法適應(yīng)度函數(shù)

高校的教學(xué)管理部門在排課的時(shí)候必須注意以上五個(gè)硬性的約束，但是在滿足影響約束的情況下還有一些軟約束。例如盡量提高教室的利用率，避免部分教室在一個(gè)學(xué)期沒(méi)有安排一門課程。采用加權(quán)的方式來(lái)設(shè)計(jì)GWO算法的適應(yīng)度函數(shù)，使得其排課達(dá)到最優(yōu)化。本文主要考慮兩個(gè)方面的軟約束[6]：

（1）教室的利用率

高校具有許多的教室，在每一個(gè)教室都安裝有教學(xué)所需的各種設(shè)備。高校的教務(wù)系統(tǒng)在排課時(shí)必須考慮教室的利用率，避免有的教室每節(jié)課都在使用，而有的教室經(jīng)常不使用。采用如下公式來(lái)評(píng)價(jià)教室的利用率，如式（12）。

s1=∑ni=1sn（i）·ch（i）cr（i）

∑ni=1ch（i）（12）

式中，n為課元個(gè)數(shù)，sn（i）為第i個(gè)課元所包含的學(xué)生個(gè)數(shù)，ch（i）為第i個(gè)課元所包含的學(xué)時(shí)數(shù)，cr（i）為第i個(gè)課元所用教室的教室容量大小，s1為教室的利用率。

（2）上課時(shí)間均勻安排

考慮到學(xué)生學(xué)習(xí)的實(shí)際情況，為了提高學(xué)生的學(xué)習(xí)效率和學(xué)習(xí)質(zhì)量，高校教務(wù)系統(tǒng)在排課時(shí)必須考慮學(xué)生上課時(shí)間的均勻安排，使得學(xué)生在上完一門課程之后可以得到休息和完成相應(yīng)的作業(yè)，然后再去上第二門課程。對(duì)一個(gè)課元而言，其時(shí)間分布均勻度T（i），如式（13）。

T（i）=

0ch（i）=1或者ch（i）>3

∑chj=1（Day（i，j+1）-Day（i，j））其它（13）

式中，Day（i，j）為第i個(gè)課元的第j個(gè)上課時(shí)間輸入第幾個(gè)上課日。

對(duì)排課方案進(jìn)行上課時(shí)間均勻安排評(píng)價(jià)的計(jì)算公式，如式（14）。

s2=∑ni=1T（i）（14）

對(duì)GWO算法所采取的個(gè)體適應(yīng)度計(jì)算公式是對(duì)教室利用率s1和上課時(shí)間均勻安排評(píng)價(jià)s2進(jìn)行加權(quán)得到，

如式（15）。

fitness（s）=a·s1+b·s2（15）

式中，fitness（s）為個(gè)體適應(yīng)度，a、b為待定系數(shù)。

3.3試驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證改進(jìn)GWO算法的有效性，以A大學(xué)為例，采用傳統(tǒng)的GWO算法和改進(jìn)的GWO算法進(jìn)行仿真試驗(yàn)，仿真試驗(yàn)測(cè)試的相關(guān)數(shù)據(jù)，如表1所示。

分別采用GWO算法和改進(jìn)的GWO算法對(duì)其進(jìn)行排課優(yōu)化，不同迭代次數(shù)下適應(yīng)度的比較，如圖4所示。其中待定系數(shù)

a、b均為0.5。

由圖4可見，改進(jìn)后的GWO算法最優(yōu)適應(yīng)度增長(zhǎng)速度明顯大于傳統(tǒng)的GWO算法，在迭代120次左右，傳統(tǒng)的GWO算法陷入局部最優(yōu)狀態(tài)，而改進(jìn)的GWO算法并沒(méi)有陷入局部最優(yōu)的狀態(tài)，而是伴隨著迭代次數(shù)的增加呈現(xiàn)出良好的增加趨勢(shì)。由此可見，采用改進(jìn)的GWO算法可以更好地對(duì)高校進(jìn)行排課，使得排課達(dá)到良好的效果，為提升高校的教學(xué)質(zhì)量提供參考。

4總結(jié)

排課問(wèn)題關(guān)系到高校的教學(xué)質(zhì)量，在當(dāng)前高校辦學(xué)規(guī)律不斷擴(kuò)大的大環(huán)境下，對(duì)排課的優(yōu)化至關(guān)重要。本文對(duì)GWO優(yōu)化算法進(jìn)行了改進(jìn)，采用Chebyshev混沌序列來(lái)生成GWO算法的初始化灰狼種群，同時(shí)采用萊維飛行來(lái)改進(jìn)灰狼位置的更新。通過(guò)將GWO算法和改進(jìn)的GWO算法應(yīng)用于排課系統(tǒng)中驗(yàn)證了改進(jìn)的GWO算法避免了陷入局部最優(yōu)，使得排課達(dá)到了良好的效果。本論文的研究對(duì)于高校排課管理系統(tǒng)的優(yōu)化具有一定的參考價(jià)值。

參考文獻(xiàn)

[1]范明杰，懷麗波.基于改進(jìn)遺傳算法的排課問(wèn)題研究[J].計(jì)算技術(shù)與自動(dòng)化，2018，37（1）：8994.

[2]韓麟，陳宏偉.基于Spark的灰狼優(yōu)化算法研究[J].湖北工業(yè)大學(xué)學(xué)報(bào)，2019，34（5）：6063.

[3]王夢(mèng)娜.灰狼優(yōu)化算法的改進(jìn)及其在參數(shù)估計(jì)中的應(yīng)用[D].西安：西安理工大學(xué)，2019.

[4]方曉玉，李曉斌，郭震.一種改進(jìn)的混合灰狼優(yōu)化SVM預(yù)測(cè)算法及應(yīng)用[J].激光與光電子學(xué)進(jìn)展，2012，12（6）：341347.

[5]王璐，楊亞偉.一種改進(jìn)的遺傳算法在年度排課問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，2016，44（8）：16191624.

[6]姜婧，白似雪.遺傳算法的改進(jìn)及其在排課問(wèn)題中的應(yīng)用[J].南昌大學(xué)學(xué)報(bào)（理科版），2018，42（4）：388392.

（收稿日期：2020.03.11）