龐凱立，梁昔明

(北京建筑大學 理學院，北京 100044)

對較好和較差個體雙向更新的混合蛙跳算法

龐凱立，梁昔明

(北京建筑大學 理學院，北京 100044)

針對基本蛙跳算法在處理復雜函數(shù)優(yōu)化問題時求解精度低且易陷入局部最優(yōu)的缺點，將共軛梯度法引入基本蛙跳算法，對排名靠前的p個模因組中的精英個體和排名靠后的q個模因組中的落后個體同時使用共軛梯度法進行更新，一方面增強對較差青蛙的指導能力，另一方面使最差的青蛙直接更新，提高了算法的收斂精度. 所得混合蛙跳算法有效結合了基本蛙跳算法較強的全局搜索能力和共軛梯度法快速精確的局部搜索能力. 將所得的混合蛙跳算法與其他智能優(yōu)化算法進行對比，數(shù)值試驗結果表明，無論從收斂精度還是進化代數(shù)而言，所得混合蛙跳算法較其他算法均有較大的改進，具有更高的收斂精度，能有效避免陷入局部最優(yōu)，且優(yōu)化結果更加穩(wěn)定.

混合蛙跳算法； 共軛梯度法； 數(shù)值試驗； 適應度函數(shù)

基本蛙跳算法[1]是一種新的基于群體智能的啟發(fā)式算法，該算法是在2003年由Eusuff和Lansey受青蛙進食行為的啟發(fā)進行建模和仿真研究的結果，該算法結合了粒子群算法和模因算法兩者的優(yōu)點，具有結構簡單、收斂速度快和全局尋優(yōu)能力強等特點.

基本蛙跳算法與其他群體迭代算法一樣，雖然具有較強的全局搜索能力，但是易陷入局部最優(yōu)，且收斂精度不高. 為此，學者們進行了深入的研究，提出了一些改進算法，也都取得了不錯的效果. 文獻[2]對子群中每只青蛙個體引入了隨機擾動，并讓子群內每只青蛙個體都參與產(chǎn)生新個體，充分利用每只青蛙個體的信息，增加了種群多樣性. 文獻[3]引入全局共享因子和局部共享因子，由于共享因子隨著迭代次數(shù)的增加而增大，使得在局部搜索初期，較小的共享因子初值能減弱最優(yōu)個體對最差個體的指導，避免了青蛙個體更新步長過大而跳過局部最優(yōu)；在進化后期，共享因子增大，增強了最優(yōu)個體對最差個體的指導，使得個體跳過局部最優(yōu)實現(xiàn)全局收斂，該算法動態(tài)改變最優(yōu)個體對最差個體的指導能力，使得青蛙個體更容易跳出局部最優(yōu)實現(xiàn)全局收斂. 文獻[4]基于量子理論提出一種量子混合蛙跳算法，該算法采用量子位的Bloch球面坐標編碼個體，利用量子位在Bloch球面上繞軸旋轉的方法更新個體，通過自適應混沌旋轉角度算子提高子群內部局部搜索能力，采用Hadamard門實現(xiàn)個體變異避免早熟，有效擴展了空間的搜索范圍. 文獻[5]定義了新的粒子分類標準，將所有青蛙按此標準進行分類，青蛙個體在迭代過程中根據(jù)自身狀態(tài)動態(tài)調整慣性權重，并以停滯代數(shù)判斷是否對最優(yōu)個體進行優(yōu)化，避免了陷入局部最優(yōu).

以上文獻中的改進算法都較好地改善了基本SFLA算法，在克服種群陷入局部最優(yōu)缺陷的基礎上增加了種群多樣性. 考慮到傳統(tǒng)優(yōu)化算法—共軛梯度法具有較強的局部搜索能力，而現(xiàn)代智能優(yōu)化算法—基本蛙跳算法收斂精度不高，尋找一種方法將蛙跳算法與共軛梯度法結合起來從而凸顯各自的優(yōu)點顯得尤為重要，且歷來很少有學者將傳統(tǒng)優(yōu)化方法與基本蛙跳算法結合起來研究. 本文提出的對較好和較差個體進行更新的混合蛙跳算法(SFLA_HH)，充分利用了SFLA算法和共軛梯度法兩者的優(yōu)點，彌補了兩者的不足，將SFLA_HH算法與其他智能優(yōu)化算法進行對比，對五個測試問題的試驗結果表明，SFLA_HH算法收斂精度更高.

1 基本蛙跳算法與共軛梯度法分析

對無約束連續(xù)優(yōu)化問題：

minf(x)，x∈Rd

(1)

若x*∈Rd滿足：

f(x*)≤f(x)，?x∈Rd

(2)

則稱x*為f(x)在全空間Rd上的全局最小點或整體極小點.

1.1 SFLA原理

SFLA算法將每個個體看做池塘中的一只青蛙[6]，搜索區(qū)間即為整個池塘.SFLA算法首先在尋優(yōu)區(qū)間內隨機初始化一組向量來組成青蛙的初始種群[7]P={X1,X2,…,Xi,…,XF}(i=1,2,…,F)，第i只青蛙為Xi=(xi1,xi2,…,xid)，每一只青蛙代表一個待選解，xij為第i只青蛙第j維的分量. 對于每個青蛙個體，計算適應度函數(shù)值fit(Xi)，本文中適應度函數(shù)取為目標函數(shù)，然后將所有青蛙個體按照它們的適應度值進行升序排列，并分別放入m個模因組中. 設Mk為第k個模因組青蛙的集合(k=1,2,…,m)，表達式如下：

Mk={Xk+m(l-1)∈P|1≤k≤m;1≤l≤n}

(3)

式中，n為每個模因組中的青蛙的個數(shù).

青蛙移動的距離向量：

(4)

更新最差青蛙位置：

(5)

(6)

(7)

1.2 共軛梯度法

共軛梯度法[8]是由Hestenes和Stiefel( 1952)提出來的，是一種介于最速下降法和牛頓法之間的經(jīng)典非線性無約束優(yōu)化算法，它的基本思想是根據(jù)迭代點處的負梯度方向構造出一組共軛方向，再沿著這組方向搜索目標函數(shù)極值，共軛梯度法的機制保證了所得到的這組共軛方向就是函數(shù)值的下降方向. 共軛梯度法最大的優(yōu)勢在于同時解決了最速下降法收斂慢和牛頓法對目標函數(shù)要求較高且計算量大的不足，具有較好的局部搜索能力，是求解大型非線性無約束最優(yōu)化問題的有效算法之一，其求解流程如下：

步驟4令Xk+1=Xk+tkPk；

步驟6計算共軛方向Pk+1，令k=k+1并轉步驟3.

2 嵌入共軛梯度法的混合蛙跳算法

考慮到基本蛙跳算法中精英個體更新效率較低、較差個體更新效果不明顯等缺陷導致的進化后期易陷入局部最優(yōu)這一缺點，本文提出在基本蛙跳算法中引入共軛梯度法，對前p個模因組中的精英個體和后q個模因組中的落后個體直接進行更新，一方面增強了對較差個體的指導能力，另一方面提高了最差個體的更新效率. SFLA_HH算法首先對種群和參數(shù)進行初始化，各青蛙的初始位置在給定搜索區(qū)間內隨機生成；然后計算每只青蛙的適應度函數(shù)值，對函數(shù)值進行升值排序. 本文中適應度函數(shù)取為目標函數(shù)，故函數(shù)值越小代表點的位置越好，由此得到Xg；然后將排完序后的青蛙按照式(3)劃分模因組，找到每個模因組中的Xb和Xw，對模因組中的前p組和后q組與共軛梯度法進行結合，具體更新規(guī)則為：前p組以Xb為初始點，即X0=Xb，初始搜索方向P0取為-g(Xb)，根據(jù)X1=X0+tP0對Xb進行更新，其中步長t根據(jù)：

(8)

求解. 如果X1滿足給定的精度要求，則跳出共軛梯度法循環(huán)，否則，按下式：

Xk+1=Xk+tPk

(9)

(10)

進行下一點的迭代，重復計算直至達到給定的精度要求或次數(shù)，更新Xb，再按照式(4)、式(5)指導更新Xw；將排列在中間的的(m-p-q)個模因組按照式(5)、式(7)進行更新；將排列在最后的q個模因組與共軛梯度法結合，以Xw為初始點，初始搜索方向P0取為-g(Xw)，再按照上面的式(8)、式(9)、式(10)對Xw進行更新. 從整體效率來考慮，可以適當放低共軛梯度法的精度要求[9]，并且同時使用精度和循環(huán)代數(shù)一起作為判斷共軛梯度法停止的條件. 當所有模因組的局部更新操作都完成后，判斷是否達到全局搜索次數(shù)，若滿足，則輸出當前最好解，即為全局最優(yōu)解；否則，將全部青蛙混合，重復進行下一輪搜索. SFLA_HH算法流程如下：

步驟1隨機初始化F只青蛙，最大蛙跳步長為Smax，模因組數(shù)為m，每個模因組中的青蛙數(shù)為n，局部迭代次數(shù)為L，整體迭代次數(shù)為G；

步驟2計算所有青蛙適應度函數(shù)值；

步驟3將青蛙按照適應度函數(shù)值從小到大排序，適應度函數(shù)值最小的青蛙記為Xg；

步驟4青蛙種群根據(jù)分組規(guī)則按照(3)式劃分為m個模因組；分別記下每個模因組中的Xb和Xw；

步驟5對前p個模因組結合共軛梯度法，以模因組中Xb為初始點進行循環(huán)迭代r次或達到精度要求，更新Xb，再按照式(4)、式(5)指導更新Xw；對中間的(m-p-q)個模因組按照式(5)、式(7)進行局部搜索L次，更新Xw；對剩余的q個模因組以Xw為初始點行進行循環(huán)迭代r次或達到精度要求，更新Xw；

步驟6當局部搜索全部完成后，判斷是否達到全局混合迭代次數(shù)G，若滿足，則輸出當前最好解，即為全局最優(yōu)解；否則，將全部青蛙混合，返回步驟3進行下一輪搜索.

因為共軛梯度法對于一個n元正定二次目標函數(shù)最多n次就可以尋得最優(yōu)解，可見共軛梯度法的尋優(yōu)效率之高. 由于共軛梯度法的運算涉及到梯度計算，運算過程中調用共軛梯度法的次數(shù)越多，耗時越久，在本文中共軛梯度法的運算次數(shù)與兩個因素有關，一是結合共軛梯度法的組數(shù)，二是共軛梯度法的內部終止迭代次數(shù)r. 為了整體尋優(yōu)速度，本試驗調用共軛梯度法的次數(shù)不宜太多，故只選取前兩組和后兩組，即p=q=2.

共軛梯度法由于不涉及矩陣，僅僅存儲向量，因而存儲量小，適合于維數(shù)較高的優(yōu)化問題，因此混合蛙跳算法SFLA_HH對較高維數(shù)的函數(shù)優(yōu)化具有較大的優(yōu)勢.

3 實驗結果與分析

為驗證混合蛙跳算法SFLA_HH的尋優(yōu)效果和穩(wěn)定性，將SFLA_HH算法與基本SFLA算法在不同維度下進行試驗. 為了進一步驗證文中所提出的混合蛙跳算法的優(yōu)越性，將SFLA_HH與SFLA、文獻[2]中提出的內嵌擾動變異的混合蛙跳算法(DVSFLA)、文獻[10]中提出的自適應粒子群優(yōu)化算法(APSO)以及文獻[11]中提出的強化學習的人工蜂群算法(GABC)分別在30維時固定全局迭代次數(shù)情況下進行對比分析. 又將SFLA_HH與文獻[5]中基于新搜索策略的混合蛙跳算法(NSSFLA)在固定精度情況下進行對比分析. 三種情況對比均使用表1中5個典型的無約束優(yōu)化問題進行數(shù)值試驗，各問題的目標函數(shù)表達式、搜索范圍和理論最優(yōu)值如表1所示[12]，其中D為問題的維度.

函數(shù)f1為Sphere單峰函數(shù)，全局最小點是(0,0,…,0)；函數(shù)f2為Rastrigin函數(shù)，函數(shù)f3為Griewank函數(shù)，函數(shù)f4為Ackley函數(shù)，都是多峰函數(shù)，有很多局部極小點，全局最小點是(0,0,…,0)；函數(shù)f5為Rosenbrock函數(shù)，是非凸的病態(tài)函數(shù)，在極小值附近有陡峭的峽谷，用SFLA求解時很容易陷入局部極值，它的全局最小點是(1,1,…,1). 為了進一步比較各種算法的性能，并減少偶然性的影響，本文采用Matlab R2014b試驗平臺進行數(shù)值試驗，并對每個測試問題進行30次獨立試驗，取試驗所得的平均最優(yōu)值、標準差進行對比. 其中，平均最優(yōu)值為30次試驗中每次求得的全局最優(yōu)解相加除以30；標準差即為30次試驗中全局最優(yōu)解的標準差.

本文所選取的試驗參數(shù)如下，其余對比算法參數(shù)設置見對應文獻：

青蛙個體數(shù)F=200;

族群數(shù)m=20;

族群內青蛙個數(shù)n=10;

局部循環(huán)迭代次數(shù)L=10;

全局循環(huán)迭代次數(shù)G=200;

青蛙最大移動步長設置規(guī)則根據(jù)文獻[13]，即：

Smax=可行域的界×45%；

p=2；q=2；r=5；eps=1e-2.

表2為將SFLA_HH算法與基本SFLA算法在不同維度下進行試驗的結果對比.

表2 兩種算法在不同維度下對比

由表2中對比結果可以看出，在不同試驗維度下，無論是解的質量還是算法的穩(wěn)定性，SFLA_HH算法較SFLA算法均有較大提高. 對于五個測試問題，SFLA算法均未找到最優(yōu)解，且隨著維數(shù)增高，SFLA尋優(yōu)效果也越來越差，而SFLA_HH算法都找到了最優(yōu)解，并且解的精度在維數(shù)變化較大的情況下保持一定的穩(wěn)定性. 對于問題f1，f2，f3，SFLA_HH算法在三種維度下都找到了理論最優(yōu)解，

SFLA求解精度較差，且未找到最優(yōu)解；對于問題f4，f5，SFLA_HH算法也都找到了最優(yōu)解，SFLA算法求解效果較差，且未找到最優(yōu)解.

表3為30維時SFLA_HH與其他現(xiàn)代智能優(yōu)化算法在固定全局迭代次數(shù)情況下結果對比.

表4為SFLA_HH與基本蛙跳算法及文獻[5]中NSSFLA算法在固定精度情況下結果對比.

表3 SFLA_HH與新近知名智能優(yōu)化算法尋優(yōu)結果對比

從表3對比結果中可以看出，SFLA_HH算法與其他算法相比有明顯的優(yōu)勢，對于五個測試問題都找到了最優(yōu)解，其中對于f1，f2，f3都找到了理論最優(yōu)解；SFLA算法對于所有的問題均未找到最優(yōu)解；DVSFLA只對f1找到了最優(yōu)解；APSO和GABC對于f1，f2和f4均找到了最優(yōu)解，但求解精度都不如SFLA_HH，可見SFLA_HH的尋優(yōu)精度之高.

從表4可以看出，SFLA對于所有問題都沒能達到指定的精度，NSSFLA和SFLA_HH都達到了指定精度；對于f2，NSSFLA和SFLA_HH進化代數(shù)沒有太大差異；對于f3，SFLA_HH比NSSFLA效果略差；但對于f1和f5，SFLA_HH只需一次就可以達到指定精度，比NSSFLA所需次數(shù)少，對于f4，NSSFLA最少需要17次才可以達到指定精度，而SFLA_HH最少只需11次就可以達到指定精度，且平均次數(shù)也比NSSFLA少.

表4 固定目標精度下30次試驗結果對比

綜上，SFLA_HH收斂精度和平均進化代數(shù)均優(yōu)于基本蛙跳算法和其他幾種智能優(yōu)化算法.

4 結論

共軛梯度法是經(jīng)典無約束優(yōu)化算法，由于采用梯度信息，因此可以較快的收斂到函數(shù)極小值；基本蛙跳算法在搜索區(qū)間廣泛隨機采點，然后從各點出發(fā)，依據(jù)青蛙覓食原理搜尋全局最小點，因而具有較好的全局搜索能力. 本文所提出的SFLA_HH算法正是結合了兩者的優(yōu)點，對于排列在前面位置較好的模因組和后面位置較差的模因組均引入共軛梯度法，不僅加強了對最差青蛙個體的指導能力，更提高了最差青蛙的更新效率，進而提高了算法的收斂精度. 改進算法無論從收斂精度、進化代數(shù)還是穩(wěn)定性方面都有較大的優(yōu)越性，但仍存在一些問題，由于共軛梯度法每次循環(huán)都需要計算梯度信息，故對于有些復雜問題，或者非凸問題無法很好地解決，這也是需要改進的地方.

[1] 崔文華，劉曉冰，王偉,等.混合蛙跳算法研究綜述[J]. 控制與決策，2012，4(3)：481-486

[2] 季駿，戴月明，吳定會.內嵌擾動變異的混合蛙跳算法[J].計算機工程與應用，2015，51(12)：27-30

[3] 劉立群，王聯(lián)國，韓俊英,等.基于全局共享因子的混合蛙跳算法[J].計算機工程，2013，39(10)：162-166

[4] 張強，李盼池.量子混合蛙跳算法求解連續(xù)空間優(yōu)化問題[J].吉林大學學報：理學版，2013，51(3)：471-477

[5] 趙芳，張桂珠.基于新搜索策略的混合蛙跳算法[J].計算機應用與軟件，2015，32(8)：224-228

[6] 楊淑瑩，張樺.群體智能與仿生計算—Matlab技術實現(xiàn)[M].北京：電子工業(yè)出版社，2012：167-176

[7] 馬魯，陳國初，王海群.蛙跳算法及其在函數(shù)優(yōu)化中的應用[J].上海電機學院學報，2014，17(2)：68-75

[8] 孫文瑜，徐成賢，朱德通.最優(yōu)化方法[M].北京：高等教育出版社，2010：125-137

[9] 梁昔明，李德生.嵌入共軛梯度法的混合粒子群優(yōu)化算法[J].小型微型計算機系統(tǒng)，2014，35(4)：835-839

[10] Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man, and Cybernetics—Part B: Cybernetics, 2009,39(6): 1362-1381

[11] Zhu Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173

[12] Meng Jia-na, Lin Hong-fei. Transfer learning based on graph ranking[C]∥Proc. Of the 9th International Conference on Fuzzy Systems and Knowledge Discovery. [S.1.]: IEEE Press, 2012

[13] Eusuff M, Lansey K, Pasha F. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization [J]. Engineering Optimization, 2006, 38(2): 129-154

[責任編輯：佟啟巾]

Hybrid SFLA Algorithm with the Bidirectional Updates of Elite and Behind Individuals

Pang Kaili，Liang Ximing

(School of Science, Beijing University of Civil Engineering and Architecture, Beijing 100044)

A kind of hybrid Shuffled Frog Leaping Algorithm (SFLA) coupling with conjugate gradient method is proposed to solve the problem of low solution precision and easy to fall into local optimal solutions under basic SFLA. The elite individuals in the frontpmeme groups and the behind individuals in the lastqmeme groups are selected to search the solution with conjugate gradient method, which enhance the ability to guide the poor frogs in one hand, and in another hand update the worst frogs directly, and improve the convergence accuracy. The proposed hybrid SFLA algorithm combines the strongly global searing ability of SFLA with the fast local searching ability of conjugate gradient method. Comparisons among the hybrid SFLA and other well-known intelligent algorithms are made and the numerical experiment results show that, in terms of convergence or evolutionary generation, the improvements have been achieved greatly in the hybrid SFLA. The improved algorithm has a higher convergent precision, more stable optimal results, and better ability to jump out local optimal solution than other well-known intelligent algorithms.

shuffled frog leaping algorithm; conjugate gradient method; numerical experiment; fitness function

2016-07-09

國家自然科學基金(61463009)；北京市自然科學基金項目(4122022)；中央支持地方科研創(chuàng)新團隊項目(PXM2013- 014210- 000173).

龐凱立(1990—)，女，碩士研究生，研究方向； 智能優(yōu)化算法.

1004-6011(2016)04-0052-06

TP301.6

A