袁清晨 程夢(mèng)杰 李時(shí)東 錢楷

摘要：群智能優(yōu)化算法已廣泛用于科學(xué)研究中，主要模擬自然界中的生物種群行為，灰狼優(yōu)化算法是一種模擬狼群捕獵模式的元啟發(fā)式算法。針對(duì)灰狼算法存在的局部最優(yōu)及收斂精度不高的問(wèn)題，采用種群競(jìng)爭(zhēng)策略和并行化技術(shù)來(lái)改進(jìn)算法，并用四個(gè)基準(zhǔn)函數(shù)對(duì)所提出方法進(jìn)行測(cè)試。結(jié)果表明，改進(jìn)算法較原算法提高了收斂速度和精度，且有效減少了局部最優(yōu)的情況。

關(guān)鍵詞：群智能算法；并行化技術(shù)；種群競(jìng)爭(zhēng)策略；灰狼優(yōu)化算法

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）08-0104-03

近幾十年來(lái)，人們提出了許多基于生物行為的算法，如進(jìn)化算法、群體智能等，很多算法應(yīng)用于電源的優(yōu)化配置[1]、路徑優(yōu)化[2]、圖像分割處理[3]等方面。灰狼算法[4]是模擬狼群捕獵過(guò)程的優(yōu)化算法，最初是由S.Mirjalili等學(xué)者2015年提出的，針對(duì)灰狼算法過(guò)早收斂、易陷入局部最優(yōu)等缺點(diǎn)，人們做了大量的改進(jìn)研究。Pan T S， Dao T K[5]采用了并行化和反向?qū)W習(xí)的種群溝通策略；Nasrabadi M S， Sharafi Y[6]對(duì)采用種群交流策略改進(jìn)算法；牛家彬等[7]把動(dòng)態(tài)權(quán)重和動(dòng)態(tài)種群結(jié)合起來(lái)提高收斂速度的同時(shí)保證了解的質(zhì)量；崔明朗等[8]在尋優(yōu)過(guò)程中加入了觀察策略，且對(duì)收斂因子做了改進(jìn)。

本文針對(duì)常規(guī)灰狼算法的缺點(diǎn)，提出以下改進(jìn)方法：有多個(gè)狼群并行實(shí)施常規(guī)灰狼算法，在達(dá)到一定迭代次數(shù)后讓狼群相互競(jìng)爭(zhēng)，剔除不良個(gè)體并更新種群，同時(shí)為了驗(yàn)證改進(jìn)算法的性能，進(jìn)行了仿真實(shí)驗(yàn)。

1 灰狼算法簡(jiǎn)介

狼群的組織結(jié)構(gòu)根據(jù)領(lǐng)導(dǎo)權(quán)力進(jìn)行排序，主要分為四個(gè)等級(jí)：、、、，高等級(jí)的狼對(duì)低等級(jí)的狼有領(lǐng)導(dǎo)權(quán)。在狩獵過(guò)程中，主要尋優(yōu)過(guò)程是由狼分散包圍獵物，其他三個(gè)等級(jí)根據(jù)收集到的信息指揮狼的移動(dòng)方向，并決定是否更新自己的位置，當(dāng)滿足終止條件以后，輸出最優(yōu)解。

在狩獵過(guò)程中，獵物位置與灰狼位置可用式（1）-（2）表示：

其中：表示當(dāng)前迭代次數(shù)，為獵物的方向向量，為狼群中某狼的位置向量，為下一步移動(dòng)方向向量，為獵物的移動(dòng)系數(shù)。通過(guò)調(diào)整系數(shù)向量來(lái)控制搜索獵物的范圍，當(dāng)時(shí)，擴(kuò)大搜索范圍尋找全局最優(yōu)；當(dāng)時(shí)，縮小搜索范圍尋找局部最優(yōu)。

其中：為收斂因子，隨著迭代次數(shù)從2線性遞減到0，max為最大迭代次數(shù)，、為0到1之間的隨機(jī)數(shù)。

當(dāng)狼群完成對(duì)獵物的包圍，由狼指揮狼和狼帶領(lǐng)狼群收縮包圍圈，狼群的位置更新用式（6）、（7）、（8）表示：

其中為狼的位置，為狼的位置，為狼的位置，為當(dāng)前狼的位置向量，、、為隨機(jī)向量。式（7）分別確定了狼朝向狼、狼、狼的前進(jìn)方向與步長(zhǎng)。

2 灰狼算法的改進(jìn)

2.1 競(jìng)爭(zhēng)策略

競(jìng)爭(zhēng)策略灰狼算法是以常規(guī)灰狼算法為基礎(chǔ)的，在尋優(yōu)區(qū)域內(nèi)有個(gè)狼群進(jìn)行獨(dú)立尋優(yōu)。兩個(gè)狼群的競(jìng)爭(zhēng)可以理解為兩個(gè)局部最優(yōu)群體的比較，狼群中的個(gè)體都會(huì)逐步逼近狼群的狼，因此通過(guò)比較兩個(gè)狼群中的狼的適應(yīng)度判斷狼群的優(yōu)劣性，適應(yīng)度高的狼群留下來(lái)，適應(yīng)度低的狼群則被兼并。為了避免比較過(guò)程中出現(xiàn)局部最優(yōu)的情況，對(duì)兩個(gè)狼群進(jìn)行相似度判斷，當(dāng)相似度小于一定值時(shí)才可以進(jìn)行比較，否則重新初始化。

2.2 數(shù)學(xué)模型

2.2.1 相似度判定

設(shè)狼群的規(guī)模為，比較狼群與狼群的相似程度，狼群中按照適應(yīng)度值從大到小排列，狼群為，狼群為，計(jì)算公式如式（9）表示：

2.2.2 競(jìng)爭(zhēng)方案

已知狼群與狼群，當(dāng)狼群與狼群滿足相似度條件并達(dá)到指定的迭代次數(shù)時(shí)，可以開始競(jìng)爭(zhēng)。當(dāng)時(shí)，則狼群兼并狼群，淘汰狼群中處于領(lǐng)導(dǎo)地位的狼、狼、狼，將狼群中的狼并入狼群組成新狼群；否則狼群兼并狼群，作相同處理。

2.3 算法流程

（1）初始化個(gè)狼群位置以及系數(shù)、、，每一個(gè)狼群都通過(guò)灰狼算法獨(dú)立進(jìn)行尋優(yōu)；（2）計(jì)算各個(gè)狼群的適應(yīng)度；（3）根據(jù)公式更新各狼群位置與相關(guān)參數(shù)；（4）可得出個(gè)狼群中的頭狼適應(yīng)度，指定在第次迭代，兩兩展開競(jìng)爭(zhēng)，組成新狼群后再進(jìn)行常規(guī)尋優(yōu)或是繼續(xù)參與競(jìng)爭(zhēng)；（5）終止：達(dá)到函數(shù)的預(yù)定值或者達(dá)到最大迭代次數(shù)時(shí)，記錄最優(yōu)個(gè)體的值以及其適應(yīng)度。

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

3.1 實(shí)驗(yàn)設(shè)置

仿真將采用4種不同的算法（GWO常規(guī)灰狼算法；GWO1采用動(dòng)態(tài)權(quán)值的灰狼算法；GWO2采用改進(jìn)收斂因子的灰狼算法；GWO3采用競(jìng)爭(zhēng)機(jī)制的并行灰狼算法），基于4個(gè)單目標(biāo)無(wú)約束的標(biāo)準(zhǔn)測(cè)試函數(shù)（如表1所示）測(cè)試比較各算法的收斂速度與求解精度。所有算法終止條件是滿足最大迭代次數(shù)500，群體規(guī)模都設(shè)置為30。

3.2 算法性能分析

4種算法對(duì)4個(gè)函數(shù)的求解結(jié)果見(jiàn)表2，列出了4種算法基于4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)分別運(yùn)行10次所取得的最優(yōu)值、最差值、平均最優(yōu)值及標(biāo)準(zhǔn)方差，并繪制單峰函數(shù)（、）、多峰多極值函數(shù)（、）的收斂曲線圖。

在單峰值函數(shù)的優(yōu)化過(guò)程中，各算法都有較好的優(yōu)化性能及較快的收斂速度，從表1看出在“最優(yōu)值”指標(biāo)和最差值方面，GWO3算法的收斂精度最高，然后依次是GWO1、GWO、GWO2，在“標(biāo)準(zhǔn)方差”指標(biāo)方面，求解結(jié)果的穩(wěn)定性排序依次是GWO3、GWO1、GWO2、GWO。由圖1可以看出在優(yōu)化過(guò)程中各算法都存在著局部最優(yōu)的現(xiàn)象，但GWO1的局部最優(yōu)情況最多，由此可見(jiàn)動(dòng)態(tài)權(quán)值的引入雖然可以提高算法的收斂速度與精度，但也會(huì)加劇局部最優(yōu)的產(chǎn)生，相比之下GWO3的局部最優(yōu)現(xiàn)象較少，且在收斂精度及穩(wěn)定性上有很大的提高。

對(duì)多峰值多極值函數(shù)，各算法在“最優(yōu)值”、“最差值”、“平均最優(yōu)值”指標(biāo)上結(jié)果精度基本相同，由圖2可以看出，各算法的局部最優(yōu)情況增多了一些，尤其是采用動(dòng)態(tài)權(quán)值的GWO1算法，采用平均權(quán)值的GWO算法和收斂因子的GWO2算法相對(duì)較輕，而采用競(jìng)爭(zhēng)機(jī)制的GWO3算法有效減少了局部最優(yōu)的出現(xiàn)。

4 結(jié)語(yǔ)

本文提出了競(jìng)爭(zhēng)機(jī)制的并行灰狼算法，設(shè)定有多個(gè)狼群并行實(shí)施常規(guī)灰狼算法，在達(dá)到一定條件后讓狼群間相互競(jìng)爭(zhēng)，剔除不良個(gè)體并更新種群，由仿真結(jié)果可知，相比于其他改進(jìn)，該改進(jìn)方法可以提高算法的收斂精度和速度，在對(duì)多峰值多極值函數(shù)的優(yōu)化過(guò)程中可減少算法陷入局部最優(yōu)。此外，如何將改進(jìn)的算法應(yīng)用到工程中的多目標(biāo)優(yōu)化問(wèn)題是需要進(jìn)一步研究的方向。

參考文獻(xiàn)

[1]張濤，張東方，王凌云.基于灰狼算法的分布式電源優(yōu)化配置[J].水電能源科學(xué)，2018，36（04）：204-207+212.

[2]姚鵬，王宏倫.基于改進(jìn)流體擾動(dòng)算法與灰狼優(yōu)化的無(wú)人機(jī)三維航路規(guī)劃[J].控制與決策，2016，31（04）：701-708.

[3]王鈦，許斌，李林國(guó)，等.基于離散灰狼算法的多級(jí)閾值圖像分割[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016，26（07）：30-35.

[4]Mirjalili S， Mirjalili S M， Lewis A. Grey Wolf Optimizer[J]. Advances in Engineering Software， 2014， 69（3）：46-61.

[5]Pan T S， Dao T K， Nguyen T T， et al. A Communication Strategy for Paralleling Grey Wolf Optimizer[C]// International Conference on Genetic and Evolutionary Computing.Springer International Publishing，2015：253-262.

[6]Nasrabadi M S， Sharafi Y， Tayari M. A parallel grey wolf optimizer combined with opposition based learning[C]// Swarm Intelligence and Evolutionary Computation. IEEE， 2016：18-23.

[7]牛家彬，王輝.一種基于混合策略的灰狼優(yōu)化算法[J].齊齊哈爾大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，34（01）：16-19+32.

[8]崔明朗，杜海文，魏政磊，等.多目標(biāo)灰狼優(yōu)化算法的改進(jìn)策略研究[J].計(jì)算機(jī)工程與應(yīng)用，2018（5）：156-164.