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

3算例

^T [-500,500]

圖1 函數(shù)=2時(shí)函數(shù)(=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)行。

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

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

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

表1p_Powell取不同值時(shí)混合法的計(jì)算結(jié)果

4結(jié)束語(yǔ)

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