引導小生境回溯優化算法

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

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

引導小生境回溯優化算法

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

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

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

回溯搜索優化算法；引導機制；小生境技術；變異策略

1 引言

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

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

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

2BSA算法

BSA算法是一種基于種群迭代的進化算法。基本BSA算法包含五個步驟，分別為：初始化，選擇Ⅰ，變異，交叉，選擇Ⅱ。基本框架如圖1所示。其五個步驟簡介如下。

圖1 基本BSA框架

2.1 種群初始化

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

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

2.2 選擇Ⅰ

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

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

2.3 變異

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

式中，F=3×randn，是變異尺度系數，能夠控制個體變異的幅度，randn是標準正態分布隨機數。

2.4 交叉

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

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

2.5 選擇Ⅱ

根據個體適應度決定保留或更新個體，如式（8）所示：

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

3 改進的BSA算法（GNBSA）

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

3.1 最優解引導機制

GNBSA算法在個體更新過程中引入當前代最優個體，為個體更新提供學習目標。由式（6）知，Map的初始值為0，假設被優化問題的維數為D，群體大小為N，則初始的映射矩陣如式（9）所示：

按照式（6）的方法，隨機產生兩個隨機數a，b，若a＜b，對第i個個體，則u為一個元素維數標識打亂的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，則：新個體的產生方法如式（12）所示：

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

而傳統的BSA方法中，當Mapi,j=0時，個體的該位將不發生變化。綜上所述，在改進的BSA算法中，個體的每一維都向當前個體學習，不論映射矩陣相應位為0還是1，正是這樣的操作，引導當前個體進行搜索，提高了算法的收斂速度。

3.2 排擠小生境技術

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

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

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

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

按照適應度值，求取當前種群中適應度最差的個體Pworst，按式（17）由排在前面的m%×N個個體和最差的個體變異產生新個體，并補充到新種群中。

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

通過這樣的操作，在半徑L之內只保留一個優秀個體，使得算法在保留較優解的同時，又維護了種群的多樣性。

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

3.3 改進算法流程

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

圖2GNBSA算法流程圖

4 仿真實驗

4.1 實驗參數設置

為驗證GNBSA算法的有效性，選取10個典型函數優化問題對算法進行測試。同時利用BSA、PSOFDR[15]、PSOwFIPS[16]、JDE[17]四種算法對典型函數進行仿真實驗，比較不同算法的性能。測試函數中，F1～F5是單峰函數，F6，F7為多峰函數，F8～F10為旋轉函數。采用Matlab R2012b作為仿真軟件，運行環境為Intel?Core?2 DuoE7400處理器，2 GB內存。測試函數如表1所示。各種算法的訓練參數如下：種群規模為50，以函數值作為算法適應度，函數被評估次數（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=0.5，CR=0.9。

表1 測試函數

4.2 實驗結果及分析

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

表2 5種算法對10個函數的測試結果

為顯示改進算法的收斂速度，不同算法的在不同FEs 時的平均最優適應度變化如圖3 所示。從圖3 可看出，與其他算法相比，GNBSA 算法的收斂速度普遍較快。對函數F1 到F8 ，收斂速度明顯快于其他四種算法。對函數F9 ，在初始階段，GNBSA算法的收斂速度優勢不明顯，但在后期較快。對函數F10 ，GNBSA 算法的收斂速度與JDE 算法相當。圖3 顯示，GNBSA 算法相對于標準的BSA算法速度明顯提高。

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

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

圖3 10 個函數的平均最好適應度變化圖

5 結束語

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

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

表4 不同m對GNBSA的測試結果

[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]段海濱，王道波.一種快速全局優化的改進蟻群算法及仿真[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]謝凱.排擠小生境遺傳算法的研究與應用[D].安徽淮南：安徽理工大學，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

國家自然科學基金（No.61572224，No.61304082）；安徽省高校自然科學研究重大項目（No.KJ2015ZD36）；安徽省高校自然科學研究重點項目（No.KJ2016A639）；安徽省國際科技合作計劃項目（No.10080703003）；安徽省第七批”115”產業創新團隊皖人才[2014]4號。

王鵬（1993—），男，碩士研究生，主要研究方向為智能優化計算；陳得寶（1975—），通訊作者，男，教授，博士，主要研究方向為智能計算、模式識別等，E-mail：chendb_88@163.com；鄒鋒（1978—），男，副教授，博士，主要研究方向為進化計算；李崢（1980—），男，副教授，主要研究方向為進化計算。

2016-05-19

2016-06-27

1002-8331（2017）21-0126-06

CNKI網絡優先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1655.026.html