多分支混沌變異的頭腦風(fēng)暴優(yōu)化算法

衣俊艷，施曉東，楊 剛

1.北京建筑大學(xué) 電氣與信息工程學(xué)院 計(jì)算機(jī)系，北京 100044

2.中國(guó)人民大學(xué) 信息學(xué)院，北京 100872

優(yōu)化問(wèn)題是指在一定約束范圍內(nèi)，尋找一組參數(shù)值，使得目標(biāo)函數(shù)得到最優(yōu)。優(yōu)化問(wèn)題在通信、交通、國(guó)防、管理、計(jì)算機(jī)等眾多領(lǐng)域都有著廣泛的應(yīng)用[1]。考慮到實(shí)際工程中優(yōu)化問(wèn)題的特點(diǎn)，需要尋找一種簡(jiǎn)單高效的優(yōu)化方法。因此，群智能優(yōu)化算法開(kāi)始進(jìn)入人們的視野。

群智能（swarn intelligence，SI）[2]算法主要是模擬昆蟲(chóng)、獸群、鳥(niǎo)群等群體進(jìn)行覓食、求偶等群體行為而提出的自適應(yīng)優(yōu)化算法。該類算法是一種隨機(jī)搜索方法，具有靈活應(yīng)對(duì)群體內(nèi)部和外部搜索環(huán)境變化的能力，即當(dāng)搜索條件多變或自身的某些個(gè)體搜索失敗時(shí)，能夠自組織逃離并找到更優(yōu)的位置[3-4]。基于群體智能的思想，國(guó)內(nèi)外學(xué)者提出了多種優(yōu)化算法，例如蟻群優(yōu)化（ant colony optimization，ACO）[5]算法、粒子群優(yōu)化（particle swarm optimization，PSO）[6]算法、人工蜂群（artificial bee colony，ABC）[7]優(yōu)化算法、布谷鳥(niǎo)搜索（cuckoo search，CS）[8]算法等，這些算法具有較強(qiáng)的魯棒性和搜索能力，易于并行實(shí)現(xiàn)，在許多優(yōu)化問(wèn)題中得到了廣泛的研究和應(yīng)用。

大多數(shù)的經(jīng)典群智能算法都來(lái)源于低等生物的群體行為，直到2011年，史玉回[9-10]基于人類思維方式和行為，提出了頭腦風(fēng)暴優(yōu)化（brain storm optimization，BSO）算法。該算法的重點(diǎn)在于模擬人類使用頭腦風(fēng)暴解決問(wèn)題，是受人類群體行為啟發(fā)的群智能優(yōu)化算法。頭腦風(fēng)暴優(yōu)化算法將收斂與發(fā)散操作同時(shí)嵌入到算法的每一次迭代中，具有很強(qiáng)的魯棒性和搜索能力。

群智能優(yōu)化算法普遍存在易陷入局部最優(yōu)，導(dǎo)致早熟收斂的問(wèn)題，BSO算法也不例外。為此，許多研究者提出了改進(jìn)算法。文獻(xiàn)[11]使用k-medians聚類替換BSO算法中的k-means聚類，提高了算法的搜索效率。文獻(xiàn)[12]提出了基于討論機(jī)制的頭腦風(fēng)暴優(yōu)化（discussion mechanism based brain storm optimization，DMBSO）算法，通過(guò)控制組內(nèi)、組間討論次數(shù)，初期加強(qiáng)全局搜索，后期加強(qiáng)局部搜索，有效地避免了算法陷入局部最優(yōu)。文獻(xiàn)[13]提出了目標(biāo)空間的頭腦風(fēng)暴優(yōu)化（brain storm optimization in objective space，BSO-OS）算法，通過(guò)將解集合分為精英類和普通類來(lái)代替BSO 中復(fù)雜的聚類操作，極大地提升了算法搜索效率，降低了算法的復(fù)雜度。文獻(xiàn)[14]提出了一種改進(jìn)的頭腦風(fēng)暴優(yōu)化（modified brain storm optimization，MBSO）算法，使用簡(jiǎn)單分組方法（simple group method，SGM）替換k-means 聚類，并用差分變異替換BSO 算法中的高斯變異，提高了算法的搜索效率和尋優(yōu)精度。

針對(duì)BSO尋優(yōu)精度不高、易陷入局部最優(yōu)的問(wèn)題，本文提出一種多分支混沌變異的頭腦風(fēng)暴優(yōu)化（brain storm optimization based on multi-branch chaotic mutation，MCMBSO）算法。該算法利用混沌序列的遍歷性、多樣性和隨機(jī)性，通過(guò)混合多種混沌序列，擴(kuò)大算法的搜索空間，增強(qiáng)其全局搜索能力。當(dāng)BSO 算法陷入局部最優(yōu)時(shí)，使用多分支混沌變異算子，生成新的解集合，平衡算法搜索時(shí)的收斂和發(fā)散操作，提高算法跳出局部最優(yōu)的能力。

本文介紹了原始BSO 算法的流程和原理、多分支混沌變異的流程以及選取的8 個(gè)混沌映射的解分布情況，并給出了MCMBSO 算法的步驟和流程圖。實(shí)驗(yàn)部分將MCMBSO 與BSO 算法在10 個(gè)經(jīng)典測(cè)試函數(shù)上進(jìn)行了3 個(gè)維度的對(duì)比實(shí)驗(yàn)，并將MCMBSO 與多種算法進(jìn)行了實(shí)驗(yàn)對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，新算法提高了BSO跳出局部最優(yōu)的能力，進(jìn)而提高了算法的尋優(yōu)精度。

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

頭腦風(fēng)暴優(yōu)化算法是一種新興的群智能優(yōu)化算法，其靈感來(lái)自于人群求解問(wèn)題時(shí)集思廣益的群體行為，即頭腦風(fēng)暴過(guò)程。頭腦風(fēng)暴過(guò)程的核心思想是召集一群不同背景的人，對(duì)需要解決的問(wèn)題提出大量的解決方案，最后通過(guò)解決方案的溝通和整合，共同解決問(wèn)題。當(dāng)面臨個(gè)人難以解決的問(wèn)題時(shí)，通過(guò)不同背景的人的大量設(shè)想、大膽假設(shè)、觀點(diǎn)融合，最終能有效提升找到最優(yōu)解決方案的概率。

BSO 算法將頭腦風(fēng)暴過(guò)程中產(chǎn)生的想法抽象為優(yōu)化問(wèn)題解空間中的個(gè)體，每個(gè)個(gè)體都是待求解問(wèn)題的一個(gè)解，所有個(gè)體視為待求解問(wèn)題的解集合，通過(guò)個(gè)體的融合變異產(chǎn)生新的個(gè)體。算法流程如下：

（1）初始化n 個(gè)個(gè)體。

（2）使用k-means 將n 個(gè)個(gè)體聚類，并計(jì)算n 個(gè)個(gè)體的適應(yīng)度值，選擇每個(gè)類中適應(yīng)度值最好的個(gè)體作為該類的聚類中心。

（3）根據(jù)概率選擇是否隨機(jī)生成一個(gè)個(gè)體代替隨機(jī)選擇的一個(gè)聚類中心。

（4）通過(guò)以下四種方式更新個(gè)體，當(dāng)一個(gè)新個(gè)體生成后，與當(dāng)前個(gè)體相比，適應(yīng)度好的個(gè)體作為下次迭代的新個(gè)體。

①隨機(jī)選擇一個(gè)類的聚類中心，添加隨機(jī)值生成新個(gè)體。

②隨機(jī)選擇一個(gè)類的普通個(gè)體，添加隨機(jī)值生成新個(gè)體。

③隨機(jī)選擇兩個(gè)類的聚類中心，合并后添加隨機(jī)值生成新個(gè)體。

④隨機(jī)各選擇兩個(gè)類中的一個(gè)普通個(gè)體，合并后添加隨機(jī)值生成新個(gè)體。

（5）重復(fù)進(jìn)行（4）操作，直到n 個(gè)個(gè)體全部更新完畢，此時(shí)產(chǎn)生n 個(gè)新個(gè)體，完成一次算法迭代。

（6）回到操作（2），再進(jìn)行下一次迭代，直到達(dá)到最大迭代次數(shù)后算法停止。

在BSO 算法中，新個(gè)體通過(guò)一個(gè)或兩個(gè)類中的中心或普通個(gè)體添加隨機(jī)值生成。當(dāng)新個(gè)體基于一個(gè)類生成時(shí)，算法傾向于收斂，當(dāng)新個(gè)體基于兩個(gè)類生成時(shí)，算法傾向于發(fā)散。算法通過(guò)類內(nèi)、類間的交互融合來(lái)實(shí)現(xiàn)個(gè)體的更新，這些操作確保了算法的種群多樣性和生成新個(gè)體的質(zhì)量。此外，BSO添加隨機(jī)值生成新個(gè)體的方式如式（1）所示：

式中，Xdnew是生成新個(gè)體的d維值，Xdselect是選中個(gè)體的d維值，N(μ,σ) 是均值為μ方差為σ的高斯隨機(jī)函數(shù)，ξ是高斯隨機(jī)函數(shù)的系數(shù)，用來(lái)控制擾動(dòng)的幅度，表示為：

式中，logsig( )是S形變換函數(shù)，Imax是最大迭代次數(shù)，I是當(dāng)前迭代次數(shù)，k是改變logsig( )函數(shù)的斜率，rand產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)。

2 多分支混沌變異的頭腦風(fēng)暴優(yōu)化算法

2.1 新解生成分析

在大多數(shù)群智能優(yōu)化算法中，種群中的所有個(gè)體都只趨向于最優(yōu)解。而在頭腦風(fēng)暴優(yōu)化算法中，每個(gè)個(gè)體不僅是目標(biāo)問(wèn)題的解，而且是解集合中的一個(gè)樣例。類似于人類頭腦風(fēng)暴過(guò)程，BSO算法通過(guò)對(duì)解集合中每個(gè)個(gè)體進(jìn)行融合和變異來(lái)生成新的解集合。因此新個(gè)體的生成在BSO算法中具有重要的作用。

傳統(tǒng)的BSO算法使用添加高斯隨機(jī)值來(lái)進(jìn)行新解的生成。根據(jù)正態(tài)分布特性，在式（1）中，當(dāng)μ和σ固定時(shí)，N(μ,σ)的取值幾乎全部集中在(μ-3σ,μ+3σ)內(nèi)。如圖1所示，是μ=0,σ=1 時(shí)的高斯分布曲線，概率密度集中在分布的中心，并以指數(shù)形式向兩邊遞減，其99.73%的面積集中在平均值左右3個(gè)標(biāo)準(zhǔn)差3σ的范圍內(nèi)。而logsig( )∈( 0,1) ，可知系數(shù)ξ∈( 0,1) 。因此，高斯變異由系數(shù)ξ和隨機(jī)函數(shù)N(μ,σ)乘積所得的變異量始終在一個(gè)固定的范圍內(nèi)。

圖1 高斯分布圖Fig.1 Gaussian distribution

根據(jù)正態(tài)分布的特點(diǎn)，高斯變異側(cè)重于搜索原個(gè)體周?chē)木植繀^(qū)域，局部搜索能力較強(qiáng)，但引導(dǎo)個(gè)體跳出局部最優(yōu)的能力較弱，容易導(dǎo)致種群搜索停滯。為了增強(qiáng)BSO 算法跳出局部最優(yōu)解的能力，本文在算法陷入局部最優(yōu)時(shí)加入多分支混沌變異算子。

2.2 多分支混沌變異算子

2.2.1 混沌與混沌解

混沌是指確定性系統(tǒng)中出現(xiàn)的一種貌似無(wú)規(guī)律的復(fù)雜運(yùn)動(dòng)形態(tài)，其行為復(fù)雜且類似于隨機(jī)，因此可用來(lái)進(jìn)行隨機(jī)搜索。對(duì)于確定性非線性系統(tǒng)，具有內(nèi)在隨機(jī)性的解稱為混沌解。不同于確定性解和隨機(jī)解，混沌解具有遍歷性、隨機(jī)性、初值敏感性、長(zhǎng)期不可預(yù)測(cè)性等自身獨(dú)有的特性[15]。

在優(yōu)化領(lǐng)域，混沌映射生成的混沌解常用于種群初始化，個(gè)體的選擇、交叉、變異等操作，而且通常能取得比隨機(jī)數(shù)更好的結(jié)果。混沌映射不斷迭代后產(chǎn)生混沌序列，每一次迭代即是實(shí)現(xiàn)一次搜索，通過(guò)不斷迭代，即可實(shí)現(xiàn)對(duì)混沌空間的遍歷搜索。

2.2.2 多分支混沌變異

本文選取8個(gè)混沌映射，設(shè)計(jì)了一種多分支混沌變異算子，當(dāng)原始BSO算法搜索陷入局部最優(yōu)時(shí)，使用多分支混沌變異生成新個(gè)體，增強(qiáng)算法跳出局部最優(yōu)解的能力。

對(duì)于m維優(yōu)化問(wèn)題，f(X)=f(x1,x2,…,xd,…,xm),xd∈[a,b],a和b分別是個(gè)體的上下界。多分支混沌變異算子的流程如下：

（1）從8個(gè)混沌映射中選取一個(gè)映射用來(lái)生成m維混沌變量，選取公式如下：

其中，p∈( 1,8 )是選取的混沌映射序號(hào)，i是混沌序列的迭代次數(shù)。

（2）在( 0,1) 之間產(chǎn)生m個(gè)隨機(jī)數(shù)作為m維混沌變量c(p)1各分量的初始值。

（3）根據(jù)所選取的混沌映射，通過(guò)K次迭代產(chǎn)生一個(gè)長(zhǎng)度為K，包含K個(gè)m維混沌變量的混沌序列

（4）通過(guò)載波映射[16]，將混沌特性引入到選中個(gè)體周?chē)磉_(dá)式如下：

式中，Xselect是選中個(gè)體的d維值是原個(gè)體所在簇的簇中心的d維值。

（5）使用式（4）生成K個(gè)在原個(gè)體周?chē)哂谢煦缣匦缘膍維搜索點(diǎn)后，將這些點(diǎn)帶入到測(cè)試函數(shù)中進(jìn)行檢驗(yàn)，選取其中適應(yīng)度值最小的搜索點(diǎn)Xmin作為待更新個(gè)體。

（6）比較最小搜索點(diǎn)Xmin與第idx個(gè)原個(gè)體Xidx的適應(yīng)度值，其中idx∈[1,n] 。如果滿足f(Xmin)＜f(Xidx)，即可將Xidx更新為Xmin。

多分支混沌變異算子中，混沌映射的選取采用隨機(jī)選擇的策略，這樣既保證了混沌搜索的多樣性，更避免了算法復(fù)雜度的增加。此外，算法陷入局部最優(yōu)是指當(dāng)算法在迭代一定次數(shù)后，全局最優(yōu)適應(yīng)度值始終不變。此時(shí)種群中的個(gè)體大都聚集在局部最優(yōu)處，因變異量有限，算法失去跳出局部最優(yōu)解的能力，且種群整體的群體多樣性過(guò)低。因此，通過(guò)使用多分支混沌變異算子，對(duì)個(gè)體嵌入不同的混沌映射序列。這樣不僅擴(kuò)大了混沌搜索的空間，給個(gè)體帶來(lái)更大的變異，增加了個(gè)體信息的多樣性，而且增強(qiáng)了算法跳出局部最優(yōu)的能力，進(jìn)而提高了算法的全局搜索能力和尋優(yōu)精度。

2.2.3 具體混沌映射

不同的混沌映射所產(chǎn)生的混沌序列是完全不同的，其分布或遍歷性質(zhì)有很大的差異。由于混沌序列的不重復(fù)性和遍歷性，使用不同混沌映射的搜索模式在搜索范圍和提高算法精度上都優(yōu)于使用單一的混沌映射。通過(guò)研究多種混沌映射所產(chǎn)生的序列分布情況，本文選取了8個(gè)典型的具有獨(dú)特分布特性的混沌映射，用于構(gòu)成多分支混沌變異算子。經(jīng)過(guò)大量實(shí)驗(yàn)測(cè)試，這8個(gè)混沌映射能有效增強(qiáng)算法跳出局部最優(yōu)解的能力，其描述如下所示：

（1）Cubic 映射。Cubic 映射[17]是處理各種應(yīng)用（如密碼學(xué)）中最常見(jiàn)的混沌映射之一，表達(dá)式為：

其中，ρ=2.59。圖2顯示了Cubic映射迭代500次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖2 Cubic映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.2 Scatter diagram and histogram of chaotic sequences generated by Cubic map

（2）Sine映射。Sine混沌映射是以正弦函數(shù)為基礎(chǔ)的混沌映射[17-18]，表達(dá)式為：

其中，μ∈[0,1] 是控制參數(shù)，當(dāng)μ越趨近于1時(shí)，混沌性越強(qiáng)，此處取μ=1；c( 2)i∈(-1,1) ，此處取c( 2)i的絕對(duì)值，使得c( 2)i∈( 0,1) 。圖3顯示了Sine映射迭代500次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖3 Sine映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.3 Scatter diagram and histogram of chaotic sequences generated by Sine map

（3）Logistic 映射。Logistic 映射[17-18]是研究動(dòng)力系統(tǒng)、混沌等復(fù)雜系統(tǒng)行為的一個(gè)經(jīng)典模型，可以用來(lái)模擬生物種群的生長(zhǎng)行為，因此也叫“蟲(chóng)口模型”，表達(dá)式為：

其中，μ∈( 0,4 ]是控制參數(shù)，當(dāng)μ=4 時(shí)，系統(tǒng)處于全混沌狀態(tài)，具有混沌性；c( 3)i∈( 0,1) 且初始值c( 3 )1≠0.25,0.50,0.75。圖4 顯示了Logistic 映射迭代500 次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖4 Logistic映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.4 Scatter diagram and histogram of chaotic sequences generated by Logistic map

（4）無(wú)限折疊混沌映射（iterative chaotic map with infinite collapses，ICMIC）[17，19]。ICMIC的表達(dá)式為：

其中，μ∈( 0,+∞)，研究表明μ對(duì)表達(dá)式的影響很小，此處取μ=100；c( 4)i∈(-1,1) ，此處取c( 4)i的絕對(duì)值，使得c( 4)i∈( 0,1) 。圖5 顯示了ICMIC 映射迭代500 次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖5 ICMIC映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.5 Scatter diagram and histogram of chaotic sequences generated by ICMIC map

（5）分段線性混沌映射（piecewise linear chaotic map，PWLCM）[17-18]。PWLCM 是多段構(gòu)成的混沌映射，表達(dá)式為：

其中，λ為控制參數(shù)，當(dāng)λ∈( 0,0.5 )時(shí)，c( 5)i∈( 0,1) 。系統(tǒng)具有以下特性：（1）Lyapunov指數(shù)大于0，系統(tǒng)為混沌狀態(tài)。（2）具有一致的不變分布密度函數(shù)和較好的遍歷性。圖6顯示了PWLCM映射迭代500次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖6 PWLCM映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.6 Scatter diagram and histogram of chaotic sequences generated by PWLCM map

（6）Neuron映射。Neuron映射[17]是具有非線性反饋的映射，由雙曲正切函數(shù)和指數(shù)函數(shù)組合構(gòu)成，表達(dá)式為：

其中，η∈[0,1] 是衰減系數(shù)，此處取η=0.5；γ是比例因子，此處取γ=5；c( 6)i∈(-1.5,0.5 )，此處取c( 6)i的絕對(duì)值，并舍去大于1 的值，使得c( 6)i∈( 0,1) 。圖7 顯示了Neuron 映射迭代500 次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖7 Neuron映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.7 Scatter diagram and histogram of chaotic sequences generated by Neuron map

（7）Sinusoidal映射[17-18]。Sinusoidal映射的表達(dá)式為：

其中，μ是控制參數(shù)，此處取μ=2.3。圖8顯示了Sinusoidal映射迭代500次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖8 Sinusoidal映射生成的混沌序列分布散點(diǎn)圖和直方圖Fig.8 Scatter diagram and histogram of chaotic sequences generated by Sinusoidal map

（8）Berboulli Shift 映射。Berboulli Shift 映射[17]是分段線性函數(shù)，表達(dá)式為：

其中，λ為控制參數(shù)，此處取λ=0.4。圖9顯示了Berboulli Shift 映射迭代500 次后混沌序列分布的散點(diǎn)圖和頻率直方圖。

圖9 Berboulli Shift映射生成的混沌序列散點(diǎn)圖和直方圖Fig.9 Scatter diagram and histogram of chaotic sequences generated by Berboulli Shift map

圖2～圖9展示了8個(gè)混沌映射迭代500次后的混沌序列分布散點(diǎn)圖和頻率直方圖。從圖中可以看出，這8個(gè)混沌映射具有不同的分布特性。例如Logistic、Sine、Cubic映射產(chǎn)生的混沌解大多分布在0和1周?chē)籔WLCM映射產(chǎn)生的混沌解分布趨向于0；而ICMIC映射產(chǎn)生的混沌解分布則趨向于1；Neuron映射產(chǎn)生的混沌解分布傾向于0.3 到0.5；Sinusoidal 映射產(chǎn)生的混沌解范圍僅在0.5 到0.9 之間。這些不同的混沌映射產(chǎn)生的不同分布的混沌解，提供了比單一混沌解更大的混沌空間，同時(shí)利用混沌序列的高隨機(jī)性，增加了個(gè)體的變異量，從而有效擴(kuò)大了算法的搜索范圍，增強(qiáng)了算法跳出局部最優(yōu)解的能力。

2.3 算法步驟

MCMBSO算法步驟如下：

步驟1 初始化：在解范圍內(nèi)隨機(jī)生成n個(gè)個(gè)體。

步驟2 聚類：用k-means 將n個(gè)個(gè)體聚類，并計(jì)算適應(yīng)度值，找出每類最優(yōu)個(gè)體作為聚類中心。

步驟3 中心替換：根據(jù)概率隨機(jī)生成一個(gè)個(gè)體替換隨機(jī)選取的聚類中心。

步驟4 根據(jù)概率在一個(gè)簇中選擇中心個(gè)體或普通解作為Xselect，或兩個(gè)簇中各選擇一個(gè)中心個(gè)體或普通解組合作為Xselect。

步驟5 判斷算法是否陷入局部最優(yōu)：若算法重復(fù)迭代20次，最優(yōu)適應(yīng)度值不變，執(zhí)行步驟6，否則轉(zhuǎn)步驟7。

步驟6 根據(jù)式（3）、（4）、（5），使用多分支混沌變異算子更新個(gè)體，完成轉(zhuǎn)步驟9。

步驟7 根據(jù)式（1）、（2），用高斯變異生成新個(gè)體。

步驟8 若新個(gè)體適應(yīng)度值優(yōu)于原個(gè)體，存儲(chǔ)適應(yīng)度好的個(gè)體作為新個(gè)體進(jìn)入下次迭代。

步驟9n個(gè)個(gè)體全部更新完轉(zhuǎn)步驟10，否則轉(zhuǎn)步驟4。

步驟10 若達(dá)到最大迭代次數(shù)，輸出最優(yōu)個(gè)體適應(yīng)度值，算法結(jié)束，否則轉(zhuǎn)步驟2。

MCMBSO流程圖如圖10所示。

圖10 MCMBSO算法流程圖Fig.10 Flowchart of MCMBSO algorithm

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

為了驗(yàn)證MCMBSO 算法解決優(yōu)化問(wèn)題的有效性和可行性，本文從兩方面進(jìn)行仿真對(duì)比實(shí)驗(yàn)。（1）將MCMBSO 與標(biāo)準(zhǔn)BSO 算法在不同的維度下進(jìn)行仿真對(duì)比；（2）將MCMBSO 與遺傳算法（genetic algorithm，GA）、粒子群優(yōu)化（PSO）算法和布谷鳥(niǎo)搜索（CS）算法進(jìn)行仿真對(duì)比。

為了便于對(duì)比分析，實(shí)驗(yàn)使用10 個(gè)經(jīng)典的測(cè)試函數(shù)[20]，如表1 所示。其中f1～f5屬于單峰函數(shù)，f6～f10屬于多峰函數(shù)。單峰函數(shù)在定義域中只有一個(gè)嚴(yán)格局部極大值或極小值，多峰函數(shù)是指在區(qū)間中有多個(gè)相同或不同極值點(diǎn)的函數(shù)。

表1 10個(gè)測(cè)試函數(shù)Table 1 10 test functions

所有算法的實(shí)驗(yàn)在同一平臺(tái)上運(yùn)行，實(shí)驗(yàn)平臺(tái)為Windows 10（64 bit）操作系統(tǒng)下的MATLAB R2018b，硬件條件為Intel?CoreTMi5-9300 CPU 2.40 GHz，16 GB內(nèi)存。

3.1 聚類數(shù)分析

在BSO和MCMBSO算法流程中，分類策略的目的是將解集合收斂到若干較小的范圍，優(yōu)化搜索區(qū)域。在算法多次迭代之后，搜索空間不斷減小，所有解大概率被聚集到一個(gè)小范圍中，增加了算法的收斂能力。因?yàn)楸疚闹饕接懱砑佣喾种Щ煦缱儺愃阕雍髮?duì)BSO算法的改進(jìn)，所以MCMBSO 參照原始BSO 算法，使用kmeans聚類對(duì)解集合進(jìn)行分類操作。k-means算法是一種經(jīng)典的聚類算法，算法本身需經(jīng)過(guò)多次迭代才能將解集合分組，并且聚類數(shù)需要事先指定。

表2展示了BSO 和MCMBSO 算法在單峰函數(shù)f1和多峰函數(shù)f7上，聚類數(shù)分別為2、5、10、20下的尋優(yōu)實(shí)驗(yàn)結(jié)果。其中，BSO算法的各參數(shù)和聚類數(shù)為5時(shí)的平均值來(lái)源于文獻(xiàn)[9]，MCMBSO 算法陷入局部最優(yōu)的判斷條件為重復(fù)迭代20 次，最優(yōu)適應(yīng)度值不變。實(shí)驗(yàn)的種群規(guī)模為100，最大迭代次數(shù)為2 000，優(yōu)化問(wèn)題維度為30。算法對(duì)每個(gè)函數(shù)獨(dú)立運(yùn)行50 次，記錄它們的平均值。其中加粗行代表2、5、10、20 聚類數(shù)下能獲得平均值較優(yōu)的一個(gè)。

由表2可以看出，無(wú)論是BSO還是MCMBSO算法，在處理單峰函數(shù)f1和多峰函數(shù)f7上，都在聚類數(shù)為5時(shí)獲得了相對(duì)更優(yōu)的平均值，并且MCMBSO算法在4個(gè)聚類數(shù)下均獲得了優(yōu)于BSO的平均值。根據(jù)文獻(xiàn)[21]，聚類個(gè)數(shù)的多少會(huì)影響B(tài)SO算法的種群多樣性。如果聚類數(shù)過(guò)小，會(huì)弱化算法的收斂能力，降低局部搜索的速度和精度。如果聚類數(shù)過(guò)大，會(huì)讓算法搜索后期不停增加種群信息的多樣性，產(chǎn)生許多無(wú)效空簇，導(dǎo)致算法難以收斂。因此，為了檢驗(yàn)使用多分支混沌變異算子的有效性，參照文獻(xiàn)[9]，本文在之后的實(shí)驗(yàn)中，將BSO 與MCMBSO的聚類數(shù)設(shè)定為統(tǒng)一值5。

表2 k-means不同聚類數(shù)下的實(shí)驗(yàn)結(jié)果比較Table 2 Comparison of experimental results under different k-means clustering numbers

3.2 MCMBSO與BSO算法對(duì)比

為了研究MCMBSO 算法的優(yōu)化性能，將表1 中的10 個(gè)測(cè)試函數(shù)分別用MCMBSO 和BSO 算法在10 維、30 維、50 維的維度下進(jìn)行30 次獨(dú)立尋優(yōu)，記錄30 次尋優(yōu)的最優(yōu)值、最差值、平均值和方差。實(shí)驗(yàn)種群規(guī)模為100，最大迭代次數(shù)為20 000，BSO 的參數(shù)參考文獻(xiàn)[9]，MCMBSO陷入局部最優(yōu)的判斷條件為重復(fù)迭代20次，最優(yōu)適應(yīng)度值不變。實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如表3和表4所示。

表3和表4分別給出了MCMBSO和BSO算法在不同維度下的單峰和多峰測(cè)試函數(shù)上尋優(yōu)的實(shí)驗(yàn)結(jié)果。表中的最優(yōu)值和最差值體現(xiàn)了算法單次的尋優(yōu)能力，平均值體現(xiàn)了算法運(yùn)行30 次后達(dá)到的尋優(yōu)精度，方差則體現(xiàn)了算法的穩(wěn)定性。其中，加粗?jǐn)?shù)字表示兩算法中較優(yōu)的平均值。加下劃線數(shù)字代表兩算法中較優(yōu)的最優(yōu)值和方差值。

表4 MCMBSO與BSO不同維數(shù)下的多峰函數(shù)實(shí)驗(yàn)結(jié)果比較Table 4 Comparison of experimental results on multimodal functions between MCMBSO and BSO in different dimensions

從表3 中可以看出，對(duì)于5 個(gè)單峰函數(shù)，MCMBSO和BSO算法得到的最優(yōu)解都非常接近理論最優(yōu)值。除去f2的10維，MCMBSO在5個(gè)單峰函數(shù)上3個(gè)維度下的平均值均優(yōu)于BSO。特別的，對(duì)于函數(shù)f5，MCMBSO在3個(gè)維度上都找到了理論最優(yōu)值0，而B(niǎo)SO只在10維上找到了理論最優(yōu)值。對(duì)比兩算法的穩(wěn)定性，在函數(shù)f3、f4、f5上，MCMBSO 算法的方差在3 個(gè)維度上都達(dá)到了10-4及以上，高于BSO算法最少3個(gè)數(shù)量級(jí)。

表3 MCMBSO與BSO算法不同維數(shù)下的單峰函數(shù)實(shí)驗(yàn)結(jié)果比較Table 3 Comparison of experimental results on unimodal functions between MCMBSO and BSO in different dimensions

針對(duì)函數(shù)f1和f2，僅在處理50維問(wèn)題上MCMBSO的方差略大于BSO，其余兩個(gè)維度上MCMBSO 的方差均優(yōu)于BSO。針對(duì)50維問(wèn)題，MCMBSO的方差大于BSO的原因是：隨著問(wèn)題維度的升高，算法尋優(yōu)的難度也逐漸增加。由于MCMBSO中8個(gè)混沌映射采取隨機(jī)選擇的策略，混沌搜索空間具有一定的隨機(jī)性。并且針對(duì)不同的函數(shù)問(wèn)題，算法具有不同的適應(yīng)性。對(duì)于函數(shù)f1和f2的50 維，雖然在方差上略大于BSO，但MCMBSO在這兩個(gè)問(wèn)題上均獲得了優(yōu)于BSO 的平均值，且最優(yōu)值精度也達(dá)到了1E-150 和1E-79，非常接近理論最優(yōu)值。說(shuō)明MCMBSO在處理這兩個(gè)函數(shù)的50維上，穩(wěn)定性略低于BSO，但具有更高的尋優(yōu)能力。

因此，對(duì)于處理5 個(gè)單峰函數(shù)，兩算法均能找到非常接近或等于理論最優(yōu)值的解。針對(duì)所測(cè)試的15個(gè)單峰問(wèn)題，MCMBSO算法求得的平均值有14個(gè)優(yōu)于BSO算法，方差值有13個(gè)優(yōu)于BSO。由此可見(jiàn)，相較于BSO算法，MCMBSO 算法具有更強(qiáng)的尋優(yōu)能力和較好的穩(wěn)定性。

從表4 中可以看出，對(duì)于5 個(gè)多峰函數(shù)，MCMBSO在5個(gè)多峰函數(shù)的3個(gè)維度上，平均值基本均優(yōu)于BSO，僅在函數(shù)f9的50 維上，MCMBSO 的平均值略低于BSO，且差值在同一個(gè)數(shù)量級(jí)內(nèi)。特別是在函數(shù)f7上，MCMBSO 在3 個(gè)維度上都獲得了比BSO 高3 個(gè)數(shù)量級(jí)及以上的尋優(yōu)精度。在穩(wěn)定性方面，對(duì)于函數(shù)f7、f8、f10，MCMBSO 在3 個(gè)維度上均獲得了優(yōu)于BSO 的方差；在函數(shù)f6上，MCMBSO 的方差僅在10 維上略大于BSO，但平均值和最優(yōu)值仍優(yōu)于BSO。

因此，在處理5個(gè)多峰函數(shù)的15個(gè)問(wèn)題時(shí)，MCMBSO求得的平均值有14個(gè)優(yōu)于BSO算法，方差值有11個(gè)優(yōu)于BSO。這說(shuō)明，在5個(gè)多峰函數(shù)上，MCMBSO可以找到比BSO更優(yōu)的解，穩(wěn)定性也優(yōu)于BSO，僅在處理f9這個(gè)比較復(fù)雜的問(wèn)題時(shí)，穩(wěn)定性略低于BSO。

綜上所述，在處理10 個(gè)測(cè)試函數(shù)上，MCMBSO 在f1～f10上都取得了優(yōu)于BSO 的尋優(yōu)平均值，說(shuō)明了MCMBSO具有更好的尋優(yōu)能力。在穩(wěn)定性上，MCMBSO在f1～f8和f10上均獲得了優(yōu)于BSO 的方差，說(shuō)明了MCMBSO 具有更高的穩(wěn)定性。尤其在函數(shù)f3、f4、f5、f7、f8、f10上，MCMBSO 在3 個(gè)維度上的平均值和方差均優(yōu)于BSO。由此可見(jiàn)，使用多分支混沌變異算子的MCMBSO，有效避免了BSO易陷入局部最優(yōu)的問(wèn)題，尋優(yōu)能力更強(qiáng)，具有更高的穩(wěn)定性和全局搜索能力。

3.3 MCMBSO與其他算法對(duì)比

表5展示了MCMBSO 算法與PSO、GA、CS 算法在表1 的10 個(gè)函數(shù)上的尋優(yōu)實(shí)驗(yàn)結(jié)果。四種算法的種群規(guī)模為100，最大迭代次數(shù)為20 000，優(yōu)化問(wèn)題維度為30，算法對(duì)每個(gè)函數(shù)獨(dú)立運(yùn)行30次，記錄它們的平均值和方差。

表5 維度為30時(shí)MCMBSO與其他優(yōu)化算法實(shí)驗(yàn)結(jié)果比較Table 5 Comparison of experimental results between MCMBSO and other optimization algorithms with dimension of 30

由表5可見(jiàn)，不同于其他三種算法，MCMBSO在函數(shù)f1和f5上均能達(dá)到理論最優(yōu)值。對(duì)于函數(shù)f2、f4、f7，MCMBSO 的平均值和方差均優(yōu)于PSO、GA、CS 最少2 個(gè)數(shù)量級(jí)，且在函數(shù)f9、f10上，MCMBSO 的平均值也略優(yōu)于其他三種算法。因此MCMBSO在7個(gè)函數(shù)上均獲得了優(yōu)于其他三種算法的尋優(yōu)結(jié)果。僅在函數(shù)f3、f6和f8上，MCMBSO的精度略遜于CS，但優(yōu)于PSO和GA。綜上可知，相比于其他優(yōu)化算法，MCMBSO 具有更強(qiáng)的全局搜索能力。

4 結(jié)束語(yǔ)

本文針對(duì)BSO 算法易早熟收斂，尋優(yōu)精度不高的問(wèn)題，在BSO 算法的基礎(chǔ)上，嵌入多分支混沌變異算子，提出了多分支混沌變異的頭腦風(fēng)暴優(yōu)化（MCMBSO）算法。當(dāng)BSO 算法搜索陷入局部最優(yōu)時(shí)，使用多分支混沌變異替換高斯變異來(lái)生成新個(gè)體，增強(qiáng)了算法跳出局部最優(yōu)解的能力。實(shí)驗(yàn)使用10 個(gè)經(jīng)典測(cè)試函數(shù)，將MCMBSO 與BSO 算法在3 個(gè)維度下進(jìn)行對(duì)比分析，并與PSO、GA、CS 算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)表明，MCMBSO算法能有效避免BSO易陷入局部最優(yōu)的問(wèn)題，且尋優(yōu)精度更高，全局搜索能力更強(qiáng)，具有較高的穩(wěn)定性。