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

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，交叉概率p_c=0.95、變異概率p_m=0.05，最大進化代數T=1000，每個變數用串長為L=16的二進位制子串表示。二進位制編碼比浮點編碼遺傳演算法計算精度低，對於標準遺傳演算法以目標函式小於-800為搜尋成功，標準遺傳演算法執行100次。當取最大進化代數為T=200時，40次（以概率0.40）搜尋到全域性最優，平均計算時間為0.51秒；當取T=500時，

51次（以概率0.51）搜尋到全域性最優，平均計算時間為1.13秒。

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

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

4 結束語

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

3 算例

^T [-500,500]

圖1 函式f***x***特性示意圖