求解不可微函數(shù)優(yōu)化的一種混合遺傳算法
3算例
圖1 函數(shù)=2時函數(shù)(=2時函數(shù)f(x) 特性如圖1示。程序編制和運行環(huán)境采用Fortran Power Station 4.0，隨機數(shù)由內(nèi)部隨機函數(shù)產(chǎn)生，在奔騰133微機上運行。
采用改進(jìn)的Powell方法計算100次，初值在區(qū)間[-500,500]內(nèi)隨機產(chǎn)生，只有6次（即以概率0.06）搜索到全局最優(yōu)，計算成功的概率極低。
Holland建立的標(biāo)準(zhǔn)（或簡單）遺傳算法，其特點是二進(jìn)制編碼、賭輪選擇方法、隨機配對、一點交叉、群體內(nèi)允許有相同的個體存在。取種群規(guī)模m=30，交叉概率pc=0.95、變異概率pm=0.05，最大進(jìn)化代數(shù)T=1000，每個變量用串長為L=16的二進(jìn)制子串表示。二進(jìn)制編碼比浮點編碼遺傳算法計算精度低，對于標(biāo)準(zhǔn)遺傳算法以目標(biāo)函數(shù)小于-800為搜索成功，標(biāo)準(zhǔn)遺傳算法運行100次。當(dāng)取最大進(jìn)化代數(shù)為T=200時，40次（以概率0.40）搜索到全局最優(yōu)，平均計算時間為0.51秒；當(dāng)取T=500時，51次（以概率0.51）搜索到全局最優(yōu)，平均計算時間為1.13秒。
采用本文混合法計算，取m=30， pc=0.85、pm=0.2，T=100，進(jìn)行Powell搜索的概率pPowell取不同值，混合法運行100次，計算結(jié)果見如表1。對于這個具有多極值的算例，多次計算表明pPowell=0.3時，混合法能以完全概率搜索到全局最優(yōu)的準(zhǔn)確值，但是此時混合法計算時間約為標(biāo)準(zhǔn)遺傳算法取T=500時計算時間的4/5。對應(yīng)的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運行100次，82次（以概率0.82）搜索到全局最優(yōu)（如表1中PPowell =0所示），計算時間約為標(biāo)準(zhǔn)遺傳算法取T=500時計算時間的1/8，但是搜索到全局最優(yōu)的概率卻遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)遺傳算法。
表1pPowell取不同值時混合法的計算結(jié)果
PPowell | 0.0 | 0.02 | 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結(jié)束語
針對不可微函數(shù)的全局優(yōu)化問題，本文提出一種把Powell方法與浮點編碼遺傳算法相結(jié)合的混合遺傳算法，該算法兼顧了遺傳算法全局優(yōu)化方面的優(yōu)勢和Powell方法局部搜索能力較強的特點，提高求得全局解的概率。計算結(jié)果表明混合法優(yōu)于遺傳算法和Powell法，可以可靠地搜索到具有多個局部極值的函數(shù)優(yōu)化問題的全局解。由于計算中只用到函數(shù)值信息，本文混合法不僅適用于不可微函數(shù)優(yōu)化問題，也適合可微函數(shù)全局優(yōu)化問題。