面向進化算法的問題相對求解難度降低方法

許春蕾，陳 昊1，，易鑫睿

1(南昌航空大學 無損檢測技術教育部重點實驗室，南昌 330063 2(南昌航空大學 信息工程學院，南昌 330063)

1 引 言

進化算法是一類模擬進化機制的智能計算方法，其中提高算法求解能力與降低問題求解難度是進化算法有效求解優化問題的兩個主要途徑，由NFL定理[1]可知，不存在能夠解決任何優化問題的超級優化算法，但是降低優化問題求解難度對于任何進化算法的研究都具有正面的指導意義.優化問題困難度是指通過較小的計算代價獲得問題的信息，并以所得信息調節進化算法的控制參數[2,3]，目前研究優化問題難度的方法和指標主要包括以下幾個方面：

通過分析不同可行解間的距離和適應值的相互關系度量問題難度，包括適應值距離測試方法、關聯長度測試方法等.Vanneschi等[4]在基因型之間定義一系列距離，選擇其中一種距離計算適應值相關系數分析問題難度；Draskoczy[5]設計一種鄰域算子計算搜索空間中可行解間的距離，分析不同距離間的特征和差異測試難度；Consoli等[6]通過分析顯著性、相關性及上位性等問題特征描述問題難度，并將特征量化分類確定其對優化過程的影響.

通過對可行解空間進行子集劃分度量問題難度，側重于優化算法與問題之間的作用過程，包括最優吸引子理論、曲面自動機等.Chen等[7]將優化問題求解過程描述為探索與利用，利用采樣點之間的信息相關性分析探索與利用作用過程；Rowe等[8]運用馬爾科夫模型建立一種突變算子，分析不同等級適應度之間的轉移概率，用曲面自動機精確建模.Munoz等[9]基于算法與優化問題之間的相互關系，研究一種基于信息特征的適應值曲面.通過適應值曲面的崎嶇程度度量問題難度，主要運用關聯長度測試方法.Malan等[10]在適應值曲面上構造隨機游走序列，通過分析這個序列的自相關系數，描述優化問題難度；Shirakawa等[11]提出一個新的特征向量表征適應值曲面；Cai等[12]利用適應值曲面分析技術研究資源項目調度問題的難度.

除上述3種度量優化問題難度方法以外，還有一些其它的研究問題難度的方法，如基于信息論的基因關聯度量方法[13]，經典基因關聯模型[14]、對問題分解重組[15]等.Gibbs等[16]定義決策變量之間的不平衡特性和相關性，并用具體的公式進行表示.Lu等[17]基于復雜度理論進行異位顯性分析，提出改進的適應值曲面分解方法，對孤立點、單峰、多峰等不同適應值曲面的細節特征詳細分析，并應用于參數調整的機器學習算法.

上述研究表明，有效辨識優化問題的求解難度對提高進化算法求解效率具有重要意義，但是目前關于問題難度研究還存在諸多缺陷，如適應值距離測試方法依賴于評價集的選取，最優吸引子理論仍沒有合適的方法估算優化特征因子，現有的研究關于問題求解難度的度量方法主要停留在理論分析階段且無法直接作用于進化過程，即問題求解難度在進化過程中無任何降低.本文提出一種面向進化算法的問題相對求解難度降低方法，以降低問題求解難度為目的，建立基于問題難度分析的相似性理論，對問題的簡化表達式、最簡表達式、相似性進行定義，利用基于云模型的相似性理論將問題估計為難度更低的相似問題.

2 難度分析方法

2.1 適應值距離測試方法

適應值距離測試方法(Fitness Distance Correlation，FDC)以評價集P的適應值和距離之間的相關系數描述優化問題[4].適應值距離相關系數FDCP可用公式表示為：

(1)

圖1 FDC方法2種典型情況

2.2 適應值距離測試方法

關聯長度測試方法(Correlation Length，CL)通過構造隨機游走函數產生游走序列f(xt)描述適應值曲面的崎嶇程度[10]，先給定初值x0，再計算隨機游走序列的自相關系數，根據自相關系數衡量優化問題難度.隨機游走序列自相關系數R(l)可用公式表示為：

(2)

2.3 最優吸引子理論

最優吸引子理論(Optimal Contraction Theorem，OCT)以探索與利用平衡原理為基準[7]，通過嚴格最優比(Strict Optimal Ratio，SOR)來對問題的難度進行分析，SOR是指最優區域(Optimal Field，OF)占整個搜索空間的比例，可用公式表示為：

(3)

式(3)中，SOR取值范圍為(0，1]，取值越趨向于1問題越簡單，反之則越困難.

3 優化問題相似性

將優化問題的全局最優解定義為特征值，在問題特征值不變的前提下，對問題適應值曲面[18]的的任意變化都視作為對優化問題的一次問題變換，變換前后的問題具有不同的求解難度.根據本文2.3的最優吸引子理論可知，圖2中F1、F2、F3的最優區域依次增加，F3的嚴格最優比等于1，難度最低.相似優化問題如圖2所示.

圖2 相似優化問題

根據最優吸引子理論可知新問題的難度低于原問題，則新問題是原問題的簡化.本文認為新問題y=g(x)與原問題y=f(x)在問題變換前后是相似的.下面給出優化問題相似性的2個定義.

定義1.簡化表達式、最簡表達式若y=g(x)的最優區域OFg大于y=f(x)的最優區域OFf，由OCT可知，原問題經有限次問題變換后滿足嚴格最優比為1，則將變換后的問題定義為原問題的簡化表達式.簡化表達式不唯一，定義其中與原問題y=f(x)差異最小的y=g(x)為原問題的最簡表達式.若y=g(x)為y=f(x)的最簡表達式，則應滿足如下條件：

②OFf≤OFg

③ 對于?xt∈X，滿足f(xt)≤g(xt)

定義2.相似性若問題變換前后的優化問題具有相同的最簡表達式，則稱新問題與原問題是相似的.對于任意數值優化問題y=f(x)，依據OCT，y=f(x)的嚴格最優比為SORf，若變換后的優化問題y=g(x)的嚴格最優比SORg≥SORf，則此變換為有效問題變換，變換后的優化問題難度小于原問題；若SORg

4 基于相似性理論的問題相對求解難度降低方法

4.1 云估計

優化問題間的差異難以衡量，本文用固定數學形式的表示簡化表達式，將簡化表達式y=g(x)表示為云模型C(Ex，En，He)：

(4)

式(4)中，Ex表示期望，對應C的中心點；En表示C的熵，根據3En準則可確定C的作用范圍；超熵He與C的置信度成反比.

若構建的云模型滿足定義1中最簡表達式的3個條件，則C(Ex，En，He)為y=f(x)最簡表達式的云模型表示，即最簡云模型Cbest(Ex，En，He).本文將進化算法的搜索目的擴展為尋找優化問題對應的最簡云模型，在t代對最簡云模型進行估計，尋找以當前最優解xopt(t)為中心點的云模型C(t)，且C(t)盡可能滿足最簡表達式的條件③，將尋找的最簡云模型過程可歸納為一個優化問題，用數學模型描述為：

(5)

式(5)中，R表示規模固定的樣本集；D表示評價最簡云模型與原問題函數值差異的距離函數.由進化過程中估計的最簡云模型可引出如下定理.

定理：進化過程中估計的最簡云模型Cbest(Ex，En，He)與原優化問題y=f(x)前后相似.

證畢.

4.2 相似性理論對問題相對求解難度的影響及最簡云模型求解方法

4.2.1 相似性理論對問題相對求解難度的影響

對于某一特定的優化問題，其真實的求解難度是不變的，如利用最優吸引子理論分析問題求解難度時，是以已知問題全局最優解為前提的，無法在進化過程之中進行測度.本文提出相對求解難度(Relative Solution Difficulty，RSD)的概念.

定義3.相對求解難度在利用進化算法求解問題之前，問題的真實難度與相對難度均是未知的；已知問題最優解xopt時，可建立Cbest(Ex，En，He)，問題的真實難度未改變，可用3個難度衡量指標求出其相對求解難度；在進化過程之中，隨著優良解的不斷產生，相對求解難度在逐漸下降.

優化問題相對求解難度變化示意圖如圖3所示.

圖3 優化問題相對求解難度變化示意圖

在進化過程中的第t代所估計的最簡云模型為C(t)=(Ex(t)，En(t)，He(t))，則可將原優化問題可變換為：

y=max(f(x)，gC(x))

(6)

由相似性理論可知，估計的新問題不改變問題的全局最優解，且新問題具有更低的相對求解難度.由圖2可知，估計的F2和F3比原問題F1難度更低，其中已估計為單峰函數的F3的嚴格最優比為1，即相對求解難度為0.

4.2.2 最簡云模型求解方法

式(5)為已知云模型期望求解熵的優化問題，該問題出現在利用進化算法求解優化問題的過程之中.估計最簡云模型的準確性直接影響問題的相對求解難度，本文先確定熵的取值范圍并生成種群，在搜索域內隨機采樣構造樣本集，以樣本集內采樣點處云模型與原問題的距離對熵個體進行評價.求解熵值具體偽代碼如下所示：

begin

設t為進化代數，初始化種群Ent

構造評價集R

repeat

for每一個個體Qi

endfor

Ent+1=select(Ent，D)//根據個體適應值選擇一定數量的個體

Ent+1=newcrossover(Ent+1，recdis)//交叉產生新子代，recdis為交叉函數

Ent+1=mutate(Ent+1，mutbga)//子代進行變異操作，mutbga為變異函數

untilterminated=ture

end

4.2.3 進化算法與最簡云模型結合

對于一個優化問題，將進化算法與問題相對求解難度降低方法相結合，可有效降低問題相對求解難度.原有進化算法中，從進化開始至進化結束，問題相對求解難度無任何變化，問題的難度始終在同一個層次上，而本文在進化算法的基礎上引入問題難度降低方法，可在進化過程中建立與優化問題對應的最簡云模型，能有效降低問題相對求解難度，基于最簡云模型的進化算法具體實現步驟如下：

Step1.t=0，產生初始化種群Pt.

Step2. 在種群中找出當前最優個體作為最簡云模型的期望值.

Step3. 利用4.2.2節方法求得最簡云模型的熵值.

Step4. 由Step 2和Step 3確定最簡云模C(t).

Step5. 根據第2節種難度分析方法求當前問題的相對求解難度.

Step6. 計算個體適應值.

Step6.1. 種群實際適應值y1=f(Pt).

Step6.2. 種群在最簡云模型上的值y2=gc(Pt).

Step6.3. 個體適應值fitness(Pt)=max(y1，y2).

Step7. 利用個體適應值進行選擇、交叉、變異操作.

Step8. 得到新種群Pt+1.

Step9. 終止條件判斷.若t>tmax，算法結束并輸出結果，否則跳轉到Step 2.

5 實驗數據及分析

本文將選取7種測試函數，在文化算法(Cultural Algorithm，CA)、差分進化算法(Differential Evolution，DE)、元胞遺傳算法(Celluar Genetic Algorithm，CGA)和粒子群算法(Particle Swarm Optimization，PSO)的基礎上引入本文方法，即CA-C、DE-C CGA-C、PSO-C.每個算法獨立運行30次，進化代數均設置為500代，種群規模都設置為200，測試函數對照表如表1所示.

表1 測試函數對照表

5.1 問題相對求解難度測試結果與分析

函數相對求解難度測試實驗結果如表2所示，算法在2維對各函數運用第2節介紹的3種方法對問題相對求解難度進行測試.其中1st、10th與50th分別為測試函數的真實求解難度、函數運行到第10代與第50代的相對求解難度；R表示函數的最終求解難度；Ave為函數在運行過程中的平均相對求解難度，即30次求解難度結果的平均值；數據加粗表示問題平均相對求解難度與真實難度相比具有顯著差異；“*”表示問題平均相對求解難度與真實難度相比具有極顯著差異.顯著性分析采用T檢驗方法，顯著性水平設置為0.05.

表2 函數相對求解難度測試實驗結果

分析表2數據可以發現：4種算法引入本文方法后，問題相對求解難度均有明顯降低.F1為簡單單峰函數，4種算法由FDC測得的初始難度均在0.9附近，由平均相對求解難度數據可知問題求解難度有一定程度降低；4種算法利用CL求得的問題相對求解難度較接近，CA-C難度降低幅度最大，幅度降低最小的是CGA-C；因F1是單峰函數，所以OCT測得的問題真實難度均相同.針對F2函數，根據FDC所得的問題真實求解難度，DE-C求得的真實難度最高，CGA-C求得的真實難度最低；利用CL求得的F2函數真實難度，CA-C的問題真實難度最低，僅為0.01，且從真實難度到最終相對難度數值降低89.6倍；各算法利用OCT測得的問題真實難度為0.08.FDC和CL對F3函數的問題求解難度影響不大，而OCT對降低難度十分有效，4種算法由OCT求得真實難度為0.09，問題最終相對求解難度均降低為1.針對線性不可分F4函數，PSO-C利用FDC在第10代求解的問題相對難度為0.79，相對于真實難度0.01，難度降低79倍，說明問題相對求解難度降低方法在進化初期已有明顯作用.F5為多密集尖峰函數，4種算法利用OCT測得問題平均相對求解難度與真實求解難度對比差異極顯著，DE-C降低8.9倍，幅度最小，CGA-C降低11.5倍，幅度最大，所以基本進化算法引入本文難度降低方法，在解決多峰問題時具有顯著優勢.針對復雜多模態F6函數，PSO-C利用FDC測得的問題求解難度變化不大，僅為5.7%；DE-C和CGA-C利用OCT測得的問題平均相對難度與真實難度相比差異極顯著.

通過分析比較測試結果可以發現，4種算法加上本文方法后，在運行中問題的相對求解難度依次呈現遞減的趨勢.整體來看，除了簡單單峰函數F1之外，CA-C、DE-C、CGA-C和PSO-C算法對每個測試函數都取得了較好的測試效果，說明面向進化算法的問題相對求解難度降低方法具有較好的問題相對求解難度降低性能，且具有較強的穩定性和通用性.

5.2 算法尋優性能測試結果與分析

為了驗證本文方法對不同進化算法尋優性能的影響，又分別利用CA-C、DE-C、CGA-C和PSO-C算法對F2、F4和F5函數進行測試(所有參數設置保持不變)，最終得到如圖4和圖5所示的測試結果.

圖4 F2函數適應值變化曲線

對于F2函數，通過適應值變化曲線可以看出，CA-C、DE-C、CGA-C和PSO-C算法均能在100代之內尋找到最優解，其中DE-C算法在進化初期就發現最優解，其次效果較好的是PSO-C算法，說明DE-C算法具有較高的收斂性能.在復雜多峰的F5函數測試中，4種算法都在30代之內達到全局收斂，CGA-C和PSO-C算法收斂速度相當，說明基本算法引入本文方法后，能較快且準確的搜索到最優解.

圖5 F5函數適應值變化曲線

為了更好的說明優化問題相對求解難度降低方法對不同算法尋優性能的影響，測試了CA、DE、CGA和PSO算法在引入本文方法前后各函數的最優適應值變化情況，圖6和圖7為CA和CGA算法前后對比圖，圖8和圖9為DE和PSO算法前后對比圖.

圖6 CA和CGA對于F3函數測試結果對比 圖7 CA和CGA對于F6函數測試結果對比

由圖6-圖9可以發現，針對不同算法對于不同問題，是否采用本文優化問題相對求解難度降低方法取得的效果并不一致.圖6中，對F3函數測試時，隨著進化代數增加，4種情況都能達到全局收斂，但CA-C和CGA-C算法較CA和CGA具有更快的收斂速度，同等條件下，F6函數取得的測試結果基本與F3函數一致，由圖7的適應值迭代曲線可明顯看出.圖8對比了DE和PSO算法采用本文方法前后的測試結果，由DE-C和PSO-C的測試曲線可以看出，其收斂代數比DE和PSO收斂代數少，且在25代內搜索到全局最優解，從圖9可看出，F6函數曲線變化趨勢基本與F3函數一致.

圖8 DE和PSO對于F3函數測試結果對比

圖9 DE和PSO對于F6函數測試結果對比

通過以上實驗測試結果可以看出，CA、DE、CGA和PSO這4種基本算法引入本文方法，能夠有效降低問題相對求解難度，且CA-C、DE-C、CGA-C和P`SO-C算法相比原來的基礎進化算法具有更好的全局收斂效果，使全局收斂速度有很大提升.

6 結 論

本文提出了一種面向進化算法的問題相對求解難度降低方法.首先介紹了3種衡量優化問題求解難度的方法，然后對優化問題相似性進行理論分析，將基于云模型的相似性理論引入到進化過程當中，并分析相似性理論對問題相對求解難度的影響.最后分別在4種傳統進化算法上引入本文提出的方法，利用3種指標對進化過程中的問題相對求解難度進行測試，以及驗證本文方法對不同進化算法尋優性能的影響.從試驗結果可以看出，4種基本算法加上本文問題難度降低方法后，由進化過程中不同階段的問題相對求解難度數據可知，不同難度指標測試所得的相對求解難度依次呈現遞減的趨勢，且對每個測試函數都取得了不錯的測試效果，說明方法具有較強的穩定性和通用性.同時，本文方法對算法的尋優性能也有著積極的影響，傳統進化算法引入本文方法之后能夠更快更精確找到問題的全局最優解.