基于改進GWO算法的高校教學管理系統排課算法研究

田方

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

關鍵詞：排課問題;改進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引言

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

1GWO算法

1.1GWO算法原理

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

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

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

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

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

1.2GWO算法流程

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

記為α狼、β狼和δ狼，其余的灰狼記為ω狼。大灰狼在大自然中搜索獵物時會采取逐步靠近再包圍獵物的方式，其數學模型如式（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為最優灰狼和候選灰狼之間的距離，A、C為協同系數向量，t為迭代次數，x為灰狼的位置向量，xp為獵物的位置向量，a在整個迭代過程中從2線性遞減到0，r1、r2為閉區間[0，1]上的隨機向量。

在自然界中，灰狼只有具有識別潛在獵物位置的能力，才能確保狼群的生存，整個灰狼群搜索獵物完全是在α狼、β狼和δ狼的命令下完成的。為了更好地對灰狼搜索獵物行為進行模擬，在GWO算法的每次迭代中均保留當前適應度值最好的三只灰狼，結合α狼、β狼和δ狼的位置信息來更新ω狼的位置信息。灰狼群的狩獵行為數學模型如式（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δ分別為候選灰狼和最優灰狼α、β、δ之間的距離，A1、A2、A3、C1、C2、C3為協同系數向量，xα、xβ、xδ分別為最優灰狼α、β、δ的位置向量，x為灰狼的位置向量。

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

2改進的GWO算法

2.1混沌初始化種群

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

式（8）。

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

2.2萊維飛行改進位置更新

采用傳統的GWO算法可能存在優化陷入局部最優的情況，在對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;⊕為點對點乘法運算規則;Levy（β）為GWO算法的隨機搜索路徑

如式（10）。

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

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

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

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

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

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

1/β（11）

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

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

3.1排課問題概述

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

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

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

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

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

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

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

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

3.2GWO算法適應度函數

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

（1）教室的利用率

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

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

∑ni=1ch（i）（12）

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

（2）上課時間均勻安排

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

3.3試驗結果對比

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

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

a、b均為0.5。

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

4總結

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

參考文獻

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

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

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

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

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

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

（收稿日期：2020.03.11）