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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、以完整 概率搜索到全局最優(yōu)的正確 值，但是此時(shí)混雜 法盤(pán)算 光陰 約為標(biāo)準(zhǔn)    遺傳算法取T=500時(shí)盤(pán)算 光陰 的4/5。對(duì)應(yīng)的浮點(diǎn)編碼遺傳算法，取m=30，pc、pm，T=100，運(yùn)行100次，82次（以概率）搜索到全局最優(yōu)（如表1中PPowell =0所示），盤(pán)算 光陰 約為標(biāo)準(zhǔn)    遺傳算法取T=500時(shí)盤(pán)算 光陰 的1/8，但是搜索到全局最優(yōu)的概率卻遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)    遺傳算法。 表1 pPowell取不同值時(shí)混雜 法的盤(pán)算 效果 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 平均盤(pán)算 光陰 / 秒 0.14 0.20 0.31 0.47 0.68 0.87 4 收?qǐng)?語(yǔ) 針對(duì)不可微函數(shù)的全局優(yōu)化問(wèn)題，本文提出一種把Powell法子    與浮點(diǎn)編碼遺傳算法相聯(lián)合 的混雜 遺傳算法，該算法兼顧    了遺傳算法全局優(yōu)化方面的優(yōu)勢(shì)和Powell法子    局部搜索能力 &

18、#160;  較強(qiáng)的特性，進(jìn)步 求得全局解的概率。盤(pán)算 效果 表明混雜 法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個(gè)局部極值的函數(shù)優(yōu)化問(wèn)題的全局解。由于盤(pán)算 中只用到函數(shù)值信息，本文混雜 法不僅實(shí)用 于不可微函數(shù)優(yōu)化問(wèn)題，也適宜可微函數(shù)全局優(yōu)化問(wèn)題。        參考文獻(xiàn) 1  周明，孫樹(shù)林遺傳算法原理及利用 M北京：國(guó)防工業(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清華大學(xué)出版社，1995，35(5)：4448 4  戴曉暉，李敏強(qiáng)，寇紀(jì)松遺傳算法理論鉆研 綜述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北京：清華大學(xué)出版社，1989 10    俞紅梅全歷程 系統(tǒng)    能量綜合法子    的鉆研 D大連理工大學(xué)博士學(xué)位論文，1998 Hybrid a