王 鵬，陳得寶，鄒 鋒，李 崢

淮北師范大學(xué) 物理與電子信息學(xué)院，安徽 淮北 235000

引導(dǎo)小生境回溯優(yōu)化算法

王 鵬，陳得寶，鄒 鋒，李 崢

淮北師范大學(xué) 物理與電子信息學(xué)院，安徽 淮北 235000

回溯搜索優(yōu)化算法（BSA）是近年提出的一種新型優(yōu)化算法，針對其收斂速度較慢、易陷于局部最優(yōu)的缺點(diǎn)，提出了一種基于最優(yōu)個體引導(dǎo)和小生境技術(shù)相結(jié)合的改進(jìn)BSA算法。本方法首先在BSA的變異操作中引入向最優(yōu)個體學(xué)習(xí)的策略，以提高算法的收斂速度；其次，設(shè)計一種新的小生境排擠技術(shù)，根據(jù)每個個體到其他個體距離的平均最小值確定小生境半徑，排除部分相似性較高的個體；結(jié)合群體當(dāng)前的最差信息，設(shè)計一種新的變異方法產(chǎn)生一定數(shù)量的新個體補(bǔ)充到新的種群中，維持群體數(shù)量的恒定并增強(qiáng)群體多樣性。改進(jìn)的BSA算法充分考慮了算法的收斂速度和群體的多樣性，較大地提高了傳統(tǒng)BSA算法的性能。對10個典型函數(shù)進(jìn)行仿真測試，并與其他算法結(jié)果進(jìn)行對比，實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在收斂速度與精度方面具有較好的效果。

回溯搜索優(yōu)化算法；引導(dǎo)機(jī)制；小生境技術(shù)；變異策略

1 引言

群智能優(yōu)化算法因其能解決一些傳統(tǒng)優(yōu)化方法難以求解的問題，廣泛應(yīng)用于函數(shù)優(yōu)化、工程設(shè)計、自動控制等領(lǐng)域。常用的群智能算法有差分進(jìn)化算法（DE）[1]、粒子群算法（PSO）[2]、蟻群算法（ACO）[3]、人工蜂群算（ABC）[4]等。為提高智能優(yōu)化算法的性能，近些年來，研究者提出了一些改進(jìn)型優(yōu)化算法，如自適應(yīng)差分進(jìn)化算法（SADE）[5]，理解學(xué)習(xí)粒子群算法（CLPSO）[6]，快速全局優(yōu)化的蟻群算法[7]，優(yōu)秀種群引導(dǎo)的人工蜂群算法（GABC）[8]等，都不同程度地提高了智能優(yōu)化算法的性能。

回溯搜索優(yōu)化算法（BSA）是近年來提出的一種新型進(jìn)化算法[9]。算法群體更新控制參數(shù)少，算法實(shí)現(xiàn)簡單，在一些優(yōu)化問題中發(fā)揮了重要的作用。與其他優(yōu)化算法相比，BSA算法不僅運(yùn)用當(dāng)前的信息，而且運(yùn)用歷史信息對群體進(jìn)行更新，充分利用了進(jìn)化過程中不同時期的信息。目前對BSA算法的研究主要集中在兩個方面，一方面是通過改進(jìn)群體的產(chǎn)生辦法提高算法的性能，這方面的研究工作目前取得的成果較少；另一方面是拓展BSA算法的應(yīng)用領(lǐng)域。如利用BSA算法進(jìn)行表面波分析并將其應(yīng)用于天線設(shè)計[10]；BSA與DE算法結(jié)合解決無限制最優(yōu)問題[11]；BSA與多種限制處理方法相結(jié)合，用于解決限制性最優(yōu)問題[12]；對抗回溯算法（OBSA）應(yīng)用于優(yōu)化超混沌系統(tǒng)參數(shù)優(yōu)化問題[13]等。

盡管BSA已成功應(yīng)用于很多領(lǐng)域，但至少存在兩方面的不足。首先，在BSA算法新個體產(chǎn)生的過程中，僅依賴于隨機(jī)交叉和變異產(chǎn)生新個體，個體進(jìn)化缺乏學(xué)習(xí)能力，群體的優(yōu)化方向缺乏較好個體的引導(dǎo)，算法的收斂速度較慢；其次，隨著進(jìn)化過程的不斷進(jìn)行，與很多的其他進(jìn)化算法一樣，群體多樣性丟失，導(dǎo)致個體趨于齊次，其歷史信息和當(dāng)前信息將會不變，導(dǎo)致個體不能更新自己的位置，算法將陷入局部最優(yōu)。因此，研究如何提高BSA算法收斂速度的同時提高種群的多樣性，對提高算法的整體性能十分重要?；谶@樣的分析，本文從提高BSA算法的收斂速度和精度兩方面入手，通過引入學(xué)習(xí)機(jī)制和小生境技術(shù)提高算法的整體性能。本文算法的主要貢獻(xiàn)有兩個方面。一是通過在產(chǎn)生新個體的全過程中引入向最優(yōu)個體學(xué)習(xí)，克服了原始BSA算法映射矩陣Map的某些位為零時相應(yīng)位不更新的弱點(diǎn)，從而通過學(xué)習(xí)提高算法的收斂速度；二是由于算法收斂速度的加快，導(dǎo)致群體多樣性快速丟失，本文方法設(shè)計一種新的小生境排擠方法，結(jié)合當(dāng)前的最差個體信息，通過變異產(chǎn)生部分新個體，以彌補(bǔ)多樣性丟失可能帶來的早熟收斂問題。仿真實(shí)驗(yàn)表明改進(jìn)算法能夠有效地提高優(yōu)化性能，在收斂速度和精度兩個方面對原始算法有較大的提高。

2BSA算法

BSA算法是一種基于種群迭代的進(jìn)化算法?；綛SA算法包含五個步驟，分別為：初始化，選擇Ⅰ，變異，交叉，選擇Ⅱ?；究蚣苋鐖D1所示。其五個步驟簡介如下。

圖1 基本BSA框架

2.1 種群初始化

隨機(jī)初始化種群P和歷史種群oldP，如式（1）、（2）所示：

式中，i=1,2,3,…,N,j=1,2,3,…,D，N 為種群的規(guī)模，D為變量維數(shù)；U(·)是隨機(jī)均勻分布函數(shù)；lowj與upj分別為變量的下界和上界；P為進(jìn)化種群，oldP為歷史種群。

2.2 選擇Ⅰ

在每次迭代開始前，BSA首先產(chǎn)生一個新的歷史種群oldP，如式（3）所示，進(jìn)而對其進(jìn)行隨機(jī)排序，如式（4）所示：

式中，a，b是服從（0，1）均勻分布的隨機(jī)數(shù)，permuting(·)是隨機(jī)排序函數(shù)。

2.3 變異

BSA算法采用變異策略如式（5）所示：

式中，F(xiàn)=3×randn，是變異尺度系數(shù)，能夠控制個體變異的幅度，randn是標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)。

2.4 交叉

BSA的交叉過程分兩步。首先定義一個大小為N×D的映射矩陣Map，其初始元素值均為零。然后用兩種方式隨機(jī)更新映射矩陣Map，如式（6）所示：

式中，mixrate是交叉率，本文中取值為1，ceil(·)為正方向取整函數(shù)，a和b均為均值為零方差為1的隨機(jī)數(shù)，randi(·)是產(chǎn)生均勻分布隨機(jī)整數(shù)函數(shù)，BSA根據(jù)生成的矩陣Map隨機(jī)更新個體的某些位（具體操作如式（7）所示），并對新種群個體元素進(jìn)行邊界判斷，若newP中的某位越界，則按照式（1）重新產(chǎn)生新位置。

2.5 選擇Ⅱ

根據(jù)個體適應(yīng)度決定保留或更新個體，如式（8）所示：

式中，fitness(Pi)和 fitness(newPi)分別為個體 Pi更新前后的適應(yīng)度值。

3 改進(jìn)的BSA算法（GNBSA）

由式（7）可看出，新個體的產(chǎn)生由當(dāng)代個體和歷史個體確定，當(dāng)群體多樣性較差時，個體趨于齊次，導(dǎo)致個體不能更新，使算法陷入局部最優(yōu)。此外，BSA算法中個體更新過程缺乏最優(yōu)個體引導(dǎo)，算法缺乏學(xué)習(xí)能力。本文通過加入最優(yōu)個體引導(dǎo)和小生境技術(shù)提高算法的整體性能。兩個主要改進(jìn)部分描述如下。

3.1 最優(yōu)解引導(dǎo)機(jī)制

GNBSA算法在個體更新過程中引入當(dāng)前代最優(yōu)個體，為個體更新提供學(xué)習(xí)目標(biāo)。由式（6）知，Map的初始值為0，假設(shè)被優(yōu)化問題的維數(shù)為D，群體大小為N，則初始的映射矩陣如式（9）所示：

按照式（6）的方法，隨機(jī)產(chǎn)生兩個隨機(jī)數(shù)a，b，若a＜b，對第i個個體，則u為一個元素維數(shù)標(biāo)識打亂的1×D的向量，若 D=6 ，則 u=[2,3,5,4,6,1]，若 ceil（mixrate×rand×D）=3，則 Map 矩陣的第 i行2，3，5列元素為1，其他元素為0，如式（10）所示：

若a≥b，則在Map矩陣的第i行中任意選擇一列為1，其他元素為0，例如任意選擇到的列為3，則：新個體的產(chǎn)生方法如式（12）所示：

式中，Pbest為當(dāng)前代全局最優(yōu)個體的位置，rand是服從（0，1）均勻分布的隨機(jī)數(shù)。由上述方法可知，對第i個個體，當(dāng)Mapi,j=1時，第 j維變量的新值由個體的歷史信息、當(dāng)前信息及當(dāng)前群體的最好位置確定。當(dāng)Mapi,j=0時，新個體由最優(yōu)個體引導(dǎo)產(chǎn)生。如式（13）所示：

而傳統(tǒng)的BSA方法中，當(dāng)Mapi,j=0時，個體的該位將不發(fā)生變化。綜上所述，在改進(jìn)的BSA算法中，個體的每一維都向當(dāng)前個體學(xué)習(xí)，不論映射矩陣相應(yīng)位為0還是1，正是這樣的操作，引導(dǎo)當(dāng)前個體進(jìn)行搜索，提高了算法的收斂速度。

3.2 排擠小生境技術(shù)

實(shí)踐證明，算法收斂速度的加快有可能導(dǎo)致種群多樣性丟失較快，從而加劇了局部收斂現(xiàn)象的產(chǎn)生。為均衡算法收斂速度和群體多樣性，本文采用排擠小生境技術(shù)[14]改善種群多樣性。為有效增加種群多樣性，本文在分析小生境方法的基礎(chǔ)上，設(shè)計了一種新的基于罰函數(shù)和結(jié)合最差個體信息的新個體產(chǎn)生排擠小生境方法。具體描述如下。

首先計算出種群中每個個體與其他個體間的歐氏距離d，如式（14）所示，然后計算出種群中每一個個體到其他任一個個體間歐式距離的最小值，得到一個最小值向量T，然后根據(jù)種群規(guī)模大小求其平均值得到小生境半徑L，如式（15）所示。若d＜L，則比較兩者的適應(yīng)度，并對其中適應(yīng)度較差的個體處以懲罰，使其適應(yīng)度降低，如式（16）所示。

式（14）中，dkl是個體k與個體l之間的歐氏距離，j=1,2,3,…,D。式（16）中，fitness(Pk)是第k個個體的適應(yīng)度，fitness(Pl)是第l個個體的適應(yīng)度，Penalty為懲罰函數(shù)。

所有個體經(jīng)過懲罰操作后，再按照適應(yīng)度進(jìn)行排序，適應(yīng)度較差的m%×N個個體將被淘汰。為維持種群數(shù)量恒定，增加種群多樣性，選取排在前面的m%×N個個體采用新的變異方式補(bǔ)充淘汰的個體，生成新的種群，m值的選取根據(jù)實(shí)際情況，采用經(jīng)驗(yàn)方法確定。具體操作如下。

按照適應(yīng)度值，求取當(dāng)前種群中適應(yīng)度最差的個體Pworst，按式（17）由排在前面的m%×N個個體和最差的個體變異產(chǎn)生新個體，并補(bǔ)充到新種群中。

式中，i=1,2,3,…,m%×N,j=1,2,3,…,D，Pworst為當(dāng)前種群最差個體的位置，newP*i,j為變異補(bǔ)充的個體。

通過這樣的操作，在半徑L之內(nèi)只保留一個優(yōu)秀個體，使得算法在保留較優(yōu)解的同時，又維護(hù)了種群的多樣性。

由于GNBSA算法的基本框架與BSA算法類似，所有個體同樣經(jīng)歷選擇Ⅰ，變異，交叉，選擇Ⅱ，在GNBSA算法中，當(dāng)種群經(jīng)歷選擇Ⅱ的操作后，啟動以上設(shè)計的小生境淘汰運(yùn)算，各個體在自己的小生境半徑內(nèi)排除近似個體，并通過變異產(chǎn)生新個體，形成下一代種群。在算法流程中更加清晰地顯示了小生境方法的作用位置。

3.3 改進(jìn)算法流程

綜合以上分析，GNBSA流程圖如圖2所示。

圖2GNBSA算法流程圖

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證GNBSA算法的有效性，選取10個典型函數(shù)優(yōu)化問題對算法進(jìn)行測試。同時利用BSA、PSOFDR[15]、PSOwFIPS[16]、JDE[17]四種算法對典型函數(shù)進(jìn)行仿真實(shí)驗(yàn)，比較不同算法的性能。測試函數(shù)中，F(xiàn)1～F5是單峰函數(shù)，F(xiàn)6，F(xiàn)7為多峰函數(shù)，F(xiàn)8～F10為旋轉(zhuǎn)函數(shù)。采用Matlab R2012b作為仿真軟件，運(yùn)行環(huán)境為Intel?Core?2 DuoE7400處理器，2 GB內(nèi)存。測試函數(shù)如表1所示。各種算法的訓(xùn)練參數(shù)如下：種群規(guī)模為50，以函數(shù)值作為算法適應(yīng)度，函數(shù)被評估次數(shù)（FES=5 000×D=150 000）作為算法的停止條件。在BSA和GNBSA中，交叉率 mixrate為 1，m=10。在 PSOFDR 中，wmin=0.4，wmax=0.9，φ1=1，φ2=1，φ3=2。 在 PSOwFIPS 中 ，w=0.729 8。在JDE中，F(xiàn)=0.5，CR=0.9。

表1 測試函數(shù)

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

為公平比較，對同一函數(shù)，每種算法獨(dú)立運(yùn)行30次，對其統(tǒng)計特性進(jìn)行比較。實(shí)驗(yàn)所得各種算法的平均值（mean）、方差（std）和最優(yōu)值（best）如表2所示。從結(jié)果可以看出，與BSA相比，對所有測試函數(shù)，GNBSA算法的收斂精度和穩(wěn)定性兩方面均明顯優(yōu)于BSA，特別對于多峰函數(shù)F6 和F7 ，都能夠找到理論最優(yōu)解。對于單峰函數(shù)和旋轉(zhuǎn)函數(shù)，平均收斂精度最少提高了6 個數(shù)量級，最多提高了116個數(shù)量級。與其他算法相比，GNBSA同樣有著較好的性能，其收斂的平均解和方差均最小。

表2 5種算法對10個函數(shù)的測試結(jié)果

為顯示改進(jìn)算法的收斂速度，不同算法的在不同F(xiàn)Es 時的平均最優(yōu)適應(yīng)度變化如圖3 所示。從圖3 可看出，與其他算法相比，GNBSA 算法的收斂速度普遍較快。對函數(shù)F1 到F8 ，收斂速度明顯快于其他四種算法。對函數(shù)F9 ，在初始階段，GNBSA算法的收斂速度優(yōu)勢不明顯，但在后期較快。對函數(shù)F10 ，GNBSA 算法的收斂速度與JDE 算法相當(dāng)。圖3 顯示，GNBSA 算法相對于標(biāo)準(zhǔn)的BSA算法速度明顯提高。

為進(jìn)一步檢測GNBSA算法的解與其他算法解的優(yōu)劣，采用雙邊t-test 方法對結(jié)果進(jìn)行檢驗(yàn)，顯著水平為0.05。GNBSA 算法對其他算法的t 值和p 值如表3 所示。表3 中，‘B’，‘W’，‘S’分別表示GNBSA算法性能優(yōu)于、劣于、等于其他算法的數(shù)量。從表3 可看出，在顯著水平為0.05 的情況下，GNBSA算法性能優(yōu)于其他算法，解可以被接受。

在GNBSA算法中，小生境操作中，刪除和補(bǔ)充個體的數(shù)量對算法性能具有一定的影響，刪除太多，群體信息丟失太多，不利于算法對原有信息的利用，刪除太少，群體多樣性難以維持，為分析參數(shù)m 對算法性能的影響，本文選取三個函數(shù)(F1,F5,F8) 對其影響進(jìn)行分析，結(jié)果如表4 所示。從表4 中可以看出，m 的取值對算法性能具有一定的影響，剛開始m 值的增大，優(yōu)化性能得到一定的提升，當(dāng)m 增加到一定值之后，再增加m 的值，群體信息丟失增加，算法性能反而下降，本文經(jīng)驗(yàn)選擇m 的值為10，對這幾個函數(shù)效果較好。

圖3 10 個函數(shù)的平均最好適應(yīng)度變化圖

5 結(jié)束語

本文提出了一種基于引導(dǎo)和小生境技術(shù)的BSA改進(jìn)算法（Gbest-guided and Niching Backtracking Search Optimization Algorithm）。相對于標(biāo)準(zhǔn)的BSA算法，GNBSA算法在個體的更新過程中加入了全局最優(yōu)解的引導(dǎo)。引入排擠機(jī)制的小生境方法來維持種群多樣性。通過對典型函數(shù)的優(yōu)化測試驗(yàn)證了方法的有效性。從比較結(jié)果可看出，無論在收斂速度和收斂精度方面，改進(jìn)算法具有較好的性能。

表3 GNBSA對其他4種算法的t-test結(jié)果

表4 不同m對GNBSA的測試結(jié)果

[1]Price K，Storn R M，Lampinen J A.Differential evolution：A practical approach to global optimization（natural computing series）[M].Secaucus，NJ，USA：Springer-Verlag New York Inc，2005.

[2]Kennedy J，Eberhart R.Particle swarm optimization[C]//IEEE InternationalConference on NeuralNetworks.IEEE，1995：1942-1948.

[3]Maniezzo V，Gambardella L M，Luigi F D.Ant colony optimization[J].Alphascript Publishing，2010，28（3）：1155-1173.

[4]Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：Artificial bee colony（ABC） algorithm[J].Journal of Global Optimization，2007，39（3）：459-471.

[5]Qin A K，Suganthan P N.Self-adaptive differential evolution algorithm for numerical optimization[J].IEEE Congress on Evolutionary Computation，2005，2：1785-1791.

[6]Liang J J，Qin A K，Baskar S.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation，2006，10（3）：281-295.

[7]段海濱，王道波.一種快速全局優(yōu)化的改進(jìn)蟻群算法及仿真[J].信息與控制，2004，33（2）：241-244.

[8]Zhu G，Kwong S.Gbest-guided artificial bee colony algorithm for numerical function optimization[J].Applied Mathematicsamp;Computation，2010，217（7）：3166-3173.

[9]Civicioglu P.Backtracking search optimization algorithm for numerical optimization problems[J].Applied Mathematicsamp;Computation，2013，219（15）：8121-8144.

[10]Song X，Zhang X，Zhao S，et al.Backtracking search algorithm for effective and efficient surface wave analysis[J].Journal of Applied Geophysics，2015，114：19-31.

[11]Wang L，Zhong Y，Yin Y，et al.A hybrid backtracking search optimization algorithm with differential evolution[J].Mathematical Problems in Engineering，2015，2015：1-16.

[12]Zhang C，Lin Q，Gao L，et al.Backtracking search algorithm with three constraint handling methods for constrained optimization problems[J].Expert Systems with Applications，2015，42（21）：112-116.

[13]Lin J.Oppositional backtracking search optimization algorithm for parameter identification of hyperchaotic systems[J].Nonlinear Dynamics，2015，80（1/2）：209-219.

[14]謝凱.排擠小生境遺傳算法的研究與應(yīng)用[D].安徽淮南：安徽理工大學(xué)，2005.

[15]Peram T，Veeramachaneni K，Mohan C K.Fitness-distanceratio based particle swarm optimization[C]//Proceedings of the 2003 IEEE Swarm Intelligence Symposium，2003（SIS’03）.IEEE，2003：174-181.

[16]Mendes R，Kennedy J，Neves J.The fully informed particle swarm：Simpler，maybe better[J].IEEE Transactions on Evolutionary Computation，2004，8（3）：204-210.

[17]Qin A K，Huang V L，Suganthan P N.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on Evolutionary Computation，2009，13（2）：398-417.

WANG Peng,CHEN Debao,ZOU Feng,LI Zheng

School of Physics and Electronic Information,Huaibei Normal University,Huaibei,Anhui 235000,China

Guidance and niching backtracking search optimization algorithm.Computer Engineering and Applications,2017,53（21）：126-131.

Backtracking Search optimization Algorithm（BSA）is a new optimization algorithm which is proposed in recent years.For the convergence speed of original BSA is slow and it is easily trapped in local optima,an improved BSA based on the combination of guidance with the best individual and niche technique is proposed to improve the global performance of it.In the method,the strategy with learning from the best individual is introduced in the mutation operator of original BSA to improve the convergence speed of it in the first.In the second,a niche repulsing technology is designed in the paper.The niching radius is determined according to the average minimal distance between every individual and the other individuals,and some parts individuals with high similarity are deleted,some new individuals are generated by a new mutation method which is designed with combining the worst information of current generation,and the new individuals are supplemented in the new population to maintain the constant number of population,the diversity of the population is increased by this operation.The convergence speed and the diversity of population is fully considered in the improved BSA,and the performance of the original BSA is largely improved.10 typical functions are used in the simulation experiments,and the results are compared with those of other algorithms.The results indicate that the improved algorithm has good performance in terms with the convergence speed and accuracy.

Backtracking Search optimization Algorithm（BSA）;guidance mechanism;niche technology;mutation strategy

A

TP301

10.3778/j.issn.1002-8331.1605-0277

國家自然科學(xué)基金（No.61572224，No.61304082）；安徽省高校自然科學(xué)研究重大項(xiàng)目（No.KJ2015ZD36）；安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目（No.KJ2016A639）；安徽省國際科技合作計劃項(xiàng)目（No.10080703003）；安徽省第七批”115”產(chǎn)業(yè)創(chuàng)新團(tuán)隊(duì)皖人才[2014]4號。

王鵬（1993—），男，碩士研究生，主要研究方向?yàn)橹悄軆?yōu)化計算；陳得寶（1975—），通訊作者，男，教授，博士，主要研究方向?yàn)橹悄苡嬎?、模式識別等，E-mail：chendb_88@163.com；鄒鋒（1978—），男，副教授，博士，主要研究方向?yàn)檫M(jìn)化計算；李崢（1980—），男，副教授，主要研究方向?yàn)檫M(jìn)化計算。

2016-05-19

2016-06-27

1002-8331（2017）21-0126-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1655.026.html