基于改進粒子群算法的高校排課問題優(yōu)化

羅義強 陳智斌(昆明理工大學理學院 云南 昆明 650500)

0 引 言

高校課程編排是一項分配時間和空間給課程同時滿足一定約束的活動。很多教育機構(gòu)的課程編排系統(tǒng)沒有完全自動化，需要一定的人工輔助。主要是因為課程編排的組合性和動態(tài)變化性。課程編排是計算機科學(CS)、運籌學(OR)、人工智能(AI)等領(lǐng)域的一個比較重要和帶有挑戰(zhàn)性問題。課程編排可以建模化為約束滿足問題(CSP)對待。約束滿足問題是組合優(yōu)化問題并且被證明是NP-complete的[1]。搜索空間龐大并隨變量指數(shù)級增長使得大多數(shù)NP-complete問題難以有效和優(yōu)化地求解。

高校課程編排被大量的學者進行了廣泛的研討。各種各樣的方法被提出去求解高校課程編排問題。這些方法包括：圖著色[2]，將高校課程編排問題轉(zhuǎn)化為一個圖，頂點代表課程，邊代表約束。顏色的數(shù)目相當于可行的時間檔。圖著色法分配有限的顏色給頂點，沒有被一條邊聯(lián)結(jié)的相鄰兩個頂點同一種顏色。遺傳算法(GA)[3]，以基因編碼課程編排限制，以懲罰函數(shù)評估課程滿意度。線性規(guī)劃[4]、模擬淬火算法(SA)[5]、禁忌搜索算法(TS)[6]等。這些算法的不足之處是難以處理課程編排過程的約束，只能產(chǎn)生可行解，結(jié)果令人難以滿意。

一些研究表明混合算法在解決高校課程編排問題顯示出有前景的結(jié)果。整合局部搜索算法(LS)到粒子群算法(PSO)中，構(gòu)建了高校課程編排的最優(yōu)解[7]。約束傳播與遺傳算法相融合，得到了高校課程編排的近似最優(yōu)解。遺傳算法的不足之處是計算耗時長。粒子群優(yōu)化算法與遺傳算法相比，收斂速度比較快，并且不需要過多的參數(shù)調(diào)整[8]。單純的PSO不能解決約束滿足問題[9-11]。課程編排問題屬于約束滿足問題，所以需要尋找一種方法處理控制課程編排問題中的約束沖突。

本文提出一種經(jīng)過改進的基于粒子群算法的算法(粒子群- 前行檢測算法(PSO-FC))，即將前行檢測算法(FC)融合到粒子群算法(PSO)中。粒子群算法產(chǎn)生課程編排的潛在解，前行檢測算法優(yōu)化這些潛在解。

1 高校課程編排問題

課程編排涉及時間檔(T)、教室(R)、教師(I)和課程(S)等因素。表1展示了某高校每周課程表的結(jié)構(gòu)。每天有11個時間檔，一周上課5天，每周總共55個時間檔，除去為特別事件(午餐、午休、會議等)預(yù)留的12個時間檔。用于課堂教學的時間檔共43個。

表1 某高校每周課程表結(jié)構(gòu)示例

續(xù)表1

為特別事件預(yù)留的時間檔

1.1 建模高校編排問題為約束滿足問題

約束滿足問題是決策問題，定義為一組對象的狀態(tài)必須滿足一定數(shù)量的約束。

一般地，約束滿足問題由變量、定義、約束條件構(gòu)成。約束滿足問題形式為P=(X,D,C)，其中：

?X={X1,X2,…，Xn}表示變量集。

?D={D1,D2,…，Dn}表示定義域集，Di為分配給變量Xi的有限可能數(shù)值。

?C={C1,C2,…，Cm}表示約束集，表示變量之間的關(guān)系，Ci?{Di1×Di2×…×Dik}。

很多約束滿足問題算法是基于搜索和推理的原則的。搜索法、推理法的代表分別為回溯算法(BT)、兼容性強化技術(shù)。前行檢測算法是常見的一種兼容性強化技術(shù)。搜索法是為一般應(yīng)用而開發(fā)的，不使用約束來提高效率。相反，兼容性強化技術(shù)使用約束縮減搜索空間直到找到解。單獨應(yīng)用搜索或兼容性強化技術(shù)都不能有效地解決約束滿足問題。所以，結(jié)合搜索法和兼容性強化技術(shù)，可以發(fā)揮兩者的優(yōu)勢，縮減搜索空間，加快搜索進程。

約束滿足問題的可行解通過實例化滿足所有約束條件的變量得到。給定目標函數(shù)，通過實例化滿足所有約束條件的所有變量并優(yōu)化給定的目標函數(shù)來找到最優(yōu)解[12-15]。

課程編排問題中，變量為課程Si，定義域為可行的時間檔T(Si)和教室R(Si)，約束C(Si)為變量之間的關(guān)系。課程編排問題的解可以定義為分配時間T(Si)和教室R(Si)給教師I(Si)講授的課程Si并滿足一定的約束C(Si)。課程編排問題可以定義為4-元組[Si,T(Si),R(Si),C(Si)]的約束滿足問題。

1.2 課程編排的約束

約束在構(gòu)筑可行和優(yōu)化的課程表方面起著重要作用。

1) 分配給課程的時間檔和教室必須從時間檔和教室定義域中選擇。

(?i)?(t∈T(Si))(δi=t)

(1)

(?i)?(r∈R(Si))(εi=r)

(2)

分配給課程i的時間檔和教室分別以δi和εi表示。

2) 某位教師講授多門課程，在同一時間檔內(nèi)，一位教師不能分配多于一門課程的教學。

?(I(Si)=I(Sj))?(T(Si)≠T(Sj))

(3)

課程Si和課程Sj的上課時間不能相同，因為是同一位教師授課。

3) 一個學生群在同一時間檔不能分配參與多門課程的學習。

?(G(Si)=G(Sj))?(T(Si)≠T(Sj))

(4)

課程Si的上課時間T(Si)不能與課程Sj的上課時間T(Sj)相同，因為它們屬于同一學生群，即G(Si)=G(Sj)。

4) 一間教室在同一時間檔內(nèi)不能分配給多門課程使用。

?(R(Si)=R(Sj))?(T(Si)≠T(Sj))

(5)

5) 教室能容納的學生數(shù)目應(yīng)該不少于上課學生人數(shù)。

?(R(Si)=rk)?(Z(R(Si))≥N(Si))

(6)

Z(R(Si))為分配給課程Si的教室R(Si)的容量，N(Si)為課程Si的上課學生人數(shù)。

6) 某些時間檔預(yù)留給特別事件E，例如對時間檔有特定要求的教師。

?(tj=E)?(T(Si)≠tj)

(7)

7) 某些教室預(yù)留給特定事件F，例如對教室有特定要求的教師。

?(rj=F)?(R(Si)≠rj)

(8)

2.1 粒子群算法

粒子群算法(PSO)是Kennedy和Eberhart受鳥群運動模型啟發(fā)而提出的隨機群體搜索算法。粒子群算法將鳥群運動模型中的棲息地類比為問題解空間中可能解的位置，將解空間中的每只鳥類比為每個候選解，稱之為粒子。由隨機初始化形成的粒子組成一個種群，種群中的粒子在解空間中以一定的速度飛行。粒子通過適應(yīng)度函數(shù)對兩個極值進行評估，更新速度和位置。第一個為個體極值，即目前粒子本身發(fā)現(xiàn)的最佳位置。第二個為全局極值，即整個種群中目前找到的最佳位置。通過粒子間的相互協(xié)作和信息共享，以迭代的方式進行搜索直至達到規(guī)定的迭代次數(shù)或滿足規(guī)定的誤差標準為止，進而得到最優(yōu)解。詳細的粒子群算法見算法1。

假設(shè)在一個D維的目標搜索空間中，有M個粒子組成一個種群，其中第i個粒子在D維空間中的位置為xi=(xi1,xi2,…,xid)，第i個粒子的速度vi=(vi1,vi2,…,vid)，記第i個粒子的個體極值pi=(pi1,pi2,…,pid)，整個種群的全局極值為g=(g1,g2,…,gd)，則粒子根據(jù)下式進行速度和位置的更新：

(9)

(10)

(11)

式中：d=1,2,…,D;i=1,2,…,M；c1和c2為學習因子，取值范圍是非負常數(shù)；r1和r2是介于之間的隨機數(shù)；χ為伸縮因子，用于控制速度的慣性，φ=c1+c2，φ>4通常φ取4.1，χ取0.729 84[16-19]。

算法1粒子群優(yōu)化算法。

Procedure of PSO

1 for each particle i=1,2,…,S do

2 Initialize the particle’s position with a uniformly distributed random vector: xi∈U(blo,bup)

// bloand bupare respectively the lower and upper boundaries

//of the search-space

3 Initialize the particle’s best known position to its initial position: xi←pi

4 if f(pi)>f(g) then

5 update the swarm’s best known position: g←pi

6 Initialize the particle’s velocity: vi∈U(-|bup-blo|,|bup-blo|)

7 while a termination criterion is not met do:

8 for each particle i=1,2,…,S do

9 for each dimension d=1,2,…,N do

10 Pick random numbers: r1,r2～U(0,1)

13 if f(xi)>f(pi) then

14 Update the particle’s best known position: pi←xi

15 if f(xi)>f(g) then

16 Update the swarm’s best known position: g←pi

17 Return the particle with the best fitness value of all as

2.2 粒子編碼

使用直接編碼的方案。每個粒子包含關(guān)于課程的時間檔和教室信息。粒子的編碼結(jié)構(gòu)形式為P[Si;Tj;Rk]。i=1,2,…,N;N為課程數(shù)目的最大值。j=1,2,…,M;M為時間檔的最大數(shù)目。k=1,2,…,P;P為教室的最大數(shù)目。特別地，若某些課程有平行班要求同步安排時間，則重復(fù)構(gòu)造出規(guī)定數(shù)量的粒子，形成初始粒子群。

2.3 前行檢測算法

前行檢測算法是一種基于回溯的算法。回溯算法是解決約束滿足問題的基本方法。回溯算法的基本思想是：在問題的解狀態(tài)空間樹中，依深度優(yōu)先方式(DFS)遍歷，不斷地嘗試為未分配變量反復(fù)選擇數(shù)值，將局部解擴展到全局解。回溯算法由根節(jié)點出發(fā)進行搜索，對于解狀態(tài)空間樹的某個節(jié)點，若該節(jié)點滿足問題的約束，則進入該子樹繼續(xù)進行搜索，否則將以該節(jié)點作為根節(jié)點的子樹進行剪枝，逐層向根節(jié)點進行回溯，直至根節(jié)點的所有子樹都搜索完畢。回溯算法適用于組合數(shù)較大的問題。

算法2前行檢測算法

Procedure of FC

輸入：約束問題P=(X,D,C)

輸出：解或無解。

//復(fù)制定義域

2 i←1

//初始化計數(shù)

3 while 1≤i≤n

4 instantiate xi←SELECT-VALUE-FC

5 if xiis null

//無值返回

6 i←i-1

//backtrack回溯

8 remove any constraints added since xiwas last instantiated

9 else

10 i←i+1

//step forward前向

11 end while

12 if i=0

13 return inconsistent

14 else

15 return instantiated values of {x1,…,xn}

16 end procedure

算法3前行檢測算法的選取數(shù)值子算法

Subprocedure of SELECT-VALUE-FC

3 empty-domain←false

4 for allk,i≤k≤n

//約束cm檢測

8 end for

//xi=a leads to a dead-end一些未來變量域為空

10 empty-domain←true

11 end for

12 if empty-domain

//不選 a

14 else

15 return a

16 end while

17 return null

//無兼容值

18 end procedure

2.4 粒子群前行檢測算法

粒子群算法具有通過更新粒子飛行位置和速度結(jié)合適應(yīng)度函數(shù)尋找優(yōu)化解的能力。單純使用粒子群算法不能解決諸如約束滿足問題這種復(fù)雜問題。這是粒子群優(yōu)化算法的本性所致，粒子群優(yōu)化算法設(shè)計用于尋求通過更新粒子飛行位置和速度結(jié)合適應(yīng)函數(shù)的可能解，但它不能處理約束。所以，需要尋找一種能夠處理約束的技巧。整合前行檢測算法到粒子群算法中，得到粒子群- 前行檢測算法(PSO-FC)，對課程編排問題的約束能進行優(yōu)化。

粒子群- 前行檢測算法分兩階段。第一階段執(zhí)行粒子群優(yōu)化算法，這個階段產(chǎn)生潛在解分配教室和時間檔給課程。搜索空間的大小由教室和時間檔決定。例如，教室數(shù)目為15，時間檔數(shù)目為20，則搜索空間大小為15×20=300。

限定搜索空間的規(guī)模，粒子就不能逃逸到搜索空間之外。每個粒子將通過與鄰近粒子共享與交換信息結(jié)合適應(yīng)函數(shù)更新教室和時間檔。

第二階段應(yīng)用前行檢測算法。為了便于搜索解，將課程編排問題羅列成樹圖的組織結(jié)構(gòu)，如圖1所示。樹的層次對應(yīng)于教室Rk和時間檔Tj。這個階段用于驗證第一階段產(chǎn)生的潛在解的兼容性。兼容性測試的目的是決定定義域取出的數(shù)值是否與相關(guān)的約束抵觸。若不兼容，數(shù)值將會從定義域移除。定義域的每個變量值代表搜索空間的一個節(jié)點，移除定義域中的數(shù)值意味著搜索空間的減小。這樣有利于加快運算的速度。檢測學生群與教師對課程的可行性，教室是否夠大可以容納上課的學生數(shù)，教室和時間檔對課程是否兼容。當?shù)谝浑A段產(chǎn)生的潛在解與約束抵觸時，前行檢測算法就會啟動，驗證教室Rk、時間檔Tj和當前課程Si的兼容性，尋找有效的解加以修復(fù)。若找到可行的教室和時間檔，分配給課程。否則將會回溯到其他可行的教室和時間檔。前行檢測算法在潛在解有效性驗證遇到標記符號“0”執(zhí)行，當遇到標記符號“1”，接受潛在解。其中“0”表示潛在解與約束抵觸，“1”表示潛在解與約束不抵觸。圖2顯示了粒子群- 前行檢測算法的流程概覽。圖3顯示了粒子群- 前行檢測算法進行約束處理的例子。

圖1 前行檢測的解狀態(tài)空間樹結(jié)構(gòu)圖

圖2 粒子群- 前行檢測算法流程概覽

圖3 粒子群- 前行檢測算法約束處理示例

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

課程編排的主要目標是找到一個近似最優(yōu)的課程表，優(yōu)化利用好資源(時間和教室)。適應(yīng)度函數(shù)的作用是對教室和時間檔的偏好值的排序進行優(yōu)化，最大化時間檔和教室的偏好值。此處的偏好值是教師基于時間檔和教室的可利用性和便利性而對時間檔和教室賦予的權(quán)重。通過對教室和時間檔排序，偏好值可以被確定。最好的教室和時間檔賦予最高的偏好值。使用這樣的適應(yīng)度函數(shù)，最好的教室和時間檔會分配給課程。滿足這樣條件的解稱之為近似最優(yōu)解。適應(yīng)度函數(shù)表示為：

(12)

式中：P(T(Si))是教師I(Si)對時間檔(課程Si對應(yīng)的時間檔)的偏好值，P(R(Si))是教師I(Si)對教室(課程Si對應(yīng)的教室)的偏好值，其中i=1,2,…,n。

2.6 變量和變量賦值排序

變量(課程)和變量賦值(時間檔和教室)排序在約束滿足問題中很重要，因為它們直接關(guān)系到粒子群- 前行檢測算法中搜索的有效性和解的可行性。它們可以減少搜索的空間，快速地尋找到問題的解。排序依據(jù)特定的偏好執(zhí)行，這樣在任何時間可以擴展最好的結(jié)點，引導找到最優(yōu)解。

設(shè)S1,S2,…,Sn為一系列課程變量，根據(jù)以下的標準進行排序為S1≤S2≤…≤Sn。

? 課程的重要性和關(guān)鍵要求。

? 課程難易程度。

結(jié)點擴展取決于序列中的變量賦值選取。根據(jù)下面的標準對時間檔T1,T2,…,Tm進行排序為T1≤T2≤…≤Tm。

? 一天之中時間檔的位置。

? 與一周起始第一天的距離。

教室R1,R2,…,Rk基于以下的標準順序排列為R1≤R2≤…≤Rk。

? 教室的設(shè)施，空調(diào)，噪聲。

? 離中心活動區(qū)的遠近。

? 樓層的高度。

? 教室的容量最接近上課學生人數(shù)

3 實驗結(jié)果分析

粒子群- 前行檢測算法在2 GB RAM， Core 2 Duo 2.2 GHz CPU，Windows 7，Visual C++2008的微機環(huán)境進行。提出的算法使用某高校數(shù)學與信息系統(tǒng)學院的數(shù)據(jù)進行了測試。粒子群算法參數(shù)設(shè)置如表2所示。表3給出了課程編排的基本信息。表4和表5給出了時間檔和教室偏好值的信息。

表2 PSO參數(shù)設(shè)置

表3 課程編排基本信息概要

表4 高校教師對時間檔的偏好值概要

表5 高校教師對教室的偏好值概要

為了評估粒子群- 前行檢測算法(PSO-FC)的課程編排的性能，將它與標準粒子群優(yōu)化算法(PSO)[21]和整合局部搜索的粒子群算法(PSO-LS)[8]進行了對比。每種算法獨立運行5次，實驗結(jié)果見表6-表8。

表6 標準PSO運行5次的結(jié)果

表7 PSO-LS運行5次的結(jié)果

表8 PSO-FC運行5次的結(jié)果

由表6-表8得出，三種算法都能產(chǎn)生課程編排的可行解。平均運行時間耗費方面，三種算法相差不大。但通過查看表8中平均適應(yīng)值的最大值，與表6和表7中的相應(yīng)值進行對比，適應(yīng)值(教師對教室和時間檔的偏好值)是最大的。這表明PSO-FC算法能產(chǎn)生可行近似最優(yōu)解，解的質(zhì)量最好。

與標準PSO算法和PSO-LS算法相比，PSO-FC算法產(chǎn)生解的時間耗費稍微長一些。因為需要驗證可能解的有效性和遇到無效解產(chǎn)生時的回溯搜索。標準PSO算法和PSO-LS算法可以更快地生成解，因為兩者接受任何一個與約束不抵觸(沒有最大化偏好值)的解且不進行任何回溯過程，所以兩者產(chǎn)生的解為可行解。單純使用PSO算法余下一些未分配的課程，因為它不能處理課程編排過程的約束。這些未分配的課程最終還需要人工編排。人工編排耗時長，效率不高。

綜上所述，標準PSO算法、PSO-LS算法和PSO-FC算法都能應(yīng)用于實際的課程編排。綜合考慮運行時間和適應(yīng)值兩方面因素，PSO-FC算法優(yōu)于標準PSO算法各PSO-LS算法，更能滿足實際課程編排的需求。

4 結(jié) 語

本文提出了一種將前行檢測算法融合到粒子群算法(粒子群- 前行檢測算法)來解決高校課程編排問題的方法。為了驗證算法的性能，與整合局部搜索的粒子群算法和標準粒子群算法進行了比較分析。使用粒子群- 前行檢測算法在解決高校課程編排問題的過程中，教師對教室和時間檔的偏好值在選擇的適應(yīng)度函數(shù)的作用下得到了最大化。粒子群- 前行檢測算法中的前行檢測階段對粒子群算法階段產(chǎn)生的解進行了驗證，當遇到無效解時就通過約束處理來尋找有效的解。前行檢測算法能夠顯著地減少搜索空間。實驗表明，所有方法都提供可行解，但粒子群- 前行檢測算法給出了近似最優(yōu)解。未來的研究工作將專注于試驗不同的約束滿足問題個案進一步驗證所提出的算法的性能。

[1] Kingston J H. Timetable construction: the algorithms and complexity perspective[J]. Annals of Operations Research, 2014, 218(1):249- 259.

[2] Hiryanto L. Incorporating dynamic constraint matching into vertex-based graph coloring approach for university course timetabling problem[C]//Proceedings of 2013 International Conference on QiR,USA: IEEE, 2013: 68- 72.

[3] Alves S S A, Oliveira S A F, Neto A R R. A novel educational timetabling solution through recursive genetic algorithms[C]// Computational Intelligence. IEEE, 2016: 1- 6.

[4] Fonseca G H G, Santos H G, Carrano E G, et al. Integer programming techniques for educational timetabling[J]. European Journal of Operational Research. 2017, 262:28- 39.

[5] Tarawneh H Y, Ayob M, Ahmad Z. A Hybrid Simulated Annealing with Solutions Memory for Curriculum-based Course Timetabling Problem[J].Journal of Applied Sciences, 2013, 13(2): 262- 269.

[6] Lüaba Z. Adaptive Tabu Search for course timetabling[J].European Journal of Operational Research, 2010, 200(1): 235- 244.

[7] Deris S, Omatu S, Ohta H, et al. Incorporating constraint propagation in genetic algorithm for university timetable planning[J]. Engineering Applications of Artificial Intelligence, 1999, 12(3): 241- 253.

[8] Ho I S F, Deris S, Zaiton M H S. A Combination of PSO and Local Search in University Course Timetabling Problem[C]//International Conference on Computer Engineering and Technology. IEEE Computer Society, 2009: 492- 495.

[9] Li H. Narrowing Support Searching Range in Maintaining Arc Consistency for Solving Constraint Satisfaction Problems[J]. IEEE Access, 2017, 5(99): 5798- 5803.

[10] Di M M, Forti M, Nistri P, et al. Nonsmooth Neural Network for Convex Time-Dependent Constraint Satisfaction Problems[J]. IEEE Transactions on Neural Networks & Learning Systems, 2016, 27(2): 295- 307.

[11] Luo T, Dolan M, Davidson E, et al. Assessment of a new constraint satisfaction problem based active demand control approach to address distribution network constraints[J]. ET Generation, Transmission & Distribution, 2015, 9(15): 2363- 2373.

[12] Jiang X, Cui P, Xu R, et al. An action guided constraint satisfaction technique for planning problem[C]//International Conference on Cognitive Informatics & Cognitive Computing. IEEE, 2017: 167- 173.

[13] Shen J, Mei D. The Freuder Width in a General Model of Constraint Satisfaction Problem[C]//International Symposium on Computational Intelligence and Design. IEEE, 2017: 303- 306.

[14] Chen H, Valeriote M, Yoshida Y. Testing Assignments to Constraint Satisfaction Problems[C]//Foundations of Computer Science. IEEE, 2016: 525- 534.

[15] Rouahi A, Salah K B, Ghydira K. Belief Constraint Satisfaction Problems[C]//Computer Systems and Applications. IEEE, 2016: 1- 4.

[16] Mallick S, Ghoshal S P, Acharjee P, et al. Optimal Static State Estimation Using hybrid Particle Swarm-Differential Evolution Based Optimization[J]. Energy & Power Engineering, 2017, 5(4): 670- 676.

[17] Jin H L, Song J Y, Kim D W, et al. Particle Swarm Optimization Algorithm with Intelligent Particle Number Control for Optimal Design of Electric Machines[J]. IEEE Transactions on Industrial Electronics, 2018, 65(2): 1791- 1798.

[18] 項鐵銘, 王建成. 改進的多目標粒子群優(yōu)化算法[J]. 計算機應(yīng)用與軟件, 2017, 34(9):302- 305.

[19] Tassopoulos I X, Beligiannis G N. Solving effectively the school timetabling problem using particle swarm optimization[J]. Expert Systems with Applications, 2012, 39(5): 6029- 6040.

[20] Dechter R, Frost D. Backjump-based backtracking for constraint satisfaction problems[J]. Artificial Intelligence,2002, 136(2): 147- 188.

[21] Irene S F H, Deris S, Zaiton M H S. A Study on PSO-Based University Course Timetabling Problem[C]//International Conference on Advanced Computer Control. IEEE Computer Society, 2009: 648- 651.