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

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

1 引 言

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

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

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

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

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

2 難度分析方法

2.1 適應值距離測試方法

適應值距離測試方法(Fitness Distance Correlation，F(xiàn)DC)以評價集P的適應值和距離之間的相關(guān)系數(shù)描述優(yōu)化問題[4].適應值距離相關(guān)系數(shù)FDCP可用公式表示為：

(1)

圖1 FDC方法2種典型情況

2.2 適應值距離測試方法

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

(2)

2.3 最優(yōu)吸引子理論

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

(3)

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

3 優(yōu)化問題相似性

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

圖2 相似優(yōu)化問題

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

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

②OFf≤OFg

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

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

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

4.1 云估計

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

(4)

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

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

(5)

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

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

證畢.

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

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

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

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

優(yōu)化問題相對求解難度變化示意圖如圖3所示.

圖3 優(yōu)化問題相對求解難度變化示意圖

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

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

(6)

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

4.2.2 最簡云模型求解方法

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

begin

設t為進化代數(shù)，初始化種群Ent

構(gòu)造評價集R

repeat

for每一個個體Qi

endfor

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

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

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

untilterminated=ture

end

4.2.3 進化算法與最簡云模型結(jié)合

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

Step1.t=0，產(chǎn)生初始化種群Pt.

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

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

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

Step5. 根據(jù)第2節(jié)種難度分析方法求當前問題的相對求解難度.

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，算法結(jié)束并輸出結(jié)果，否則跳轉(zhuǎn)到Step 2.

5 實驗數(shù)據(jù)及分析

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

表1 測試函數(shù)對照表

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

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

表2 函數(shù)相對求解難度測試實驗結(jié)果

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

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

5.2 算法尋優(yōu)性能測試結(jié)果與分析

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

圖4 F2函數(shù)適應值變化曲線

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

圖5 F5函數(shù)適應值變化曲線

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

圖6 CA和CGA對于F3函數(shù)測試結(jié)果對比 圖7 CA和CGA對于F6函數(shù)測試結(jié)果對比

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

圖8 DE和PSO對于F3函數(shù)測試結(jié)果對比

圖9 DE和PSO對于F6函數(shù)測試結(jié)果對比

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

6 結(jié) 論

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