田文凱

(西安電子科技大學數學與統(tǒng)計學院，陜西西安 710126)

近年來，進化算法由于強大的實際應用能力得到了快速發(fā)展。各種進化算法如雨后春筍般相繼而出。在長期的實踐檢驗中，主流的進化算法大致有(1)粒子群算法(PSO)［1］。(2)蜂群算法(ABC)［2］。(3)差分進化算法(DE)［3］。(4)協方差矩陣算法(CMAES)［4］，以及它們相應的改進算法，如基于粒子群算法改進的CLPSO［5］，PSO2011［6］，基于差分進化算法改進的JDE［7］，SaDE［8］，基于 ABC 改進的 GABC［9］等。

回溯搜索優(yōu)化算法(BSA)是Civicioglu于2013年提出的一種基于種群的新進化算法，其算法框架類似于差分進化算法，但在變異操作或者擾動策略，和交叉操作或者混合策略上，與差分進化算法有本質的區(qū)別。它的擾動策略和混合策略新穎高效，在全局搜索能力和收斂速度方面表現良好，使其在與 PSO，ABC，CMAES，JDE，SADE 的比較中，顯出較大的優(yōu)勢［10］。BSA應該會成為繼以上算法后的一個新主流進化算法。

1 BSA的介紹

BSA的算法框架與差分進化算法相似，但BSA有兩個選擇過程，分別稱為選擇I和選擇II。選擇I為變異策略中隨機選擇一個歷史種群，用于產生差分量，選擇II用于更新種群。總體算法框架可分為初始化種群，選擇I，變異，交叉，選擇II 5部分。

BSA算法的邏輯框架如下:

(1)初始化種群。

1.1 初始化種群

BSA的初始化種群與差分進化算法相同，但BSA的初始化種群P包括種群old P的初始化和歷史種群的初始化

其中 i=1，2，3…，popsize;j=1，2，3…，D，popsize 是種群規(guī)模，D是問題維數，lowj，upj分別表示第j維分量的下界和上界，U 表示均勻分布，Pi，j，old Pi，j是(lowj，upj)上服從均勻分布的隨機數。兩初始化過程相互獨立。對old P的初始化是為了防止第一次執(zhí)行選擇I時，old P值為空，以保證算法的可行性。

1.2 選擇 I

BSA的選擇I用于選擇一個新的歷史種群old P，其算法思想如式(2)所示

其中，a，b是(0，1)上服從均勻分布的隨機數。式(2)的作用是在前代種群中選擇一個歷史種群，并記住這個歷史種群直至再次發(fā)生改變，當代歷史種群old P可以是前n代種群中的任何一代以及初始的歷史種群，其中n=1，2，…，N－1，N是當前已迭代的最大代數。

1.3 變異

在old P的值確定后，對old P中的個體進行隨機排序，并重新賦予old P。利用式(3)進行變異

這里F是變異尺度系數用以控制變異的幅度;F=3·randn，randn是一服從標準正態(tài)分布的隨機數。

1.4 交叉

BSA的交叉策略是一種基于兩種交叉方式等概率調用的聯合交叉策略，相比差分進化算法較為復雜。BSA在交叉時，首先選擇一個交叉長度n，然后將父代種群P中每個個體隨機選取n個元素與Mutant中的相同位置個體的同維元素進行互換，生成新的個體，其中n是(0，mixrate·D)中的整數。但在每代交叉時，n的選擇有兩種可能，根據n的賦值方式，做以下分類敘述:

(1)交叉策略I:n恒為1。

(2)交叉策略II:先給每個個體隨機生成一個隨機數 rand·U(0，1)，以

為交叉長度。其中mixrate是交叉概率，D是問題維數即染色體長度。

兩種交叉策略等概率隨機調用構成BSA的交叉策略。在式(3)中，Mutant的元素有可能超出相應分量的取值范圍，若交換到此類元素，將重新在相應的取值區(qū)間內隨機選擇一個值，最終生成新一代試驗種群T。

1.5 選擇 II

比較P和T同位置個體的適應度，當T中第i個個體Ti的適應度小于Pi時，便用Ti代替Pi更新當代種群，如式(5)所示

更新后的種群進入下一代循環(huán)。

2 BSA的改進

長期以來，進化算法總是在收斂速度和全局搜索性之間做改進，如何在保證算法全局收斂性的前提下，加快收斂速度，是改進進化算法的主要目標之一。本文經過實驗數據分析，對BSA的變異尺度系數和交叉策略做了相應改進，使得BSA的收斂速度和收斂結果都有了一定的提高。

2.1 BSA變異尺度方程的改進

BSA的變異尺度系數F=3·randn，其容易產生過大或過小的隨機值，過大的變尺度系數會降低算法的收斂性，過小的變異尺度系數會增加算法陷入局部最優(yōu)解的可能性，所以本文提出了一種新的變異方程

其中randperm(old P－P)表示old P－P中行向量的一個隨機重排。假設old P－P中行向量的方差為Var(old P－P)，則有 Var(randperm(old P－P))=Var(old P－P)，所以有

Var［0.5·(old P － P)+0.5·randperm(old P －P)］=0.5·Var(old P －P)

差分量方差比原來減小了一半，意味著新變異形式能有效減少過大或過小擾動量的產生。而兩個隨機差分量合成擾動量的方式使引導方式由線性引導變?yōu)榉蔷€性引導，所以負變尺度系數失去意義，不是必須的。

在改進變異尺度系數時，本文參考了物理學中的一些分布，令變異尺度系數是服從麥克斯韋－玻爾茲曼分布的隨機數，麥克斯韋－玻爾茲曼分布描述的是處于熱平衡態(tài)下理想氣體分子速率的分布，能進一步減小方差，且大量數值實驗表明，麥克斯韋－玻爾茲曼分布能有效地擾動種群，使變異過程出現更好的實驗種群。圖1說明新的變異尺度系數具有更好的搜索性能。新變異尺度系數為

χ2(3)是自由度為3的卡方分布，CH3是服從χ2(3)隨機數。圖1～圖5是原算法和改進變異系數的算法在測試函數F1～F5上的收斂效果比較，可以看到新的變異尺度系數在多峰函數的測試中有較好的收斂效果。

圖1 測試函數F1收斂速度對比

圖2 測試函數F2收斂速度對比圖

圖3 測試函數F3收斂速度對比

圖4 測試函數F4收斂速度對比

圖5 測試函數F5收斂速度對比

2.2 BSA交叉策略的改進

實驗表明，單獨使用交叉策略I或者交叉策略II，收斂速度比聯合交叉策略慢得多，聯合交叉策略對BSA良好的收斂效果有較大貢獻。而受到JADE［11］中交叉率產生方式的啟發(fā)，在聯合交叉策略的隨機選取過程中加入了一定的自學習性，使收斂的效果有了進一步提高。

原聯合交叉策略中，兩種交叉策略的選取是隨機的，即從(0，1)上均勻選取隨機數a，b以a，b的大小來選擇進行哪種交叉;在改進的交叉策略中，我們只生成一個隨機數a，以a和自適應概率分度p的大小來決定，當a＜p時，進行交叉策略I，否者進行交叉策略II，其中 p·N(cr，0.25)，N(cr，0.25)是以 cr為中心，以0.25為方差的正態(tài)分布。以隨機數a，b的大小來決定選擇哪種交叉策略，使得交叉過程有些盲目，而以概率分度p和a進行比較便使得兩種交叉策略的選擇有一定的偏向。每進行per代進化后，將對cr進行一次更新，cr的更新策略如下:

首先，定義種群的一個進化評判度Δs，如式(7)

g是代數，g－1代表 g的上一代，g=1，2，…，epoch，epoch是最大進化代數，pi，g是g代種群中第i個個體，當 g － 1 為 0 時，pi，g－1表示初始種群的個體，fi，g為 pi，g的函數值，適應度值定義為

定義兩種交叉策略的收斂效果評判度cr1和cr2

G1，G2分別代表進行交叉策略I和交叉策略II的代數集合表示G1，G2中元素的個數。如果進行per了次迭代，cr將如下進行更新

同時，cr1和 cr2重新歸零，G1和 G2重新置為空集，其中cr的初始值為0.5。這樣，算法將吸取上per代的經驗，為下per次迭代規(guī)劃一個新的cr。為說明新的交叉策略的效果，在相同的變異策略下，即不更改變異尺度系數的情況下，單獨比較了新交叉策略和原交叉策略的收斂效果，結果如圖6～圖10所示(F1～F4中，per=200，F5中，per=20)。

圖6 測試函數F1收斂速度對比

圖7 測試函數F2收斂速度對比

圖8 測試函數F3收斂速度對比

圖9 測試函數F4收斂速度對比

圖10 測試函數F5收斂速度對比

新交叉策略在算法效果上有一定的提高，但遺憾的是，新交叉策略的改進效果并不明顯，交叉策略還需要有更合理判定準則的引入和參數調整。

3 數值實驗

實驗分為測試函數選取，停止條件制定和測試結果的統(tǒng)計分析3部分。

3.1 Benchmark測試函數選取

數值實驗選取了15個函數進行測試，其中有5個高維單峰函數，5個高維多峰函數和5個限定維多峰函數，如表1所示。

表1 測試用到的Benchmark測試函數

表1中，M為Multimodal(多峰)，N為Non－Separable(不可分)，U 為Unimodal(單峰)，S 為Separable(可分)。

3.2 停止條件制定與參數選取

(1)所求結果與Benchmark測試函數的已知最優(yōu)解的絕對差＜10－323時，停止。

(2)到達最大進化代數epoch時，停止。

最大進化代數epoch根據每個測試函數的性質選定，如表3所示。實驗參數取值如表2所示。

表2 測試中的實驗參數取值

實驗均在相同配置的計算機上，使用Matlab2013a進行編程測試。

3.3 測試結果的統(tǒng)計分析

進化算法的結果是隨機的，每次運行結果都是一個最優(yōu)解的近似值，同一進化算法對同一測試函數的運行結果也并不穩(wěn)定，所以不能憑借一次運行結果來比較算法的優(yōu)劣。在測試中，對于同一Benchmark函數分別運行IBSA和BSA的程序30次，比較30次運行結果的均值和方差，以評定BSA和IBSA的收斂效果。30次結果的均值與方差如表3所示。

表3 由BSA和IBSA獲得相應測試函數30次測試結果的均值與方差

從15個測試函數的結果可以看出，IBSA的收斂效果均優(yōu)于BSA，且對高維多峰函數在較長的進化代數下，IBSA取得的結果仍然優(yōu)于BSA，可見IBSA不僅具有較快的收斂速度，也表明了IBSA同時具有良好的全局搜索性能。

4 結束語

在數值實驗中，IBSA取得了較大的優(yōu)勢，這歸功于其更加有效的變異尺度系數和智能化的交叉選擇策略，兩者使IBSA在處理種群中比BSA更加高效和更有針對性;同時，新的變異尺度系數和交叉選擇策略的智能化設計注重對原有算法的繼承，從而使IBSA和BSA一樣具有良好的全局搜索性能。IBSA較成功地在保證算法全局收斂性的前提下，加快了收斂速度。但IBSA的交叉策略并沒有大幅提高算法的收斂性能，其控制結構和相關參數還需進一步的改進和調整。

［1］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］.Proceedings of the Sixth International Symposium on Micro Machine and Human Science，MHS'95.，IEEE，1995.

［2］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.

［3］Price K V.Differential evolution:a fast and simple numerical optimizer［C］.Fuzzy Information Processing Society，1996 Biennial Conference of the North American，IEEE，2009.

［4］Dorigo M，Maniezzo V.Ant system:optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics－ Part，1996，26(1):29 －41.

［5］Liang J J，Qin A K，Suganthan P N，et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions［J］.IEEETransactions on Evolutionary Computation，2006，10(3):281 －295.

［6］Thangaraj R，Pant M，Ajith Abraham，et al.Particle swarm optimization:Hybridization perspectives and experimental illustrations ［J］.Applied Mathematics and Computation，2011，218(12):5208 －5226.

［7］Qin A K，Huang V L，Suganthan P N，et al.Differential evolution algorithm with strategy adaptation for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation，2009，13(2):398 －417.

［8］Brest J，Greiner S，Boskovic B，et al.Self－ adapting control parameters in differential evolution:A comparative study on numerical benchmark problems［J］.IEEE Transactions on Evolutionary Computation，2006，10(6):646 －657.

［9］Zhu G，Kwong S.Gbest－ guided artificial bee colony algorithm for numerical function optimization［J］.Applied Mathematics and Computation，2010，217(7):3166 －3173.

［10］Civicioglu P.Backtracking search optimization algorithm for numerical optimization problems［J］.Applied Mathematics and Computation，2013，220(15):8121 －8144.

［11］Zhang J，Sanderson A C.JADE:adaptive differential evolution with optional external archive［J］.IEEE Transactions on Evolutionary Computation，2009，13(5):945 －958.

［12］Molga M，Smutnicki C.Test functions for optimization needs［M］.Berlin:Test Functions for Optimization Needs，2005.

［13］Karaboga D，Akay B.A comparative study of artificial bee colony algorithm ［J］.Application Mathematical Computation，2009，216(1):108 －132.