羅義強(qiáng) 陳智斌(昆明理工大學(xué)理學(xué)院 云南 昆明 650500)

0 引 言

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

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

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

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

1 高校課程編排問題

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

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

續(xù)表1

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

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

約束滿足問題是決策問題，定義為一組對(duì)象的狀態(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)、兼容性強(qiáng)化技術(shù)。前行檢測(cè)算法是常見的一種兼容性強(qiáng)化技術(shù)。搜索法是為一般應(yīng)用而開發(fā)的，不使用約束來提高效率。相反，兼容性強(qiáng)化技術(shù)使用約束縮減搜索空間直到找到解。單獨(dú)應(yīng)用搜索或兼容性強(qiáng)化技術(shù)都不能有效地解決約束滿足問題。所以，結(jié)合搜索法和兼容性強(qiáng)化技術(shù)，可以發(fā)揮兩者的優(yōu)勢(shì)，縮減搜索空間，加快搜索進(jìn)程。

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

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

1.2 課程編排的約束

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

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

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

(1)

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

(2)

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

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

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

(3)

課程Si和課程Sj的上課時(shí)間不能相同，因?yàn)槭峭晃唤處熓谡n。

3) 一個(gè)學(xué)生群在同一時(shí)間檔不能分配參與多門課程的學(xué)習(xí)。

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

(4)

課程Si的上課時(shí)間T(Si)不能與課程Sj的上課時(shí)間T(Sj)相同，因?yàn)樗鼈儗儆谕粚W(xué)生群，即G(Si)=G(Sj)。

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

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

(5)

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

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

(6)

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

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

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

(7)

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

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

(8)

2.1 粒子群算法

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

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

(9)

(10)

(11)

式中：d=1,2,…,D;i=1,2,…,M；c1和c2為學(xué)習(xí)因子，取值范圍是非負(fù)常數(shù)；r1和r2是介于之間的隨機(jī)數(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 粒子編碼

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

2.3 前行檢測(cè)算法

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

算法2前行檢測(cè)算法

Procedure of FC

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

輸出：解或無解。

//復(fù)制定義域

2 i←1

//初始化計(jì)數(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前行檢測(cè)算法的選取數(shù)值子算法

Subprocedure of SELECT-VALUE-FC

3 empty-domain←false

4 for allk,i≤k≤n

//約束cm檢測(cè)

8 end for

//xi=a leads to a dead-end一些未來變量域?yàn)榭?/p>

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 粒子群前行檢測(cè)算法

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

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

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

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

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

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

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

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

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

(12)

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

2.6 變量和變量賦值排序

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

設(shè)S1,S2,…,Sn為一系列課程變量，根據(jù)以下的標(biāo)準(zhǔn)進(jìn)行排序?yàn)镾1≤S2≤…≤Sn。

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

? 課程難易程度。

結(jié)點(diǎn)擴(kuò)展取決于序列中的變量賦值選取。根據(jù)下面的標(biāo)準(zhǔn)對(duì)時(shí)間檔T1,T2,…,Tm進(jìn)行排序?yàn)門1≤T2≤…≤Tm。

? 一天之中時(shí)間檔的位置。

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

教室R1,R2,…,Rk基于以下的標(biāo)準(zhǔn)順序排列為R1≤R2≤…≤Rk。

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

? 離中心活動(dòng)區(qū)的遠(yuǎn)近。

? 樓層的高度。

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

表4 高校教師對(duì)時(shí)間檔的偏好值概要

表5 高校教師對(duì)教室的偏好值概要

為了評(píng)估粒子群- 前行檢測(cè)算法(PSO-FC)的課程編排的性能，將它與標(biāo)準(zhǔn)粒子群優(yōu)化算法(PSO)[21]和整合局部搜索的粒子群算法(PSO-LS)[8]進(jìn)行了對(duì)比。每種算法獨(dú)立運(yùn)行5次，實(shí)驗(yàn)結(jié)果見表6-表8。

表6 標(biāo)準(zhǔn)PSO運(yùn)行5次的結(jié)果

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

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

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

與標(biāo)準(zhǔn)PSO算法和PSO-LS算法相比，PSO-FC算法產(chǎn)生解的時(shí)間耗費(fèi)稍微長(zhǎng)一些。因?yàn)樾枰?yàn)證可能解的有效性和遇到無效解產(chǎn)生時(shí)的回溯搜索。標(biāo)準(zhǔn)PSO算法和PSO-LS算法可以更快地生成解，因?yàn)閮烧呓邮苋魏我粋€(gè)與約束不抵觸(沒有最大化偏好值)的解且不進(jìn)行任何回溯過程，所以兩者產(chǎn)生的解為可行解。單純使用PSO算法余下一些未分配的課程，因?yàn)樗荒芴幚碚n程編排過程的約束。這些未分配的課程最終還需要人工編排。人工編排耗時(shí)長(zhǎng)，效率不高。

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

4 結(jié) 語

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

[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] 項(xiàng)鐵銘, 王建成. 改進(jìn)的多目標(biāo)粒子群優(yōu)化算法[J]. 計(jì)算機(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.