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

3算例

^T [-500,500]

圖1 函數(shù)=2時函數(shù)(=2時函數(shù)f(x) 特性如圖1示。程序編制和運行環(huán)境采用Fortran Power Station 4.0，隨機數(shù)由內部隨機函數(shù)產(chǎn)生，在奔騰133微機上運行。

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

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

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

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

4結束語

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