多子群多策略差分進(jìn)化算法

高媛，姜志俠，劉宇寧

（1.長(zhǎng)春理工大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，長(zhǎng)春 130022；2.中電金信軟件有限公司，北京 100192）

差分進(jìn)化算法（Differential Evolution，DE）是由Storn等人在1995年為解決Chebyshev多項(xiàng)式問題所提出的，現(xiàn)在已經(jīng)成為解決復(fù)雜優(yōu)化問題的常用方法［1-2］。DE算法是一種結(jié)構(gòu)簡(jiǎn)單、魯棒性強(qiáng)的全局搜索算法，在物流調(diào)度［3］、運(yùn)動(dòng)目標(biāo)檢測(cè)［4］、成本控制［5］、數(shù)據(jù)挖掘［6］等許多領(lǐng)域得到了廣泛的應(yīng)用。

差分進(jìn)化算法主要由變異、交叉、選擇和邊界條件處理幾步組成。經(jīng)過幾十年的發(fā)展，眾多基于標(biāo)準(zhǔn)DE算法的改進(jìn)算法被提出。Brest J［7］為每個(gè)個(gè)體設(shè)置了可以自動(dòng)調(diào)整的控制參數(shù)，提出了jDE算法。Qin等人［8］運(yùn)用個(gè)體之間的迭代經(jīng)驗(yàn)來自適應(yīng)調(diào)整參數(shù)和變異策略，提出了自適應(yīng)差分進(jìn)化算法（SaDE），提高了算法的收斂速度。為了完善差分進(jìn)化算法在解決高維優(yōu)化問題時(shí)存在的缺陷，張錦華等人［9］結(jié)合了DE-rand-1和DE-best-1的優(yōu)點(diǎn)，并將其加權(quán)組合，提出了WMDDE算法。陳穎潔等人［10］提出了一種以優(yōu)秀個(gè)體為導(dǎo)向的多策略差分算法，該算法將種群等分為三個(gè)子種群，根據(jù)每個(gè)部分不同的特點(diǎn)，采取了不同的變異策略。

本文首先將種群按照適應(yīng)度值從小到大排列，并將其按一定比例分為三個(gè)子種群，針對(duì)每個(gè)子種群不同的搜索能力構(gòu)建不同的變異策略，設(shè)置不同的控制參數(shù)。針對(duì)第一個(gè)適應(yīng)度值較好的子種群，使用DE-best-2變異策略，提高種群收斂速度和搜索能力。針對(duì)第二個(gè)適應(yīng)度值中等的子種群提出了一種基于優(yōu)秀個(gè)體的DE-rand-1 to DE-best-1變異策略，這有利于平衡種群的全局搜索和局部搜索能力。針對(duì)第三個(gè)適應(yīng)度值較差的子種群提出了一種引入學(xué)習(xí)參數(shù)和均衡參數(shù)的組合變異策略，以此降低種群陷入停滯狀態(tài)的概率，保持算法的穩(wěn)定性。

1 標(biāo)準(zhǔn)DE算法

DE算法作為一種進(jìn)化類算法，結(jié)構(gòu)中包含了變異、交叉、選擇三種進(jìn)化操作。設(shè)DE算法的第t代種群由NP個(gè)維數(shù)為D的實(shí)數(shù)值參數(shù)向量組成，第i個(gè)個(gè)體表示為：xi(t)(i=1,2,…,NP)。

1.1 變異操作

標(biāo)準(zhǔn)DE算法采用差分策略產(chǎn)生變異向量。對(duì)于每個(gè)目標(biāo)向量xi(t)(i=1,2,…,NP)，常用的變異策略如下：

1.2 交叉操作

交叉操作的目的在于提高種群的多樣性。標(biāo)準(zhǔn)DE算法的交叉操作如下：

其中，j=1,2,…,D；jrand為[1 ,2,…,D]之間的隨機(jī)數(shù)，來確保交叉?zhèn)€體至少有一個(gè)分量會(huì)與目標(biāo)個(gè)體不同；CR稱為交叉算子，取值一般為[0 ,1]內(nèi)的實(shí)數(shù)。

1.3 選擇操作

選擇操作在目標(biāo)個(gè)體及交叉?zhèn)€體之間進(jìn)行，通過優(yōu)勝劣汰的競(jìng)爭(zhēng)法則，選取其中更加適應(yīng)環(huán)境的個(gè)體進(jìn)入子代繼續(xù)繁衍，使種群向最優(yōu)解的方向進(jìn)化。其迭代公式如下：

2 多子群多策略DE算法

下面提出一種多子群多策略DE算法，記為“改進(jìn)DE”算法。

2.1 初始化種群

根據(jù)問題需要，確定種群個(gè)數(shù)NP及個(gè)體維數(shù)D，按下式隨機(jī)生成的初始種群(t=0)：

其中，xmax(t)，xmin(t)表示取值區(qū)間的最大值和最小值；rand(0 ,1)是在區(qū)間[0 ,1]上的隨機(jī)數(shù)。

設(shè)計(jì)“改進(jìn)DE”算法的關(guān)鍵問題是如何劃分種群、選擇變異策略和設(shè)置參數(shù)?！案倪M(jìn)DE”算法針對(duì)每個(gè)子種群不同的搜索能力構(gòu)建不同的變異策略、設(shè)置不同的控制參數(shù)，使得各子種群具備不同的搜索能力，體現(xiàn)不同的作用，保持整個(gè)種群的搜索和開采能力。本文根據(jù)適應(yīng)度值從小到大的排序?qū)⒎N群分為三個(gè)子種群，選取前10%個(gè)體作為第一個(gè)子種群即優(yōu)秀種群，第二、第三個(gè)子種群根據(jù)經(jīng)驗(yàn)分別選擇40%和50%。

2.2 第一個(gè)子種群X1（優(yōu)秀種群）

針對(duì)第一個(gè)子種群X1（優(yōu)秀種群），考慮到個(gè)體適應(yīng)度值較好，為了提高種群的收斂速度并且增加種群的搜索能力，不使種群陷入停滯的狀態(tài)，同時(shí)也能夠維持整個(gè)種群的平衡狀態(tài)，采用了開采能力較強(qiáng)的DE-best-2變異策略：

其中，xbest為種群當(dāng)前的最優(yōu)個(gè)體；xr1(t)，xr2(t)，xr3(t)，xr4(t)為子種群X1中隨機(jī)選取的四個(gè)不同個(gè)體。該策略具有較強(qiáng)的局部尋優(yōu)能力，可以在子種群X1中選擇更接近最優(yōu)解的解。在第一個(gè)子種群中F設(shè)為0.9可增加差分向量的擾動(dòng)程度，有利于增強(qiáng)算法的搜索能力，CR設(shè)為0.1，是因?yàn)榈谝粋€(gè)子群X1本身就為優(yōu)秀種群。考慮到交叉算子CR可以控制種群中試驗(yàn)個(gè)體的多樣性，較大的CR值使得試驗(yàn)個(gè)體更多地繼承變異個(gè)體的性質(zhì)，這樣可以使種群增強(qiáng)搜索能力；相反，變異算子CR值越小，試驗(yàn)向量改變?cè)叫?，有助于種群保持多樣性。

2.3 第二個(gè)子種群X2

DE-best-1因包含全局最優(yōu)個(gè)體，局部尋優(yōu)能力突出，適合求解單峰類型的問題；而DE-rand-1包含的個(gè)體均為隨機(jī)選擇，使得該策略的全局搜索能力突出，適合求解多峰類型的問題。因此對(duì)于適應(yīng)度值中等的子種群X2來說，參考文獻(xiàn)［10］引入學(xué)習(xí)參數(shù)μ(xi(t))構(gòu)造一種新的加權(quán)變異策略，用來平衡子種群X2的全局搜索能力和局部開發(fā)能力。

學(xué)習(xí)參數(shù)定義如下：

其中，t是當(dāng)前迭代次數(shù)；f(xi(t))為個(gè)體xi(t)的適應(yīng)度函數(shù)值；f(x(t))min和f(x(t))max表示種群在當(dāng)前代數(shù)t中個(gè)體適應(yīng)度值的最大值和最小值。μ(xi(t))為單調(diào)遞增函數(shù)，隨著適應(yīng)度函數(shù)值f(xi(t))的增大而增大。設(shè)種群規(guī)模NP=100，維數(shù)D=50，F(xiàn)=0.6，CR=0.9，以函數(shù)f1為例，其中f1的表達(dá)式為：

圖1更加直觀地展示出函數(shù)f1的學(xué)習(xí)參數(shù)μ(xi(t))在第一次迭代中的變化曲線。

圖1 種群X2中 μ(x i(t))的變化曲線

定義引入學(xué)習(xí)參數(shù)的加權(quán)變異策略DE-rand-1 to DE-best-1：

其中，xr1，xr2，xr3，xr4，xr5為X2中隨機(jī)選取的不同個(gè)體；μ(xi(t))為單調(diào)遞增函數(shù)，隨著適應(yīng)度函數(shù)值f(xi(t))的增大而增大。

可知構(gòu)造的變異策略在前期，主要進(jìn)行全局搜索，隨著μ(xi(t))的遞增，后期主要以在xbest附近進(jìn)行局部開發(fā)，其中rand(0 ,1)用來隨機(jī)調(diào)整算法的進(jìn)化方向，引導(dǎo)個(gè)體朝著最優(yōu)值靠近，從而提高種群多樣性，避免DE算法停滯和過早收斂的情況。

2.4 第三個(gè)子種群X3

在變異策略中，種群的多樣性在很大程度上與所選取的搜索中心有關(guān)，也就是圍繞著哪個(gè)個(gè)體進(jìn)行差分進(jìn)化，稱這個(gè)個(gè)體為基向量。設(shè)當(dāng)前迭代次數(shù)為t，對(duì)個(gè)體xi(t)參考文獻(xiàn)［10］定義均衡參數(shù)EP(xi(t))和系數(shù)at：

其中，xx1,best是在優(yōu)秀種群中隨機(jī)選取的個(gè)體，Tmax是最大迭代次數(shù)，隨著進(jìn)化的推進(jìn)，由式（6）可以看出系數(shù)at的值是在逐漸增大。

μ(xi(t))，EP(xi(t))，1-EP(xi(t))為f(xi(t))的單調(diào)函數(shù)，即當(dāng)個(gè)體適應(yīng)度值越大時(shí)，μ(xi(t))和EP(xi(t))的值越大，而相應(yīng)1-EP(xi(t))的值越小。

對(duì)于子種群X3中的個(gè)體xi(t)，當(dāng)其適應(yīng)度值越大時(shí)，其向優(yōu)秀種群中個(gè)體的學(xué)習(xí)能力就需越強(qiáng)，因此用學(xué)習(xí)參數(shù)μ(xi(t))來增強(qiáng)其向優(yōu)秀個(gè)體的學(xué)習(xí)能力，引入呈遞減趨勢(shì)的均衡參數(shù)1-EP(xi(t))是為避免其收斂過快，陷入局部最優(yōu)的狀態(tài)。而1-μ(xi(t))的作用則是當(dāng)其適應(yīng)度值越小時(shí)，子種群X3中個(gè)體越需要降低其向優(yōu)秀種群中個(gè)體的學(xué)習(xí)能力。為了避免子種群X3中個(gè)體因適應(yīng)度值較差而向優(yōu)秀種群學(xué)習(xí)能力過大的情況，引入呈遞減趨勢(shì)的均衡參數(shù)EP(xi(t))來對(duì)其自身進(jìn)行平衡。

仍以函數(shù)f1為例，圖2更加直觀地展示出第三個(gè)子種群在第一次迭代中均衡參數(shù)EP(xi(t))隨著個(gè)體的變化而上升的變化曲線。

圖2 種群X3中EP(x i(t))的變化曲線

選取以下變異策略：

其中，xbest是當(dāng)前迭代的全局最優(yōu)值；xr1(t)，xr2(t)，xr3(t)是在子種群X3中隨機(jī)選取的三個(gè)個(gè)體。這里randnormal是指以u(píng)i(t)為均值，0.1為方差的正態(tài)分布形成的個(gè)體。randnormal的目的為探索周圍鄰域存在的有潛力解，相比于文獻(xiàn)［10］中的柯西分布，考慮到正態(tài)分布比柯西分布在峰值附近的取值概率更大，接近最優(yōu)值的概率更多，因此引入正態(tài)分布保證了以較大的概率生成均值的控制參數(shù)值，同時(shí)不丟失隨機(jī)性，保證了種群的多樣性。實(shí)驗(yàn)結(jié)果表明正態(tài)分布在變異策略中可以起到較好的效果。對(duì)于變異策略中差分向量采取隨機(jī)的機(jī)制，從而在基向量的基礎(chǔ)上向周圍尋優(yōu)。對(duì)于適應(yīng)度越差的子種群X3中的個(gè)體，為了避免整個(gè)種群陷入局部最優(yōu)狀態(tài)從而引入均衡參數(shù)，其目的在于當(dāng)它向優(yōu)秀的個(gè)體學(xué)習(xí)的學(xué)習(xí)參數(shù)較大時(shí)，減緩向優(yōu)秀的個(gè)體學(xué)習(xí)的速度。當(dāng)它向優(yōu)秀個(gè)體學(xué)習(xí)參數(shù)較小時(shí)，變異向量個(gè)體側(cè)重在個(gè)體自身與差分向量的組合基礎(chǔ)上產(chǎn)生，因此CR取0.9有利于維持種群的多樣性。

2.5 算法流程

通過對(duì)不同的子種群使用不同的變異策略和控制參數(shù)的選取，使得不同的變異策略和參數(shù)在種群的進(jìn)化過程中所發(fā)揮的作用不同，使得各個(gè)種群之間的搜索能力能夠互補(bǔ)，最終達(dá)到平衡全局搜索能力和局部搜索能力的作用。算法流程如圖3所示。

圖3 算法流程圖

3 數(shù)值實(shí)驗(yàn)

針對(duì)提出的“改進(jìn)DE”算法，選取8個(gè)經(jīng)典的測(cè)試函數(shù)對(duì)算法的性能進(jìn)行測(cè)試，函數(shù)全局最優(yōu)值均為0。8個(gè)測(cè)試函數(shù)表達(dá)式如表1所示。

表1 測(cè)試函數(shù)

用以上提到的常見的四種差分變異策略DE-best-1、DE-rand-1、DE-best-2、DE-current-tobest-2與“改進(jìn)DE”算法計(jì)算8個(gè)測(cè)試函數(shù)的最優(yōu)值，為了考察算法的綜合性能，設(shè)置種群規(guī)模NP=100，維數(shù)D=50，所有算法最大迭代次數(shù)均為1 000次。結(jié)果對(duì)比如表2所示。

表2 測(cè)試函數(shù)最優(yōu)值結(jié)果對(duì)比NP=100，D=50，Tmax=1000

五種算法對(duì)8個(gè)函數(shù)進(jìn)行測(cè)試的適應(yīng)度值的迭代曲線如圖4所示，從圖中可以看出本文所提出的“改進(jìn)DE”算法在迭代過程中所展示的良好的性能，迭代曲線下降速度較快，并且尋優(yōu)精度較高，相比于其他算法總體上尋優(yōu)能力強(qiáng)，收斂速度快。

圖4 測(cè)試函數(shù)迭代曲線

4 結(jié)論

本文在標(biāo)準(zhǔn)DE算法的基礎(chǔ)上，將種群按適應(yīng)度值從小到大排列并按一定比例分為三個(gè)子種群，針對(duì)不同子種群采用了不同的變異策略，進(jìn)而使不同的變異策略在不同子種群進(jìn)化過程中發(fā)揮不同的作用。

第一個(gè)子種群采用標(biāo)準(zhǔn)DE算法中DE-best-2變異策略，該策略具有較強(qiáng)的局部尋優(yōu)能力。針對(duì)第二個(gè)適應(yīng)度值中等的子種群引入學(xué)習(xí)參數(shù)，結(jié)合DE-rand-1和DE-best-1變異策略的各自優(yōu)點(diǎn)，提出了一種新的變異策略DE-rand-1 to DE-best-1，該變異策略通過學(xué)習(xí)參數(shù)在全局搜索和局部搜索之間建立一種平衡。針對(duì)第三個(gè)適應(yīng)度值較差的子種群提出了一種引入學(xué)習(xí)參數(shù)和均衡參數(shù)的組合變異策略，使其能夠更加平衡的向優(yōu)秀種群中的個(gè)體進(jìn)行學(xué)習(xí)，以此降低種群陷入停滯狀態(tài)的概率，保持算法的穩(wěn)定性并達(dá)到更優(yōu)的狀態(tài)。通過8個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果可得出，“改進(jìn)DE”算法在大多數(shù)函數(shù)上的尋優(yōu)能力和收斂速度上都有了一定的提升，并具有較強(qiáng)的穩(wěn)定性。