改進(jìn)差分進(jìn)化算法及其在模糊聚類分析中的應(yīng)用

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

（1.長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，長春 130022；2.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院，長春 130118）

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

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

綜上可知，DE算法性能依賴于策略與參數(shù)的選擇，選擇不當(dāng)會(huì)導(dǎo)致算法的早熟和搜索效率低下。針對(duì)這個(gè)問題，本文提出了一種多策略多參數(shù)并行的DE算法。在種群的演化過程中，對(duì)每個(gè)目標(biāo)個(gè)體采用多個(gè)策略與多個(gè)參數(shù)，一次產(chǎn)生多個(gè)試驗(yàn)個(gè)體。利用競(jìng)爭規(guī)則確定進(jìn)入選擇階段的優(yōu)勢(shì)個(gè)體，有效的保持了種群內(nèi)個(gè)體的多樣性，提高了搜索效率，在一定程度上避免了早熟收斂現(xiàn)象的發(fā)生。

1 差分進(jìn)化算法

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

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

CR∈[0,1)是交叉概率，jrand∈{1,2,…,D}是一個(gè)均勻分布隨機(jī)數(shù)發(fā)生器產(chǎn)生的整數(shù)。

2 改進(jìn)的差分進(jìn)化算法

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

全局收斂：算法在要求的代數(shù)內(nèi)達(dá)到了全局最優(yōu)解。此時(shí)表明，算法在開發(fā)和探索之間達(dá)到了一個(gè)較好的平衡。

早熟收斂：算法在搜索過程中陷入了某個(gè)非最優(yōu)解點(diǎn)。表明算法的開發(fā)能力較弱，沒有有效地保持種群的多樣性。

慢速收斂：算法具有找到全局最優(yōu)解的能力，但速度較慢沒有在要求的代數(shù)內(nèi)達(dá)到全局最優(yōu)解。表明與探索能力相比，開發(fā)（擾動(dòng)）能力過強(qiáng)。

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

由于優(yōu)化問題本身性質(zhì)（如單峰或者多峰）的不同，不可能找到一個(gè)統(tǒng)一組合策略與參數(shù)的DE算法來有效地處理不同類型的優(yōu)化問題；而對(duì)于一個(gè)具體的優(yōu)化問題，不同策略和參數(shù)組合的DE算法的尋優(yōu)能力也會(huì)有差異［4，7］。對(duì)于一個(gè)具體的問題，某些組合具有更高的尋優(yōu)能力，說明它在進(jìn)化的過程中較好的保持了個(gè)體的多樣性，并能夠在開發(fā)和探索上達(dá)到了較好的平衡?；谝陨戏治?，本文提出了一種改進(jìn)的差分進(jìn)化算法（IDE，improved Differential Evolution Algorithm）來繼承不同策略與參數(shù)組合DE的優(yōu)點(diǎn)。

在變異階段，IDE采用并行的方法在進(jìn)化的過程中同時(shí)采用多個(gè)策略與參數(shù)組合來一次產(chǎn)生多個(gè)實(shí)驗(yàn)個(gè)體，這樣就保持了種群的多樣性，在一定程度上避免了早熟收斂的發(fā)生。在選擇階段，IDE采用錦標(biāo)賽規(guī)則決定進(jìn)入下一代的個(gè)體，保持了優(yōu)勢(shì)個(gè)體，提高了搜索的效率。IDE吸收了不同策略與參數(shù)組合DE算法的優(yōu)點(diǎn)，在開發(fā)與探索上達(dá)到了較好的平衡。IDE算法具體步驟如下：

對(duì)i=1,2,…,NP，進(jìn)行下面操作：

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 標(biāo)準(zhǔn)測(cè)試函數(shù)

表1 測(cè)試數(shù)據(jù)Tab.1 Test data

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

表2 不同算法結(jié)果Tab.2 Results from different algorithms

表3 不同算法函數(shù)平均調(diào)用次數(shù)Tab.3 Average function evaluations of different algorithms

3.2 聚類應(yīng)用

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

從表4的結(jié)果能夠看出，當(dāng)聚類個(gè)數(shù)較小的時(shí)候，F(xiàn)CM算法能夠找到目標(biāo)函數(shù)的全局最優(yōu)解。而隨著聚類個(gè)數(shù)的增加，算法很難正確的初始化所有中心，導(dǎo)致了陷入局部極值，此時(shí)，應(yīng)用了IDE的聚類優(yōu)化結(jié)果具有明顯的優(yōu)勢(shì)。從圖1中也可以看出，基于IDE的模糊聚類結(jié)果更加合理，能夠正確的得到聚類的結(jié)構(gòu)，而FCM則由于使用的迭代法無法保證收斂到全局最優(yōu)，產(chǎn)生了錯(cuò)誤的聚類劃分。

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

表4 目標(biāo)函數(shù)優(yōu)化結(jié)果Tab.4 Optimization results of the objective functions

4 結(jié)論

本文算法在種群的演化過程中，對(duì)每個(gè)目標(biāo)個(gè)體采用多個(gè)策略與多個(gè)參數(shù)，一次產(chǎn)生多個(gè)試驗(yàn)個(gè)體。利用競(jìng)爭規(guī)則確定進(jìn)入選擇階段的優(yōu)勢(shì)個(gè)體，有效的保持了種群內(nèi)個(gè)體的多樣性，在開發(fā)和探索上達(dá)到了較好的平衡，并將提出的算法應(yīng)用到模糊聚類分析中取得了良好的效果。實(shí)驗(yàn)結(jié)果表明，算法具有較高的尋優(yōu)效率和較好的穩(wěn)定性。

［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.