1、求解不可微函數優(yōu)化的一種混合遺傳算法摘 要 在浮點編碼遺傳算法中加入Powell方法，構成適于不可微函數全局優(yōu)化的混合遺傳算法。混合算法改善了遺傳算法的局部搜索能力，顯著提高了遺傳算法求得全局解的概率。由于只利用函數值信息，混合算法是一種求解可微和不可微函數全局優(yōu)化問題的通用方法。關鍵詞 全局最優(yōu)；混合算法；遺傳算法；Powell方法1 引言 不可微非線性函數優(yōu)化問題具有廣泛的工程和應用背景，如結構設計中使得結構內最大應力最小而歸結為極大極小優(yōu)化（minmax）問題、數據魯棒性擬合中采取最小絕對值準則建立失擬函數等。其求解方法的研究越來越受到人們的重視，常用的算法有模式搜索法、單純形法、Pow

2、ell方法等，但是這些方法都是局部優(yōu)化方法，優(yōu)化結果與初值有關。近年來，由Holland研究自然現象與人工系統(tǒng)的自適應行為時，借鑒“優(yōu)勝劣汰”的生物進化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數全局最優(yōu)解的方法。以遺傳算法為代表的進化算法發(fā)展很快，在各種問題的求解與應用中展現了其特點和魅力，但是其理論基礎還不完善，在理論和應用上暴露出諸多不足和缺陷，如存在收斂速度慢且存在早熟收斂問題1,2。為克服這一問題，早在1989年Goldberg就提出混合方法的框架2，把GA與傳統(tǒng)的、基于知識的啟發(fā)式搜索技術相結合，來改善基本遺傳算法的局部搜索能力，使遺傳算法離開早熟收斂狀態(tài)而繼

3、續(xù)接近全局最優(yōu)解。近來，文獻3和4在總結分析已有發(fā)展成果的基礎上，均指出充分利用遺傳算法的大范圍搜索性能，與快速收斂的局部優(yōu)化方法結合構成新的全局優(yōu)化方法，是目前有待集中研究的問題之一，這種混合策略可以從根本上提高遺傳算法計算性能。文獻5采用牛頓萊佛森法和遺傳算法進行雜交求解旅行商問題，文獻6把最速下降法與遺傳算法相結合來求解連續(xù)可微函數優(yōu)化問題，均取得良好的計算效果，但是不適于不可微函數優(yōu)化問題。本文提出把Powell方法融入浮點編碼遺傳算法，把Powell方法作為與選擇、交叉、變異平行的一個算子，構成適于求解不可微函數優(yōu)化問題的混合遺傳算法，該方法可以較好解決遺傳算法的早熟收斂問題。數值算

4、例對混合方法的有效性進行了驗證。2 混合遺傳算法 編碼是遺傳算法應用中的首要問題，與二進制編碼比較，由于浮點編碼遺傳算法有精度高，便于大空間搜索的優(yōu)點，浮點編碼越來越受到重視7?？紤]非線性不可微函數優(yōu)化問題(1)，式中 min step1 給遺傳算法參數賦值。這些參數包括種群規(guī)模m，變量個數n，交叉概率pc、變異概率pm，進行Powell搜索的概率pPowell和遺傳計算所允許的最大代數T。Step2 隨機產生初始群體，并計算其適應值。首先第i個個體適應值取為fi=fmax - fi，fi是第i個個體對應的目標函數值，fmax為當前種群成員的最大目標函數值，i=1,2,m。然后按Goldber

5、g線性比例變換模型2 式(2)進行拉伸。fi= afi+b （ fi 0 ） (2) step3 執(zhí)行比例選擇算子進行選擇操作。 step4 按概率 step5 按照概率 step6 對每個個體按照概率pPowell進行Powell搜索。若個體 step7 計算個體適應值，并執(zhí)行最優(yōu)個體保存策略。 step8 判斷是否終止計算條件，不滿足則轉向step3，滿足則輸出計算結果。作為求解無約束最優(yōu)化問題的一種直接方法，Powell法的整個計算過程由若干輪迭代組成，在每一輪迭代中，先依次沿著已知的n個方向搜索，得一個最好點，然后沿本輪迭代的初始點與該最好點連線方向進行搜索，求得這一階段的最好點。再用

6、最后的搜索方向取代前n個方向之一，開始下一階段的迭代。為了保持算法中n個搜索方向是線性無關的，保證算法的收斂性，對替換方向的規(guī)則進行改進，在混合法的計算步驟step6中采用文9中的改進Powell方法，其求解過程如下： (1) 變量賦初值 (2) 令 (3) 求 (4) 若 函數f(x)有相當多的極小點,全局極小點是采用改進的Powell方法計算100次，初值在區(qū)間-500,500內隨機產生，只有6次（即以概率0.06）搜索到全局最優(yōu)，計算成功的概率極低。Holland建立的標準（或簡單）遺傳算法，其特點是二進制編碼、賭輪選擇方法、隨機配對、一點交叉、群體內允許有相同的個體存在。取種群規(guī)模m=

7、30，交叉概率pc=0.95、變異概率pm=0.05，最大進化代數T=1000，每個變量用串長為L=16的二進制子串表示。二進制編碼比浮點編碼遺傳算法計算精度低，對于標準遺傳算法以目標函數小于-800為搜索成功，標準遺傳算法運行100次。當取最大進化代數為T=200時，40次（以概率0.40）搜索到全局最優(yōu)，平均計算時間為0.51秒；當取T=500時，51次（以概率0.51）搜索到全局最優(yōu)，平均計算時間為1.13秒。采用本文混合法計算，取m=30，pc=0.85、pm=0.2，T=100，進行Powell搜索的概率pPowell取不同值，混合法運行100次，計算結果見如表1。對于這個具有多極值

8、的算例，多次計算表明pPowell=0.3時，混合法能以完全概率搜索到全局最優(yōu)的準確值，但是此時混合法計算時間約為標準遺傳算法取T=500時計算時間的4/5。對應的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運行100次，82次（以概率0.82）搜索到全局最優(yōu)（如表1中PPowell=0所示），計算時間約為標準遺傳算法取T=500時計算時間的1/8，但是搜索到全局最優(yōu)的概率卻遠遠高于標準遺傳算法。表1 pPowell取不同值時混合法的計算結果PPowell0.00.020.050.10.20.3求得最優(yōu)解的次數8285899498100求得最優(yōu)解的概率0.820.8

9、50.890.940.981.00平均計算時間/秒0.140.200.310.470.680.874 結束語針對不可微函數的全局優(yōu)化問題，本文提出一種把Powell方法與浮點編碼遺傳算法相結合的混合遺傳算法，該算法兼顧了遺傳算法全局優(yōu)化方面的優(yōu)勢和Powell方法局部搜索能力較強的特點，提高求得全局解的概率。計算結果表明混合法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個局部極值的函數優(yōu)化問題的全局解。由于計算中只用到函數值信息，本文混合法不僅適用于不可微函數優(yōu)化問題，也適合可微函數全局優(yōu)化問題。參考文獻1周明，孫樹林遺傳算法原理及應用M北京：國防工業(yè)出版社，19992Goldberg D E. Genet