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

1、求解不可微函數(shù)優(yōu)化的一種混雜 遺傳算法        摘 要 在浮點編碼遺傳算法中參加 Powell法子    ，構(gòu)成適于不可微函數(shù)全局優(yōu)化的混雜 遺傳算法。混雜 算法改良 了遺傳算法的局部搜索能力    ，明顯 進步 了遺傳算法求得全局解的概率。由于只利用    函數(shù)值信息，混雜 算法是一種求解可微和不可微函數(shù)全局優(yōu)化問題的通用法子    。要害 詞 全局

2、最優(yōu)；混雜 算法；遺傳算法；Powell法子    1 引言 不可微非線性函數(shù)優(yōu)化問題具有廣泛    的工程和利用 背景，如結(jié)構(gòu)    設(shè)計中使得結(jié)構(gòu)    內(nèi)最大應力最小而歸結(jié)為極大極小優(yōu)化（minmax）問題、數(shù)據(jù)魯棒性擬合中采納最小絕對值準則建立    失擬函數(shù)等。其求解法子    的鉆研 越來越受到人們的器重 ，常用的算法有模式搜索法、單純形法、Po

3、well法子    等，但是這些法子    都是局部優(yōu)化法子    ，優(yōu)化效果 與初值有關(guān)。近年來，由Holland鉆研 自然現(xiàn)象與人工系統(tǒng)    的自適應行徑時，借鑒“優(yōu)越 劣汰”的生物進化與遺傳思想而首先提出的遺傳算法，是一種較為有效的求不可微非線性函數(shù)全局最優(yōu)解的法子    。以遺傳算法為代表的進化算法發(fā)展很快，在各種問題的求解與利用 中展現(xiàn)    了

4、其特性和魅力，但是其理論根基 還不完善    ，在理論和利用 上裸露 出諸多不足和缺點 ，如存在收斂速度慢且存在早熟收斂問題1,2。為克服    這一問題，早在1989年Goldberg就提出混雜 法子    的框架2，把GA與傳統(tǒng)的、基于知識的啟迪 式搜索技巧 相聯(lián)合 ，來改良 根基遺傳算法的局部搜索能力    ，使遺傳算法離開    早熟收斂狀態(tài)    

5、而持續(xù) 接近全局最優(yōu)解。近來，文獻3和4在總結(jié)分析    已有發(fā)展效果的根基 上，均指出充沛 利用    遺傳算法的大領(lǐng)域搜索性能，與快速收斂的局部優(yōu)化法子    聯(lián)合 構(gòu)成新的全局優(yōu)化法子    ，是目前有待集中鉆研 的問題之一，這種混雜 策略可以從根本    上進步 遺傳算法盤算 性能。文獻5采納 牛頓萊佛森法和遺傳算法進行雜交求解旅行商問題，文獻6把最速降落 法與遺傳算法相聯(lián)合 來求解繼續(xù)可

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

7、與二進制編碼對比 ，由于浮點編碼遺傳算法有精度高，便于大空間搜索的優(yōu)點    ，浮點編碼越來越受到器重 7。考慮    非線性不可微函數(shù)優(yōu)化問題(1)，式中 為變量個數(shù)， 、 分辨    是第 個變量 的下界和上界。把Powell法子    嵌入到浮點編碼遺傳算法中，得到求解問題(1)如下混雜 遺傳算法： min (1) step1 給遺傳算法參數(shù)賦值。這些參數(shù)包孕種群規(guī)模    m，變量個數(shù)n，

8、交叉概率pc、變異概率pm，進行Powell搜索的概率pPowell和遺傳盤算 所容許 的最大代數(shù)T。Step2 隨機產(chǎn)生    初始群體，并盤算 其適應值。首先第i個個體適應值取為fi=fmax - fi，fi是第i個個體對應的目標    函數(shù)值，fmax為當前種群成員的最大目標    函數(shù)值，i=1,2,m。然后按Goldberg線性比例變換模型2 式(2)進行拉伸。fi= a×fi+b （ fi ³ 0 ） (2) step3 履行 比例選擇算子進行

9、選擇操作。 step4 按概率 履行 算術(shù)交叉算子進行交叉操作。即對于選擇的兩個母體 和 ，算術(shù)交叉產(chǎn)生    的兩個子代為 和 ， 是0，1上的隨機數(shù)，1 , 。 step5 遵守概率 履行 非均勻變異算子8。若個體 的元素 被選擇變異， ，則變異效果 為 ，其中 ， (3) (4)返回區(qū)間 , 里的一個值，使 靠近0的概率隨代數(shù) 的增加而增加。這一性質(zhì)使算子在初始階段均勻地搜索空間，而在后面階段非常局部化。 是 , 之間的隨機數(shù)， 為最大代數(shù)， 為抉擇 非均勻度的系統(tǒng)    參數(shù)。 step6 對每個個體遵守概

10、率pPowell進行Powell搜索。若個體 被選擇進行Powell搜索操作，則以 作為初始點履行 Powell法子    得 ，若 則把所得盤算 效果 作為子代 ，否則，若 取 = ；若 取 = ，1 。 step7 盤算 個體適應值，并履行 最優(yōu)個體保存    策略。 step8 確定    是否終止盤算 條件，不滿足則轉(zhuǎn)向step3，滿足則輸出盤算 效果 。作為求解無束縛 最優(yōu)化問題的一種直接法子    ，Powell法的全部 盤

11、算 歷程 由若干輪迭代組成，在每一輪迭代中，先依次沿著已知的n個方向搜索，得一個最好點，然后沿本輪迭代的初始點與該最好點連線方向進行搜索，求得這一階段的最好點。再用最后的搜索方向代替 前n個方向之一，起頭下一階段的迭代。為了維持 算法中n個搜索方向是線性無關(guān)的，保證算法的收斂性，對調(diào)換 方向的規(guī)矩 進行改善，在混雜 法的盤算 步驟step6中采納 文9中的改善Powell法子    ，其求解歷程 如下： (1) 變量賦初值 ，n個線性無關(guān)的n個方向 , , ，和容許 誤差>0，令k=1。 (2) 令 ，從 起程 ，依次沿方向 , , 作一維搜索，得

12、到點 , , 求指標m，使得 - =max - ，令 。若 ，則Powell法子    盤算 收場 ，否則，履行 (3)。 (3) 求 使得 =min ，令 = = ，若 ，則Powell法子    盤算 收場 ，得點 ；否則，履行 (4)。 (4) 若 ，令 ，否則令 ( )，然后置 ，轉(zhuǎn)(2)。         3 算例 T -500,500 圖1 函數(shù)f(x)特征 示意圖 函數(shù)f(x)有相當多的極小點,全局極小點是 ， =1,2,

13、 ，最優(yōu)值為；次最優(yōu)點    為 =( , , )： =-420.97, , =302.52， =1,2, ，次優(yōu)值。變量個數(shù)n=2時函數(shù)f(x) 特征 如圖1示。程序編制和運行環(huán)境采納 Fortran Power Station 4.0，隨機數(shù)由內(nèi)部隨機函數(shù)產(chǎn)生    ，在奔跑 133微機上運行。采納 改善的Powell法子    盤算 100次，初值在區(qū)間-500,500內(nèi)隨機產(chǎn)生    ，只有6次（即以概率）搜索到全局最優(yōu)，盤算

14、成功    的概率極低。Holland建立    的標準    （或簡略 ）遺傳算法，其特性是二進制編碼、賭輪選擇法子    、隨機配對、一點交叉、群體內(nèi)容許 有雷同 的個體存在。取種群規(guī)模    m=30，交叉概率pc、變異概率pm，最大進化代數(shù)T=1000，每個變量用串長為L=16的二進制子串表現(xiàn) 。二進制編碼比浮點編碼遺傳算法盤算 精度低，對于標準   

15、0;遺傳算法以目標    函數(shù)小于-800為搜索成功    ，標準    遺傳算法運行100次。當取最大進化代數(shù)為T=200時，40次（以概率）搜索到全局最優(yōu)，平均盤算 光陰 為秒；當取T=500時，51次（以概率）搜索到全局最優(yōu)，平均盤算 光陰 為秒。采納 本文混雜 法盤算 ，取m=30， pc、pm，T=100，進行Powell搜索的概率pPowell取不同值，混雜 法運行100次，盤算 效果 見如表1。對于這個具有多極值的算例，多次盤算 表明pPowell時，混雜 法能

16、以完整 概率搜索到全局最優(yōu)的正確 值，但是此時混雜 法盤算 光陰 約為標準    遺傳算法取T=500時盤算 光陰 的4/5。對應的浮點編碼遺傳算法，取m=30，pc、pm，T=100，運行100次，82次（以概率）搜索到全局最優(yōu)（如表1中PPowell =0所示），盤算 光陰 約為標準    遺傳算法取T=500時盤算 光陰 的1/8，但是搜索到全局最優(yōu)的概率卻遠遠高于標準    遺傳算法。 表1 pPowell取不同值時混雜 法的盤算 效果 PPowell 0.0 0.0

17、2 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 收場 語 針對不可微函數(shù)的全局優(yōu)化問題，本文提出一種把Powell法子    與浮點編碼遺傳算法相聯(lián)合 的混雜 遺傳算法，該算法兼顧    了遺傳算法全局優(yōu)化方面的優(yōu)勢和Powell法子    局部搜索能力 &

18、#160;  較強的特性，進步 求得全局解的概率。盤算 效果 表明混雜 法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個局部極值的函數(shù)優(yōu)化問題的全局解。由于盤算 中只用到函數(shù)值信息，本文混雜 法不僅實用 于不可微函數(shù)優(yōu)化問題，也適宜可微函數(shù)全局優(yōu)化問題。        參考文獻 1  周明，孫樹林遺傳算法原理及利用 M北京：國防工業(yè)出版社，1999 2  Goldberg D E. Genetic algorithms in search, optimization

19、and machine learningM. Reading, Ma: Addison Wesley,1989 3  孟慶春，賈培發(fā)關(guān)于Genetic算法的鉆研 及利用 現(xiàn)狀J清華大學出版社，1995，35(5)：4448 4  戴曉暉，李敏強，寇紀松遺傳算法理論鉆研 綜述J把持 與決策，2000，15(3)：263268 5  Lin W，Delgado-Frias J GHybrid Newton-Raphson genetic algorithm for traveling salesman problemJ. Cybernetics and systems

20、, 1995，26(5)：387-412 6  趙明旺繼續(xù)可微函數(shù)全局優(yōu)化的混雜 遺傳算法J 把持 與決策，1997，12(5)：589592 7  Goldberg D EReal-Code Genetic Algorithm,Virtual Alphabets and BlockingJ. Complex Systems，1991，5：139-167 8  Michalewicz ZA modified genetic algorithm for optimal control problemsJComputers math. Application，1992，23（12）：83-94 9  陳寶林最優(yōu)化理論與算法M北京：清華大學出版社，1989 10    俞紅梅全歷程 系統(tǒng)    能量綜合法子    的鉆研 D大連理工大學博士學位論文，1998 Hybrid a