基于反饋和混沌變異的自適應(yīng)進(jìn)化策略

摘 要：為了提高進(jìn)化策略的搜索精度和全局搜索能力，提出了一種基于反饋和混沌變異的改進(jìn)進(jìn)化策略，將各代當(dāng)前最優(yōu)搜索結(jié)果反饋到變異步長的更新公式中，通過對變異算子中隨機(jī)數(shù)方差的調(diào)整使進(jìn)化策略的變異步長隨搜索過程自適應(yīng)地變化，同時根據(jù)混沌運(yùn)動具有遍歷性的特點(diǎn)，利用混沌變異產(chǎn)生個體，保證種群中的部分個體在搜索后期仍保持較大的跳出局部極小的能力，從而達(dá)到提高算法全局搜索能力和搜索精度。為了對比改進(jìn)后進(jìn)化策略與常規(guī)進(jìn)化策略的優(yōu)化效果，利用三個測試函數(shù)對兩種進(jìn)化策略進(jìn)行了仿真測試，測試結(jié)果表明，與常規(guī)進(jìn)化策略相比，提出的基于反饋和混沌變異進(jìn)化策略具有更高的搜索精度和更強(qiáng)的全局搜索能力。

關(guān)鍵詞：進(jìn)化策略；反饋機(jī)制；混沌變異；變異步長；全局搜索

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2056-03

doi:10.3969/j.issn.1001-3695.2009.06.017

Adaptive evolutionary strategy based on feedback and chaotic mutation

LI Guang-wen， JIA Qiu-ling， LIU Xiao-xiong， ZHANG Wei-guo

(College of Automation， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:In order to enhance the global searching ability and precision，this paper proposed an adaptive evolutionary strategy based on the feedback and chaos mutation (ESBFCM)，in which the information of every generation’s current optimal searching result and sharing degree was fed into the mutating formula. By tuning the variance of the mutation operator according to the feedback information，changed the mutation step of ES with the current searching result. And a part of individuals of the population in the searching procedure kept higher probability of jumping out the local minimum by the chaotic mutation. By these measures，enhanced the searching precision and the global searching ability.To compare the optimizing effect between traditional ES and the ESBFCM， the test based on three benchmarks were done， the test result demonstrates that the ESBFCM has higher the global searching ability and precision than the traditional ES.

Key words:evolutionary strategy; feedback mechanism; chaotic mutation; mutation step; global searching

進(jìn)化策略是20世紀(jì)60年代由德國的Ingo Rechenberg等人所提出的，它是針對連續(xù)函數(shù)參數(shù)優(yōu)化問題而設(shè)計的^[1]。

由于進(jìn)化策略能較好地解決連續(xù)函數(shù)優(yōu)化問題，幾十年來一直受到人們的關(guān)注，有很多學(xué)者投入到進(jìn)化策略的改進(jìn)研究中，取得了很多成果。盡管進(jìn)化策略在解決連續(xù)函數(shù)優(yōu)化問題方面顯示了其優(yōu)勢，但是在進(jìn)化策略的應(yīng)用中，變異步長的選擇始終是個棘手的問題。變異步長選擇過大，會提高全局搜索能力，但是搜索精度不高；變異步長選擇過小，則容易陷入局部極小^[2]。

本文將進(jìn)化策略搜索的結(jié)果反饋到變異步長的更新中，使進(jìn)化策略的變異步長隨搜索過程自適應(yīng)調(diào)整。同時為了保證進(jìn)化策略的全局搜索能力，在引入反饋信息的基礎(chǔ)上，利用混沌具有隨機(jī)性、遍歷性和對初始條件的敏感性的特點(diǎn)，采用混沌變異的方法產(chǎn)生部分個體，使得種群中的部分個體在搜索后期仍保持較大的跳出局部極小的能力。通過這兩個措施使改進(jìn)后的進(jìn)化策略能夠隨搜索過程的自動調(diào)整變異步長，達(dá)到提高全局搜索能力和搜索精度的目的。

1 進(jìn)化策略（μ，λ）-ES

目前進(jìn)化策略主要有（μ+λ）-ES和（μ，λ）-ES兩種方法。由于（μ，λ）-ES比（μ+λ）-ES具有更大的優(yōu)越性，本文主要針對（μ，λ）-ES進(jìn)行改進(jìn)。

（μ，λ）-ES很簡單，其計算步驟如下：

a)采用實(shí)數(shù)編碼。隨機(jī)生成μ個個體，構(gòu)成第一代種群(x1，x2，…，xμ)。

b)變異。每個個體進(jìn)行變異，產(chǎn)生λ/μ個子個體，整個種群一共產(chǎn)生λ個個體，變異步長σi，計算公式如式(1)，個體變異式如式(2)。

σ′i=σi exp(τ1 randi1+τ2 randi2)(1)

X′i=Xi+σ′i randi3(2)

式(1)(2)中的randi1、randi2和randi3均為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)；τ1和τ2為σi的控制參數(shù)。Schwefel給出的建議計算式如下：

τ1=(2n)-1(3)τ2=(2n)-1(4)

式(3)和(4)中的n為種群中個體個數(shù)。

c)評價。對于變異產(chǎn)生的個體，計算各個體的適應(yīng)度，由于個體基因型不同，體現(xiàn)出對環(huán)境的不同適應(yīng)性。 

d)選擇。從變異產(chǎn)生的λ個子個體中選擇適應(yīng)度大的μ個個體，構(gòu)成下一代種群。判斷終止條件是否滿足，若是，則終止迭代；否則轉(zhuǎn)到步驟b)。

(μ，λ)-ES的搜索精度取決于變異公式中正態(tài)分布方差的選擇，方差越大，個體變異的幅度越大，(μ，λ)-ES進(jìn)化策略的全局搜索能力越強(qiáng)，也就是說方差決定了變異步長的大小。為了提高進(jìn)化策略的全局搜索能力，參考文獻(xiàn)[3，4]引入Cauchy變異算子，用服從Cauchy分布的隨機(jī)數(shù)代替服從正態(tài)分布的隨機(jī)數(shù)。為了發(fā)揮柯西變異算子產(chǎn)生大的變異的能力以減小陷入局部最優(yōu)點(diǎn)的危險， 同時利用正態(tài)變異算子局部搜索能力佳的優(yōu)點(diǎn)， 以提高收斂速度， 文獻(xiàn)[5]中提出了一個折中的方案， 將柯西變異算子和正態(tài)變異算子結(jié)合起來， 定義一個新的變異算子， 稱之為平均變異算子。文獻(xiàn)[6]分析比較了正態(tài)變異、Cauchy變異、平均變異的局部和全局搜索能力，證明了Gauss變異局部搜索能力最強(qiáng)，平均變異的全局搜索能力最強(qiáng)，而Cauchy變異的局部和全局搜索能力均居中。

2 基于反饋和混沌變異的進(jìn)化策略

影響進(jìn)化策略搜索結(jié)果和收斂速度的因素除了變異步長以外，初始種群的選擇也起著很重要的作用。一般情況下，進(jìn)化策略的初始種群是隨機(jī)生成的，如果個體分布集中，則可能導(dǎo)致算法收斂速度慢，陷入局部極小。所以應(yīng)盡可能地保證初始種群個體在搜索空間上均勻分布，在搜索過程中能夠遍歷整個空間。為了做到這一點(diǎn)，本文提出了一種基于反饋和混沌變異的進(jìn)化策略(evolutionary strategy based on the feedback and chaotic mutation，ESBFCM)，利用混沌具有遍歷性的特點(diǎn)來提高進(jìn)化策略的全局搜索能力。

混沌是非線性動力學(xué)系統(tǒng)所特有的一種運(yùn)動形式^[7]，體現(xiàn)了系統(tǒng)內(nèi)在的隨機(jī)性。混沌具有隨機(jī)性、遍歷性和對初始條件的敏感性，能夠在一定范圍內(nèi)按自身規(guī)律遍歷所有狀態(tài)。所以，如果把混沌序列引入到進(jìn)化策略之中，就有可能提高算法的搜索能力。本章探討混沌序列與進(jìn)化策略的結(jié)合途徑。

目前學(xué)術(shù)界對混沌還沒有一個嚴(yán)格的定義，一般將確定性方程得到的具有隨機(jī)性的運(yùn)動狀態(tài)稱為混沌，呈現(xiàn)混沌狀態(tài)的變量稱為混沌變量。Logistic映射是一個典型的混沌系統(tǒng)，其有限差分方程如下：

zn+1=f(u，zn)=uzn(1-zn)；n=0，1，2，…(5)

其中：u為控制參數(shù)，初值z0∈[0，1]。當(dāng)u確定后，由任意z0可以迭代出一個時間序列，當(dāng)u=4時，差分方程式(5)將呈現(xiàn)完全混沌狀態(tài)，所得到的時間序列是區(qū)間上的一個滿映射。

混沌雖然是由確定性的方程導(dǎo)出來的，但是它具有一些特殊的運(yùn)動規(guī)律，主要表現(xiàn)如下：

a)隨機(jī)性。當(dāng)u=4時，Logistic映射在區(qū)間上呈現(xiàn)不穩(wěn)定的運(yùn)動狀態(tài)，隨著時間的增加，其運(yùn)動狀態(tài)呈現(xiàn)完全的隨機(jī)狀態(tài)。

b)遍歷性。混沌運(yùn)動的遍歷性是指混沌變量能在一定范圍內(nèi)按自身運(yùn)動規(guī)律不重復(fù)地遍歷所有狀態(tài)。

c)對初始值的敏感性。初始值的微小變化將會導(dǎo)致混沌序列在長期行為上的巨大差異。

利用混沌運(yùn)動的上述性質(zhì)可以進(jìn)行優(yōu)化搜索。混沌優(yōu)化搜索的基本思想是：首先產(chǎn)生一組與待優(yōu)化參數(shù)個數(shù)相同的優(yōu)化變量，然后以載波的方式把混沌運(yùn)動狀態(tài)引入到優(yōu)化變量中，同時把混沌變量的遍歷范圍擴(kuò)大到待優(yōu)化參數(shù)的整個取值空間^[8]。由于混沌變量具有隨機(jī)性、遍歷性等特點(diǎn)，其搜索比其他隨機(jī)搜索具有一定的優(yōu)越性。本章將混沌引入到進(jìn)化策略的搜索過程中，以提高進(jìn)化策略的搜索精度和跳出局部極小的能力。

為了充分利用混沌運(yùn)動的遍歷性，首先用混沌變量產(chǎn)生一個種群。若待優(yōu)化參數(shù)有m個，pi的取值范圍為pi∈[ai，bi](i=0，1，2，…，m；ai，bi∈R)。如果采用實(shí)數(shù)編碼來產(chǎn)生個體，設(shè)第j個個體xj=(xj1，xj2，…，xjm)。其中xj1、xj2分別對應(yīng)待優(yōu)化參數(shù)p1和p2的編碼。個體xj的第i維xji由下式計算。

xji=(bi-ai)Rchaos+ai(6)

其中:Rchaos是由混沌運(yùn)動方程Logistic映射所產(chǎn)生的混沌序列中的一個數(shù)。

影響(μ，λ)-ES搜索精度和結(jié)果的就是正態(tài)分布方差的選擇，方差越大，個體變異的幅度越大。變異步長選擇過大，會提高全局搜索能力，但是搜索精度不高；變異步長選擇過小，則容易陷入局部極小，所以需要對變異步長的選擇進(jìn)行改進(jìn)。如果在變異更新公式中能夠引入反映進(jìn)化策略搜索過程的反饋信息，讓更新公式中服從正態(tài)分布隨機(jī)數(shù)的方差根據(jù)這些反饋信息隨迭代過程的進(jìn)行而自動變化，需要提高精度時減小步長，需要擴(kuò)大搜索范圍時則增大步長，這就有可能達(dá)到提高進(jìn)化策略搜索精度的目的。

為了加快進(jìn)化策略的收斂，首先引入一個進(jìn)化引導(dǎo)方向。選出在當(dāng)前種群中適應(yīng)度最大的當(dāng)前最優(yōu)個體xoptimal，在對當(dāng)前種群進(jìn)行變異時，變異步長更新公式中引入反映其他個體與當(dāng)前最優(yōu)個體xoptimal距離的項(xiàng)d1(xi，xoptimal)和d2(xi，xoptimal)，d1(xi，xoptimal)表示個體xi與xoptimal的歐氏距離，d2(xi，xoptimal)表示個體xi與xoptimal的適應(yīng)度距離。當(dāng)個體xi與xoptimal距離較遠(yuǎn)時，它的變異幅度較大；反之，則變動幅度小，進(jìn)行小步長的高精度搜索。修改后的變異步長更新公式如下：

σ′i=σi exp[τ1 rand′i1+

τ2 rand′i2] (7)

其中rand′i1~N(0，1+d1(xi，xoptimal)) (8)

rand′i2~N(0，0.1+ln[d2(xi，xoptimal)+1]) (9)

當(dāng)?shù)M(jìn)行到一定程度時，種群逐步向某一區(qū)域收縮，種群中個體的相似程度也逐漸增大，這就增加了搜索陷入局部極小的可能。為了保證進(jìn)化策略的全局優(yōu)化能力，應(yīng)保證種群中的個體在整個搜索空間內(nèi)具備遍歷性，因此除了由式(7) ~(9)所定義的正態(tài)變異更新公式產(chǎn)生的個體外，還要有一部分個體由變異程度較大的更新公式產(chǎn)生。為此本文把式(2)的個體變異更新公式修改為

x′i=xi+σ′iRchaos(10)

其中：Rchaos是由混沌運(yùn)動方程Logistic映射所產(chǎn)生的混沌序列；σ′i為由式(7)~(9)所定義的正態(tài)變異更新公式產(chǎn)生的變異步長，其計算公式為式(5)。由于混沌序列能夠不重復(fù)地遍歷其搜索空間上的所有狀態(tài)，引入混沌變異的進(jìn)化策略將提高其跳出局部極小的能力。

3 基于反饋和混沌變異的進(jìn)化策略步驟

基于反饋和混沌變異進(jìn)化策略的步驟概括如下：

a)設(shè)置最大迭代次數(shù)作為終止條件，采用實(shí)數(shù)編碼，按式(6)生成μ個個體，構(gòu)成第一代種群(x1，x2，…，xμ)。其中Logistic映射的初值z0取一個服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，u=4。

b)對種群中的個體進(jìn)行評估，選出當(dāng)前最優(yōu)個體xoptimal。

c）變異。每個個體已用式(7)~(9)分別產(chǎn)生了λ/μ個變異步長σ′i，再根據(jù)式(2)產(chǎn)生m個個體，然后根據(jù)式(10)產(chǎn)生λ/μ-m個子個體，則整個種群一共產(chǎn)生λ個個體。

d)評價。對于變異產(chǎn)生的個體，計算各個體的適應(yīng)度。 

e)選擇。從變異產(chǎn)生的λ個子個體中選擇適應(yīng)度大的μ個個體，構(gòu)成下一代種群。判斷終止條件是否滿足，若是，則終止迭代；否則轉(zhuǎn)到步驟b）。

改進(jìn)的變異步長更新公式充分利用了進(jìn)化策略迭代過程中的反饋信息，能夠隨搜索結(jié)果和個體的相似程度自適應(yīng)調(diào)整。并且有部分個體利用混沌變異的方式產(chǎn)生，利用了混沌具有的遍歷性，從而提高了改進(jìn)后進(jìn)化策略的全局搜索能力。

4 仿真測試

為了驗(yàn)證本文所提的基于反饋和共享機(jī)制的進(jìn)化策略的有效性，采用下面三個測試函數(shù)對算法進(jìn)行測試。

1)Shubert函數(shù)

F1=min fun(x1，x2)=[5i=1i cos((1+i)x1+1)]×[5i=1i cos((1+i)x2+1)]+0.5[(x2+1.4253)2+(x2+0.80032)2]

Shubert函數(shù)的全局小值為-185.229 3，在尋找全局最小值的過程中非常容易收斂到局部極小值-184.839。

2)Camel函數(shù)

F2=fun(x1，x2)=(4-2.1x21+x41/3)x21+x1x2+(-4+4x22)x22

x1和x2的取值分別為x1∈(-2，2)，x2∈(-1.3，1.3)，Camel函數(shù)有四個局部極小點(diǎn)和兩個全局最小點(diǎn)，在全局最小點(diǎn)處函數(shù)值為-1.031 628。

3)F5=x1 sin(|x2-x1+1|)cos(|x1+x2+1|)+(x2+1)cos (|x2-x1+1|)sin (|x1+x2+1|)

x1和x2的取值為x1，x2∈(-512，512)，全局最小值為-511.708 9。

設(shè)置基于反饋和混沌變異的進(jìn)化策略的μ為20，λ為140，m為3，迭代次數(shù)為100，對上述三個測試函數(shù)分別進(jìn)行10次測試，測試結(jié)果如表1和2所示。為了與常規(guī)進(jìn)化策略的優(yōu)化結(jié)果對比，本文也使用常規(guī)進(jìn)化策略（μ，λ）-ES對上述三個測試函數(shù)進(jìn)行了優(yōu)化，其結(jié)果如表3和4所示。

為了對比基于反饋和混沌變異的進(jìn)化策略和常規(guī)(μ，λ)-ES對測試函數(shù)的優(yōu)化結(jié)果，將表1~4的結(jié)果列于表5中。

從表5可以看出，本文所提出的基于反饋和共享機(jī)制的進(jìn)化策略有效地解決了常規(guī)進(jìn)化策略搜索精度不高的問題。與常規(guī)進(jìn)化策略相比，基于反饋機(jī)制的進(jìn)化策略能夠在較短的時間內(nèi)搜索到更接近全局最優(yōu)值的解。

用基于反饋和混沌變異的進(jìn)化策略和常規(guī)進(jìn)化策略對Shubert函數(shù)進(jìn)行仿真測試時，最大和最小變異步長分別如圖1和2所示。由此可以看出，使用基于反饋和混沌變異的進(jìn)化策略的變異步長會隨優(yōu)化過程而自動調(diào)節(jié)，其最小變異步長明顯小于采用常規(guī)進(jìn)化策略的最小變異步長，這表明基于反饋和混沌變異的進(jìn)化策略能夠進(jìn)行更為細(xì)致的搜索，搜索精度比常規(guī)進(jìn)化策略更高。另外，在算法運(yùn)行后期，基于反饋和混沌變異的進(jìn)化策略的最大變異步長仍保持了較大的值，這說明算法能夠保證一定的跳出局部極小的能力。所以改進(jìn)后的進(jìn)化策略與常規(guī)進(jìn)化策略相比提高了搜索精度，并保證了一定的全局搜索能力。

5 結(jié)束語

本文所提出的基于反饋和共享機(jī)制的進(jìn)化策略將搜索得到的當(dāng)前最優(yōu)信息和種群中個體聚集程度反饋到個體的更新公式中，使變異更新公式中服從正態(tài)分布的隨機(jī)數(shù)的方差隨反饋信息而適時調(diào)整，充分利用了正態(tài)變異算子局部搜索能力強(qiáng)的特點(diǎn)進(jìn)行高精度的搜索；同時利用共享度隨種群中個體聚集程度升高而增大的特點(diǎn)，使部分個體保持較大的變異幅度，提高了算法跳出局部極小的能力，增強(qiáng)了算法的全局搜索能力。

參考文獻(xiàn)：

［1］閻嶺.進(jìn)化策略學(xué)習(xí)、收斂和逃逸能力的研究及應(yīng)用[D].杭州：浙江大學(xué)，2005.

[2]閻嶺，蔣靜坪.進(jìn)化學(xué)習(xí)策略收斂性和逃逸能力的研究[J].自動化學(xué)報，2005，31(6):873-880.

[3]YAO Xin，LIU Yong.Fast evolutionary programming[C]//Proc of the 5th International Conference on Evolutionary Computation.MA:The MIT Press，1996:441-450.

[4]YAO Xin，LIU Yong.Fast evolutionary strategies[C]//ANGELINE P J.Proc of the 6th Annual Conference on Evolutionary Programming.Berlin:Springer，1997:151-161.

[5]GEHLHAAR D K，F(xiàn)OGEL D B.Two new mutation operators for enhanced search and optimization in evolutionary programming[C]//BIOSACCHI B，BEZDEK J，F(xiàn)OGEL D B.Proc of SPIE.Piscataway，NJ:IEEE Press， 1996:260-269.

[6]林丹，李敏強(qiáng)，寇紀(jì)凇.進(jìn)化規(guī)劃和進(jìn)化策略中變異算子的若干研究[J].天津大學(xué)學(xué)報，2000，33(5)：627-630.

[7]駱晨鐘，邵惠鶴.采用混沌變異的進(jìn)化算法[J].控制與決策，2000，15(5)：557-560.

[8]袁曉輝，袁艷斌，王乘，等.一種新型的混沌遺傳算法[J].電子學(xué)報，2006，34(4)：708-712.