衣俊艷，施曉東，楊 剛

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

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

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

群智能（swarn intelligence，SI）[2]算法主要是模擬昆蟲、獸群、鳥群等群體進(jìn)行覓食、求偶等群體行為而提出的自適應(yīng)優(yōu)化算法。該類算法是一種隨機(jī)搜索方法，具有靈活應(yīng)對群體內(nèi)部和外部搜索環(huán)境變化的能力，即當(dāng)搜索條件多變或自身的某些個體搜索失敗時，能夠自組織逃離并找到更優(yōu)的位置[3-4]?；谌后w智能的思想，國內(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)化算法、布谷鳥搜索（cuckoo search，CS）[8]算法等，這些算法具有較強(qiáng)的魯棒性和搜索能力，易于并行實現(xiàn)，在許多優(yōu)化問題中得到了廣泛的研究和應(yīng)用。

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

群智能優(yōu)化算法普遍存在易陷入局部最優(yōu)，導(dǎo)致早熟收斂的問題，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）算法，通過控制組內(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）算法，通過將解集合分為精英類和普通類來代替BSO 中復(fù)雜的聚類操作，極大地提升了算法搜索效率，降低了算法的復(fù)雜度。文獻(xiàn)[14]提出了一種改進(jìn)的頭腦風(fēng)暴優(yōu)化（modified brain storm optimization，MBSO）算法，使用簡單分組方法（simple group method，SGM）替換k-means 聚類，并用差分變異替換BSO 算法中的高斯變異，提高了算法的搜索效率和尋優(yōu)精度。

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

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

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

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

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

（1）初始化n 個個體。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 新解生成分析

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

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

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

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

2.2 多分支混沌變異算子

2.2.1 混沌與混沌解

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

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

2.2.2 多分支混沌變異

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

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

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

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

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

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

（4）通過載波映射[16]，將混沌特性引入到選中個體周圍，表達(dá)式如下：

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

（5）使用式（4）生成K個在原個體周圍具有混沌特性的m維搜索點后，將這些點帶入到測試函數(shù)中進(jìn)行檢驗，選取其中適應(yīng)度值最小的搜索點Xmin作為待更新個體。

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

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

2.2.3 具體混沌映射

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

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

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

圖2 Cubic映射生成的混沌序列分布散點圖和直方圖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時，混沌性越強(qiáng)，此處取μ=1；c( 2)i∈(-1,1) ，此處取c( 2)i的絕對值，使得c( 2)i∈( 0,1) 。圖3顯示了Sine映射迭代500次后混沌序列分布的散點圖和頻率直方圖。

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

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

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

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

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

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

圖5 ICMIC映射生成的混沌序列分布散點圖和直方圖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 )時，c( 5)i∈( 0,1) 。系統(tǒng)具有以下特性：（1）Lyapunov指數(shù)大于0，系統(tǒng)為混沌狀態(tài)。（2）具有一致的不變分布密度函數(shù)和較好的遍歷性。圖6顯示了PWLCM映射迭代500次后混沌序列分布的散點圖和頻率直方圖。

圖6 PWLCM映射生成的混沌序列分布散點圖和直方圖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的絕對值，并舍去大于1 的值，使得c( 6)i∈( 0,1) 。圖7 顯示了Neuron 映射迭代500 次后混沌序列分布的散點圖和頻率直方圖。

圖7 Neuron映射生成的混沌序列分布散點圖和直方圖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次后混沌序列分布的散點圖和頻率直方圖。

圖8 Sinusoidal映射生成的混沌序列分布散點圖和直方圖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 次后混沌序列分布的散點圖和頻率直方圖。

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

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

2.3 算法步驟

MCMBSO算法步驟如下：

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

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

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

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

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

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

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

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

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

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

MCMBSO流程圖如圖10所示。

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

3 實驗測試與結(jié)果分析

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

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

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

所有算法的實驗在同一平臺上運行，實驗平臺為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ū)域。在算法多次迭代之后，搜索空間不斷減小，所有解大概率被聚集到一個小范圍中，增加了算法的收斂能力。因為本文主要探討添加多分支混沌變異算子后對BSO算法的改進(jìn)，所以MCMBSO 參照原始BSO 算法，使用kmeans聚類對解集合進(jìn)行分類操作。k-means算法是一種經(jīng)典的聚類算法，算法本身需經(jīng)過多次迭代才能將解集合分組，并且聚類數(shù)需要事先指定。

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

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

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

3.2 MCMBSO與BSO算法對比

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

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

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

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

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

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

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

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

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

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

3.3 MCMBSO與其他算法對比

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

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

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

4 結(jié)束語

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