差分進(jìn)化算法參數(shù)控制與適應(yīng)策略綜述

楊振宇，唐珂

(1.華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系，上海 200241;2.中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽合肥 230027)

差分進(jìn)化算法參數(shù)控制與適應(yīng)策略綜述

楊振宇1，唐珂2

(1.華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系，上海 200241;2.中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽合肥 230027)

差分進(jìn)化算法逐漸成為進(jìn)化計(jì)算領(lǐng)域最流行的隨機(jī)搜索算法之一，已被成功用于求解各類應(yīng)用問題.差分進(jìn)化算法參數(shù)設(shè)置與其性能密切相關(guān)，因此算法參數(shù)控制與適應(yīng)策略設(shè)計(jì)是目前該領(lǐng)域的研究熱點(diǎn)之一，目前已涌現(xiàn)出大量參數(shù)控制方案，但尚缺乏系統(tǒng)性的綜述與分析.首先簡要介紹差分進(jìn)化算法的基本原理與操作，然后將目前參數(shù)控制與適應(yīng)策略分成基于經(jīng)驗(yàn)的參數(shù)控制、參數(shù)隨機(jī)化適應(yīng)策略、基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略和參數(shù)自適應(yīng)策略4類進(jìn)行系統(tǒng)性綜述，重點(diǎn)介紹其中的參數(shù)適應(yīng)與自適應(yīng)策略.此外，為分析各種參數(shù)控制與適應(yīng)策略的功效，以實(shí)值函數(shù)優(yōu)化為問題背景設(shè)計(jì)了相關(guān)實(shí)驗(yàn)，進(jìn)一步分析各種策略的效率與實(shí)用性，實(shí)驗(yàn)結(jié)果表明，參數(shù)自適應(yīng)控制策略是目前該領(lǐng)域最有效的方法之一.

進(jìn)化計(jì)算;差分進(jìn)化;參數(shù)控制;適應(yīng)策略;自適應(yīng)

差分進(jìn)化(differential evolution，DE)算法［1－3］于1995年由Storn和Price提出，是一種新穎的通過引入獨(dú)特的差分變異模式進(jìn)行迭代搜索的進(jìn)化算法.該方法因具有簡單、易實(shí)現(xiàn)、高效、魯棒性強(qiáng)等多種優(yōu)點(diǎn)［4］，已被廣泛和成功地應(yīng)用于全局優(yōu)化、運(yùn)籌管理、工程設(shè)計(jì)等領(lǐng)域［5－6］.

進(jìn)化算法參數(shù)控制與適應(yīng)一直都是進(jìn)化計(jì)算領(lǐng)域的核心研究問題，這主要是因?yàn)樵擃惙椒ǖ木唧w流程與操作通常由算法參數(shù)控制，使得這些參數(shù)的設(shè)置與算法性能息息相關(guān)［7］.與傳統(tǒng)進(jìn)化算法類似，DE算法同樣也具有其自身的控制參數(shù).經(jīng)典DE算法具有3個(gè)主要的控制參數(shù)［1］:1)種群大小N;2)變異縮放因子F;3)交叉概率PCR.除了種群大小N這個(gè)任何基于群體搜索的算法都具有的一般性參數(shù)外，研究發(fā)現(xiàn)DE算法性能對(duì)另外2個(gè)參數(shù)的設(shè)置非常敏感，而且往往與具體問題相關(guān)，經(jīng)驗(yàn)參數(shù)設(shè)置并不總能使該算法發(fā)揮出其最高性能，而手動(dòng)參數(shù)調(diào)節(jié)費(fèi)時(shí)費(fèi)力，極大降低了算法的實(shí)用性.為了提高DE算法的性能和實(shí)用性，其參數(shù)的控制與適應(yīng)策略設(shè)計(jì)已成為DE領(lǐng)域的熱點(diǎn)研究方向，除基于經(jīng)驗(yàn)的參數(shù)設(shè)置外，研究者們提出了大量更先進(jìn)的參數(shù)控制與適應(yīng)策略，如參數(shù)隨機(jī)化適應(yīng)策略［8］、基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略［9］、參數(shù)自適應(yīng)策略［10］等.

針對(duì)DE算法的參數(shù)控制與適應(yīng)問題，目前研究者多以他們各自的視角提出了各種不同策略，尚缺乏對(duì)這些現(xiàn)存策略的綜述與系統(tǒng)性對(duì)比分析.本文對(duì)目前研究中出現(xiàn)的主要的參數(shù)控制與適應(yīng)策略進(jìn)行綜述，將它們分成如下4類進(jìn)行分析:1)基于經(jīng)驗(yàn)的參數(shù)控制;2)參數(shù)隨機(jī)化適應(yīng)策略;3)基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略;4)參數(shù)自適應(yīng)策略.除此之外，還以實(shí)值函數(shù)優(yōu)化問題為背景，用具體實(shí)驗(yàn)結(jié)果對(duì)比來討論各種參數(shù)控制與適應(yīng)策略的實(shí)際效果.

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

DE的主要思想是引入一種全新的可利用當(dāng)前群體中個(gè)體差異來構(gòu)造變異個(gè)體的差分變異模式.相對(duì)于傳統(tǒng)進(jìn)化算法，差分變異模式是DE算法中最為獨(dú)特的進(jìn)化操作.以經(jīng)典DE算法為例，在每代算法迭代過程中，對(duì)于當(dāng)前群體中的每個(gè)目標(biāo)個(gè)體，算法首先隨機(jī)選擇2個(gè)其他個(gè)體并使它們相減構(gòu)成差分向量，然后將該差分向量乘以一個(gè)縮放因子F后加到第3個(gè)隨機(jī)個(gè)體上構(gòu)成變異個(gè)體，最后該變異個(gè)體再經(jīng)過與對(duì)應(yīng)目標(biāo)個(gè)體的交叉和選擇操作生成一個(gè)新個(gè)體進(jìn)入下一代.基于上述過程并結(jié)合文獻(xiàn)［1］中的描述，以下將以實(shí)值優(yōu)化問題(即決策變量為實(shí)數(shù))為背景，具體介紹DE算法的群體表示與各種進(jìn)化操作.

1.1 群體表示與初始化

對(duì)于實(shí)值優(yōu)化問題，DE算法中的群體一般表示成N個(gè)D維向量:

式中:實(shí)值向量 Xi=(Xi(1)，Xi(2)，…，Xi(D))代表群體中的一個(gè)個(gè)體，D是目標(biāo)問題的決策變量個(gè)數(shù)，也可以稱為該問題的維數(shù)，N是群體大小.DE算法的初始化方法與其他進(jìn)化算法類似，一般是在指定搜索空間內(nèi)均勻隨機(jī)生成N個(gè)D維實(shí)值向量構(gòu)成其初始群體.

1.2 變異操作

給定當(dāng)前群體{Xi|i=1，2，…，N}，對(duì)其中的任意個(gè)體Xi，DE算法的變異操作按照式(1)生成一個(gè)對(duì)應(yīng)的變異個(gè)體.

式中:Xr1、Xr2和Xr3是從當(dāng)前群體中隨機(jī)選擇的3個(gè)互不相同的個(gè)體，而且它們也不應(yīng)與目標(biāo)個(gè)體Xi相同;縮放因子F是一個(gè)大于0的實(shí)常數(shù)，實(shí)驗(yàn)表明它一般應(yīng)滿足條件F∈(0，2］，而F=0.5通常是比較合適的設(shè)置［1］.在具體算法實(shí)現(xiàn)中，由于式(1)中的Xr2和Xr3是隨機(jī)選擇的2個(gè)個(gè)體，F(xiàn)取負(fù)值僅代表兩者交換位置，并不違背DE算法的設(shè)計(jì)原理，因此DE研究中也會(huì)出現(xiàn)將F限定在區(qū)間［－2，0)∪(0，2］的情況.

隨著DE算法的發(fā)展，根據(jù)差分向量構(gòu)造方式的不同，研究者還提出其他多種算法變種，常用的有如下幾種［2］:

根據(jù)具體應(yīng)用問題的不同，這些變異模式各有優(yōu)缺點(diǎn)，但式(1)所表示的經(jīng)典方式仍然是最常用、最有效的變異模式之一.

1.3 交叉操作

在完成變異操作后，DE算法將在目標(biāo)個(gè)體Xi和變異個(gè)體Vi之間執(zhí)行一種離散交叉操作，從而生成一個(gè)測(cè)試個(gè)體Ui，該離散交叉可描述如下:

式中:Rj(0，1)是一個(gè)在(0，1)的均勻隨機(jī)數(shù)發(fā)生器;jrand是［1，D］的一個(gè)隨機(jī)整數(shù)，以確保不會(huì)出現(xiàn)測(cè)試個(gè)體Ui完全復(fù)制Xi的情況;PCR∈［0，1］是交叉概率，用來控制在哪些決策變量上采用變異值，一般可設(shè)置為 0.9［1］.

1.4 選擇操作

對(duì)于每一個(gè)測(cè)試個(gè)體Ui，DE算法采用如下一對(duì)一的貪心選擇方式:

式中:f(·)是目標(biāo)函數(shù)(最小化問題);X'i是代替Xi而進(jìn)入下一代的子個(gè)體.

完成上述選擇操作后，DE算法得到一個(gè)新的群體{X'i|i=1，2，…，N}進(jìn)入下一代，從而可以迭代地繼續(xù)執(zhí)行進(jìn)化搜索過程.

2 DE算法參數(shù)控制與適應(yīng)策略

2.1 基于經(jīng)驗(yàn)的參數(shù)控制

在DE算法發(fā)展的早期，其參數(shù)主要是根據(jù)人為經(jīng)驗(yàn)設(shè)定為一些常數(shù)，如文獻(xiàn)［1］首先指出F=0.5是一個(gè)很好的初始選擇，如果群體出現(xiàn)早熟收斂現(xiàn)象，則應(yīng)該相應(yīng)地增大F值，但是小于0.4或大于1的F值往往只在極少數(shù)情況下才有用;對(duì)于交叉概率PCR，該文獻(xiàn)則指出0.1是一個(gè)合適的初始選擇，但考慮到大的PCR值有助于提高算法收斂速度，PCR=0.8通常也是不錯(cuò)的選擇.

文獻(xiàn)［11］以實(shí)值函數(shù)優(yōu)化問題為背景對(duì)DE算法的參數(shù)展開了詳細(xì)的數(shù)值分析，指出了該算法性能對(duì)參數(shù)敏感的問題，這些參數(shù)的設(shè)定不僅與具體問題相關(guān)，而且它們之間也相互影響，不易合理設(shè)置.對(duì)縮放因子F，該文獻(xiàn)推薦0.6為初始選擇，如果發(fā)現(xiàn)算法只能收斂到局部最優(yōu)，則應(yīng)適當(dāng)增大F值，但當(dāng)F＞1時(shí)往往導(dǎo)致群體難以收斂;對(duì)于交叉概率參數(shù)，大的PCR值有利于增加算法收斂速度，但如果過大將有可能導(dǎo)致算法早熟，介于0.3～0.9的值往往是比較好的設(shè)置.

在與其他算法的性能比較中，文獻(xiàn)［12］發(fā)現(xiàn)參數(shù)設(shè)置為F=0.5，PCR=0.9的DE算法要顯著優(yōu)于粒子群優(yōu)化(particle swarm optimization，PSO)算法［13］及其改進(jìn)版本 arPSO［14］，也優(yōu)于簡單進(jìn)化算法(simple evolutionary algorithm，SEA)［15］.

也有研究者認(rèn)為F應(yīng)該設(shè)為稍大值以避免算法早熟，如文獻(xiàn)［16］中就建議將參數(shù)F和PCR都設(shè)置為常數(shù)0.9.對(duì)于DE算法的經(jīng)驗(yàn)參數(shù)設(shè)置，目前研究中一般都認(rèn)為F=0.5，PCR=0.9是比較有效的經(jīng)典設(shè)置［17］.

2.2 參數(shù)隨機(jī)化適應(yīng)策略

雖然基于經(jīng)驗(yàn)的參數(shù)控制可在一定程度上緩解DE算法的參數(shù)控制問題，但是由于這種“經(jīng)驗(yàn)”通常與具體目標(biāo)問題密切相關(guān)，不同的解空間分布往往具有不同的需求，甚至同一問題的不同進(jìn)化階段也可能具有不同需求，不存在能適用于所有目標(biāo)問題的統(tǒng)一固定參數(shù)設(shè)置，所以經(jīng)驗(yàn)參數(shù)控制逐漸不能滿足DE算法在越來越廣泛的應(yīng)用問題上的求解性能要求.特別是對(duì)于特征未知的應(yīng)用問題，仍然需要通過費(fèi)時(shí)費(fèi)力的手動(dòng)參數(shù)調(diào)節(jié)才能找到比較合適的經(jīng)驗(yàn)參數(shù)，這大大降低了DE算法的實(shí)用價(jià)值.為解決此問題，研究者們逐漸開始考慮引入隨機(jī)化適應(yīng)策略進(jìn)行參數(shù)控制.與將參數(shù)設(shè)置為固定常數(shù)的經(jīng)驗(yàn)參數(shù)控制不同，這種方法在每代對(duì)每個(gè)個(gè)體根據(jù)一個(gè)預(yù)先制定的概率分布模型生成偽隨機(jī)數(shù)作為參數(shù)值，其基本思想與進(jìn)化算法思想類似，主要是希望通過生成－測(cè)試的模式讓算法自己選取比較合適的參數(shù)值.常用的概率分布模型有均勻分布(uniform distribution)、高斯分布(Gaussian distribution，又稱正態(tài)分布)、柯西分布(Cauchy distribution)等.

文獻(xiàn)［8］將每次變異的縮放因子F設(shè)置為［0.5，1］之間的均勻隨機(jī)數(shù)，提出一種改進(jìn)的算法DERSF;文獻(xiàn)［18］修改DE算法的變異模式提出2種改進(jìn)算法DERL和DELB，它們也都使用了均勻隨機(jī)數(shù)生成縮放因子F，均勻隨機(jī)數(shù)的范圍限定為［－1，－0.4］∪［0.4，1］.文獻(xiàn)［19］提出一種 NSDE算法，將DE算法的交叉概率PCR設(shè)置為［0，1］之間的均勻隨機(jī)數(shù).實(shí)驗(yàn)分析發(fā)現(xiàn)這些改進(jìn)算法都優(yōu)于參數(shù)設(shè)置為F=0.5，PCR=0.9的經(jīng)典DE算法.

文獻(xiàn)［20］針對(duì)多目標(biāo)優(yōu)化問題提出一種改進(jìn)的DE算法PDE，該算法中縮放因子F被設(shè)置為均值為0、標(biāo)準(zhǔn)差為1的高斯分布，即Fi=Ni(0，1)，其中i表示對(duì)每次變異都重新生成一個(gè)F值.文獻(xiàn)［21－22］通過引入多種變異策略提出一種自適應(yīng)DE算法SADE，該算法中縮放因子F被設(shè)定為均值為0.5、標(biāo)準(zhǔn)差為0.3的高斯分布，即Fi=Ni(0.5，0.3)，其中參數(shù)0.5是參考了DE算法的經(jīng)驗(yàn)參數(shù)設(shè)置，目的是在比較好的經(jīng)驗(yàn)值附近進(jìn)行參數(shù)隨機(jī)化，給生成合適的參數(shù)值提供更大可能.

由DE變異公式(1)可以看出，縮放因子F與算法搜索步長密切相關(guān)，在不同的搜索階段算法可能偏好不同的搜索步長，比如當(dāng)群體離全局最優(yōu)點(diǎn)較遠(yuǎn)時(shí)，較大的搜索步長將有助于算法快速收斂到好的子空間，而當(dāng)群體離全局最優(yōu)點(diǎn)較近時(shí)，小的搜索步長則有助于算法準(zhǔn)確找到更優(yōu)解［23］.縮放因子F的經(jīng)驗(yàn)設(shè)置只能提供一種步長選擇，而隨機(jī)化參數(shù)設(shè)置則可以提供多種選擇，這也是隨機(jī)化參數(shù)設(shè)置通用性更強(qiáng)的原因.但是無論均勻分布還是高斯分布，其搜索步長的廣度都是有限的，當(dāng)算法靠近多極值問題的局部最優(yōu)點(diǎn)時(shí)，可能無法提供足夠大的步長進(jìn)行跳躍式搜索，因而仍然存在陷入局部最優(yōu)的風(fēng)險(xiǎn).

針對(duì)均勻分布和高斯分布的局限性，研究者們開始考慮引入范圍更廣的柯西分布進(jìn)行參數(shù)隨機(jī)化控制.文獻(xiàn)［19］結(jié)合進(jìn)化規(guī)劃(evolutionary programming，EP)的特點(diǎn)，提出一種鄰域控制差分進(jìn)化算法NSDE，該算法的縮放因子根據(jù)式(2)生成.

式中:p設(shè)為0.5;Ni(0.5，0.5)表示均值、標(biāo)準(zhǔn)差均為0.5的高斯隨機(jī)數(shù);Ci(0，1)表示位置參數(shù)為0、規(guī)模參數(shù)為1的柯西隨機(jī)數(shù);Ri(0，1)表示(0，1)的均勻隨機(jī)數(shù).NSDE算法希望通過式(2)同時(shí)兼顧大小搜索步長，從而能有效搜索各種適應(yīng)度分布特征未知的解空間.

文獻(xiàn)［24］對(duì)NSDE算法進(jìn)行了進(jìn)一步改進(jìn)，提出一種SaNSDE算法，其縮放因子F的控制方法與式(2)類似，只是根據(jù)經(jīng)驗(yàn)將高斯隨機(jī)數(shù)的參數(shù)修正為均值0.5，標(biāo)準(zhǔn)差0.3，并采用適應(yīng)策略調(diào)整式(2)中的參數(shù)p.SaNSDE算法中參數(shù)適應(yīng)策略的有效性在很多測(cè)試函數(shù)上都得到了驗(yàn)證，并成功用于輔助求解問題規(guī)模高達(dá)1 000維的大規(guī)模實(shí)值優(yōu)化問題［25］.

2.3 基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略

參數(shù)隨機(jī)化適應(yīng)策略通過將DE算法的參數(shù)，即縮放因子F和交叉概率PCR，設(shè)置成隨機(jī)數(shù)，增加了這些參數(shù)取值的多樣性，從而使算法在面臨無任何先驗(yàn)知識(shí)的問題時(shí)，仍然能夠自動(dòng)產(chǎn)生適合當(dāng)前搜索需要的參數(shù)值，這在一定程度上提高了算法的性能.然而，這些用于控制DE算法參數(shù)的隨機(jī)數(shù)發(fā)生器同樣存在其自身的參數(shù)，比如高斯分布的均值和方差，這些參數(shù)同樣需要合理設(shè)置.這些參數(shù)沒有原算法的參數(shù)敏感，在上述參數(shù)隨機(jī)化適應(yīng)策略中一般都是根據(jù)經(jīng)驗(yàn)設(shè)置，尋求這些參數(shù)的最優(yōu)設(shè)置意味著存在進(jìn)一步改進(jìn)DE算法性能的空間，研究者們開始利用統(tǒng)計(jì)學(xué)習(xí)技術(shù)分析搜索過程中的歷史信息，嘗試從中找出規(guī)律以控制隨機(jī)數(shù)發(fā)生器的參數(shù).

文獻(xiàn)［21－22］通過對(duì)交叉概率PCR的分析指出，該參數(shù)在某個(gè)小范圍內(nèi)變動(dòng)時(shí)對(duì)DE算法性能影響不大，但該范圍不易確定.為解決此問題，該文獻(xiàn)提出一種SADE算法，它假設(shè)交叉概率PCR滿足一個(gè)均值為PCRM、標(biāo)準(zhǔn)差較小的高斯分布，算法開始時(shí)對(duì)每個(gè)個(gè)體根據(jù)式(3)生成一個(gè)PCR值.

式中:PCRM在算法開始時(shí)被設(shè)置為0.5，在其周圍生成的PCRi值將被使用若干代(如SADE算法中設(shè)置的5代)，然后重新按照式(3)生成新的PCRi.這樣在每一代演化過程中，能使后代進(jìn)入下一代的個(gè)體，對(duì)應(yīng)的PCRi將會(huì)被記錄在一個(gè)數(shù)組ACR中，經(jīng)過一定代數(shù)的累積后(如SADE算法中使用的25代)，均值將按式(4)更新.

在每次PCRM更新后，數(shù)組ACR將會(huì)被清空進(jìn)入下一次統(tǒng)計(jì)過程.

文獻(xiàn)［24］分析認(rèn)為當(dāng)PCR比較小時(shí)后代更易于進(jìn)入下一代，但是該后代對(duì)應(yīng)的適應(yīng)度改進(jìn)程度通常比較小;而大的PCR值生成的后代雖然相對(duì)而言較難進(jìn)入下一代，但當(dāng)成功進(jìn)入下一代時(shí)其引起的適應(yīng)度改進(jìn)程度往往要大很多，因此式(4)對(duì)應(yīng)的適應(yīng)策略存在將PCR取較小值的導(dǎo)向.為緩解此問題，該文獻(xiàn)提出一種加權(quán)的交叉概率適應(yīng)策略，其基本原理與式(4)類似，區(qū)別在于每當(dāng)在數(shù)組ACR中記錄成功PCR值的時(shí)候，同時(shí)在另一數(shù)組A△f={△f}中額外記錄對(duì)應(yīng)個(gè)體的適應(yīng)度改進(jìn)值，即△f=f(k)－fnew(k)，然后PCRM的更新公式修正為:

實(shí)驗(yàn)證明這種改進(jìn)的參數(shù)適應(yīng)機(jī)制使DE算法在一些復(fù)雜測(cè)試函數(shù)上的性能有了較顯著的改進(jìn).

無論SADE還是SaNSDE都是采用一種離散的方式，通過歷史信息更新用于參數(shù)控制的概率分布，這意味著只有當(dāng)歷史信息累積一定代數(shù)后才能被使用，當(dāng)最大進(jìn)化代數(shù)比較有限時(shí)，概率分布的參數(shù)被更新的頻度將會(huì)很有限，這將影響參數(shù)適應(yīng)性調(diào)整的及時(shí)性.文獻(xiàn)［9］提出一種改進(jìn)的DE算法JADE，該方法采用了聯(lián)系更新的方式適應(yīng)性調(diào)整概率分布的參數(shù).對(duì)于交叉概率PCR，JADE仍然假設(shè)它服從均值為PCRM、標(biāo)準(zhǔn)差為0.1的高斯分布，即滿足式(3).

在每代進(jìn)化過程中，算法將用SCR記錄能使對(duì)應(yīng)后代進(jìn)入下一代的PCRi值，并用式(7)更新PCRM.

式中:參數(shù)c是介于(0，1)的實(shí)數(shù)，JADE中被設(shè)置為c=0.1.對(duì)于縮放因子F，該文獻(xiàn)假設(shè)它服從位置參數(shù)為Fm，規(guī)模參數(shù)為0.1的柯西分布:

式中:Fm被初始化為0.5，如果Fi不在0～1之間，將會(huì)被重新生成.在每代進(jìn)化過程中，能使后代進(jìn)入下一代的個(gè)體對(duì)應(yīng)的Fi值將會(huì)被記錄在數(shù)組SF中，然后根據(jù)式(9)更新.

式中:meanL(·)表示萊默均值(Lehmer mean)，這里使用萊默均值而非一般均值是為了避免出現(xiàn)F過小而導(dǎo)致算法低效的情況.

文獻(xiàn)［26］通過引入基于歷史信息的可信度和影響適應(yīng)度值變化程度的加權(quán)機(jī)制，將上述2種適應(yīng)策略擴(kuò)展為控制任意與個(gè)體相關(guān)聯(lián)的算法參數(shù)的一般性方法，其基本思想是首先假設(shè)該參數(shù)的分布滿足某個(gè)概率模型，然后通過統(tǒng)計(jì)學(xué)習(xí)的方法逐漸調(diào)整概率模型的參數(shù).該文獻(xiàn)使用這種一般性的參數(shù)隨機(jī)化適應(yīng)方法提出一種改進(jìn)的DE算法GaDE，并將其成功用于求解大規(guī)模實(shí)值優(yōu)化問題.

大量的實(shí)驗(yàn)結(jié)果表明，基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略不僅優(yōu)于經(jīng)驗(yàn)參數(shù)設(shè)置，而且由于這類方法可以從歷史信息中學(xué)習(xí)出一些參數(shù)變化趨勢(shì)，比簡單的參數(shù)隨機(jī)化適應(yīng)策略更有方向性，當(dāng)這種方向性比較準(zhǔn)確時(shí)，這類方法將更有效.

2.4 參數(shù)自適應(yīng)策略

根據(jù)文獻(xiàn)［27］的定義，參數(shù)適應(yīng)與自適應(yīng)策略的本質(zhì)區(qū)別在于后者須將算法參數(shù)放入個(gè)體編碼中與決策變量一同進(jìn)化.依據(jù)這個(gè)條件，無論是參數(shù)隨機(jī)化策略還是基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化策略都只能稱之為適應(yīng)策略，而自適應(yīng)策略一般被認(rèn)為是進(jìn)化算法參數(shù)控制的最高級(jí)手段，在DE算法領(lǐng)域同樣存在相關(guān)工作.

既然DE是一種非常有效的參數(shù)優(yōu)化算法，那么一種非常直觀的自適應(yīng)策略就是仍然采用DE這種模式來進(jìn)化其自身的參數(shù)F和PCR.文獻(xiàn)［28］提出一種SPDE算法，該算法首先對(duì)每個(gè)個(gè)體都增加Fi和這2個(gè)參數(shù)作為決策變量放入個(gè)體表示，在算法開始時(shí)Fi和被初始化為［0，1］的均勻隨機(jī)數(shù)，然后在每代進(jìn)化運(yùn)算時(shí)，首先根據(jù)式(11)、(12)生成.

式中:Ni(0，1)代表均值為0、標(biāo)準(zhǔn)差為1的高斯隨機(jī)數(shù);r1、r2和r3表示3個(gè)互不相同且也不與i相同的個(gè)體下標(biāo).在這些參數(shù)進(jìn)化完成后，它們將參與到DE算法中的包含決策變量的個(gè)體的變異和交叉，由于這些參數(shù)值存在于編碼中，如果每組參數(shù)對(duì)應(yīng)生成的后代能成功進(jìn)入下一代，那么參數(shù)本身自然也進(jìn)入了下一代，從而達(dá)到一種控制參數(shù)層次的進(jìn)化與自適應(yīng).由于一般要求F和PCR在控制在區(qū)間［0，1］中，因此如果式(11)、(12)生成的參數(shù)值超出了此范圍，將會(huì)應(yīng)用修復(fù)規(guī)則使它們重新回到此范圍.文獻(xiàn)［28］在一組多目標(biāo)問題上測(cè)試了SPDE算法的性能，與其他13種算法的比較表明了這種自適應(yīng)策略比較有效.類似地，文獻(xiàn)［29］建議用如下這種方式自適應(yīng)控制參數(shù)F:

而交叉概率PCR被設(shè)置為根據(jù)均值為0.5、標(biāo)準(zhǔn)差為0.15的高斯隨機(jī)數(shù)N(0.5，0.15)生成.文獻(xiàn)［30］指出，根據(jù)這種自適應(yīng)策略設(shè)計(jì)的SDE算法要優(yōu)于文獻(xiàn)［28］中的SPDE算法.

文獻(xiàn)［10］提出一種改進(jìn)的DE算法jDE，它采用了另一種參數(shù)自適應(yīng)策略.算法jDE同樣將Fi和PCRi與每個(gè)個(gè)體關(guān)聯(lián)起來放入個(gè)體編碼，算法開始時(shí)Fi和PCRi被分別初始化0.5和0.9，然后每代在決策變量進(jìn)化前按式(14)、(15)更新.式中:Rj(j∈{1，2，3，4})是［0，1］的均勻隨機(jī)數(shù);τ1和τ2分別表示更新參數(shù)F和PCR的概率，在jDE中被設(shè)置為 τ1=τ2=0.1;為了使新的Fi在［0.1，1.0］之間，F(xiàn)l和Fu分別被設(shè)置為0.1和1.0.文獻(xiàn)［10］中設(shè)計(jì)了大量的數(shù)值實(shí)驗(yàn)分析了這種自適應(yīng)策略的效果，實(shí)驗(yàn)結(jié)果表明這種自適應(yīng)策略在求解實(shí)值函數(shù)優(yōu)化問題時(shí)非常有效，使jDE成為目前最為高效的DE改進(jìn)算法之一.

表1簡要列出了本節(jié)介紹的各種DE算法變種及其采用的參數(shù)控制與適應(yīng)策略.

表1 DE算法變種及其對(duì)應(yīng)的參數(shù)控制與適應(yīng)策略Table 1 DE variants and the corresponding parameter control and adaptation strategies

3 實(shí)驗(yàn)分析

本文前面系統(tǒng)介紹了目前DE算法研究領(lǐng)域常用的參數(shù)控制與適應(yīng)策略，為了對(duì)這些策略的實(shí)際效果有更直觀的認(rèn)識(shí)，筆者以實(shí)值函數(shù)優(yōu)化為問題背景設(shè)計(jì)了一組實(shí)驗(yàn)進(jìn)行驗(yàn)證.為保證實(shí)驗(yàn)結(jié)果比較的公平性，所有算法都采用經(jīng)典DE變異公式(即式(1))，用表2來標(biāo)記要測(cè)試的算法及其對(duì)應(yīng)的參數(shù)控制策略.

表2 測(cè)試的DE算法變種及其參數(shù)控制與適應(yīng)策略Table 2 The tested DE variants and their parameter control and adaptation strategies

由表2可以看出，第1種方法是采用經(jīng)驗(yàn)參數(shù)設(shè)置的經(jīng)典DE算法;接下來是3種采用參數(shù)隨機(jī)化適應(yīng)策略的算法，分別對(duì)應(yīng)均勻分布、高斯分布和柯西分布;第5、6種算法采用基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略，分別按文獻(xiàn)［21］中的SADE和文獻(xiàn)［9］中的JADE所采用的策略進(jìn)行參數(shù)控制，由于這2種算法還采用了其他策略進(jìn)一步改進(jìn)算法性能，與這里只采用經(jīng)典變異公式的方法稍有區(qū)別，分別用SADE*和JADE*來標(biāo)記它們以示區(qū)別;最后一種采用參數(shù)自適應(yīng)策略，與文獻(xiàn)［10］中的jDE完全一致.

在測(cè)試集方面，采用了13個(gè)被廣泛使用的經(jīng)典實(shí)值函數(shù)優(yōu)化函數(shù)［23］，表3給出了這些函數(shù)的定義與搜索空間.其中函數(shù)f1～f4、f6和f7是單峰函數(shù)(即只有1個(gè)極值點(diǎn))，函數(shù)f5、f8～f13是多峰函數(shù)，而且極值點(diǎn)的個(gè)數(shù)非常多［23］，所有測(cè)試函數(shù)都被設(shè)定為30維，其最優(yōu)值皆為0.

在參數(shù)設(shè)置方面，所有算法的群體大小都設(shè)為100，其參數(shù)F與PCR的設(shè)置則按照表2及相關(guān)文獻(xiàn)中的描述，對(duì)于比較復(fù)雜的函數(shù)f3、f4、f5、f8和f9進(jìn)化代數(shù)N設(shè)定為5 000，而對(duì)于相對(duì)簡單的其他函數(shù)，進(jìn)化代數(shù)N設(shè)定為1 500.對(duì)于每個(gè)測(cè)試函數(shù)，每個(gè)算法都獨(dú)立運(yùn)行30次統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果，并計(jì)算均值與方差.表4和表5分別列出了算法在單峰和多峰函數(shù)上的均值與方差.

從表4的結(jié)果可以看出，基于經(jīng)驗(yàn)參數(shù)設(shè)置的經(jīng)典DE算法在函數(shù)f1、f3和f6上具有不錯(cuò)的結(jié)果，但在其他函數(shù)上結(jié)果稍差.采用參數(shù)隨機(jī)化適應(yīng)策略的算法DEU、DEG和DEC一般比經(jīng)典DE算法結(jié)果更好，而在函數(shù)f4上結(jié)果卻變得更差，說明參數(shù)隨機(jī)化并不總是有效，這3個(gè)算法中使用高斯隨機(jī)數(shù)的DEG效果最好.對(duì)于基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化適應(yīng)策略SADE*和JADE*，它們?cè)谶@些單峰函數(shù)上結(jié)果并不突出，僅在比較復(fù)雜的f4上取得了更好結(jié)果.采用參數(shù)自適應(yīng)的算法jDE幾乎在所有函數(shù)上都取得了更好的結(jié)果，說明這種參數(shù)自適應(yīng)策略對(duì)求解單峰函數(shù)比較有效.

從表5中算法在多峰函數(shù)上的結(jié)果看，經(jīng)典DE算法在比較復(fù)雜的函數(shù)f8和f9上結(jié)果很差，在其他函數(shù)上結(jié)果一般.使用均勻隨機(jī)數(shù)的DEU算法在大部分問題上都得到了更好結(jié)果，但在函數(shù)f5上的結(jié)果變得很差;使用高斯隨機(jī)數(shù)的DEG算法只在函數(shù)f8～f10上得到了更好結(jié)果;使用柯西隨機(jī)數(shù)的DEC算法在函數(shù)f5和f11上結(jié)果不理想.采用基于統(tǒng)計(jì)學(xué)習(xí)參數(shù)隨機(jī)化適應(yīng)策略的算法SADE*在除f5外的函數(shù)上都取得了更好結(jié)果，而另一種JADE*則在函數(shù)f8和f9上性能有顯著提高.對(duì)于自適應(yīng)參數(shù)控制算法jDE，它在除f5外的函數(shù)上都取得了明顯更好的結(jié)果.

表3 經(jīng)典實(shí)值優(yōu)化測(cè)試函數(shù)集Table 3 Classical benchmark functions for real-valued optimization

表4 采用各種不同參數(shù)控制與適應(yīng)策略的DE算法在單峰函數(shù)上的結(jié)果Table 4 Results of DE with different parameter control and adaptation strategies for unimodal functions

表5 采用各種不同參數(shù)控制與適應(yīng)策略的DE算法在多峰函數(shù)上的結(jié)果Table 5 Results of DE with different parameter control and adaptation strategies for multimodal functions

從以上實(shí)驗(yàn)結(jié)果可以看出，采用經(jīng)驗(yàn)參數(shù)控制的DE算法雖然能有效求解一部分問題，但由于其最優(yōu)參數(shù)組合往往與問題相關(guān)而不易設(shè)置，導(dǎo)致這種方法一般不具有通用性;參數(shù)隨機(jī)化適應(yīng)策略和基于統(tǒng)計(jì)學(xué)習(xí)的參數(shù)隨機(jī)化策略能彌補(bǔ)經(jīng)驗(yàn)參數(shù)控制的不足，但并不是對(duì)任何問題都有效，精確度有待進(jìn)一步提高;而參數(shù)自適應(yīng)策略對(duì)絕大部分問題都適用，但也不排除對(duì)極少數(shù)問題存在更優(yōu)的經(jīng)驗(yàn)設(shè)置的可能(如函數(shù)f5).

4 結(jié)束語

差分進(jìn)化(DE)是進(jìn)化計(jì)算領(lǐng)域一個(gè)非常重要的隨機(jī)搜索算法新興分支，在很多基準(zhǔn)測(cè)試和實(shí)際應(yīng)用問題上都表現(xiàn)出了卓越的性能，其新穎的進(jìn)化操作起到了決定性的作用，而與這些操作相關(guān)的算法參數(shù)的控制與適應(yīng)方法一直都是該領(lǐng)域的研究熱點(diǎn)，目前已涌現(xiàn)出大量行之有效的策略.本文首先簡要介紹了DE算法的基本原理與操作，然后著重綜述了目前比較有代表性的參數(shù)適應(yīng)策略，并加以分類總結(jié)，最后通過設(shè)計(jì)具體實(shí)驗(yàn)，對(duì)這些適應(yīng)策略進(jìn)行了對(duì)比分析，以驗(yàn)證它們的實(shí)際功效，相關(guān)實(shí)驗(yàn)結(jié)果表明，參數(shù)自適應(yīng)控制策略是目前最有效的方法之一.此外，目前也存在很多通過設(shè)計(jì)更精巧的變異模式來改進(jìn)DE算法性能的研究工作，將這些工作與參數(shù)自適應(yīng)控制結(jié)合將是設(shè)計(jì)更高效DE算法的有效研究手段之一.

［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］PRICE K，STORN R，LAMPINEN J.Differential evolution:a practical approach to global optimization［M］.Berlin，Germany:Springer－Verlag，2005.

［3］CHAKRABORTY U K.Advances in differential evolution［M］.Berlin，Germany:Springer－Verlag，2008.

［4］STORN R，PRICE K.Differential evolution:a simple and efficient adaptive scheme for global optimization over continuous spaces［EB/OL］. ［2010－10－25］.http://www.icsi.berkeley.edu/～ storn/TR－95－012.pdf.

［5］STORN R.System design by constraint adaptation and differential evolution［J］.IEEE Transactions on Evolutionary Computation，1999，3(1):22－34.

［6］THOMSEN R.Flexible ligand docking using differential evolution［C］//Proceedings of the 2003 IEEE Congress on E－volution Computation.Canberra，Australia，2003:2354－2361.

［7］BACK T，SCHWEFEL H P.An overview of evolutionary algorithms for parameter optimization［J］.Evolutionary Computation，1993，1(1):1－23.

［8］DAS S，KONAR A，CHAKRABORTY U K.Two improved differential evolution schemes for faster global search［C］//Proceedings of the 2005 Genetic and Evolutionary Computation Conference.Washington，DC，USA，2005:991－998.

［9］ZHANG J，SANDERSON A C.JADE:adaptive differential evolution with optimal external archive［J］.IEEE Transactions on Evolutionary Computation，2009，13(5):945－958.

［10］BREST J，GREINER S，BOSKOVC B，et al.Self－adapting control parameters in differential evolution:a comparative study on numerical benchmark problems［J］.IEEE Transactions on Evolutionary Computation，2006，10(6):646－657.

［11］GAMPERLE R，MULLER S，KOUMOUTSAKOS P.A parameter study for differential evolution［C］//WSEAS International Conference on Advances in Intelligent Systems，F(xiàn)uzzy Systems， Evolutionary Computation. Interlaken，Switzerland，2002:293－298.

［12］VESTERSTROM J，THOMSEN R.A comparative study of differential evolution，particle swarm optimization and evolutionary algorithms on numerical benchmark problems［C］//Proceedings of the 2004 IEEE Congress on Evolution Computation.Portland，USA，2004:1980－1987.

［13］KENNEDY J，EBERHART R C.Particle swarm optimization［C］//IEEE International Conference on Neural Networks.Perth，Australia，1995:1942－1948.

［14］RIGET J，VESTERSTROM J.A diversity－guided particle swarm optimizer—the arPSO，Technical Report 2002－02［R］.Aarhus，Denmark:Department of Computer Science，University of Aarhus，2002.

［15］THOMSEN R.Flexible ligand docking using evolutionary algorithms:investigating the effects of variation operators and local search hybrids［J］.BioSystems，2003，72(1/2):57－73.

［16］ROMKKONEN J，KUKKONEN S，PRICE K V.Real－parameter optimization with differential evolution［C］//Proceedings of the 2005 IEEE Congress on Evolution Computation.Edinburgh，UK，2005:506－513.

［17］RAHNAMAYAN S，TIZHOOSH H R，SALAMA M A.Opposition－based differential evolution［J］.IEEE Transactions on Evolutionary Computation，2008，12(1):64－79.

［18］KAELO P，ALI M M.A numerical study of some modified differential evolution algorithms［J］.European Journal of Operational Research，2006，169(3):1176－1184.

［19］YANG Zhenyu，YAO Xin，HE Jingsong.Making a difference to differential evolution［M］//MICHALEWICZ Z，SIARRY P.Advances in Metaheuristics for Hard Optimization.Berlin，Germany:Springer，2008:397－414.

［20］ABBASS H A，SARKER R，NEWTON C.PDE:a Paretofrontier differential evolution approach for multi－objective optimization problems［C］//Proceedings of the 2003 IEEE Congress on Evolution Computation.Canberra，Australia，2003:971－978.

［21］QIN A K，SUGANTHAN P N.Self－adaptive differential evolution algorithm for numerical optimization［C］//Proceedings of the 2005 IEEE Congress on Evolution Computation.Edinburgh，UK，2005:1785－1791.

［22］QIN A K，HUANG V L，SUGANTHAN P N.Differential evolution algorithm with strategy adaptation for global numerical optimization［J］.IEEE Transactions on Evolutionary Computation，2009，13(2):398－417.

［23］YAO Xin，LIU Yong，LIN Guangming.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82－102.

［24］YANG Zhenyu，TANG Ke，YAO Xin.Self－adaptive differential evolution with neighborhood search［C］//Proceedings of the 2008 IEEE Congress on Evolution Computation.Hong Kong，China，2008:1110－1116.

［25］YANG Zhenyu，TANG Ke，YAO Xin.Large scale evolutionary optimization using cooperative coevolution［J］.Information Sciences，2008，178(15):2985－2999.

［26］YANG Zhenyu，TANG Ke，YAO Xin.Scalability of generalized adaptive differential evolution for large－scale continuous optimization［J］. Soft Computing，2011(in press).

［27］HINTERDING R，MICHALEWICZ Z，EIBEN A E.Adaptation in evolutionary computation:a survey［C］//Proceedings of the 1997 IEEE International Conference on Evolutionary Computation.Indianapolis，USA，1997:65－69.

［28］ABBASS H A.The self－adaptive Pareto differential evolution algorithm［C］//Proceedings of the 2002 IEEE Congress on Evolution Computation.Honolulu，USA，2002:831－836.

［29］OMRAN M，SALMAN A，ENGELBRECHT A.Self－adaptive differential evolution［C］//Proceedings of the International Conference on Computational Intelligence and Security.Xi’an，China，2005:192－199.

［30］SALMAN A，ENGELBRECHT A，OMRAN M.Empirical analysis of self－adaptive differential evolution［J］.European Journal of Operational Research，2007，183(2):785－804.

楊振宇，男，1982年生，講師，博士，主要研究方向?yàn)檫M(jìn)化計(jì)算與應(yīng)用，發(fā)表學(xué)術(shù)論文多篇，其中被SCI、EI檢索10余篇.

唐珂，男，1981年生，教授，博士，IEEE Computational Intelligence Magazine副編輯，IEEE計(jì)算智能協(xié)會(huì)Emergent Technologies Technical Committee委員.主要研究方向?yàn)橛?jì)算智能、機(jī)器學(xué)習(xí)、模式識(shí)別等，發(fā)表學(xué)術(shù)論文50余篇.

An overview of parameter control and adaptation strategies in differential evolution algorithm

YANG Zhenyu1，TANG Ke2

(1.Department of Computer Science and Technology，East China Normal University，Shanghai 200241，China;2.School of Computer Science and Technology，University of Science and Technology of China，Hefei 230027，China)

Differential evolution algorithms have gradually become one of the most popular types of stochastic search algorithms in the area of evolutionary computation.They have been successfully applied to solve various problems in real－world applications.Since their performance often depends heavily on the parameter settings，the design of parameter control and adaptation strategies is one of the current hot topics of research in differential evolution.Although numerous parameter control schemes have been proposed，systematic overviews and analysis are still lacking.In this paper，first the basic principles and operations of the differential evolution algorithm were briefly introduced，and then a detailed overview was provided on different parameter control and adaptation strategies by dividing them into the following four classes:empirical parameter settings，randomized parameter adaptation strategies，randomized parameter adaptation strategies with statistical learning，and parameter self－adaptation strategies.The overview emphasized the latter two classes.To study the efficacy of these parameter control and adaptation strategies，experiments with the background of real－valued function optimization were conducted to compare their efficiency and practicability further.The results showed that the parameter self－adaptation is one of the most effective strategies so far.

evolutionary computation;differential evolution;parameter control;adaptation strategies;self－adaptation

TP18;O224

A

1673－4785(2011)05－0415－09

10.3969/j.issn.1673－4785.2011.05.005

2010－11－02.

海外及港澳學(xué)者合作研究基金資助項(xiàng)目(61028009).

唐珂.E－mail:ketang@ustc.edu.cn.