改進差分進化算法及其在模糊聚類分析中的應用

曲福恒，胡雅婷，楊勇，谷欣超

（1.長春理工大學 計算機科學技術學院，長春 130022；2.吉林農業大學 信息技術學院，長春 130118）

差分進化算法（Differential evolution，DE）是由Storn與Price提出的一種進化算法［1］，DE性能良好且易于控制，已經成功的應用于各個領域，成為進化算法的研究熱點之一。與其它的進化算法一樣，DE是一種基于種群演化的隨機搜索算法。它通過變異、交叉、選擇操作引導種群走向優化問題的全局最優解。

DE的性能主要依賴于新個體的產生策略及算法中的三個控制參數種群規模NP、縮放因子F與交叉概率CR。在面臨一個具體的最優化問題時，首先需要確定采用哪種策略來運行DE，然后還要根據當前的策略選擇合適的參數。選擇的不合理可能導致算法的搜索效率低下以及產生早熟收斂的問題。不同的優化問題其適用的策略與參數可能不同，這就需要采用嘗試不同的組合來找到最適合于當前問題的策略與參數。DE的進化策略眾多加之不同的參數都具有一定的取值范圍，這種窮舉嘗試的方法在效率上顯然是非常低下的。為了解決這個問題，學者們提出了自適應參數或者策略的DE算法。多數自適應DE算法集中在參數方面，大體可分為兩類，第一類是通過進化過程的信息反饋來調整DE的參數［2］，第二種是直接把DE的參數編碼于進化個體中直接參與進化［3］。最近，學者對DE的策略進行了自適應方面的研究，提出了自適應策略的DE算法［4］，取得了一定的進展并提高了DE的性能，值得指出的是算法不需要設定任何參數具有較好的可控性［5］。

綜上可知，DE算法性能依賴于策略與參數的選擇，選擇不當會導致算法的早熟和搜索效率低下。針對這個問題，本文提出了一種多策略多參數并行的DE算法。在種群的演化過程中，對每個目標個體采用多個策略與多個參數，一次產生多個試驗個體。利用競爭規則確定進入選擇階段的優勢個體，有效的保持了種群內個體的多樣性，提高了搜索效率，在一定程度上避免了早熟收斂現象的發生。

1 差分進化算法

DE算法是一種簡單高效的基于種群演化的隨機全局優化技術，由Storn和Price于1995年提出［6］。與其它進化算法一樣，DE從某一隨機初始化的群體開始，通過多種操作（變異和交叉）產生新的個體，在按照一定的規則進行選擇操作決定進入下一代的個體，最終引導種群走向全局最優解。下面以典型的DE算法-DE/rand/1/bin來敘述各個操作的細節。

這里rl(l=1,2,3)是從集合{1,2,…,NP}中隨機選擇的互不相同整數。F∈[0,2]為縮放因子，它體現了新向量中差分向量所占的比重。

CR∈[0,1)是交叉概率，jrand∈{1,2,…,D}是一個均勻分布隨機數發生器產生的整數。

2 改進的差分進化算法

差分進化算法通過兩個主要的操作變異和交叉來對種群個體進行擾動，從而保持種群內個體的多樣性，實現在整個搜索空間的開發；通過選擇操作引導個體走向全局最優解，實現算法在局部區域的探索。這種擾動（開發）與選擇（探索）過程的實現與其它的進化算法類似。在擾動過程中，首先在父代中，按照某種規則選擇一個個體加上兩個隨機選擇個體的差向量，得到一個新個體，DE算法的個體以一定的概率被新個體取代。選擇過程中，通過適者生存的競爭機制保留新個體與原個體中的優勢個體。DE算法中至少存在三種不同性質的收斂類型：

全局收斂：算法在要求的代數內達到了全局最優解。此時表明，算法在開發和探索之間達到了一個較好的平衡。

早熟收斂：算法在搜索過程中陷入了某個非最優解點。表明算法的開發能力較弱，沒有有效地保持種群的多樣性。

慢速收斂：算法具有找到全局最優解的能力，但速度較慢沒有在要求的代數內達到全局最優解。表明與探索能力相比，開發（擾動）能力過強。

影響DE算法收斂性質的兩個最為重要的因素為控制參數和進化策略。目前對控制參數的研究較多，控制參數包括種群規模、交叉概率和縮放因子。大量研究的實驗結果表明，DE算法的性能對控制參數的取值極為敏感。已有的經驗表明，對應于三種不同的收斂性質可以把參數空間分解為三部分。假設已經得到了參數空間的這種分解，將很容易的對算法的參數進行選擇。然而不幸的是，這種參數空間的分解是很難得到的。鑒于此，學者對自適應參數的DE算法進行了大量的研究，并取得了一定進展。結果表明，自適應參數的DE算法在保持種群的多樣性同時具有較好的探索能力。另一方面，DE算法的進化策略眾多，不同的進化策略具有不同的尋優性能。最近，學者對DE的策略進行了自適應方面的研究，提出了自適應策略的DE算法［4］，取得了一定的進展并提高了DE的性能。這也說明良好的策略對于保持開發與探索之間的平衡具有重要的意義。

由于優化問題本身性質（如單峰或者多峰）的不同，不可能找到一個統一組合策略與參數的DE算法來有效地處理不同類型的優化問題；而對于一個具體的優化問題，不同策略和參數組合的DE算法的尋優能力也會有差異［4，7］。對于一個具體的問題，某些組合具有更高的尋優能力，說明它在進化的過程中較好的保持了個體的多樣性，并能夠在開發和探索上達到了較好的平衡。基于以上分析，本文提出了一種改進的差分進化算法（IDE，improved Differential Evolution Algorithm）來繼承不同策略與參數組合DE的優點。

在變異階段，IDE采用并行的方法在進化的過程中同時采用多個策略與參數組合來一次產生多個實驗個體，這樣就保持了種群的多樣性，在一定程度上避免了早熟收斂的發生。在選擇階段，IDE采用錦標賽規則決定進入下一代的個體，保持了優勢個體，提高了搜索的效率。IDE吸收了不同策略與參數組合DE算法的優點，在開發與探索上達到了較好的平衡。IDE算法具體步驟如下：

對i=1,2,…,NP，進行下面操作：

若滿足終止條件，停止算法。否則，令g=g+1，轉至步驟2。

3 實驗結果與分析

3.1 標準測試函數

表1 測試數據Tab.1 Test data

測試數據集包括標準測試數據庫CEC2005中的8個典型函數，其中有4個單峰函數，4個多峰函數，具體細節見表1。對比的算法包括三組不同參數設置下的DE/rand/1/bin算法，三組參數分別為F=0.9、CR=0.9，F=0.9、CR=0.1，F=0.5、CR=0.3。IDE的參數設置為，最大函數調用次數FEmax=300000，種群規模NP=100，進化策略為（1）DE/rand-to-best/1/bin，（2）DE/best/1/bin，策略參數選擇兩組分別為F=0.5、CR=0.5，F=0.9、CR=0.9。每個算法獨立運行25次，最優適應度值與理論最優值的誤差、標準差以及函數調用次數分別列于表2、表3。從表2可以看出，本文算法在6組測試數據上達到了所有算法的最好結果，其次是DE3算法，在3組數據上達到了最好結果。而從標準差上可以看出，本文算法在6組最好結果的5組中的標準差是最小的。從表3可以看出，IDE在7組數據上達到了最快的收斂速度。綜上可知，與傳統DE算法相比，本文算法在尋優能力、穩定性和尋優效率上均有著相對較好的性能。

表2 不同算法結果Tab.2 Results from different algorithms

表3 不同算法函數平均調用次數Tab.3 Average function evaluations of different algorithms

3.2 聚類應用

模糊c均值聚類（FCM）是應用最為廣泛的一種聚類算法，但其受到初始化敏感問題的影響性能欠佳，把提出的IDE應用到FCM目標函數優化中以改進聚類效果。由于聚類問題的數據維數和函數復雜程度較低，IDE的參數設置中最大函數調用次數改為FEmax=10000，種群規模NP=10，其它設置與前面一致。

從表4的結果能夠看出，當聚類個數較小的時候，FCM算法能夠找到目標函數的全局最優解。而隨著聚類個數的增加，算法很難正確的初始化所有中心，導致了陷入局部極值，此時，應用了IDE的聚類優化結果具有明顯的優勢。從圖1中也可以看出，基于IDE的模糊聚類結果更加合理，能夠正確的得到聚類的結構，而FCM則由于使用的迭代法無法保證收斂到全局最優，產生了錯誤的聚類劃分。

圖1 不同算法聚類結果圖Fig.1 Clustering results from different algorithms

表4 目標函數優化結果Tab.4 Optimization results of the objective functions

4 結論

本文算法在種群的演化過程中，對每個目標個體采用多個策略與多個參數，一次產生多個試驗個體。利用競爭規則確定進入選擇階段的優勢個體，有效的保持了種群內個體的多樣性，在開發和探索上達到了較好的平衡，并將提出的算法應用到模糊聚類分析中取得了良好的效果。實驗結果表明，算法具有較高的尋優效率和較好的穩定性。

［1］Storn R，Price K.Differential evolution--a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of global optimization，1997，11（4）：341-359.

［2］Omran M，Salman A，Engelbrecht A.Self-adaptive Differential Evolution［A］.Computational intelligence and security［C］.Berlin：Springer，2005：192-199.

［3］Brest J，Greiner S，Boskovic B，et al.Self-adapting control parameters in differential evolution：A comparative study on numerical benchmark problems［J］.Evolutionary Computation，IEEE Transactions on，2006，10（6）：646-657.

［4］Qin A，Huang V，Suganthan P.Differential evolution algorithm with strategy adaptation for global numerical optimization［J］.Evolutionary Computation，IEEE Transactions on，2009，13（2）：398-417.

［5］Neri F，Tirronen V.Recent advances in differential evolution：a survey and experimental analysis［J］.Artificial Intelligence Review，2010，33（1）：61-106.

［6］STORN R，PRICE K.Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces［R］.Berkeley，USA：University of Califiornia，International Computer Science Institute，1995.

［7］Mallipeddi R，Suganthan PN，Pan QK，et al.Differential evolution algorithm with ensemble of parameters and mutation strategies［J］.Applied soft computing，2011，11（2）：1679-1696.