CIMS論文的天地

 

求解不可微函數優化的一種混合遺傳算法

注意:本論文已在《東北大學學報(自然科學版)》2001,22(S1)74-77.發表
使用者請注明論文出處

王登剛,劉迎曦,李守巨

( 大連理工大學 工程力學系,遼寧 大連,116024)

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

關鍵詞  全局最優;混合算法;遺傳算法;Powell方法

中圖法分類號  O39O221.2

1  引言

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

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

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

2  混合遺傳算法

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

             min            (1)

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

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

fi= a×fi+b fi  ³ 0                      (2)

    step3 執行比例選擇算子進行選擇操作。

    step4 按概率 執行算術交叉算子進行交叉操作。即對于選擇的兩個母體 ,算術交叉產生的兩個子代為 [01]上的隨機數,1 ,

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

                              (3)

                               (4)

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

    step6 對每個個體按照概率pPowell進行Powell搜索。若個體 被選擇進行Powell搜索操作,則以 作為初始點執行Powell方法得 ,若 則把所得計算結果 作為子代 ,否則,若 = ;若 = 1

    step7 計算個體適應值,并執行最優個體保存策略。

    step8 判斷是否終止計算條件,不滿足則轉向step3,滿足則輸出計算結果。

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

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

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

    (3) 使得 =min ,令 = = ,若 ,則Powell方法計算結束,得點 ;否則,執行(4)

    (4) ,令 ,否則令 ( ),然后置 ,轉(2)。

3  算例

    T  [-500,500] 

 


1 函數f(x)特性示意圖

函數f(x)有相當多的極小點,全局極小點是 =-420.97 =1,2,…, ,最優值為-837.97;次最優點為 ={( , ,…, ) =-420.97, , =302.52} =1,2,…, ,次優值-719.53。變量個數n=2時函數f(x) 特性如圖1示。程序編制和運行環境采用Fortran Power Station 4.0,隨機數由內部隨機函數產生,在奔騰133微機上運行。

采用改進的Powell方法計算100次,初值在區間[-500,500]內隨機產生,只有6次(即以概率0.06)搜索到全局最優,計算成功的概率極低。

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

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

 

1  pPowell取不同值時混合法的計算結果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最優解的次數

82

85

89

94

98

100

求得最優解的概率

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  結束語

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

 

參考文獻

[1]  周明,孫樹林.遺傳算法原理及應用[M].北京:國防工業出版社,1999

[2]  Goldberg D E. Genetic algorithms in search, optimization and machine learning[M]. Reading, Ma: Addison Wesley,1989

[3]  孟慶春,賈培發.關于Genetic算法的研究及應用現狀[J].清華大學出版社,199535(5)4448

[4]  戴曉暉,李敏強,寇紀松.遺傳算法理論研究綜述[J].控制與決策,200015(3)263268

[5]  Lin WDelgado-Frias J GHybrid Newton-Raphson genetic algorithm for traveling salesman problem[J]. Cybernetics and systems, 199526(5)387-412

[6]  趙明旺.連續可微函數全局優化的混合遺傳算法[J] .控制與決策,199712(5)589592

[7]  Goldberg D EReal-Code Genetic Algorithm,Virtual Alphabets and Blocking[J]. Complex Systems19915139-167

[8]  Michalewicz ZA modified genetic algorithm for optimal control problems[J]Computers math. Application19922312):83-94

[9]  陳寶林.最優化理論與算法[M].北京:清華大學出版社,1989

[10]    俞紅梅.全過程系統能量綜合方法的研究[D].大連理工大學博士學位論文,1998

Hybrid approach for global optima of indifferentiable nonlinear function

WANG Denggang,  LIU Yingxi,  LI Shouju

 ( Dept. of Eng. Mechanics., Dalian Univ. of Technol. Dalian, 116024)

Abstract  A hybrid computational intellective algorithm for locating the global optima of indifferentiable nonlinear function was put forward by setting the Powell algorithm in real-code genetic algorithm. The hybrid approach improved the local searching ability of the genetic algorithm and promoted the probability for the global optima greatly. Because only the objective values are used, the hybrid approach is a generalized genetic algorithm for global optima of differentiable and indifferentiable nonlinear functions.

Key words  global optimahybrid approachgenetic algorithmsPowell algorithm

       T   -500:2:500       (9)

 

 


本站收錄的本文作者的其他論文:

1、A relialble approach to compute the forward kinematics of robot with uncertain geometric parameters

2、非線性最優化問題的一種混合解法

3、混凝土重力壩振動參數識別研究

4、巷道圍巖初始應力場和彈性模量的區間反演方法

5、結構可靠性分析的區間方法

 更多相關論文請點擊本站的<<<站內全文搜索>>>查找

歡迎您參加討論,發表您對此論文及其研究領域的看法!
(請在發言時在標題中使用所點評的論文的題目或研究方向,這樣方便大家瀏覽!)

返回首頁 | CIMS論文 | 并行工程 | 虛擬制造 | 敏捷制造 | 其他論文 | 項目開發 | 學術資源 | 站內全文搜索 | 免費論文網站大全 |

line.gif (4535 字節)

為了更好的為大家服務,歡迎您參加本站的投票調查

>>>>參加更多投票調查請點擊!

本站永久域名:http://www.sqvswk.live歡迎訪問

注意:本站內容未經書面允許不得轉載

All rights reserved, all contents copyright 2000-2019
本站自2000年3月總網頁訪問量為
pk10开奖记录直播