田方

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

關鍵詞：排課問題;改進GWO算法;Chebyshev混沌序列

中圖分類號：TP301.6

文獻標志碼：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引言

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

1GWO算法

1.1GWO算法原理

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

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

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

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

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

1.2GWO算法流程

采用GWO算法必須構建灰狼群的社會等級層次模型。對灰狼群中的灰狼個體計算適應度，依據(jù)適應度的大小來選擇適應度比較大的三只灰狼，

記為α狼、β狼和δ狼，其余的灰狼記為ω狼。大灰狼在大自然中搜索獵物時會采取逐步靠近再包圍獵物的方式，其數(shù)學模型如式（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在整個迭代過程中從2線性遞減到0，r1、r2為閉區(qū)間[0，1]上的隨機向量。

在自然界中，灰狼只有具有識別潛在獵物位置的能力，才能確保狼群的生存，整個灰狼群搜索獵物完全是在α狼、β狼和δ狼的命令下完成的。為了更好地對灰狼搜索獵物行為進行模擬，在GWO算法的每次迭代中均保留當前適應度值最好的三只灰狼，結合α狼、β狼和δ狼的位置信息來更新ω狼的位置信息?；依侨旱尼鳙C行為數(shù)學模型如式（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為灰狼的位置向量。

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

2改進的GWO算法

2.1混沌初始化種群

傳統(tǒng)的GWO算法產(chǎn)生初始的灰狼種群是隨機的，這使得灰狼種群的多樣性受到影響，進而影響到GWO算法的迭代效率?；煦缡亲匀豢茖W中行為不可預測的確定性系統(tǒng)，可以借助混沌來對GWO算法的灰狼種群進行初始化，這樣就可以在很大程度上提高初始灰狼種群個體的多樣性，使得GWO算法的計算效率得到大大提升。在數(shù)學中，各種混沌行為往往借助于迭代函數(shù)來檢測。對于不同的初始值，混沌函數(shù)所產(chǎn)生的序列不同，但是比較有趣的事情是伴隨著迭代次數(shù)的不斷增大，混沌函數(shù)所產(chǎn)生的序列極限值是一樣的。在GWO群智能算法中，各種隨機性對搜索產(chǎn)生巨大的影響。混沌序列目前被廣泛應用于各種群智能算法中，同時取得了良好的效果。針對GWO算法的改進，采用Chebyshev混沌序列來生成GWO算法的初始化灰狼種群，使得種群個體多樣性增加，改進算法的計算效率大大提升。Chebyshev的映射方程如

式（8）。

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

2.2萊維飛行改進位置更新

采用傳統(tǒng)的GWO算法可能存在優(yōu)化陷入局部最優(yōu)的情況，在對GWO算法進行改進時采用萊維飛行對GWO算法種群位置更新的公式進行改進，從而在一定程度上擴大GWO算法的搜索范圍[4]。采用萊維飛行改進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為步長控制量，一般取值為0.01;⊕為點對點乘法運算規(guī)則;Levy（β）為GWO算法的隨機搜索路徑

如式（10）。

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

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

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

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

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

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

1/β（11）

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

3改進GWO算法在高校排課中的應用

3.1排課問題概述

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

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

（2）在同一個時間段內不能為同一個學生安排兩門課程的學習任務，否則就會出現(xiàn)學生上課時間的沖突，學生不知道應該去上什么課程，出現(xiàn)嚴重教學事故;

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

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

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

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

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

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

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

（1）教室的利用率

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

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

∑ni=1ch（i）（12）

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

（2）上課時間均勻安排

考慮到學生學習的實際情況，為了提高學生的學習效率和學習質量，高校教務系統(tǒng)在排課時必須考慮學生上課時間的均勻安排，使得學生在上完一門課程之后可以得到休息和完成相應的作業(yè)，然后再去上第二門課程。對一個課元而言，其時間分布均勻度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個課元的第j個上課時間輸入第幾個上課日。

對排課方案進行上課時間均勻安排評價的計算公式，如式（14）。

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

對GWO算法所采取的個體適應度計算公式是對教室利用率s1和上課時間均勻安排評價s2進行加權得到，

如式（15）。

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

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

3.3試驗結果對比

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

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

a、b均為0.5。

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

4總結

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

參考文獻

[1]范明杰，懷麗波.基于改進遺傳算法的排課問題研究[J].計算技術與自動化，2018，37（1）：8994.

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

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

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

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

[6]姜婧，白似雪.遺傳算法的改進及其在排課問題中的應用[J].南昌大學學報（理科版），2018，42（4）：388392.

（收稿日期：2020.03.11）