多樣性指數(shù)與頭腦風(fēng)暴算法研究

沈兆琪　曹倬銘　王文國

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

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

DOIDOI：10.11907/rjdk.172450

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：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引言

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

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

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

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

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

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

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

圖1BSO算法流程

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

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

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

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

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

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

ξ值按如下公式計算得到：

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

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

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

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

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

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

H=-∑ni=1pilogpi2（4）

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

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

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

3仿真測試與分析

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

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

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

4結(jié)語

本文在深入研究原始頭腦風(fēng)暴算法的基礎(chǔ)上，首次引入香農(nóng)多樣性指數(shù)來選擇初始種群，以便獲得最接近最優(yōu)解的出發(fā)點進(jìn)行尋優(yōu)。仿真實驗結(jié)果表明，改進(jìn)的算法能極大提升原始算法的尋優(yōu)效果，在優(yōu)化速度和算法穩(wěn)定性方面有明顯優(yōu)勢。改進(jìn)后的算法易于實現(xià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]楊玉婷，史玉回，夏順仁.基于討論機制的頭腦風(fēng)暴優(yōu)化算法[J].浙江大學(xué)學(xué)報：工學(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].計算機工程與應(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)化算法與基于視頻的非接觸式運動定量分析方法研究[D].杭州：浙江大學(xué)，2015.

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