一種高效自學(xué)習(xí)性回溯搜索優(yōu)化算法

田文凱

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

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

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

1 BSA的介紹

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

BSA算法的邏輯框架如下:

(1)初始化種群。

1.1 初始化種群

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

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

1.2 選擇 I

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

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

1.3 變異

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

這里F是變異尺度系數(shù)用以控制變異的幅度;F=3·randn，randn是一服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)。

1.4 交叉

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

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

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

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

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

1.5 選擇 II

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

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

2 BSA的改進(jìn)

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

2.1 BSA變異尺度方程的改進(jìn)

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

其中randperm(old P－P)表示old P－P中行向量的一個隨機(jī)重排。假設(shè)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)

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

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

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

圖1 測試函數(shù)F1收斂速度對比

圖2 測試函數(shù)F2收斂速度對比圖

圖3 測試函數(shù)F3收斂速度對比

圖4 測試函數(shù)F4收斂速度對比

圖5 測試函數(shù)F5收斂速度對比

2.2 BSA交叉策略的改進(jìn)

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

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

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

g是代數(shù)，g－1代表 g的上一代，g=1，2，…，epoch，epoch是最大進(jìn)化代數(shù)，pi，g是g代種群中第i個個體，當(dāng) g － 1 為 0 時，pi，g－1表示初始種群的個體，fi，g為 pi，g的函數(shù)值，適應(yīng)度值定義為

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

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

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

圖6 測試函數(shù)F1收斂速度對比

圖7 測試函數(shù)F2收斂速度對比

圖8 測試函數(shù)F3收斂速度對比

圖9 測試函數(shù)F4收斂速度對比

圖10 測試函數(shù)F5收斂速度對比

新交叉策略在算法效果上有一定的提高，但遺憾的是，新交叉策略的改進(jìn)效果并不明顯，交叉策略還需要有更合理判定準(zhǔn)則的引入和參數(shù)調(diào)整。

3 數(shù)值實驗

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

3.1 Benchmark測試函數(shù)選取

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

表1 測試用到的Benchmark測試函數(shù)

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

3.2 停止條件制定與參數(shù)選取

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

(2)到達(dá)最大進(jìn)化代數(shù)epoch時，停止。

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

表2 測試中的實驗參數(shù)取值

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

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

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

表3 由BSA和IBSA獲得相應(yīng)測試函數(shù)30次測試結(jié)果的均值與方差

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

4 結(jié)束語

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

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