基于灰狼算法的高校實驗課網(wǎng)絡(luò)排課問題研究

阮德致, 梁榮, 遲軍, 季英萍

(寧波工程學(xué)院 杭州灣汽車學(xué)院， 浙江 寧波 315000)

0 引言

隨著我國高等教育規(guī)模的擴大和在校人數(shù)的增加，排課的工作量和難度不斷增加，因此研究高校實驗課網(wǎng)絡(luò)排課系統(tǒng)算法具有重要的理論價值和實際意義[1]。傳統(tǒng)的人工排課算法具有任務(wù)量大、費時和效率低下的缺點，隨著人工智能算法、運籌學(xué)和計算機科學(xué)的發(fā)展，很多群智能算法被應(yīng)用于課程編排領(lǐng)域，比如粒子群算法和遺傳算法[2、3]，為課程編排提供了新的方法和途徑。然而，粒子群算法不能單獨解決課程排課約束問題，遺傳算法雖然可以解決約束問題，但存在計算時間過長的缺點。

灰狼優(yōu)化算法(Grey Wolf Optimization Algorithm，GWO)是模仿灰狼等級劃分和灰狼捕食行為而提出的群智能搜索算法[4]。該算法具有控制參數(shù)少、收斂速度快和計算簡單等優(yōu)點，已在機器學(xué)習(xí)、函數(shù)尋優(yōu)、數(shù)據(jù)挖掘、電力調(diào)度、控制器設(shè)計調(diào)優(yōu)等方面得到廣泛應(yīng)用[5-6]。為提高高校實驗課網(wǎng)絡(luò)排課的效率，節(jié)約排課時間和工作量，提出一種基于GWO的高校實驗課網(wǎng)絡(luò)排課優(yōu)化算法。

1 排課問題數(shù)學(xué)模型

1.1 排課問題數(shù)學(xué)描述

教師T={t1,t2,…,tn}，ti具有教師工號、姓名和職稱等屬性，其中教師號是唯一標(biāo)志。課程C={c1,c2,…,cn}，ci具有課程號、總課時量、周課時量以及周數(shù)等屬性，其中課程號是唯一標(biāo)志。班級B={b1,b2,…,bn}，bi具有班級號和班級人數(shù)等屬性，其中班級號是唯一標(biāo)志。課堂CU={cu1,cu2,…,cun}，cui具有課堂號、班級號和人數(shù)等屬性，其中課堂號是唯一標(biāo)志。排課問題可以簡化為作業(yè)調(diào)度問題[7]：若教室個數(shù)為m、上課周數(shù)為w、某天上課次數(shù)為j，那么有m×w×j個可以分配的教室時間段，如何分配n個教師號課堂號ticui使得所有排課時間最短。定義ti為安排第i個教師號課堂號ticui所耗費的最短時間；Ti為安排第i個教師號課堂號ticui所等待的時間，包括時間沖突檢測、課堂沖突檢測、班級沖突檢測和教師沖突檢測。

1.2 排課問題數(shù)學(xué)模型

排課目標(biāo)函數(shù)為式(1)。

(1)

式中，kmαmtj+Tj>0。目標(biāo)函數(shù)minT表示某一個教師號課堂號分配到第j個教室時間段內(nèi)所耗費的時間最少或最短。

約束條件為式(2)、式(3)。

(2)

其中：

(3)

式(2)中，ti∩tj=?，?WiJi≠WjJj用來約束同一周、同一節(jié)次的教師不能是同一個教師；cui∩cuj=?，?WiJi≠WjJj用來約束在同一時間、不同課堂號不能包括同一個自然班。

2 GWO算法

GWO算法中，灰狼個體分為α、β、δ和ω。α負(fù)責(zé)狼群的決策與管理；β和δ為適應(yīng)度次于α的灰狼個體；ω為其它灰狼個體。GWO算法主要包括包圍、捕獵和攻擊三種行為[8]：

2.1 包圍行為

首先灰狼包圍獵物，數(shù)學(xué)模型如式(4)和式(5)。

(4)

(5)

2.2 捕獵行為

包圍獵物之后，狼群將捕獵獵物。假定α、β、δ分別為全局最優(yōu)解、全局第二解以及全局第三解，對α、β、δ重新定位,如式(6)—式(8)。

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2.3 攻擊行為

狼群捕食的最后階段就是攻擊捕獲獵物，攻擊過程主要通過調(diào)節(jié)參數(shù)a實現(xiàn)。當(dāng)|A|≤1時，狼群將接近獵物(X*,Y*)集中攻擊獵物；當(dāng)|A|>1時，狼群將遠(yuǎn)離獵物。

3 基于GWO的高校實驗課網(wǎng)絡(luò)排課系統(tǒng)優(yōu)化

基于GWO的高校實驗課網(wǎng)絡(luò)排課系統(tǒng)優(yōu)化流程如圖1所示。

圖1 基于GWO的高校實驗課網(wǎng)絡(luò)排課系統(tǒng)優(yōu)化流程圖

基于GWO的高校實驗課網(wǎng)絡(luò)排課系統(tǒng)優(yōu)化算法步驟可以詳細(xì)描述為：

步驟1：讀取課程信息、時間信息和教室信息以及相關(guān)約束信息；

步驟2：GWO算法初始化：設(shè)定灰狼種群數(shù)量N、最大迭代次數(shù)Maxgen和參數(shù)維度D、并初始化灰狼種群位置X=(X1,X2,…,XN)和灰狼個體的位置Xi=(xi1,xi2,…,xiD)，其中i∈{1,2,3,…,N}；

步驟3：計算不同灰狼個體的適應(yīng)度值fi并排序，將適應(yīng)度值前三位的灰狼個體的位置分別記作為Xα、Xβ和Xδ。

步驟4：按式(9)分別計算各ω狼與α、β、δ狼之間的近似距離，并按式(10)和式(11)更新α、β、δ狼的位置和獵物的位置；

步驟5：更新參數(shù)a、A和C；

步驟6：判斷算法終止條件：若達(dá)到最大迭代次數(shù)Maxgen，則輸出最優(yōu)解，即最優(yōu)排課信息；否則，返回步驟3。

4 仿真試驗與結(jié)果分析

為驗證GWO進(jìn)行高校實驗課網(wǎng)絡(luò)排課系統(tǒng)優(yōu)化的可靠性和有效性，選擇Matlab2015(a)為仿真軟件平臺，PC機系統(tǒng)為Windows7、CPU主頻2.2GHz、中央處理器為Intel core i5以及內(nèi)存為4G。課程信息、時間信息和教室信息分別如表1—表3所示。

表1 課程信息

將GWO和PSO、GA進(jìn)行對比[9-12]，不同算法參數(shù)設(shè)置如下：(1)GWO參數(shù)：種群規(guī)模N=50、最大迭代次數(shù)Maxgen=500。(2)粒子群算法(particle swarm optimization algorithm，PSO)：種群規(guī)模N=50、最大迭代次數(shù)Maxgen=500、學(xué)習(xí)因子c1=c2=2、慣性權(quán)重w=0.2。(3)遺傳算法(genetic algorithm，GA)：種群大小N=50、最大迭代次數(shù)Maxgen=500交叉概率Pc=0.7和變異概率Pm=0.1，對比結(jié)果如圖2—圖4和表4所示。

表2 時間段信息

表3 教室信息

表4 GWO、PSO和GA對比結(jié)果

由表4和圖2—圖4可知，與PSO和GA相比，GWO算法進(jìn)行課程排課優(yōu)化的分配時間minT為337.675 5 s，優(yōu)于PSO的565.800 1 s和GA的603.003 1 s，從而驗證了GWO進(jìn)行高校實驗課網(wǎng)絡(luò)排課的有效性和可靠性。

圖2 GWO尋優(yōu)收斂圖

圖3 PSO尋優(yōu)收斂圖

圖4 GA尋優(yōu)收斂圖

5 總結(jié)

為解決高校實驗課網(wǎng)絡(luò)排課問題，將灰狼優(yōu)化算法應(yīng)用于網(wǎng)絡(luò)排課問題優(yōu)化求解，有效解決了網(wǎng)絡(luò)排課問題，提高了網(wǎng)絡(luò)排課的效率，降低了排課時間和減少了排課工作量。然而，本研究只研究了簡單約束條件下的網(wǎng)絡(luò)排課數(shù)學(xué)模型，未來將研究多沖突、多約束的網(wǎng)絡(luò)排課問題，從而提高模型的適用性和應(yīng)用性。