沈兆琪　曹倬銘　王文國(guó)

摘要：頭腦風(fēng)暴算法是目前僅有的受人類社會(huì)性行為啟發(fā)的優(yōu)化算法，該算法和其它群體智能算法一樣，存在執(zhí)行效率低和收斂速度慢等缺點(diǎn)。首次定義了一個(gè)香農(nóng)多樣性指數(shù)來(lái)估算樣本群落的多樣性以及均勻性，并對(duì)原始頭腦風(fēng)暴優(yōu)化算法進(jìn)行多次初始化，從而有效加快算法后期的收斂性。利用6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)改進(jìn)后的算法進(jìn)行了可行性驗(yàn)證，統(tǒng)計(jì)分析后表明，該算法只要選擇多樣性及均勻性足夠好的初始種群，就能顯著減少迭代次數(shù)。改進(jìn)后的頭腦風(fēng)暴算法在執(zhí)行效率和收斂速度上都有所提高。

關(guān)鍵詞：頭腦風(fēng)暴算法；多樣性指數(shù)；均勻性；收斂速度

DOIDOI：10.11907/rjdk.172450

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2018）003007103

英文摘要Abstract：Brain storm is the only swarm intelligence algorithm with origin from modeling human activities， which can help solve some NP problems but often behaves odd and converges slowly. To overcome its shortcomings， a new idea of diversity index arising from ecology is introduced for brain storm optimization， which will measure diversity and uniformity of a solution group， and help us select a good starting point for optimization. Simulation tests with 6 benchmark functions have been conducted， and results show that the improved brain storm optimization with diversity index can speed up convergence and reduce number of iterations significantly.

英文關(guān)鍵詞Key Words：brain storm； diversity index； uniformity； convergence rate

0引言

群體智能算法是一種基于隨機(jī)搜索機(jī)制的優(yōu)化方法，具有靈活應(yīng)對(duì)群體內(nèi)部和外部搜索環(huán)境變化的能力，即當(dāng)搜索條件多變或自身的某些個(gè)體失敗時(shí)，能夠自組織逃離并發(fā)現(xiàn)更優(yōu)的位置。群體智能算法與傳統(tǒng)的完備算法相比，盡管不一定能找到最優(yōu)解，但可以確保在短時(shí)間內(nèi)找到較優(yōu)質(zhì)的解。由于其在解決優(yōu)化問(wèn)題上具有獨(dú)特的優(yōu)勢(shì)，群體智能算法應(yīng)用于很多實(shí)際問(wèn)題中，如機(jī)器人控制、無(wú)人駕駛交通工具、社會(huì)性行為預(yù)測(cè)、通信網(wǎng)絡(luò)加強(qiáng)、醫(yī)學(xué)圖像處理等。然而這些算法常常存在易陷入局部最優(yōu)、早熟或收斂過(guò)慢等問(wèn)題。

大多數(shù)經(jīng)典算法是受低等生物的社會(huì)性行為啟發(fā)的，但長(zhǎng)期沒(méi)有由人類的社會(huì)行為啟發(fā)而提出的智能算法。2011年史玉回[12]提出了頭腦風(fēng)暴優(yōu)化算法。頭腦風(fēng)暴優(yōu)化算法是一種非常有潛力的方法，通常能夠產(chǎn)生超出經(jīng)典智能算法的結(jié)果。

目前，頭腦風(fēng)暴優(yōu)化算法的研究與應(yīng)用還處于初級(jí)階段。許多人在過(guò)去的幾年中嘗試對(duì)頭腦風(fēng)暴優(yōu)化算法進(jìn)行各種研究及改進(jìn)。史玉回等[3]提出了引入兩種組件提高傳統(tǒng)頭腦風(fēng)暴優(yōu)化的性能，第一個(gè)組件使用一個(gè)簡(jiǎn)單分組操作符的分組方法（SGM），代替聚類方法從而減輕算法的計(jì)算負(fù)擔(dān)；第二個(gè)組件使用一個(gè)想法不同的策略（IDS）代替高斯隨機(jī)策略來(lái)創(chuàng)建操作符；Jingqian Xue等[4]提出了一種新的基于頭腦風(fēng)暴過(guò)程的多目標(biāo)優(yōu)化算法（MOBSO），在目標(biāo)空間采用了聚類策略，并通過(guò)兩種不同的變異算子——高斯變異和柯西變異產(chǎn)生新個(gè)體；史玉回等[5]在原始頭腦風(fēng)暴優(yōu)化算法基礎(chǔ)上改進(jìn)了新個(gè)體的生成和選擇策略。首先根據(jù)個(gè)體在每個(gè)維度的動(dòng)態(tài)范圍調(diào)整步長(zhǎng)，然后用一個(gè)批處理模式生成新個(gè)體并選擇新個(gè)體；楊玉婷等[6]引入分組合作機(jī)制以優(yōu)化算法的實(shí)現(xiàn)過(guò)程，提出了基于討論機(jī)制的頭腦風(fēng)暴優(yōu)化算法，同時(shí)進(jìn)一步引入差分步長(zhǎng)從而避免算法進(jìn)入局部最優(yōu)。頭腦風(fēng)暴優(yōu)化算法迅速發(fā)展，不同領(lǐng)域都開(kāi)展了應(yīng)用研究[712]。

頭腦風(fēng)暴算法的改進(jìn)算法依然存在缺點(diǎn)，如執(zhí)行效率低和收斂速度慢等。為克服此類缺陷，本文將首次定義一個(gè)香農(nóng)多樣性指數(shù)來(lái)估算樣本群落的多樣性以及均勻性，并對(duì)原始頭腦風(fēng)暴優(yōu)化算法進(jìn)行多次初始化，從而有效加快算法后期的收斂性。

1基本頭腦風(fēng)暴優(yōu)化算法

頭腦風(fēng)暴優(yōu)化（Brain Storm Optimization， BSO）算法是受頭腦風(fēng)暴過(guò)程啟發(fā)而產(chǎn)生的優(yōu)化算法。頭腦風(fēng)暴過(guò)程的核心思想是將一群不同背景的人聚集起來(lái)，就同一個(gè)問(wèn)題進(jìn)行頭腦風(fēng)暴，為待解決問(wèn)題提出大量解決方案，最后通過(guò)交流及方案的融合共同解決問(wèn)題。在面對(duì)許多問(wèn)題時(shí)，個(gè)人的能力有限，但若是由一群來(lái)自不同背景的人進(jìn)行頭腦風(fēng)暴，通?？梢詷O大程度地提高解決問(wèn)題的可能性。

基于人類的頭腦風(fēng)暴過(guò)程，史玉回提出了BSO算法。BSO算法過(guò)程簡(jiǎn)單，算法中的毎個(gè)個(gè)體都代表一個(gè)潛在的問(wèn)題解，算法包含3個(gè)操作：初始化、聚類和更新個(gè)體，如圖1所示。

圖1BSO算法流程

BSO算法實(shí)現(xiàn)過(guò)程中，通過(guò)kmeans聚類算法將n個(gè)個(gè)體聚成m個(gè)類；更新個(gè)體則根據(jù)概率選擇4種方式進(jìn)行，分別為類中心添加隨機(jī)值、個(gè)體添加隨機(jī)值、兩個(gè)類中心融合添加隨機(jī)值、兩個(gè)隨機(jī)個(gè)體融合添加隨機(jī)值。融合過(guò)程可用以下公式表示：

xdcombined=vxd1+（1-v）xd2（1）

式（1）中，xcombined是隨機(jī)選中的個(gè)體xd1和xd2融合生成的個(gè)體，d是d維上的取值；v∈[0，1]是一個(gè)符合均勻分布的隨機(jī)數(shù)。

添加隨機(jī)值生成新個(gè)體的過(guò)程按式（2）進(jìn)行：

xdnew=xdselect+ξ×n（μ，σ）（2）

式（2）中，xdnew是新生成個(gè)體的d維值，xdselect是隨機(jī)選中個(gè)體的d維值，n（μ，σ）是均值為μ、方差為σ的一個(gè)高斯隨機(jī)函數(shù)，ξ是步長(zhǎng)，用來(lái)控制隨機(jī)擾動(dòng)幅度。

ξ值按如下公式計(jì)算得到：

ξ=logsig0.5Nmax_gen-Ncur_genkrand（）（3）

式（3）中，logsig（）是對(duì)數(shù)變換函數(shù)，k用來(lái)控制logsig（）的變化速率， rand（）是0-1之間符合均勻分布的隨機(jī)值。

2改進(jìn)的頭腦風(fēng)暴算法

在上述基本頭腦風(fēng)暴算法搜索機(jī)制中，初始化步驟僅隨機(jī)產(chǎn)生n個(gè)個(gè)體，這些初始解實(shí)際上距離最優(yōu)解可能有很大的偏離，使得后續(xù)的尋優(yōu)過(guò)程很漫長(zhǎng)或者幾乎不可達(dá)?；谶@一考慮，本文將首次引進(jìn)一個(gè)多樣性指數(shù)來(lái)評(píng)估初始種群的多樣性以及均勻性。

新算法根據(jù)兩個(gè)判定條件選擇出最有潛力或最優(yōu)秀的初始種群：①種群多樣性，判斷依據(jù)是群內(nèi)類的數(shù)目越多，種群多樣性就越復(fù)雜，越能夠包容全局最優(yōu)；②均勻性，用來(lái)描述群內(nèi)各個(gè)物種的相對(duì)豐度或所占比例，即在類數(shù)目相同條件下，群內(nèi)所有類中的個(gè)體數(shù)量越均勻越好。

多樣性指數(shù)是一個(gè)統(tǒng)計(jì)量，通常被用來(lái)描述一個(gè)群落或種群的多樣性。在生態(tài)學(xué)中，往往使用香農(nóng)多樣性指數(shù)估計(jì)群落多樣性，其公式如下：

H=-∑ni=1pilogpi2（4）

式（4）中，n代表種群總數(shù)，pi是第i個(gè)種群占總種數(shù)的比值。種群數(shù)越多，或者個(gè)體分配越均勻，則多樣性指數(shù)越高，對(duì)應(yīng)的群落越優(yōu)秀。

香農(nóng)多樣性指數(shù)中包含兩個(gè)重要部分：種群數(shù)目及每個(gè)種群之間個(gè)體分配的均勻性。H值的大小取決于每個(gè)種群之間個(gè)體分配是否均勻，均勻性越大H值就越大，反之則越小。因此，上述香農(nóng)多樣性指數(shù)既可以表示種群多樣性，也可以反映種群均勻性。根據(jù)這兩個(gè)判定條件挑選出相對(duì)優(yōu)秀的初始群，就能確保BSO算法的正確方向和收斂速度，從而平衡控制算法的全局搜索方向和局部搜索能力。

改進(jìn)后的算法流程如下：①多次初始化并聚類分析；②用多樣性指數(shù)估計(jì)種群的多樣性和均勻性，挑選出最有潛力的初始種群；③更新個(gè)體等后續(xù)BSO操作。

3仿真測(cè)試與分析

為了評(píng)測(cè)改進(jìn)頭腦風(fēng)暴算法的效果，選取了6個(gè)測(cè)試函數(shù)進(jìn)行測(cè)試，分別為Sphere、Step、Griewank、Rastrigin、Rosenbrock、Schaffer。其中6個(gè)經(jīng)典函數(shù)中，Sphere、Step是單模函數(shù)，其余4個(gè)函數(shù)是多模函數(shù)。所采用的6 個(gè)測(cè)試函數(shù)及其值域范圍見(jiàn)表1。

改進(jìn)算法的主要參數(shù)取值與原始BSO算法中對(duì)應(yīng)參數(shù)一致，其它參數(shù)根據(jù)經(jīng)驗(yàn)設(shè)定，所有參數(shù)取值如表2所示。

仿真實(shí)驗(yàn)對(duì)6個(gè)測(cè)試函數(shù)進(jìn)行50次獨(dú)立測(cè)試，并對(duì)所得的優(yōu)化結(jié)果進(jìn)行對(duì)比分析。實(shí)驗(yàn)仿真平臺(tái)為：Intel（R） Pentium E6500，CPU 主頻2.93GHz，2GB內(nèi)存，Windows 7 操作系統(tǒng)下的MATLAB 7.8 。 圖2、表3分別為Sphere函數(shù)H值曲線對(duì)比和6個(gè)測(cè)試函數(shù)的收斂過(guò)程對(duì)比?？梢钥闯觯灰x擇多樣性及均勻性好的初始種群，就能顯著減少迭代次數(shù)。

4結(jié)語(yǔ)

本文在深入研究原始頭腦風(fēng)暴算法的基礎(chǔ)上，首次引入香農(nóng)多樣性指數(shù)來(lái)選擇初始種群，以便獲得最接近最優(yōu)解的出發(fā)點(diǎn)進(jìn)行尋優(yōu)。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的算法能極大提升原始算法的尋優(yōu)效果，在優(yōu)化速度和算法穩(wěn)定性方面有明顯優(yōu)勢(shì)。改進(jìn)后的算法易于實(shí)現(xiàn)，對(duì)處理單模問(wèn)題和多模問(wèn)題均表現(xiàn)出良好的潛力及可塑性。

參考文獻(xiàn)參考文獻(xiàn)：

[1]SHI Y. Brain storm optimization algorithm[C].Springer Berlin Heidelberg，2011：303309.

[2]SHI Y. An optimization algorithm based on brainstorming process[J].International Journal of Swarm Inteligence Research（IJSIR），2011，2（4）：3562.

[3]ZHAN AH，ZHANG J，SHI YH，et al.A modified brain storm optimization[C]. In IEEE Congress on Evolutionary Computation， Brisbane，QLD，2012：18.

[4]XUE J，WU Y，SHI Y，et al.Brain storm optimization algorithm for multiobjective optimization problems[C].Springer Berlin Heidelberg，2012：513519.

[5]ZHOU D，SHI Y，CHENG S.Brain storm optimization algorithm with modified stepsize and individual generation[C].Springer Berlin Heidelberg，2012：243252.

[6]楊玉婷，史玉回，夏順仁.基于討論機(jī)制的頭腦風(fēng)暴優(yōu)化算法[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2013，47（10）：17051711.

[7]SUN C，DUAN H，SHI Y.Optimal satellite formation reconfiguration based on closedloop brain storm optimization[J].IEEE Computational Intelligence Magazine，2013，8（4）：3951.

[8]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.

[9]KENNEDY J， KENNEDY J F， EBERHART R C， et al. Swarm intelligence[M]. Morgan Kaufmann，2001：123265.

[10]余建平，周新民，陳明.群體智能典型算法研究綜述[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（25）：7074.

[11]DUAN H，LI S，SHI Y.Predatorprey based brain storm optimization for DC brushless motor[J].IEEE Transactions on Magnetics，2013，49（10）：53365340.

[12]楊玉婷.頭腦風(fēng)暴優(yōu)化算法與基于視頻的非接觸式運(yùn)動(dòng)定量分析方法研究[D].杭州：浙江大學(xué)，2015.

責(zé)任編輯（責(zé)任編輯：杜能鋼）