差分進化布谷鳥算法在實驗室排課中的應用

彭勇　陳俞強

摘? ?要：隨著高校實驗課程比例越來越高，針對傳統實驗室排課手段效率低、出現沖突的可能性高等缺點，提出了一種基于改進布谷鳥算法的智能排課模型。首先，定義了課元表示教師在什么班級上什么課程，把排課問題轉化為課元確定教室-時間對，提出了一個多目標、多約束的排課數學模型。其次將數學模型的求解轉化為對二部圖進行完美匹配操作獲取初始解。然后，利用差分進化方法改進了布谷鳥算法，實現布谷鳥算法在實驗室排課中的應用。最后，通過對仿真實驗的結果分析來驗證算法可行性與有效性。

關鍵詞：實驗室排課;布谷鳥算法;二部圖;差分進化;課元;排課模型

中圖分類號：TP319? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A

Application of Improved Cuckoo Search Based on Differential Evolution

in Laboratory Course Arrangement

PENG Yong？覮，CHEN Yu-qiang

（Department of Computer，Dongguan Polytechnic College，Dongguan，Guangdong 523808，China）

Abstract：As proportion of experimental courses is increasing in colleges，aiming at the shortcomings of low efficiency and high possibility of conflict in traditional laboratory course arrangement methods，an intelligent course scheduling model based on improved cuckoo algorithm is proposed. Firstly，it defines the course elements to indicate what classes and courses teachers are taking，transforming the problem of course scheduling into course elements to determine classroom-time pairs，a mathematical model of multi-objective and multi-constraint is proposed. Secondly，the solution of mathematical model is transformed into perfect matching of bipartite graphs，then，the improved cuckoo search based on differential evolution is used to find the optimal schedule in the solution space，finally，the feasibility and validity of the algorithm are verified by analyzing the simulation results.

Key words：laboratory course arrangement;cuckoo search;bipartite graphs;differential evolution;course elements ;course scheduling model

在高校的實驗室管理中，實驗課程排課是一項非常復雜而繁瑣的工作。近年來，高校招生規模日益擴大，各種新型專業課程層出不窮，大部分專業課程都要求在實驗室進行理實一體化教學，盡管實驗室建設進度也不斷加快，但是實驗實訓資源仍然十分短缺，各高校對實驗室的利用率提出較高的要求，盡量讓課程能夠共享實驗室，這無形就增大了實訓課程排課的復雜度和難度。目前高校排課很多還是利用Excel軟件由教學秘書手工排課，遠遠不能滿足新時代高校實驗室排課的需求。早在70年代，高校排課問題就被證明是一個NP完全問題，即算法的計算時間是呈指數增長的，這一論斷確立了排課問題的理論深度[1]。

近年來，有很多學者針對不同應用環境的高校排課問題給出不同的解決方法。蘇軍波提出運用在把排課過程轉化為二部圖之后，首先利用貪心選擇最大未排課班級，再貪心選擇符合課程要求的最小教室，降低了排課算法的復雜度，最終的算法的復雜度由指數復雜度降為線性復雜度[2]，但當問題規模較大時，貪心算法運算時間過長，得到的結果不是全局最優;蔣中云運用混合螞蟻的信息素來改進蟻群算法解決了排課問題[3]，該算法與傳統的蟻群算法對比，有所提升，但在排課的算法模型生還不夠優化，與高校實際排課還是有一定差距;張媛探索了禁忌搜索法來設計排課系統，該系統可操作性強，搜索效率高，具有可用性與可適性[4]，該算法的把各種排課約束表示填充到禁忌表，較好的管理了約束，但對約束的不同等級沒有分析，沒有區分硬約束和軟約束;高健、高培等人在傳統模擬退火算法的基礎上，通過加入一個記錄因子來保留較好的狀態，不會丟失每次迭代的最優解，同時還給出了一個可變步長的溫度更新函數，并通過雙閾值的設置減少了計算量，提高了模擬退火算法在求解排課問題上的可行性和有效性[5]，但由于排課算法的復雜度非常高，特別是達到一定規模的排課實際問題，上述算法無法得到較好的排課結果。

智能進化算法發展日新月異，各種新型智能進化算法層出不窮。例如蝙蝠算法、螢火蟲算法、生物地理學算法等，其中布谷鳥搜索（Cuckoo Search，縮寫 CS），是由YANG Xin-she和DEB S于2009年提出的一種新興啟發算法[6]，具有參數少、操作簡單、易實現、隨機搜索路徑優和尋優能力強等優點，目前已經應用于電力系統、生物醫藥、模糊控制、金融、電子與電磁場等領域。本文提出一種基于差分進化的布谷鳥優化算法應用于實驗室排課，旨在合理利用實訓資源，提高排課的效率。

1? ?高校排課問題數學描述

排課問題是一個多元分配問題，主要包括教師、課程、班級、教室、時間這5個元組，但這5個元組不是隨機分配的，一般而言，高校在每學期期末就確定了下學期每個老師的教學任務，即哪位教師承擔某個班級的什么課程，這個是已經確定的，一般情況下并不能調整，我們把教師、課程和班級的組合定義為教學課程元（簡稱為課元），那么排課問題這個多元分配問題轉變成在滿足約束情況下為每個課元分配給教室和時間的問題[7]，這就成為一個三元問題了，在這個三元問題中，有兩類排課約束，一類是必須滿足的，如果不滿足的話，完全無法上課，我們稱為硬約束，比如兩個班排到同一教室上不同的課程;還有一類我們稱為軟約束，主要是最好要滿足，沒有滿足的話只是影響教學效果或老師的滿意度，比如同一門課程最好是不要同一天或連續兩天都安排。

1.1? ?變量表示

（1）課元集合M：課元表示教師、課程和班級的集合，具體如表1所示。

表1? ?課元示例

其中，M = {M1，M2，…，Mm}為所有課元構成的集合，按照班級c（·） = βs人數從大到小排列;函數h（·）用來提取課元Mi所任教的教師為αk;函數c（·）用來提取課元Mi所任教的班級為βs;Wi表示課元Mi對教室的要求，已經按要求的從低到高排序，這種需求主要和課程屬性有關，有些課程操作性非常強，就需要普通機房;有的課程以講解為主，就需求多媒體教室，但在機房上可也以，為了簡化排課模型，對部分理論教學，部分上機實驗的課程，我們統一以機房為準。教室要求的優先級順序為W1：多媒體教室

（2）教室集合N：包含校區、教室編號、教室類別（例如多媒體教室、普通機房、多功能教室、圖書館報告廳）和可容納人數（工位數），一共有n個教室，N = {N1，Nj，…，Nn}。

（3）上課時段集合T：定義的是教學時間段，一般情況下，教師按照大節（包含2節課）上課，一天的教學實踐可以分為第一大節、第二大節、第三大節、第四大節和第五大節共計5個時間段，則每周共有25個授課時間元，T = {T1，Tt，…，T25}，例如T1表示周一第一大節（上午12節），T10表示周二第五大節（晚上9、10節）。

（4）教師集合H：則表1中h（Mi） = αk∈H，并記αk = （0 … 1 … 0）T為除第k行為 1 其余各行都是0的單位向量，向量的維度等于教師總數H。

（5）班級集合C：則表1中c（Mi） = βs∈C，并記 βs = （0 … 1 … 0）T為除第s行為 1 其余各行都是0的單位向量，向量維度等于班級總數C。

（6）根據以上表述，在實驗室排課就是在滿足上述條件的情況下，為每一個課元元素找出最佳的教室時間對，即在什么時候，某位老師帶某個班級的什么課程在指定的教室上課。課元和教室時間對D之間共有2D個映射。

（1）

可以將課元Mi的排課結果Ri■N×T表示為教室和授課時間之間的有序元素對（Nj，Tt）構成的集合，排課決策變量為：

rijt = 1，Mi課元被按安排在Nj教室Tt時間段進行2個課時教學0，否則? ? ? ? （2）

排課結果：

Ri = （j，t）|rijt ≠ 0，i = 1，2，…，m? ? ? ? ? （3）

1.2? ?排課所遵循的約束條件

（1）硬約束條件

1）對教師的約束：在同一個上課時段內老師只能在一個班級上一門課。

■αkrijt = ■h（Mi）rijt ≤ 1? ? ? ? ? （4）

2）班級約束：在同一個上課時段一個班級內只能在一個教室上一門課。

■βsrijt = ■c（Mi）rijt ≤ 1? ? ? ? ? （5）

3）教室約束：在同一個上課時段內一個教室只能安排上一門課程。

■rijt ≤ 1? ? ? ? ? （6）

4）課時約束：課元Mi的每周的課時量為Xi，每次課記2個課時。

■2rijt = Xi? ? ? ? ? （7）

5）人數約束：課元Mi的班級人數必須小于實驗室的工位數，Nj表示實驗室工位數，c（Mj）表示班級人數。

（j，t）∈Ri，Nj≥c（Mj），i = 1，2，…，m

（8）

6）教室類型約束：教室N的類型標準必須大于課元Mi的教室要求Wi，函數L（·）用來提取教室的類型值。

（j，t）∈Ri，L（Nj）≥Wi，i = 1，2，…，m? ? ?（9）

（2）軟約束條件

1）學習效果約束

排課時間段盡量安排在學習效果較好的時間段，即讓學習效果：

f1 = max■p（Tt）rijt? ? ? ? ? （10）

盡可能大。

表2? ?時間段評價值

函數p（·）用來提取時間段Tt所對應的學習效果評估值，根據我們的問卷調查和隨機訪談，對于絕大部分學生而言，在上午12節上課，取得的學習效果最好，其次是上午34節和下午78節，下午56節效果更差一些，晚上（9、10節）和周五的下午78節的學習效果最差，這個效果評價可以根據季節和學校實際情況進行調整。

2）排課間隔約束

相同課程的排課結果Ri在時間段T中盡可能分散，即方差：

f2 = max■■（j - ■）2? ? ? ? ? （11）

保持最大，實際上就是一門課程在同一個班不能連續排課，為了提高教學效果，讓學生有自行消化吸收已經課程復習和預習時間，把課程適當排散。

3）可用資源約束

排課結果Ri應使未利用教室的座位總和：

f3 = max■Nj（1 - rijt）? ? ? ? ? （12）

盡可能大，也就是安排完所有課元后，還有最多的教室-時間對資源可以，以便部分老師出差時，調整課程方便。

綜上所述，排課問題實際是一個整數線性約束的多目標優化模型，可以描述為如下：

max（C1 f1 + C2 f2 + C3 f3）? ? ? ? （13）

2? ?基于改進布谷鳥算法的高校排課

2.1? ?標準布谷鳥算法

根據文獻[8]所述標準布谷鳥搜索算法，可知布谷鳥尋巢的位置更新公式如下：

xi（t + 1） = xi（t） + α ■ Levy（λ），i = 1，2，…，n

（14）

在第t + 1代時，第i個鳥巢的位置為xi（t + 1）;α是用于控制飛行距離的常數;■為點對點乘法; Levy（λ）表示搜索下一個鳥巢位置的路徑，服從 Levy分布：

Levy（λ） ～ μ = t-λ（1 < λ ≤ 3）? ? ? ? （15）

隨機萊維飛行的計算：

Levy（λ） ～ ■? ? ? ? （16）

其中，μ和ν都服從正態分布，φ的計算公式如下：

φ = ■■? ? ? ?（17）

為了能夠更好地控制隨機搜索的范圍，采用如下公式計算α：

α = α0（xi（t） - xbest）? ? ? ? （18）

其中，α0為常數，xbest表示最優鳥巢位置。

綜上所述，CS算法采用以下公式生成新的解：

xi（t + 1） = xi（t） - α0 ■（xi（t） - xbest）? ?（19）

具體的CS算法流程詳見文獻[9]。

CS算法通過增加迭代的時間，一般情況下是可以找到較優的解，但是由于對解的搜索完全依賴于Levy飛行這樣一個隨機游走的過程，CS算法的快速收斂性和高精度無法得到保證。

2.2? ?差分進化布谷鳥搜索算法思想

差分進化實際是一種增加通過差分策略增加種群多樣性的一種全局優化算法，主要的差分手段有變異、交叉、選擇，與遺傳算法類似，但是算子的具體內容和遺傳算法有較大差別，通過不同的差分操作促進種群中不同個體之間的競爭與合作，可以保留最優個體的有效遺傳的基礎上，通過個體信息交流，提高種群個體的多樣性，是一種非常有效的全局優化算法[10]。

在CS算法基礎上，第t代鳥巢并不是直接進入（ t + 1） 次迭代，而是對其進行變異、交叉、選擇操作，通過變異，增加個體的差異性，通過交叉，增加整個種群的多樣性，通過選擇，能夠指導個體進化的方向，提高快速收斂性，使個體向種群中優秀個體靠攏，得到新的鳥巢位置后，再進入（t+1）次迭代，然后回到標準布谷鳥算法進行萊維飛行搜索，更新鳥巢的位置[11，12]。

1）變異

xi（t）為第t代時，第i個鳥巢的位置，隨機從種群中提取兩個其他個體xr1（t）、xr2（t），利用式（20）產生變異個體vi（t）：

vi（t） = xi（t） + F（xr1（t） - xr2（t））? ? ? ? （20）

其中，F是變異因子，F ∈ [0，2]。 可以看出，vi（t）既包含了xi（t）部分信息，根據變異因子的大小，vi（t）還能夠獲得種群其他個體xr1（t）、xr2（t）的信息，實現種群個體間信息的交流？

2）交叉

交叉是對變異個體vi（t）和第t代個體xi（t）的重組：

uij（t）=vij（t），rand（0，1）≤CR or j = rand（1，n）xij（t），rand（0，1）>CR or j ≠ rand（1，n）

（21）

其中，CR∈ [0，1]是交叉概率，rand（0，1）是[0，1]區間均勻分布的隨機數，rand[1，d]是[1，d]區間均勻分布的隨機整數，j = 1，2，…，d。可以看出，候選個體uij（t）至少有一維的分量是由變異個體vi（t）貢獻的，種群的多樣性明顯得到提升。

3）選擇

通過適應度函數來判斷第t代個體xi（t）與候選個體ui（t）之間的支配關系，產生（t+1）代個體xi（t+1），可以將較優的差異化的個體傳承到下一代。

xi（t） = ui（t），f（ui（t） < f（xi（t））xi（t），other? ? ? ? （22）

2.3? ?布谷鳥算法的二進制轉換

在標準的CS算法中，每次迭代解更新的位置是解空間中的連續值，多用于求解連續解空間的優化問題。為了使算法能處理搜索空間是離散值的情況，Rodrigues等[13]人提出了二進制布谷鳥算法（Binary Cuckoo Algorithm，BCS），BCS是布谷鳥算法的二進制版本。在 BCS中將每一個鳥巢編碼為一個二進制值向量，每一個鳥巢表示一個候選解，每一個布谷鳥蛋表示一個特征，向量中數值1表示特征被選擇，0表示特征沒有被選擇。

使用如下公式將鳥巢每個維度的值映射為二進制值：

s（xij（t）） = ■? ? ? ? （23）

xij（t + 1） = 1? ? ?s（xij（t））≥σ0? ? ?other? ? ? ? （24）

式中，函數s為一個Sigmond映射函數，可將 xij（t）映射到[0，1];i = 1，2，…，m（m為布谷鳥種群數）;j = 1，2，…，d（d 為編碼長度）;σ為在[0，1]區間均勻分布的隨機數;xij（t+1）表示t+1次迭代中第i個鳥巢的第j維的數值。

2.4? ?基于差分進化的多目標布谷鳥算法

多目標進化算法實際是得到一個全局最優的解集，在這個過程中需要保證每個解的Pareto前沿收斂性和多樣性特征。對具有K個子目標的多目標優化問題，Yang等提出了一種多目標布谷鳥算法[14]，在結合上述差分進化思想后，其具體步驟如圖1所示：

圖1? ?基于差分進化的多目標布谷鳥算法流程圖

2.5? ?解的構造

布谷鳥算法的編碼好壞直接影響到算法的計算復雜度，令教師的課表作為每個鳥巢的編碼，編碼位數由排課規模決定，其結構示例如下：

表3? ?課元編碼表

表4? ?鳥巢編碼表

設有某位教師（教師編號為0011）承擔2017級計算機應用技術專業1班（班級編號為1100）的《移動應用開發技術》課程（課程編號為0101），則可以得到其課元編號為001111000101，這個在每個學期末就已經確定，一般不再修改;該課元的一種排課計劃為：教室為教三203（編號為11011），授課時間段為周四下午56節（編號為10010），則可以得到一個可行解的二進制編碼為0011110001011101110010，（鳥巢的二進制表示）。

2.6? ?解的初始化

由上述的分析可知，排課問題就是將課元M向教室-時間對笛卡爾積D上映射，可用二部圖的完美匹配算法來解決，所得的結果不一定是最優解，但是這個結果一定是滿足基本約束條件的可行解[14]。

圖2? ?排課問題二部圖構造初始解模型

圖3中左邊集合M表示課元，即教師、課程和班級的集合，是由院系每學期期末下發的下學期教學任務，它是已知的，不可調整的;右邊D表示教室-時間對，可根據公式（1）獲得，即教室集合與授課時間段集合的笛卡爾積。集合M與D的笛卡爾積就是排課問題的解空間，可根據表3和表4對其進行二進制編碼。通過二部圖完美匹配算法求出一個包含M集合所有元素的M × D一個真子集，此真子集就是排課問題的初始解。

2.7? ?基于改進布谷鳥的多目標排課算法

3? ?仿真實驗及結果分析

3.1? ?實驗環境

軟件環境：Windows 7 64位，Matlab 2016a;

硬件環境：CPU：Intel（R） i7-77003.60GHz;內存：8.00GB;硬盤：128G SSD+1TB。

3.2? ?參數設置

本文實驗中參數設置如下：種群規模為150，迭代次數為200，淘汰概率pα = 0.25，變異因子F = 0.35，交叉概率 CR = 0.25，目標函數權值因子C1、C2、C3分別取0.4、0.3、0.3。

圖3? ?基于改進布谷鳥的多目標排課算法

3.3? ?結果分析

（1）基于差分進化的多目標二進制布谷鳥算法（IMBCS）標準二進制布谷鳥算法（BCS）的性能比較

1）收斂性比較

object[1]

圖4? ?BCS算法非支配前沿

object[1]

圖5? ?IMBCS算法非支配前沿

從圖5和圖4中可以看出，IMBCS算法目標收斂形狀較規則，IMBCS算法的收斂性稍好于BCS算法。

2）多樣性比較

mean_rank_size，maximum generation=200

大小

mean_rank_size，maximum generation=200

圖7? ?IMBCS算法1-3前沿平均大小

從圖6與圖7對比，可以看出，IMBCS算法的多樣性明顯好于BCS算法。BCS算法的第3前沿平均大小在130代左右就基本趨于零值，而由于采用了差分進化的模式，IMBCS算法無論第2還是第3前沿平均大小均未出現衰減為0的現象。由于在迭代初期就增加了種群的多樣性，使其避免陷入局部最優而獲得全局最優值，所以IMBCS算法在多樣性明顯強于BCS算法，說明本文的算法改進是成功的。

3）排課效果比較

表5? ?排課性能評估與對比表

從表5可得，IMBCS算法比起BCS算法在操作時間上略有增加，主要由于IMBCS算法增加了變異、交叉、選擇計算，但由于采取多線程對IMBCS算法進行了加速，所以增加不多，但在排課質量指標（學習效果、排課間隔、剩余可用資源）上均較大優于BCS算法。

4? ?結? 論

高校排課問題是一個多元分配問題，通過分析高校實驗室排課實踐中的各種變量，找出排課過程中需要遵循的軟硬約束，將高校實驗室排課問題轉化為了一個整數線性約束的多目標優化模型，為解決排課問題提供了數學描述基礎。在標準布谷鳥算法的基礎上，通過Sigmond映射函數將連續布谷鳥算法改進為二進制布谷鳥算法，再通過差分進化的方法改善了算法的收斂性和多樣性，利用二部圖完美匹配算法構造初始種群，并用于對實驗室排課模型的求解。通過具體的實驗分析了不同算法求解模型的收斂性和求解結果質量，得出基于差分進化布谷鳥算法的所得結果令人滿意，能明顯提高排課工作效率。

參考文獻

[1]? ? 張媛，祁蘭.高校實驗室排課系統的研究與開發[J].榆林學院學報，2018，28（3）：97—99.

[2]? ? 蘇軍波.基于優化的啟發式算法進行排課的研究[D].長春：東北師范大學，2018.

[3]? ? 蔣中云.基于改進蟻群算法的機房排課系統設計與實現[J].信息技術，2014，（2）：56—59.

[4]? ? 張媛.基于禁忌搜索法的排課系統設計與應用[J].電子設計工程，2018，26（16）：40—44.

[5]? ? 高健，廖斌華，高培.基于改進模擬退火算法的中學排課問題[J].工業控制計算機，2018，31（1）：101—102+104.

[6]? ? 張宸瑞.布谷鳥算法的含分布式電源配電網最優潮流優化[J].現代電子技術，2017，40（15）：159—162.

[7]? ? 李靜，趙建平.高校排課系統優化模型的可行性研究[J].數學的實踐與認識，2018，48（20）：234—243.

[8]? ? 馬衛，孫正興，李俊樓. 基于Powell局部搜索策略的全局優化布谷鳥算法[J]. 計算機應用研究，2015，32（6）：1667—1675.

[9]? ? 王凡，賀興時，王燕. 基于高斯擾動的布谷鳥搜索算法[J]. 西安工程大學學報，2011，25（4）：566—569.

[10]? 劉鳳龍，陳曦，曹敦. 基于差分演化的K-均值聚類算法[J]. 計算技術與自動化. 2010，19（01）：48—50.

[11]? SU Gan-than. Multi-objective differential evolution with diversity enhancement[J]. Journal of Zhejiang University，2010，11（07）：538—543.

[12]? MEHTA P，BHATT P，PANDYA V. Optimized coordinated control of frequency and voltage for distributed generating system using Cuckoo Search Algorithm [J]. Ain Shams Engineering Journal，2018，9（4）：1855—1864.

[13]? 崔妍，王權，王康，等. 排課問題的數學模型[J].沈陽工程學院學報：自然科學版，2016，12（3）：276—278+288.

[14]? YANG Xin-she，SUASH D. Multiobjective cuckoo search for design optimization[J]. Computer & Operations and Research，2013，40：1616—1624.