混合進化策略算法及其在函數(shù)優(yōu)化中的應用

張成，李明輝(沈陽化工大學數(shù)理系，遼寧沈陽110142)

混合進化策略算法及其在函數(shù)優(yōu)化中的應用

張成，李明輝
(沈陽化工大學數(shù)理系，遼寧沈陽110142)

自適應進化策略中高斯變異算子容易使進化過程陷入局部最優(yōu)，出現(xiàn)進化早熟.文中針對上述缺點，引入柯西變異算子和子代距離率方法.在進化前期采用柯西的變異，保證個體能夠快速地向全局最優(yōu)的方向移動;在進化后期采用高斯變異，當個體聚集在全局最優(yōu)解附近時，以較小的變異步長驅動個體向全局最優(yōu)解方向移動.子代距離率系數(shù)進行調整變異算子.通過對單峰與多峰函數(shù)仿真試驗，驗證了算法的有效性.

函數(shù)優(yōu)化;進化算法;進化策略;自適應步長

函數(shù)優(yōu)化是智能算法應用中的一個基本問題.進化算法是基于自然選擇原理的一種自適應搜索算法，是生命科學與工程科學的交叉學科，也是計算機科學和系統(tǒng)優(yōu)化領域的熱點研究課題.進化算法是現(xiàn)代科學計算的一種強有力方法，具有智能性、通用性和全局搜索能力，已成為函數(shù)優(yōu)化問題的重要工具.它包括遺傳算法、遺傳規(guī)劃、進化策略和進化規(guī)劃.

達爾文的自然選擇學說說明地球上的生物具有較強的繁殖能力，生物都是經(jīng)過長期進化而不斷完善自身的.大多數(shù)生物在繁殖過程中通過遺傳使物種保持相似的后代;而部分生物由于變異，后代具有明顯差異甚至形成新的物種.自然界中的生物根據(jù)優(yōu)勝劣汰的原則不斷地進行進化.進化策略算法是模擬生物進化而產(chǎn)生的一種進化算法，該方法在工程與控制領域有著重要的應用.

1 進化策略

進化策略由Rechenberg和Schwefel提出，是一種反映自然進化機制的隨機優(yōu)化技術.其搜索過程不依賴目標函數(shù)的梯度信息，具有較強的魯棒性［1］.大量的研究表明［2］，進化計算方法在求解一些復雜的問題時，效果通常優(yōu)于傳統(tǒng)的優(yōu)化算法.進化策略采用實數(shù)編碼，適用于求解實值函數(shù)優(yōu)化問題.進化策略算法按照其發(fā)展過程可劃分為以下幾種形式: (μ+1)，(μ+λ)，(μ，λ).本文采用(μ+λ)型，即父代種群由μ個個體組成，經(jīng)過重組，突變產(chǎn)生λ個體，在μ+λ個體中進行進化策略的選擇操作，最終生成下一代個體.

進化策略的工作步驟是:

(1)確定問題的表達方式.

(2)隨機生成初始種群，并計算適應度.

(3)根據(jù)進化策略，用下述操作產(chǎn)生新的群體.

①重組.將兩個父代個體交換目標變量和隨機因子產(chǎn)生新的個體.②變異.對重組后的個體添加隨機變量產(chǎn)生新的個體.③計算新的個體的適應度.④選擇.根據(jù)選擇策略，挑選優(yōu)良個體組成下一代群體.

(4)反復執(zhí)行(3)，直到達到終止條件，選擇最佳個體作為進化策略結果.

n維實值函數(shù)f:S→R，SRn，sj∈［aj，bj］，j= 1，2，…，n.尋找一點Xmin∈，使f(x)最小，即X∈S，f(Xmin)f(X).Backend schaefer提出的自適應進化策略算法(SAEP)，采用公式(1)對個體進行突變操作

圖1 高斯分布與柯西分析比較

2 進化策略算法變異算子的改進

在進化策略中，變異算子作為主要算子起著相當大的作用.所以進化策略的收斂速度與變異有著密切的關系.為了改變現(xiàn)有進化策略在收斂性能方面存在的不足，這里主要從變異這一方面進行改進.因此，在原來變異算子的基礎上提出一種新的變異算子，即柯西變異算子.

Caucy(1)和Caucyj(1)均為一個柯西分布的隨機數(shù)，它比高斯分布產(chǎn)生的隨機變量的范圍大，同時對目標變量(xij(t))和策略變量(ηij(t))進行修改.稱公式(2)為柯西變異算子(Caucy)［5］.根據(jù)兩種分布的特點，提出改進的混合變異進化策略算法.在進化初期引用柯西變異算子，在進化后期引用高斯變異算子.這樣可以在初期應用柯西隨機數(shù)產(chǎn)生較大的變異步長，使群體中個體能夠快速向全局最優(yōu)解移動，以提高收斂速度，避免出現(xiàn)早熟問題.同時，在進化后期采用高斯變異，可以保證當前代中最優(yōu)個體穩(wěn)步向全局最優(yōu)解方向移動，提高收斂精度.

對于變異算子的選擇引入子代距離率pdistance(t).第t子代距離率由下式計算:

3 仿真試驗

測試函數(shù)1:De Jong函數(shù)min f=i∈［－512，512］.這是一個典型的多元單峰函數(shù)，二維(n=2)圖形如圖2所示，該函數(shù)的最小值出現(xiàn)在坐標原點，最小值為0.

圖2 De Jong函數(shù)2維圖像

設種群規(guī)模為N=50，維數(shù)為n=20，隨機生成初始種群P(0)，進化代數(shù)gen=200獨立運行10次.下面將高斯變異(SAEP)、柯西變異(CEA)、本文算法(GCEA)及遺傳算法(GA)四種測試結果進行以比分析.同時圖3、圖4給出種群初始化及200代種群均值與最優(yōu)解的變化趨勢圖.

圖3 混合變異解與均值變化

表1 算法仿真試驗對比表

圖4 種群初始化目標函數(shù)散點圖

表2 四種算法運行10次最優(yōu)解均值分布情況

表1表明本文算法可以在相同條件下使收斂精度高于其它算法.由圖3可以看出本文算法在進化初期能夠提高進化速度，使種群中的個體能夠快速、穩(wěn)定地向全局最優(yōu)解的方向移動.而在進化后期可以保證個體在全局最優(yōu)解附近波動，提高收斂精度.圖4說明在進化初期種群分布范圍較廣，能夠搜索范圍比較完整，能夠有效在全局進行搜索.表2說明混合變異算法在運行上比較穩(wěn)定且平均收斂程度要高于遺傳算法.

測試函數(shù)2:Shubert函數(shù)是一個典型多元多峰值的函數(shù).

表3 各種算法運行10次最優(yōu)解均值分布情況

表3中數(shù)據(jù)說明本文算法對于多峰極值問題是有效的.在同維數(shù)(2維)、同個體(50個)前提下本文算法通過較少進化代數(shù)即可以取得優(yōu)化結果.對于精度要求較高的優(yōu)化問題，本文算法也能達到理想的收斂效果.

［1］周明，孫樹棟.遺傳算法原理及應用［M］.北京國防工業(yè)出版社，1999.

［2］Kim JH.MYUNG H.Evolutionary programming techniques for constrained op tmfization problems［J］.IEEE Transactions on Evolutionary Computation 1997，1(2):129－140.

［3］X.Yao，Yule，Glen.Evolutionary Programmingmade faster［J］.IEEE Trans.Evolutionary Computation，1999，3(2):82－102.

［4］T.Back，H－P，Schaefer.An overview of evolutionary algorithms for parameter optimization［J］.Evolutionary Computation，1993(11):1－23.

［5］王戰(zhàn)全，云慶夏，等.進化策略中變異算子的改進研究［J］.計算機仿真，1999(7):16－3.

［6］雷英杰，等.MATLAB遺傳算法工具箱及應用［M］.西安:西安電子科技大學出版社，2005:111－115.

(責任編輯:王前)

Abstract:In adaptive evolution strategy，Gaussianmutation operatormade the evolutionary process fall into local optimal，the evolution appeared premature.Aiming at the shortcoming，introducing Cauchymutation operator and progeny distance ratemethod.In the early evolution，using the variation of Cauchy，ensure the individual can quicklymove to global optimal direction.In the later evolution using Gaussian mutation，when the individual gathered in the vicinity of global optimum solution，with smallermutation step drive the individual tomove to global optimal solution direction.Through the single－peak and multi－peak functions，a simulation testing verifies the effectiveness of this algorithm.

Key words:function optimization;evolutionary algorithm;evolutionary strategy;self－adaptive step

Hybrid Evolutionary Strategy Algorithm and Its Application in Function Optim ization

ZHANG Cheng，LIMing－h(huán)ui
(Shenyang University of Chemical Technology，Shenyang，Liaoning 110004，China)

TP301.6

A

1008－7974(2011)04－0028－03

2010－10－20

張成(1979－)，男，遼寧錦州人，碩士，沈陽化工大學數(shù)理系講師.