求解不可微函數(shù)優(yōu)化的一種混合遺傳算法

導(dǎo)語：求解不可微函數(shù)優(yōu)化的一種混合遺傳算法一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要在浮點編碼遺傳算法中加入Powell方法，構(gòu)成適于不可微函數(shù)全局優(yōu)化的混合遺傳算法。混合算法改善了遺傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數(shù)值信息，混合算法是一種求解可微和不可微函數(shù)全局優(yōu)化問題的通用方法。

關(guān)鍵詞全局最優(yōu)；混合算法；遺傳算法；Powell方法

1引言

不可微非線性函數(shù)優(yōu)化問題具有廣泛的工程和應(yīng)用背景，如結(jié)構(gòu)設(shè)計中使得結(jié)構(gòu)內(nèi)最大應(yīng)力最小而歸結(jié)為極大極小優(yōu)化（minmax）問題、數(shù)據(jù)魯棒性擬合中采取最小絕對值準(zhǔn)則建立失擬函數(shù)等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Powell方法等，但是這些方法都是局部優(yōu)化方法，優(yōu)化結(jié)果與初值有關(guān)。

近年來，由Holland研究自然現(xiàn)象與人工系統(tǒng)的自適應(yīng)行為時，借鑒“優(yōu)勝劣汰”的生物進化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的方法。以遺傳算法為代表的進化算法發(fā)展很快，在各種問題的求解與應(yīng)用中展現(xiàn)了其特點和魅力，但是其理論基礎(chǔ)還不完善，在理論和應(yīng)用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題[1,2]。為克服這一問題，早在1989年Goldberg就提出混合方法的框架[2]，把GA與傳統(tǒng)的、基于知識的啟發(fā)式搜索技術(shù)相結(jié)合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態(tài)而繼續(xù)接近全局最優(yōu)解。近來，文獻(xiàn)[3]和[4]在總結(jié)分析已有發(fā)展成果的基礎(chǔ)上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優(yōu)化方法結(jié)合構(gòu)成新的全局優(yōu)化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計算性能。文獻(xiàn)[5]采用牛頓－萊佛森法和遺傳算法進行雜交求解旅行商問題，文獻(xiàn)[6]把最速下降法與遺傳算法相結(jié)合來求解連續(xù)可微函數(shù)優(yōu)化問題，均取得良好的計算效果，但是不適于不可微函數(shù)優(yōu)化問題。

本文提出把Powell方法融入浮點編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構(gòu)成適于求解不可微函數(shù)優(yōu)化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數(shù)值算例對混合方法的有效性進行了驗證。

2混合遺傳算法

編碼是遺傳算法應(yīng)用中的首要問題，與二進制編碼比較，由于浮點編碼遺傳算法有精度高，便于大空間搜索的優(yōu)點，浮點編碼越來越受到重視[7]。考慮非線性不可微函數(shù)優(yōu)化問題(1)，式中為變量個數(shù)，、分別是第個變量的下界和上界。把Powell方法嵌入到浮點編碼遺傳算法中，得到求解問題(1)如下混合遺傳算法：

min(1)

step1給遺傳算法參數(shù)賦值。這些參數(shù)包括種群規(guī)模m，變量個數(shù)n，交叉概率pc、變異概率pm，進行Powell搜索的概率pPowell和遺傳計算所允許的最大代數(shù)T。

Step2隨機產(chǎn)生初始群體，并計算其適應(yīng)值。首先第i個個體適應(yīng)值取為fi’=fmax-fi，fi是第i個個體對應(yīng)的目標(biāo)函數(shù)值，fmax為當(dāng)前種群成員的最大目標(biāo)函數(shù)值，i=1,2,…,m。然后按Goldberg線性比例變換模型[2]式(2)進行拉伸。

fi’=a×fi’+b（fi³0）(2)

step3執(zhí)行比例選擇算子進行選擇操作。

step4按概率執(zhí)行算術(shù)交叉算子進行交叉操作。即對于選擇的兩個母體和，算術(shù)交叉產(chǎn)生的兩個子代為和，是[0，1]上的隨機數(shù)，1,。

step5按照概率執(zhí)行非均勻變異算子[8]。若個體的元素被選擇變異，，則變異結(jié)果為，其中，

(3)

(4)

返回區(qū)間[,]里的一個值，使靠近0的概率隨代數(shù)的增加而增加。這一性質(zhì)使算子在初始階段均勻地搜索空間，而在后面階段非常局部化。是[,]之間的隨機數(shù)，為最大代數(shù)，為決定非均勻度的系統(tǒng)參數(shù)。

step6對每個個體按照概率pPowell進行Powell搜索。若個體被選擇進行Powell搜索操作，則以作為初始點執(zhí)行Powell方法得，若則把所得計算結(jié)果作為子代，否則，若取=；若取=，1。

step7計算個體適應(yīng)值，并執(zhí)行最優(yōu)個體保存策略。

step8判斷是否終止計算條件，不滿足則轉(zhuǎn)向step3，滿足則輸出計算結(jié)果。

作為求解無約束最優(yōu)化問題的一種直接方法，Powell法的整個計算過程由若干輪迭代組成，在每一輪迭代中，先依次沿著已知的n個方向搜索，得一個最好點，然后沿本輪迭代的初始點與該最好點連線方向進行搜索，求得這一階段的最好點。再用最后的搜索方向取代前n個方向之一，開始下一階段的迭代。為了保持算法中n個搜索方向是線性無關(guān)的，保證算法的收斂性，對替換方向的規(guī)則進行改進，在混合法的計算步驟step6中采用文[9]中的改進Powell方法，其求解過程如下：

(1)變量賦初值，n個線性無關(guān)的n個方向,,…,，和允許誤差ε>0，令k=1。

(2)令，從出發(fā)，依次沿方向,,…,作一維搜索，得到點,,…,求指標(biāo)m，使得-=max{-}，令。若ε，則Powell方法計算結(jié)束，否則，執(zhí)行(3)。

(3)求使得=min，令==，若，則Powell方法計算結(jié)束，得點；否則，執(zhí)行(4)。

(4)若，令，否則令()，然后置，轉(zhuǎn)(2)。

3算例

T[-500,500]

函數(shù)f(x)有相當(dāng)多的極小點,全局極小點是=-420.97，=1,2,…,，最優(yōu)值為-837.97；次最優(yōu)點為={(,,…,)：=-420.97,,=302.52}，=1,2,…,，次優(yōu)值-719.53。變量個數(shù)n=2時函數(shù)f(x)特性如圖1示。程序編制和運行環(huán)境采用FortranPowerStation4.0，隨機數(shù)由內(nèi)部隨機函數(shù)產(chǎn)生，在奔騰133微機上運行。

采用改進的Powell方法計算100次，初值在區(qū)間[-500,500]內(nèi)隨機產(chǎn)生，只有6次（即以概率0.06）搜索到全局最優(yōu)，計算成功的概率極低。

Holland建立的標(biāo)準(zhǔn)（或簡單）遺傳算法，其特點是二進制編碼、賭輪選擇方法、隨機配對、一點交叉、群體內(nèi)允許有相同的個體存在。取種群規(guī)模m=30，交叉概率pc=0.95、變異概率pm=0.05，最大進化代數(shù)T=1000，每個變量用串長為L=16的二進制子串表示。二進制編碼比浮點編碼遺傳算法計算精度低，對于標(biāo)準(zhǔn)遺傳算法以目標(biāo)函數(shù)小于-800為搜索成功，標(biāo)準(zhǔn)遺傳算法運行100次。當(dāng)取最大進化代數(shù)為T=200時，40次（以概率0.40）搜索到全局最優(yōu)，平均計算時間為0.51秒；當(dāng)取T=500時，51次（以概率0.51）搜索到全局最優(yōu)，平均計算時間為1.13秒。

采用本文混合法計算，取m=30，pc=0.85、pm=0.2，T=100，進行Powell搜索的概率pPowell取不同值，混合法運行100次，計算結(jié)果見如表1。對于這個具有多極值的算例，多次計算表明pPowell=0.3時，混合法能以完全概率搜索到全局最優(yōu)的準(zhǔn)確值，但是此時混合法計算時間約為標(biāo)準(zhǔn)遺傳算法取T=500時計算時間的4/5。對應(yīng)的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運行100次，82次（以概率0.82）搜索到全局最優(yōu)（如表1中PPowell=0所示），計算時間約為標(biāo)準(zhǔn)遺傳算法取T=500時計算時間的1/8，但是搜索到全局最優(yōu)的概率卻遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)遺傳算法。

表1pPowell取不同值時混合法的計算結(jié)果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最優(yōu)解的次數(shù)

82

85

89

94

98

100

求得最優(yōu)解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均計算時間/秒

0.14

0.20

0.31

0.47

0.68

0.87

4結(jié)束語

針對不可微函數(shù)的全局優(yōu)化問題，本文提出一種把Powell方法與浮點編碼遺傳算法相結(jié)合的混合遺傳算法，該算法兼顧了遺傳算法全局優(yōu)化方面的優(yōu)勢和Powell方法局部搜索能力較強的特點，提高求得全局解的概率。計算結(jié)果表明混合法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個局部極值的函數(shù)優(yōu)化問題的全局解。由于計算中只用到函數(shù)值信息，本文混合法不僅適用于不可微函數(shù)優(yōu)化問題，也適合可微函數(shù)全局優(yōu)化問題。

參考文獻(xiàn)

[1]周明，孫樹林．遺傳算法原理及應(yīng)用[M]．北京：國防工業(yè)出版社，1999．

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989．

[3]孟慶春，賈培發(fā)．關(guān)于Genetic算法的研究及應(yīng)用現(xiàn)狀[J]．清華大學(xué)出版社，1995，35(5)：44－48．

[4]戴曉暉，李敏強，寇紀(jì)松．遺傳算法理論研究綜述[J]．控制與決策，2000，15(3)：263－268．

[5]LinW，Delgado-FriasJG．HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995，26(5)：387-412．

[6]趙明旺．連續(xù)可微函數(shù)全局優(yōu)化的混合遺傳算法[J]．控制與決策，1997，12(5)：589－592．

[7]GoldbergDE．Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems，1991，5：139-167．

[8]MichalewiczZ．Amodifiedgeneticalgorithmforoptimalcontrolproblems[J]．Computersmath.Application，1992，23（12）：83-94．

[9]陳寶林．最優(yōu)化理論與算法[M]．北京：清華大學(xué)出版社，1989．

[10]俞紅梅．全過程系統(tǒng)能量綜合方法的研究[D]．大連理工大學(xué)博士學(xué)位論文，1998．