差分進(jìn)化布谷鳥算法在實(shí)驗(yàn)室排課中的應(yīng)用

彭勇　陳俞強(qiáng)

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

關(guān)鍵詞：實(shí)驗(yàn)室排課;布谷鳥算法;二部圖;差分進(jìn)化;課元;排課模型

中圖分類號(hào)：TP319? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：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

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

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

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

1? ?高校排課問題數(shù)學(xué)描述

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

1.1? ?變量表示

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

表1? ?課元示例

其中，M = {M1，M2，…，Mm}為所有課元構(gòu)成的集合，按照班級(jí)c（·） = βs人數(shù)從大到小排列;函數(shù)h（·）用來(lái)提取課元Mi所任教的教師為αk;函數(shù)c（·）用來(lái)提取課元Mi所任教的班級(jí)為βs;Wi表示課元Mi對(duì)教室的要求，已經(jīng)按要求的從低到高排序，這種需求主要和課程屬性有關(guān)，有些課程操作性非常強(qiáng)，就需要普通機(jī)房;有的課程以講解為主，就需求多媒體教室，但在機(jī)房上可也以，為了簡(jiǎn)化排課模型，對(duì)部分理論教學(xué)，部分上機(jī)實(shí)驗(yàn)的課程，我們統(tǒng)一以機(jī)房為準(zhǔn)。教室要求的優(yōu)先級(jí)順序?yàn)閃1：多媒體教室

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

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

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

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

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

（1）

可以將課元Mi的排課結(jié)果Ri■N×T表示為教室和授課時(shí)間之間的有序元素對(duì)（Nj，Tt）構(gòu)成的集合，排課決策變量為：

rijt = 1，Mi課元被按安排在Nj教室Tt時(shí)間段進(jìn)行2個(gè)課時(shí)教學(xué)0，否則? ? ? ? （2）

排課結(jié)果：

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

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

（1）硬約束條件

1）對(duì)教師的約束：在同一個(gè)上課時(shí)段內(nèi)老師只能在一個(gè)班級(jí)上一門課。

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

2）班級(jí)約束：在同一個(gè)上課時(shí)段一個(gè)班級(jí)內(nèi)只能在一個(gè)教室上一門課。

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

3）教室約束：在同一個(gè)上課時(shí)段內(nèi)一個(gè)教室只能安排上一門課程。

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

4）課時(shí)約束：課元Mi的每周的課時(shí)量為Xi，每次課記2個(gè)課時(shí)。

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

5）人數(shù)約束：課元Mi的班級(jí)人數(shù)必須小于實(shí)驗(yàn)室的工位數(shù)，Nj表示實(shí)驗(yàn)室工位數(shù)，c（Mj）表示班級(jí)人數(shù)。

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

（8）

6）教室類型約束：教室N的類型標(biāo)準(zhǔn)必須大于課元Mi的教室要求Wi，函數(shù)L（·）用來(lái)提取教室的類型值。

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

（2）軟約束條件

1）學(xué)習(xí)效果約束

排課時(shí)間段盡量安排在學(xué)習(xí)效果較好的時(shí)間段，即讓學(xué)習(xí)效果：

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

盡可能大。

表2? ?時(shí)間段評(píng)價(jià)值

函數(shù)p（·）用來(lái)提取時(shí)間段Tt所對(duì)應(yīng)的學(xué)習(xí)效果評(píng)估值，根據(jù)我們的問卷調(diào)查和隨機(jī)訪談，對(duì)于絕大部分學(xué)生而言，在上午12節(jié)上課，取得的學(xué)習(xí)效果最好，其次是上午34節(jié)和下午78節(jié)，下午56節(jié)效果更差一些，晚上（9、10節(jié)）和周五的下午78節(jié)的學(xué)習(xí)效果最差，這個(gè)效果評(píng)價(jià)可以根據(jù)季節(jié)和學(xué)校實(shí)際情況進(jìn)行調(diào)整。

2）排課間隔約束

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

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

保持最大，實(shí)際上就是一門課程在同一個(gè)班不能連續(xù)排課，為了提高教學(xué)效果，讓學(xué)生有自行消化吸收已經(jīng)課程復(fù)習(xí)和預(yù)習(xí)時(shí)間，把課程適當(dāng)排散。

3）可用資源約束

排課結(jié)果Ri應(yīng)使未利用教室的座位總和：

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

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

綜上所述，排課問題實(shí)際是一個(gè)整數(shù)線性約束的多目標(biāo)優(yōu)化模型，可以描述為如下：

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

2? ?基于改進(jìn)布谷鳥算法的高校排課

2.1? ?標(biāo)準(zhǔn)布谷鳥算法

根據(jù)文獻(xiàn)[8]所述標(biāo)準(zhǔn)布谷鳥搜索算法，可知布谷鳥尋巢的位置更新公式如下：

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

（14）

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

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

隨機(jī)萊維飛行的計(jì)算：

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

其中，μ和ν都服從正態(tài)分布，φ的計(jì)算公式如下：

φ = ■■? ? ? ?（17）

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

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

其中，α0為常數(shù)，xbest表示最優(yōu)鳥巢位置。

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

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

具體的CS算法流程詳見文獻(xiàn)[9]。

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

2.2? ?差分進(jìn)化布谷鳥搜索算法思想

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

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

1）變異

xi（t）為第t代時(shí)，第i個(gè)鳥巢的位置，隨機(jī)從種群中提取兩個(gè)其他個(gè)體xr1（t）、xr2（t），利用式（20）產(chǎn)生變異個(gè)體vi（t）：

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

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

2）交叉

交叉是對(duì)變異個(gè)體vi（t）和第t代個(gè)體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]區(qū)間均勻分布的隨機(jī)數(shù)，rand[1，d]是[1，d]區(qū)間均勻分布的隨機(jī)整數(shù)，j = 1，2，…，d?？梢钥闯?，候選個(gè)體uij（t）至少有一維的分量是由變異個(gè)體vi（t）貢獻(xiàn)的，種群的多樣性明顯得到提升。

3）選擇

通過適應(yīng)度函數(shù)來(lái)判斷第t代個(gè)體xi（t）與候選個(gè)體ui（t）之間的支配關(guān)系，產(chǎn)生（t+1）代個(gè)體xi（t+1），可以將較優(yōu)的差異化的個(gè)體傳承到下一代。

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

2.3? ?布谷鳥算法的二進(jìn)制轉(zhuǎn)換

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

使用如下公式將鳥巢每個(gè)維度的值映射為二進(jìn)制值：

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

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

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

2.4? ?基于差分進(jìn)化的多目標(biāo)布谷鳥算法

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

圖1? ?基于差分進(jìn)化的多目標(biāo)布谷鳥算法流程圖

2.5? ?解的構(gòu)造

布谷鳥算法的編碼好壞直接影響到算法的計(jì)算復(fù)雜度，令教師的課表作為每個(gè)鳥巢的編碼，編碼位數(shù)由排課規(guī)模決定，其結(jié)構(gòu)示例如下：

表3? ?課元編碼表

表4? ?鳥巢編碼表

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

2.6? ?解的初始化

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

圖2? ?排課問題二部圖構(gòu)造初始解模型

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

2.7? ?基于改進(jìn)布谷鳥的多目標(biāo)排課算法

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

3.1? ?實(shí)驗(yàn)環(huán)境

軟件環(huán)境：Windows 7 64位，Matlab 2016a;

硬件環(huán)境：CPU：Intel（R） i7-77003.60GHz;內(nèi)存：8.00GB;硬盤：128G SSD+1TB。

3.2? ?參數(shù)設(shè)置

本文實(shí)驗(yàn)中參數(shù)設(shè)置如下：種群規(guī)模為150，迭代次數(shù)為200，淘汰概率pα = 0.25，變異因子F = 0.35，交叉概率 CR = 0.25，目標(biāo)函數(shù)權(quán)值因子C1、C2、C3分別取0.4、0.3、0.3。

圖3? ?基于改進(jìn)布谷鳥的多目標(biāo)排課算法

3.3? ?結(jié)果分析

（1）基于差分進(jìn)化的多目標(biāo)二進(jìn)制布谷鳥算法（IMBCS）標(biāo)準(zhǔn)二進(jìn)制布谷鳥算法（BCS）的性能比較

1）收斂性比較

object[1]

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

object[1]

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

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

2）多樣性比較

mean_rank_size，maximum generation=200

大小

mean_rank_size，maximum generation=200

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

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

3）排課效果比較

表5? ?排課性能評(píng)估與對(duì)比表

從表5可得，IMBCS算法比起B(yǎng)CS算法在操作時(shí)間上略有增加，主要由于IMBCS算法增加了變異、交叉、選擇計(jì)算，但由于采取多線程對(duì)IMBCS算法進(jìn)行了加速，所以增加不多，但在排課質(zhì)量指標(biāo)（學(xué)習(xí)效果、排課間隔、剩余可用資源）上均較大優(yōu)于BCS算法。

4? ?結(jié)? 論

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

參考文獻(xiàn)

[1]? ? 張媛，祁蘭.高校實(shí)驗(yàn)室排課系統(tǒng)的研究與開發(fā)[J].榆林學(xué)院學(xué)報(bào)，2018，28（3）：97—99.

[2]? ? 蘇軍波.基于優(yōu)化的啟發(fā)式算法進(jìn)行排課的研究[D].長(zhǎng)春：東北師范大學(xué)，2018.

[3]? ? 蔣中云.基于改進(jìn)蟻群算法的機(jī)房排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].信息技術(shù)，2014，（2）：56—59.

[4]? ? 張媛.基于禁忌搜索法的排課系統(tǒng)設(shè)計(jì)與應(yīng)用[J].電子設(shè)計(jì)工程，2018，26（16）：40—44.

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

[6]? ? 張宸瑞.布谷鳥算法的含分布式電源配電網(wǎng)最優(yōu)潮流優(yōu)化[J].現(xiàn)代電子技術(shù)，2017，40（15）：159—162.

[7]? ? 李靜，趙建平.高校排課系統(tǒng)優(yōu)化模型的可行性研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2018，48（20）：234—243.

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

[9]? ? 王凡，賀興時(shí)，王燕. 基于高斯擾動(dòng)的布谷鳥搜索算法[J]. 西安工程大學(xué)學(xué)報(bào)，2011，25（4）：566—569.

[10]? 劉鳳龍，陳曦，曹敦. 基于差分演化的K-均值聚類算法[J]. 計(jì)算技術(shù)與自動(dòng)化. 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]? 崔妍，王權(quán)，王康，等. 排課問題的數(shù)學(xué)模型[J].沈陽(yáng)工程學(xué)院學(xué)報(bào)：自然科學(xué)版，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.