李國平

湖南工學(xué)院，湖南衡陽 421002

面向多峰函數(shù)優(yōu)化的PASFLI算法及應(yīng)用

李國平

湖南工學(xué)院，湖南衡陽 421002

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）是Eusuff等人根據(jù)混合競爭進化思想，提出的一種新型智能啟發(fā)式計算技術(shù)[1]。由于該算法具有實現(xiàn)簡單、前期收斂速度快、搜索能力強等特點，已被成功應(yīng)用于復(fù)雜非線性函數(shù)優(yōu)化以及車間流水調(diào)度、ΤSP等工程領(lǐng)域[2-3]。目前，改善算法復(fù)雜問題優(yōu)化性能已成為研究熱點之一[4-9]。

針對基本SFLA求解復(fù)雜優(yōu)化問題時存在后期收斂速度慢、早熟收斂等[6]缺陷，學(xué)者進行了大量研究，提出了相應(yīng)的改進方法。常見的改進策略是通過修改SFLA參數(shù)以提高算法收斂性能，如采用線性遞減調(diào)整慣性權(quán)重[4]、搜索加速因子[5]來協(xié)調(diào)全局和局部搜索能力；也有的通過引入其他智能算子，如自適應(yīng)混沌變異算子[6]、領(lǐng)域正交叉算子[7]、多種群協(xié)同進化[8]等形成混合智能蛙跳算法；還有的通過增加子種群多樣性，如EO-SFLA[9]來增強SFLA全局尋優(yōu)能力。這些改進策略不同程度地改善了算法性能，但是由于SFLA提出時間不長，相應(yīng)理論分析較少，特別是對于復(fù)雜高維多峰函數(shù)優(yōu)化問題，收斂效果不理想仍是SFLA面臨的難題。

免疫克隆選擇算法（Clonal Selection Algorithm，CSA）是生物免疫理論重要算法之一[10]。CSA能夠?qū)崿F(xiàn)局部與全局同步搜索，有效地避免了早熟和陷入局部極值，特別是在算法運行后期，隨著親和度的提高，CSA能夠很快地收斂于全局極值而且具有較高的精度[11]。CSA的缺陷在于對初始值比較敏感，算法運算初期收斂效率不高。文獻[12]對CSA與SFLA協(xié)同進化進行了嘗試，但是其組合方式仍屬于多種群獨立協(xié)同進化范疇。針對基本SFLA在高維多峰函數(shù)優(yōu)化時早熟及難以找到所有全局極值的缺陷，利用SFLA及CSA各自優(yōu)勢，提出了自適應(yīng)混合蛙跳免疫算法（Polymorphic Adaptive Shuffled Frog Leaping Immune Algorithm，PASFLIA）。算法采用雙層進化模式，在低層混合蛙跳操作中，加入多態(tài)自適應(yīng)子種群機制，將子種群動態(tài)地劃分為精英群和擴散群；在算法進化后期，提出全局極值篩選策略，將子種群極值點提升到高層進行免疫克隆選擇操作。仿真結(jié)果表明PASFLIA在高維多峰函數(shù)優(yōu)化方面取得了良好效果。

1 PASFLIA算法實現(xiàn)

PASFLIA采用兩層進化模型（如圖1所示），低層為青蛙粒子種群集合SF={E1，E2，…，EM}，SF又劃分為M個子種（族）群；高層為免疫抗體種群C。更新操作是指一方面將低層子種群個體極值提升到高層，另一方面將高層經(jīng)過CSA操作后的個體極值更新低層中對應(yīng)的個體極值。

圖1 PASFLIA算法模型

1.1 多態(tài)子種群自適應(yīng)SFLA操作

基本SFLA工作過程可以描述為：由F只青蛙組成的種群SF，對于n維優(yōu)化問題，每只青蛙代表優(yōu)化問題的一個解，第k只青蛙位置為Xk={xk1，xk2，…，xkn}。計算每只青蛙的適應(yīng)度值f(Xk)[11]并按降序排列，然后平均分配到M個子種群Ei(1≤i≤M)中，每個子種群青蛙數(shù)為N。Ei按式（1）進行劃分。

SFLA對子種群Ei中適應(yīng)度值最差的解Xi，w按式（2）進行更新。

其中，r∈[0，1]且為隨機數(shù)，Xi，b為Ei當(dāng)前適應(yīng)度最好的解。如果f[Xi，w(t+1)]優(yōu)于f[Xi，w(t)]，則用新位置替代舊位置，否則用Xg（Xg為當(dāng)前青蛙群體中適應(yīng)度最好的解）代替Xi，b執(zhí)行更新策略（2），如果結(jié)果仍然不能優(yōu)于舊位置，則生成隨機青蛙取代Xi，w。Ei重復(fù)執(zhí)行局部搜索過程，直到局部搜索迭代次數(shù)為止。當(dāng)所有子種群完成搜索后，所有青蛙重新組合，然后重新劃分族群，重新進行局部搜索，并更新群體最優(yōu)解位置，直到滿足終止條件。

研究表明，隨著迭代次數(shù)增加，SFLA收斂效率明顯降低。這是因為，在算法運算后期，當(dāng)某個青蛙粒子為當(dāng)前最優(yōu)位置時，其他青蛙會向其聚攏，特別是如果該位置為局部極值點，則算法就會很容易陷入局部極值，需要迭代較多次數(shù)才能跳出[9]，并出現(xiàn)早熟現(xiàn)象。為了提高基本SFLA算法收斂速度和避免早熟，本文提出了多態(tài)子種群機制：將子種群Ei按適應(yīng)度值降序排列，適應(yīng)度值較優(yōu)的青蛙粒子劃分到精英群，剩余的為擴散群。精英群內(nèi)的青蛙粒子具有較優(yōu)的適應(yīng)度值，因此對其采用精英學(xué)習(xí)機制，使得粒子能夠以更大的概率跳出局部極值；擴散群內(nèi)的青蛙粒子采用改進的粒子更新策略，充分利用了歷史信息，擴大了樣本多樣性和搜索空間。

定義1（子種群劃分規(guī)模確定因子D() t）

其中，α為取值極小的正數(shù)。當(dāng)D(t)=0時表示進化停止。定義D(t)之后，擴散群規(guī)模由式（4）確定。

其中，Ni，s(t)為Ei內(nèi)的擴散群規(guī)模，ω為規(guī)?？刂葡禂?shù)。為了避免Ni，s(t)的數(shù)值過大或者過小，設(shè)定Nmin≤Ni，s(t)≤Nmax。從式（3）、（4）可以看出，進化初期D(t)取值較大，擴散群規(guī)模較小。隨著迭代次數(shù)增加，D(t)取值逐漸減少，這表明種群樣本多樣性降低，Ni，s(t)規(guī)模變大，因此算法可以用更多的擴散粒子去增加樣本多樣性，提高搜索空間。

定義2（擴散群青蛙粒子更新策略）

其中，Xi，e、Xi，f為Ei中隨機抽取的個體(e≠f≠b≠w)，式（5）在式（2）的基礎(chǔ)上增加了其他個體信息，擴大了樣本空間。如果上式不能產(chǎn)生更優(yōu)解，則生成隨機青蛙替代舊粒子。

精英群Ni，L(t)規(guī)?？捎墒剑?）確定。

定義3（精英群精英學(xué)習(xí)機制）

其中，Tmax為算法最大迭代次數(shù)。精英學(xué)習(xí)機制實質(zhì)為具有自適應(yīng)的高斯變異，隨著迭代次數(shù)增加，σ逐漸減小。采用式（7）更新方式，使得青蛙粒子在算法初期能夠在較大學(xué)習(xí)空間內(nèi)搜索，更容易跳出局部極值；在算法后期，青蛙粒子在較小的學(xué)習(xí)空間內(nèi)進行較精細度搜索，有利于提高算法精度。

1.2 高層CSA操作

定義4（同峰判斷準(zhǔn)則）

對于多峰函數(shù)f(x)，xa、xb為函數(shù)的兩個全局極值點，在兩點之間均勻插入l-1個點，得到l+1個點組成的集合L={xa，xa+1，…，xb}。依次從L集合中取兩兩相鄰的點xn、xn+1(a≤n〈b)，若式（9）值出現(xiàn)由正變負，則說明xa、xb為異峰全局極值點，否則為同峰全局極值點。

全局極值篩選策略：設(shè)子種群Ei極值點集合為Pi= {Xj}，j∈(i·N，(i+1)·N]，全局極值點結(jié)合為Pi，min。取Xi，b為Pi，min第一點，然后依次從集合Pi中取點Xj，如果滿足式（10），則Xj為全局極值點。

其中，f(a)為理論全局極值，ε為已設(shè)定常數(shù)。如果Xj滿足式（10），將其與Pi，min的點依次判斷是否同峰。如果同峰且適應(yīng)度值優(yōu)于已存在的點，則用Xj替代該點，若為異峰，則將Xj加入到Pi，min中。

定義5（親和度）定義混合蛙跳算法的適應(yīng)度函數(shù)為免疫克隆親和度函數(shù)。即

高層CSA操作種群C={ai}由低層個子種群Pi，min組成。高層CSA操作工作過程為：

（1）克隆擴增：對于Pi，min中的抗體按照式（12）進行克隆擴增。

其中，aff(Ej)為低層Ej中最優(yōu)個體親和度值。由式（12）可以看出，適應(yīng)度值越優(yōu)的子種群其克隆倍數(shù)越大，使得具有高親和力的抗體獲得了更多的克隆機會。

（2）自適應(yīng)變異：克隆后的抗體按照式（13）進行高斯變異。

其中，ρ、η為調(diào)節(jié)系數(shù)，Cu、Cl為Ck上下限。上式表明，進化初期，粒子在較大空間內(nèi)變異。隨著迭代次數(shù)增加，算法將在小范圍內(nèi)進行精細搜索。

（3）免疫選擇。對于抗體Ck(t)，其經(jīng)過克隆及變異得到的抗體集合為S，取S中親和度最優(yōu)個體C′k(t)，并判斷C′k(t)是否優(yōu)于Ck(t)，若是，則Ck(t+1)←C′k(t)，否則Ck(t)保持不變。這種選擇機制確保了子種群最優(yōu)解不會變得更差。

2 PASFLIA收斂性及算法流程

2.1 PASFLIA收斂性

文獻[9]給出了基本SFLA算法的收斂性證明，并指出SFLA依概率1收斂于全局最優(yōu)解，在此基礎(chǔ)上，本文就PASFLIA算法收斂性進行分析。對于隨機算法G、優(yōu)化問題〈S，f〉（S為可行解空間，f為適應(yīng)度函數(shù)），Xk表示第k次迭代結(jié)果，第k+1次結(jié)果Xk+1=G() Xk，δ（δ為算法G搜索過的解）。

條件1（假設(shè)函數(shù)f為最小化函數(shù)優(yōu)化問題）

f(G(X，δ))≤f(X)，并且如果δ∈S，則有f(G(X，δ))≤f(δ)。

綜上所述，PASFLIA具有全局收斂性，證畢。

2.2 PASFLIA算法實現(xiàn)流程

PASFLIA算法主要流程的偽碼描述如下：

步驟1算法設(shè)置：設(shè)置種群規(guī)模F，子族群數(shù)量M，精英群與擴散群規(guī)?？刂葡禂?shù)ω，最大迭代次數(shù)。

步驟2初始化：隨機產(chǎn)生規(guī)模為F的青蛙初始種群，迭代次數(shù)t←0。

步驟3低層自適應(yīng)SFLA操作：青蛙粒子按適應(yīng)度值降序排列，根據(jù)式（1）劃分子種群；

步驟3.1局部收索：對于每個子種群Ei，根據(jù)式（4）、（6）確定精英群和擴散群規(guī)模；根據(jù)式（7）對精英群內(nèi)粒子進行更新，根據(jù)式（5）對擴散群最差個體進行更新。

步驟3.2局部迭代停止判斷：判斷局部迭代次數(shù)是否滿足，不滿足繼續(xù)局部搜索。

步驟3.3個體極值集合Pi與全局極值集合Pi，min更新。

步驟4是否進入高層CSA操作判斷：如果迭代次數(shù)t≤tC（tC為高層開始迭代次數(shù)），t←t+1，轉(zhuǎn)步驟3；否則進入高層CSA操作。

步驟5高層CSA操作：

步驟5.1根據(jù)式（12）對克隆抗體克隆，根據(jù)式（13）對抗體進行變異，免疫選擇操作。

步驟5.2更新子種群極值點，轉(zhuǎn)步驟3。

步驟6算法停止判斷：判斷算法是否滿足終止條件，是輸出結(jié)果，算法結(jié)束；否則轉(zhuǎn)步驟3。

3 仿真實驗

3.1 實例仿真

為了驗證PASFLIA算法性能，在Matlab7.0仿真平臺上，采用以下多峰函數(shù)進行仿真，其中f1為單模態(tài)函數(shù)，f2具有少量局部極值，f3～f6具有大量局部極值。PASFLIA算法參數(shù)設(shè)置為：F=500，M=10，N=50，ω=0.75，ω1=0.8， ω2=0.2，ε=1×10-4，局部迭代10次，全局迭代500次。

為進一步分析PASFLIA在高維復(fù)雜函數(shù)下的尋優(yōu)能力，將其應(yīng)用于多維函數(shù)f1、f4優(yōu)化過程中。仿真實驗設(shè)定不同的維數(shù)（由于篇幅限制D取1 000和5 000），并與算法PASFLA和ASFLIA進行比較。圖4給出了D=5 000時的函數(shù)收斂曲線，表2給出了高維情況下PASFLIA算法與其他兩種算法對比結(jié)果。

3.2 PASFLIA性能分析

從表1可以看出，PASFLIA各項對比指標(biāo)明顯優(yōu)于PASFLA及ASFLIA算法。除函數(shù)f3外，PASFLIA都找到了函數(shù)的理論最優(yōu)值，而其他兩種算法均未找到函數(shù)的理論最優(yōu)值。從圖2、3可以看出，PASFLIA收斂效率明顯高于其他兩種算法，在500次迭代內(nèi)完成了尋優(yōu)運算，此外ASFLIA的收斂性能要優(yōu)于PASFLA算法，這說明免疫克隆選擇操作對算法運算后期提高收斂能力具有一定的效果。從表2和圖4可以看出，與其他兩種算法相比，PASFLIA在高維函數(shù)優(yōu)化過程中效果更佳突出，隨著函數(shù)維數(shù)的增加，PASFLIA收斂精度并沒有明顯降低，迭代次數(shù)沒有明顯增加。

表1 PASFLIA算法與其他兩種算法對比

圖2 f2、f3函數(shù)收斂曲線

圖3 f5、f6函數(shù)收斂曲線

圖4 維數(shù)為5 000時f1、f4函數(shù)收斂曲線

表2 高維情況下PASFLIA算法與其他兩種算法對比

PASFLIA之所以具有突出的優(yōu)化能力，是因為多態(tài)子種群自適應(yīng)的使用，改善了算法在運算后期樣本多樣性，精英學(xué)習(xí)機制的引入提高了算法跳出局部極值的能力，免疫克隆選擇操作進一步提高了算法求解復(fù)雜多維函數(shù)的性能。此外，全局機制篩選策略保證了算法能夠找出多峰函數(shù)的全部全局極值點。

4 結(jié)語

對混合蛙跳算法改進及在復(fù)雜多峰優(yōu)化中的應(yīng)用問題進行了研究。提出了具有雙層進化模式的多態(tài)子種群自適應(yīng)混合蛙跳免疫算法。加入了多態(tài)自適應(yīng)子種群機制，在算法進化后期，給出了全局極值篩選策略，并分析了算法的全局收斂性。復(fù)雜多峰函數(shù)仿真實驗表明，多態(tài)子種群自適應(yīng)機制及免疫克隆選擇操作擴大了種群樣本空間，平衡了全局與局部的關(guān)系，明顯增強了算法求解復(fù)雜多維函數(shù)的能力。

[1]Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management，2003，129（3）：210-225.

[2]Rahimi-Vahed A，Mirzaei A H.A hybrid multi-objective shuffled frog-leaping algorithm for a mixed model assembly line sequencing problem[J].Computers and Industrial Engineering，2007，53（4）：642-666.

[3]羅雪暉，楊燁，李霞.改進混合蛙跳算法求解旅行商問題[J].通信學(xué)報，2009，30（7）：130-135.

[4]劉悅婷.帶有選擇和自適應(yīng)變異機制的混合蛙跳算法[J].計算機工程，2012，38（23）：206-210.

[5]Elbeltagi E，Hegazy Τ，Grierson D.A modified shuffled frogleaping optimization algorithm applications to project management[J].Structure and Infrastructure Engineering，2007，3（1）：53-60.

[6]葛宇，王學(xué)平，梁靜.自適應(yīng)混沌變異蛙跳算法[J].計算機應(yīng)用研究，2011，28（3）：945-947.

[7]孟慶瑩，王聯(lián)國.基于領(lǐng)域正交叉算子的混合蛙跳算法[J].計算機工程與應(yīng)用，2011，47（36）：54-56.

[8]Niknam Τ，F(xiàn)arsani E A.A hybrid evolutionary algorithm for distribution feeder reconfiguration[J].Science China：Τechnological Sciences，2010，53（4）：950-959.

[9]駱劍平，陳泯融.混合蛙跳算法及其改進算法的運動軌跡及收斂性分析[J].信號處理，2010，26（9）：1428-1433.

[10]劉芳，潘曉英.基于免疫克隆選擇的塊匹配運動估計[J].軟件學(xué)報，2007，18（4）：850-860.

[11]吳建輝，章兢，李仁發(fā)，等.多子種群微粒群免疫算法及其在函數(shù)優(yōu)化中應(yīng)用[J].計算機研究與發(fā)展，2012，49（9）：1883-1898.

[12]Antariksha B.A clonal selection based shuffled frog leaping algorithm[C]//IEEE Int Advance Computing Conf.New York：IEEE Press，2009：125-130.

LI Guoping

Hunan Institution of Τechnology,Hengyang,Hunan 421002,China

As basic Shuffled Frog Leaping Algorithm（SFLA）has many problems in the high dimensional multimodal function optimization such as premature and difficult to find all global extremes,a hybrid intelligent Polymorphic Adaptive Shuffled Frog Leaping Immune Algorithm（PASFLIA）is presented.PASFLIA which combines the SFLA and immune Clonal Selection Algorithm （CSA）technology is convergent to the global optimal solution with probability 1.PASFLIA adopts a double-layer model evolution:in the lower layer,the polymorphic adaptive population mechanism is joined to SFLA,which improves the diversity of the population,and effectively suppresses premature behavior of the convergence progress;in the higher layer,the global extreme screening strategy is proposed,which puts the population extreme points to high-level immune clonal selection operation,further enhancing the global optimization ability.Τhe complex multimodal function simulation experiments results show that the PASFLIA can quickly and efficiently give all the global optimal solution.

shuffled frog leaping algorithm;immune algorithm;adaptive;function optimization

針對基本混合蛙跳算法在高維多峰函數(shù)優(yōu)化時早熟及難以找到所有全局極值的問題，提出了一種具有混合智能的多態(tài)子種群自適應(yīng)混合蛙跳免疫算法，證明了算法以概率1收斂于全局最優(yōu)解。該算法采用雙層進化模式，融合了混合蛙跳、免疫克隆選擇技術(shù)。在低層混合蛙跳操作中，加入了多態(tài)自適應(yīng)子種群機制，提高了子種群多樣性，有效抑制了早熟現(xiàn)象；在算法進化后期，提出了全局極值篩選策略，將子種群極值點提升到高層免疫克隆選擇操作，進一步提高了全局尋優(yōu)能力。通過復(fù)雜多峰函數(shù)仿真實驗，表明該算法能夠快速有效地給出全部全局最優(yōu)解。

混合蛙跳算法；免疫算法；自適應(yīng)；函數(shù)優(yōu)化

A

ΤP183

10.3778/j.issn.1002-8331.1306-0061

LI Guoping.PASFLI algorithm for multimodal function optimization and its application.Computer Engineering and Applications,2013,49（21）：199-203.

李國平（1979—），男，講師，主要研究方向：數(shù)值最優(yōu)化和智能處理。

2013-06-08

2013-09-16

1002-8331（2013）21-0199-05