基于浮點數(shù)的多極值優(yōu)化方法

基于浮點數(shù)的多極值優(yōu)化方法

genticalgorithm（ga）是一種隨機優(yōu)化方法，具有很強的魯棒性。ga優(yōu)化過程首先提取問題，然后開始整個群體，反復(fù)選擇、交叉、變異和其他遺傳操作，使整個群體朝著最佳方向發(fā)展。對于二進制編碼的優(yōu)點，存在討論。二進制編碼的優(yōu)點是明顯的文傳操作，并且有圖式理論的指導(dǎo)。然而，在全局優(yōu)化多極值函數(shù)時，二進制編碼難以高精度分解，因此有必要將二進制編碼解碼為十進制浮點數(shù)。一些科學(xué)家研究了浮點數(shù)編碼的問題，主要困難是難以設(shè)計浮點數(shù)編碼。在分析二進制遺產(chǎn)的基礎(chǔ)上，本文研究了浮點數(shù)編碼的遺傳算法。本文的基本思想是：從該群體中個體表現(xiàn)出的優(yōu)化參數(shù)的值改換方法，即fga的遺傳操作具有相同的效果：fga尋求操作結(jié)果的多樣性和簡單性，。1浮點數(shù)編碼及其傳傳操作1.1改進的“或二元編碼”流行的觀點認(rèn)為二進制編碼能在相同的范圍內(nèi)表示盡可能多的模式,能更充分地體現(xiàn)所謂的隱含的并行性.而有些人則認(rèn)為采用二進制編碼不過是因為它的理論分析方便及它的遺傳操作更類似生物進化,另外還有歷史的原因.從精度及使用方便的角度來看,多極值函數(shù)的優(yōu)化問題更適合用十進制浮點數(shù)編碼.本文正是采用這種編碼方式.假定有n個待尋優(yōu)變量,則n個導(dǎo)優(yōu)范圍內(nèi)的十進制浮點數(shù)排列在一起成為一個個體.1.2群體復(fù)制概率法FGA采用排序選擇(RankingSelection)操作.假定最小化目標(biāo)函數(shù),這樣對每一個體計算目標(biāo)函數(shù)后需要對它們由小到大排序(若極大化目標(biāo)函數(shù)則由大到小排序),用序號充當(dāng)適值.序號為rank(x)的個體x的復(fù)制概率Ρ(x)=[Μin+(Μax-Μin)Ρop-rank(x)Ρop-1]/Ρop?P(x)=[Min+(Max?Min)Pop?rank(x)Pop?1]/Pop?其中Pop為群體尺寸,Max∈(1,5,2),Max+Min=2.rank(x)=1,2,…,Pop.根據(jù)復(fù)制概率,可以按輪盤賭方式來進行選擇操作.大量仿真計算表明如下改進方式不僅極其簡單方便,而且同樣有效.即排序選擇的結(jié)果實際是把序號在前的m個個體復(fù)制兩份,淘汰序號在后面的m個個體,序號在中間Pop-2m個個體復(fù)制一份.這種做法能保證群體尺寸不變,編程實現(xiàn)非常容易.采用排序選擇操作的意義在于它能保持一致的選擇壓力,能較好地抑制非成熟收斂.1.3fga的交叉方式考察二進制編碼的單點交叉和一致交叉操作,它們的最終效果是把兩個個體中的相應(yīng)參數(shù)a、b操作成a′、b′,滿足a+b=a′+b′,一致交叉通常優(yōu)于單點交叉,其原因在于一致交叉可能得到更多的圖式結(jié)果,基于上述兩點,FGA采用如下的交叉方式:{a′=(1-α)?a+βb,b′=(1-β)?b+αa,0<α,β<r,ifa′(b′)<Lthena′(b′)=L;ifa′(b′)>Rthena′(b′)=R,(1)其中α,β為(0,r)區(qū)間上均勻分布的隨機數(shù),r≤1,L,R分別為尋優(yōu)參數(shù)的左右邊界.調(diào)節(jié)式(1)中r的大小可以控制交叉操作的變化范圍.當(dāng)r較小時參數(shù)在原值附近小范圍內(nèi)變化,而當(dāng)r較大時交叉結(jié)果可能離原值較遠(yuǎn).采用這樣的交叉操作方式可以得到多種可能結(jié)果,能充分地實現(xiàn)兩個個體間的“信息交換”,對找到全局極值很有利.1.4基于同機數(shù)的變異操作考察二進制編碼的變異操作,它的最終效果是把某個體的參數(shù)c操作成域內(nèi)另一值c′.FGA中的變異操作亦要達到這樣的效果.FGA采用如下的變異操作:{c′=Ν(c,σ),ifc′<Lthenc′=L;ifc′>Rthenc′=R,(2)其中N(c,σ)表示均值為c,方差為σ的正態(tài)分布的隨機數(shù).參數(shù)在[L,R]內(nèi)范圍內(nèi)變化.可以看出,FGA對參數(shù)的變異操作即以當(dāng)前值為中心,主要在一個小范圍內(nèi)進行隨機擾動.式(2)的變異操作需要產(chǎn)生正態(tài)分布的隨機數(shù)且需做邊界處理,編程實現(xiàn)有些繁瑣.大量仿真實驗表明如下變異操作實現(xiàn)簡便,效果同樣很好:c′={c+k?(R-c)?γ,random(2)=0,c-k?(c-L)?γ,random(2)=1,(3)其中“0”,“1”代表變異的兩個方向,γ為(0,1)區(qū)間上的隨機數(shù),k∈(0,1]為一系數(shù).random(2)為C語言庫函數(shù)調(diào)用,隨機產(chǎn)生整數(shù)0或1.1.5初始種群的確定對全局優(yōu)化問題minX∈Rnf(X),其中xi∈[ai,bi],i=1,2,…,n.本文提出的浮點數(shù)編碼遺傳算法步驟總結(jié)如下:(1)n個指定范圍內(nèi)的浮點數(shù)排列在一起成為一個個體.隨機產(chǎn)生Pop個這樣的個體作為初始種群;(2)計算每一個體的目標(biāo)函數(shù)值并對這Pop個函數(shù)值由小到大排序,記錄最優(yōu)個體;(3)淘汰m個較大函數(shù)值對應(yīng)的個體并分別替換成m個較小函數(shù)值對應(yīng)的個體;(4)對這Pop個個體隨機兩兩配對,按一指定概率Pc進行式(1)的交叉操作;(5)對每一個體中的每一參數(shù),按一指定概率Pm進行式(3)的變異操作;(6)刪除種群中一任意個體并替換成步驟(2)中記錄的最優(yōu)個體;(7)若滿足收斂條件則輸出最優(yōu)解并退出,否則轉(zhuǎn)向步驟(2).2局部尋優(yōu)算法在fga和aga中的應(yīng)用本文將用提出的FGA與文獻提出的AGA比較.AGA采用自適應(yīng)交叉、變異概率,是二進制編碼遺傳算法中較為優(yōu)秀的.用FGA和AGA對如下三個著名的測試函數(shù)進行優(yōu)化計算:F5=0.002+25∑j=11j+2∑i=1(xi-aij)6,-65.536<xi<65.536,其中,其中F5,F6求極大值,F7求極小值.DeJone的F5函數(shù)是具有25個稀疏尖峰的多極值函數(shù),找尋該函數(shù)的最優(yōu)點被稱之為大海撈針.Schaffer的F6函數(shù)有無數(shù)個局部極大點,其中只有一個(0,0)為全局最大,最大值為1.此函數(shù)的最大值峰周圍有一圈脊,它們的取值均為0.990284,因此很容易停滯在此局部極大點.F7函數(shù)與F6類似,全局極小點為(0,0).對FGA和AGA,同樣選擇群體尺寸為100.AGA編碼長度為44,其它參數(shù)詳見文獻.對FGA,取1.5節(jié)步驟(3)中m=15,步驟(4)中交叉概率Pc=0.8,步驟(5)中變異概率Pm=0.08.對F5取式(1)中r=0.1,式(3)中k=0.4;對F6、F7取式(1)中r=1.0,式(3)中k=0.04.對每一測試函數(shù),設(shè)置一定的最大遺傳代數(shù).若在最大遺傳代數(shù)內(nèi)得到的最優(yōu)目標(biāo)函數(shù)值超過給定的閾值,則認(rèn)為算法成功找到了全局最優(yōu)解,否則認(rèn)為算法阻滯于局部最優(yōu)解.對每個測試函數(shù),FGA和AGA都將進行100次尋優(yōu)計算.表1給出了兩種優(yōu)化算法的性能比較.其中遺傳代數(shù)為找到最優(yōu)解的平均遺傳代數(shù).從表1可以看出:(1)FGA在設(shè)定的最大遺傳帶數(shù)內(nèi)全部找到了最優(yōu)解,具有很強的跳出局部極值的能力;(2)FGA的收斂速度快,計算量明顯少于AGA.另外,FGA的優(yōu)化精度很高.例如對F6,FGA在遺傳200代后能達到(10-8,10-8)數(shù)量級.二進制遺傳算法要想達到這個精度,編碼長度須從原來的44位增加到70位,這意味著計算量的大大增加.對多極值函數(shù)的優(yōu)化問題,FGA還有一個優(yōu)點是因不需要編碼解碼操作而易于和各種局部尋優(yōu)策略(如最速下降法)相結(jié)合,形成所謂的混合遺傳算法.需要說明的是在優(yōu)化過程中,注意到了對式(1)及式(3)中參數(shù)r和k的選取問題.對這兩個參數(shù)的不同選取,優(yōu)化結(jié)果將大不一樣.對待不同的優(yōu)化問題,如何自適應(yīng)確定這兩