求解不可微函數優化的一種混合遺傳算法
3算例
圖1 函數=2時函數(=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.85、pm=0.2，T=100，進行Powell搜索的概率pPowell取不同值，混合法運行100次，計算結果見如表1。對于這個具有多極值的算例，多次計算表明pPowell=0.3時，混合法能以完全概率搜索到全局最優的準確值，但是此時混合法計算時間約為標準遺傳算法取T=500時計算時間的4/5。對應的浮點編碼遺傳算法，取m=30，pc=0.85、pm=0.2，T=100，運行100次，82次（以概率0.82）搜索到全局最優（如表1中PPowell =0所示），計算時間約為標準遺傳算法取T=500時計算時間的1/8，但是搜索到全局最優的概率卻遠遠高于標準遺傳算法。
表1pPowell取不同值時混合法的計算結果
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法，可以可靠地搜索到具有多個局部極值的函數優化問題的全局解。由于計算中只用到函數值信息，本文混合法不僅適用于不可微函數優化問題，也適合可微函數全局優化問題。