張 強,鄒德旋,耿 娜,沈 鑫

(1.江蘇師范大學 電氣工程及自動化學院,江蘇 徐州 221116; 2.徐州開放大學 信息技術與電氣工程學院,江蘇 徐州 221000)(*通信作者電子郵箱uqaing@outlook.com)

0 引言

啟發(fā)式優(yōu)化算法本質上是隨機性算法,它利用各種隨機尋優(yōu)策略來獲得不同優(yōu)化問題的最優(yōu)解。 在實踐領域,很多需要優(yōu)化的目標函數(shù)是不連續(xù)的或者不可微的,傳統(tǒng)的數(shù)學優(yōu)化方法針對這種情況無法找到較好的解決辦法,而啟發(fā)式優(yōu)化算法不需要目標函數(shù)的連續(xù)性和可微性,這就為該算法提供了更廣闊的應用空間。 近年來研究人員對啟發(fā)式優(yōu)化算法的性質進行了研究和分析。到目前為止,已經出現(xiàn)了大量的啟發(fā)式優(yōu)化算法,如遺傳算法(Genetic Algorithm, GA)[1]、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[2-3]、模擬退火算法(Simulated Annealing Algorithm, SAA)[4]、蟻群優(yōu)化(Ant Colony Optimization, ACO)算法[5]等。這些計算技術已經被成功地應用于許多實際的優(yōu)化問題[6-9],在求解最優(yōu)值的過程中發(fā)揮了重要的作用。

在這些優(yōu)化算法中，差分進化(Differential Evolution, DE)算法[10]于1995年由Storn和Price提出,它是一種隨機的、并行直接尋優(yōu)的優(yōu)化算法。該方法因具有簡單、易實現(xiàn)、魯棒性強等多種優(yōu)點,被廣泛和成功的應用于函數(shù)優(yōu)化、多目標優(yōu)化、背包問題、生產調度及其他工程領域。對于進化算法而言,控制參數(shù)是該領域研究的核心問題,DE算法也有自身的控制參數(shù)。經典的DE算法有3個控制參數(shù):1)種群個數(shù)Np;2)變異縮放因子F;3)交叉概率因子CR。相對于其他控制參數(shù)而言,Np的變化相對具有普遍性,所以DE算法對于F、CR兩個參數(shù)的設置更敏感,也是DE算法改進的方向。另外,變異策略對差分進化算法的性能也有很大的影響。本文將從變異策略和參數(shù)F、CR的設置為切入點對DE算法進行改進。

1 經典DE算法

DE算法是一種基于群體進化的自組織最小化方法,它的主要思想是引入一種可利用當前群體中的個體差異來構造變異個體的差分變異模式。相對于傳統(tǒng)進化算法,差分變異模式是DE算法中最為獨特的進化操作。以下簡單地介紹經典DE算法的進化過程。

步驟1 種群初始化。

DE算法采用隨機方式進行種群初始化,由下面公式產生:

xi, j=xi_min+(xi_max-xi_min)×rand

(1)

其中:rand表示[0,1]內均勻分布的隨機數(shù)；xi_max、xi_min分別表示每一個向量粒子的每一維分量的上界和下界;i=1,2,…,Np;j=1,2,…，Nd;Np表示種群(向量)個數(shù);Nd表示向量粒子的維度。

步驟2 變異操作。

對給定的當前群體,每一個新變異向量粒子由式(2)產生:

(2)

步驟3 交叉。

(3)

其中:r1～Nd是在區(qū)間[1,Nd]中的一個隨機整數(shù);CR的取值區(qū)間為[0,1]。

步驟4 選擇。

(4)

步驟5 判別結束。

如果取得理論最優(yōu)值或者達到最大迭代次數(shù)Ni,則計算結束；否則重復步驟3和步驟4。

2 影響差分進化算法性能的因素

差分進化算法尋優(yōu)速度和尋優(yōu)范圍存在著相互制約的關系。如果單方面提高尋優(yōu)速度,雖然能快速得到最優(yōu)解,但是有可能會陷入局部最優(yōu),降低穩(wěn)定性；反之,如果單方面擴大尋優(yōu)范圍,雖然有利于種群的多樣性,防止陷入局部最優(yōu),提高算法的穩(wěn)定性,但是這勢必會影響其尋優(yōu)速度。通常從變異策略和參數(shù)設置兩個方面來解決這個矛盾。

2.1 變異策略

為了提高尋優(yōu)的成功率,除了經典的變異策略外,研究者還提出了其他的變種形式。

1)DE/ rand/1/bin:

(5)

2)DE/rand/2/bin:

(6)

3)DE/best/1/bin:

(7)

4)DE/best/2/bin:

(8)

5)DE/current-to-best/1/bin:

(9)

2.2 參數(shù)設置

這里的參數(shù)主要是針對F、CR。其中F對算法的局部尋優(yōu)和全局尋優(yōu)起到一定影響：當F較大時有利于提高種群多樣性和提升全局尋優(yōu)能力;當F較小時有利于提高尋優(yōu)速度和提升局部尋優(yōu)能力。而CR是一個閾值,用來決定經過變異的向量粒子能夠進入下一步選擇操作的數(shù)量：CR增大有利于擴大尋優(yōu)范圍,但會降低尋優(yōu)速度；CR減小會縮小尋優(yōu)范圍,但會提高尋優(yōu)速度。

從以上分析中可以發(fā)現(xiàn),很難找到一種策略和一種參數(shù)設置能夠完全解決所有的問題。國內外很多學者對DE算法進行了大量的改進,主要聚焦在三個方面:一是對參數(shù)的選取機制的研究[11];二是對差分變異策略的研究,將經典差分進化算法的變異策略串行組合,提出多變異策略差分進化算法[12-13];三是將DE算法與其他算法組成混合算法[14-16]。學者們的改進不同程度地提升了DE算法的尋優(yōu)性能,但是改進后的算法依然存在尋優(yōu)精度不高、對不同函數(shù)魯棒性不好等問題。

與此同時,雖然有些學者也提出在DE算法改進中加入學習功能,但是單純的參數(shù)學習就是總結上一次迭代中獲勝的向量粒子所用的各種參數(shù),將這些參數(shù)直接或間接地用于本次迭代中。經仿真測試表明，這種具有學習能力的改進,可以大幅提高算法的尋優(yōu)能力；但是對于另外一些函數(shù),特別是多峰函數(shù),存在容易出現(xiàn)局部最優(yōu)的問題。這是因為在學習的過程中無法確認被學習的對象本身(即上一次迭代獲勝的向量粒子)是否已經向局部最優(yōu)值收斂。從另一個側面也說明,由于差分算法本質是隨機算法的一種,過多人為干預就會喪失或者減弱其原有的特質。這也可以理解為人為干預有利于提高尋優(yōu)速度,隨機尋優(yōu)有利于擴大尋優(yōu)范圍。為此,本文提出一種基于多變異策略的自適應差分進化(Adaptive Differential Evolution based on Multi-Mutation strategy, ADE-MM)算法。對于多種變異策略的選擇,采取的方法是根據(jù)學習結果設置擾動閾值,并根據(jù)此閾值隨機選擇每一次迭代中使用的變異策略,因此在學習的過程中又適量地加入擾動因素,做到了有序尋優(yōu)和隨機尋優(yōu)上的最優(yōu)結合。

3 ADE-MM算法的改進方法

3.1 變異策略

在ADE-MM算法中共用到三種變異策略:

策略一

(10)

策略二

(11)

策略三

(12)

(13)

其中:Np是向量粒子種群個數(shù);Ni是設定的最大迭代次數(shù);k代表當前迭代次數(shù);θ取1.5。根據(jù)此公式繪制變化曲線,如圖1所示,隨著迭代次數(shù)的增加,p值逐漸減小。

圖1 式(13)函數(shù)曲線Fig. 1 Formula (13) function curve

結合策略二的變異交叉方式可以看出,當?shù)_始時,種群向量粒子的優(yōu)劣不明顯,對于精英粒子來說數(shù)量比質量更重要,因此需要p取較大的值來獲得較大的尋優(yōu)范圍。但是隨著尋優(yōu)過程的運行,向量粒子的優(yōu)劣越來越明顯,對于精英粒子來說質量反而比數(shù)量更重要,需要排名更靠前的粒子來進行局部最優(yōu)搜索,所以p先大后小。關于三個策略的選擇問題,本文中ADE-MM算法引入兩個干擾變量B1、B2作為擾動閾值,在一定范圍內隨機選擇,其關系式如下:

(14)

其中：rand1、rand2分別是[0,1]區(qū)間內兩組均勻分布的隨機數(shù)。關于B1、B2的取值問題,將在后面討論。

3.2 學習參數(shù)說明

3.2.1 B1和B2設置

(15)

(16)

3.2.2F參數(shù)設置

(17)

(18)

(19)

3.2.3CR參數(shù)設置

CR與F采用的方法基本一致,分別用式(20)～(22)取得:

(20)

(21)

(22)

(23)

(24)

(25)

(26)

圖2 式(25)函數(shù)曲線Fig. 2 Formula (25) function curve

3.2.4 其他改進

(27)

(28)

表1 測試函數(shù)Tab. 1 Test functions

3.3 算法實現(xiàn)過程

步驟1 參數(shù)設置。設置迭代次數(shù)Ni;種群規(guī)模Np;向量維度Nd;F∈[0.1,0.8];Fsi=0.5;δFi=0.1;CR∈[0.3,1];CRsi=0.6;δCRi=0.1;B1∈[0.9,1];B2∈[0.5,0.6];q=1.5;n=1.5;θ=1.5。

步驟3 變異操作。根據(jù)式(14)進行變異操作。如果變異后的向量粒子超出種群設定范圍,則重新隨機生成這些向量粒子,直至所有種群都在取值范圍內。

步驟4 交叉操作。參照式(3)。

步驟5 選擇操作。參照式(4)。

步驟6 生成下一代參數(shù)。根據(jù)選擇操作中的比較結果,找出獲勝的向量粒子,按照式(15)～(26)產生新的參數(shù),按照式(27)產生向量粒子池,按照式(28)生成用于下一次迭代的中心粒子,并將其加入到下一次迭代的向量粒子群x中。

步驟7 終止判斷。當?shù)_到最大次數(shù),或者已經尋優(yōu)出最優(yōu)值時,算法結束；否則返回步驟3。

3.4 函數(shù)與仿真參數(shù)設置

為了驗證ADE-MM算法的性能,本文選用了8個函數(shù)來進行測試。其中：f1～f3是單峰函數(shù),f4～f7是多峰函數(shù),f8是帶有平移坐標的函數(shù)。這些函數(shù)的定義見表1。

此外,為了驗證ADE-MM算法在求解無約束優(yōu)化問題上的優(yōu)勢,將其與隨機變異差分進化(Random Mutation Differential Evolution, RMDE)算法[19]、OLCPDE算法以及經典改進算法JADE(Adaptive Differential Evolution with Optional External Archive)[20]、SaDE(Self-adaptive Differential Evolution)[21]、MDE_pBX(Modified Differential Evolution with p-best Crossover)[22]進行比較。根據(jù)各種算法在參考文獻內的描述,將參數(shù)設置如下。

1)RMDE中,縮放因子F=0.5;交叉概率CR=0.3;擾動因子p=0.9。

2)OLCPDE中,縮放因子F=0.5;交叉概率CR=0.8。

3)JADE中,縮放因子F柯西分布的位置參數(shù)和尺度參數(shù)分別為μF=0.5和δF=0.1;交叉概率CR正態(tài)分布的均值和標準差分別μCR=0.5和δCR=0.1;積極的常數(shù)c=1;百分比p%=5%。

4)SaDE中,縮放因子F正態(tài)分布的均值和標準差分別μF=0.5和δF=0.3;交叉概率CR正態(tài)分布的均值和標準差分別μCR=0.5;δCR=0.1;LP=50;p=0.25。

5)MDE_pBx中,縮放因子F柯西分布的位置參數(shù)和尺度參數(shù)分別為μF=0.5和δF=0.1;交叉概率CR正態(tài)分布的均值和標準差分別μCR=0.5和δCR=0.1;q=0.15;n=1.5。

由于學習功能需要對上一代向量粒子進行統(tǒng)計,隨著測試維度的增加,向量粒子的個數(shù)也應增加以獲得更好的學習效果。為了公平起見,針對30維、50維和100維的問題,對于每個測試算法的種群規(guī)模Np均分別設置為100、160、300,迭代次數(shù)為2 000,獨立運行30次。從均值、標準差、Wilcoxon ranksum test、勝率以及算法耗時5個方面來進行分析比較。本文中除Wilcoxon ranksum test利用R語言分析外,其余仿真實驗均在Matlab R2016b中進行,內存8 GB,CPU速度為2.4 GHz。

表2 ADE-MM算法與其他算法的均值與標準差計算數(shù)據(jù)比較Tab. 2 Average and standard variance comparison of ADE-MM and other algorithms

4 仿真實驗與數(shù)據(jù)分析

4.1 均值與標準差分析

表2顯示了函數(shù)的均值和標準差分別在30維、50維、100維三種的情況下的對比結果。從表2中可以發(fā)現(xiàn),ADE-MM算法取得全勝,其中包括5個函數(shù)的單獨勝利(f1、f2、f3、f6、f8),3個函數(shù)的并列勝利(f4、f5、f7)。為了說明ADE-MM算法在并列勝利的情況下仍具有優(yōu)勢,把這3個函數(shù)均值的迭代過程繪制成圖3。從圖3可以發(fā)現(xiàn),ADE-MM算法在同時都獲得最優(yōu)值的情況下,尋優(yōu)速度優(yōu)于其他算法,使用更少的迭代次數(shù),更早地獲得最優(yōu)值。在函數(shù)為50維的情況下,ADE-MM算法取得全勝,其中包括6個函數(shù)的單獨勝利(f1、f2、f3、f5、f6、f8),2個函數(shù)的并列勝利(f4、f7)。如圖4所示,同樣在并列取勝的情況下ADE-MM算法尋優(yōu)速度要快于其他對比算法。同時在30維的情況下對f4、f5和f7的測試中,與ADE-MM算法并列取勝的對比算法個數(shù)分別為4、1和2,而在50維的情況下,變?yōu)?、0和3。必須承認,在50維的情況下對f7的測試中并列取勝的對比算法比在30維的情況下多了1個。而在函數(shù)為100維的情況下,ADE-MM算法取得全勝,且為單獨勝利。因此,總體趨勢是隨著維度的增加,與ADE-MM算法并列取勝的測試函數(shù)個數(shù)和對比算法個數(shù)均在漸減少,甚至消失。這說明隨著函數(shù)維度的增加、難度的提高, ADE-MM算法在均值和標準差的比較中的優(yōu)勢更加突顯。

圖3 ADE-MM算法與其他算法在函數(shù) f4、 f5、 f7的收斂曲線(Nd=30)Fig. 3 Convergence curves of ADE-MM and other algorithms in functions f4, f5, f7(Nd=30)

圖4 ADE-MM算法與其他算法在函數(shù) f4、 f7的收斂曲線(Nd=50)Fig. 4 Convergence curves of ADE-MM andother algorithms in functions f4, f7(Nd=50)

4.2 Wilcoxon rank sum test分析

下面利用Wilcoxon rank sum test[23-24]對仿真數(shù)據(jù)進行分析,確定6種算法中的最優(yōu)算法與其他對比算法是否具有統(tǒng)計學意義上的差異。針對每一個函數(shù)取出6種算法中均值最優(yōu)解的算法,取其每次尋優(yōu)結果中最優(yōu)解構成由30個元素組成的基量,同理取其他5種算法每次尋優(yōu)結果中各自最優(yōu)解分別構造出5個向量,然后分別與基量進行Wilcoxon rank sum test比較,從中可以獲得p-value值。如果得到的p-value小于0.05,說明此算法與最優(yōu)算法有明顯差距;如果得到的p-value大于0.05,則說明此算法與最優(yōu)算法差距不明顯。 需要說明三點:第一，均值最優(yōu)解相同的,利用標準差的比較結果來確定基量。如果均值和標準差都一樣,任選一個最優(yōu)值作為基量,此選擇方式不影響最終比較結果。因為在均值比較中ADE-MM取得了全部的勝利,所以基量均來自ADE-MM算法;第二，當兩個對比向量相同,且每個向量內元素也相同時, p-value得NaN,需說明的是由于Matlab和R語言的有效值精度問題,此結果無法與之前標準差對應,但不影響p-value實驗分析結果;當兩個對比向量相同,但每個向量內元素不同時, p-value等于1。以上兩個種情況均認為兩個對比向量是無差別的。第三， p-value值可以表示最優(yōu)算法與其他對比算法測試結果存在著“明顯區(qū)別”和“不明顯區(qū)別”兩種情況,但不能根據(jù)p-value值的大小顯示同為“明顯區(qū)別”的結果,區(qū)別程度有多大,也不能根據(jù)p-value值的大小顯示同為“不明顯區(qū)別”的結果,區(qū)別程度有多大。從表3中可以發(fā)現(xiàn),在單峰測試函數(shù)f1、f2、f3中ADE-MM算法在3種維度情況下的p-value值均為1,而其他對比算法的p-value值沒有出現(xiàn)一個大于0.05,說明此情況下ADE-MM算法不僅在比較中獲勝,而且優(yōu)勢明顯。在多峰測試函數(shù)f4、f5、f6、f7和平移測試函數(shù)f8中,從30維的情況到100維的情況的測試中,ADE-MM算法的p-value值全部等于1或者取NaN,而對比算法的p-value值大于0.05、等于1和取NaN的情況在逐漸減少。說明隨著維度的增加,能夠接近或等于ADE-MM算法的尋優(yōu)結果的算法越來越少,甚至沒有。這進一步體現(xiàn)了ADE-MM算法的優(yōu)勢,特別是解決高維問題時更明顯。

4.3 勝率分析

為了展示最優(yōu)算法與其他對比算法的區(qū)別程度,引入勝率進行比較。關于勝率比較作出如下解釋:在同一個函數(shù)中,分別取ADE-MM算法的30次尋優(yōu)結果中的每一次數(shù)值與其他5種算法的30次尋優(yōu)結果的每一次數(shù)值輪流進行比較,共計進行30×5×30=4 500次,每次比較獲勝的一方加1分,結果一樣就各加0.5分,輸?shù)囊环讲患臃?最后用獲勝次數(shù)除以比較次數(shù)得到勝率,如果勝率超過50%,說明ADE-MM算法在勝率比較中勝出。

表3 最優(yōu)算法與其他算法的p-value計算結果Tab. 3 p-value calculation results of the optimal algorithm and other algorithms

表4 ADE-MM算法與其他算法的勝率計算結果 %Tab. 4 Winning rate calculation results of ADE-MM over other algorithms %

表4中顯示的是30維、50維和100維勝率的結果。下面以30維為例,結合均值和p-value值來進行分析。如前文所述,在30維的測試中ADE-MM算法獲得全勝,但是從勝率比較中卻發(fā)現(xiàn),在函數(shù)f2、f8中ADE-MM算法分別輸給了JADE、SaDE。下面將以函數(shù)f2為例說明出現(xiàn)這種情況的原因。如表5所示,在30維的測試中,JADE算法30次的尋優(yōu)值大部分優(yōu)于ADE-MM算法,但是存在3個比較差的尋優(yōu)結果,最優(yōu)值和最差值之間有1018量級的差距,這三個較差的尋優(yōu)結果最終影響了JADE算法的均值。反觀ADE-MM算法的30次尋優(yōu)結果,最優(yōu)值和最差值之間只有104量級的差距,遠遠低于JADE的浮動范圍,相對穩(wěn)定,且其最差值比JADE算法的最差值小了106量級。這就解釋了為什么ADE-MM算法在對f2、f8測試中,均值比較可以獲勝,而勝率比較卻失敗的原因。通常優(yōu)化算法的優(yōu)秀性不僅體現(xiàn)在尋優(yōu)精度和尋優(yōu)速度上,尋優(yōu)穩(wěn)定性也是重要的衡量指標。這也從另一個側面顯示了ADE-MM算法的優(yōu)秀性。在100維的勝率比較中,ADE-MM算法在和其他5個對比算法的勝率對比結果均達到或接近100%,此結果與前面均值、標準差和Wilcoxon rank sum test分析結果一致,再次說明ADE-MM算法在解決高維度問題時性能優(yōu)異。

5 算法耗時分析

由于算法耗時普遍會隨著函數(shù)維度的增加而同步增加,所以只選取函數(shù)為30維的情況來比較各種算法的平均耗時。從表6可以發(fā)現(xiàn),ADE-MM算法對f6和f7兩個函數(shù)測試用時最少。根據(jù)對表2中均值對比,在函數(shù)f7的測試中ADE-MM和JADE、SaDE共3種算法同時取得理論最優(yōu)值0,提前結束迭代。由此可知，在沒有獲得理論最優(yōu)值的情況下,運行2 000代ADE-MM算法整體運行時間不是最少的,但是在獲得理論最優(yōu)值可以提前結束迭代的情況下,ADE-MM算法整體用時最少。這說明雖然ADE-MM算法的單次迭代時間不是最短的, 但可以使用更少的迭代次數(shù)完成尋優(yōu)過程。另外,從表6中還可以發(fā)現(xiàn),在8個函數(shù)中相比其他對比算法,ADE-MM算法均不是耗時最多的一個。

6 結語

在對差分進化算法改進中,提高尋優(yōu)速度和擴大尋優(yōu)范圍是一對相對制約的關系,本文提出的ADE-MM算法通過對前一代向量粒子尋優(yōu)性能的判斷與學習來決定下一次迭代中所用到的變異策略和參數(shù)設置,以達到增強自適應性和提高尋優(yōu)速度、精度的目的；同時加入帶有學習功能的擾動閾值來改善學習過程,擴大尋優(yōu)范圍,防止向量粒子誤入局部最優(yōu)的陷阱,增強尋優(yōu)穩(wěn)定性。本文利用8個函數(shù)分別在30維、50維和100維的情況下進行仿真測試,并采用均值、標準差、 p-value、勝率和算法耗時5個指標對仿真結果進行分析。結果表明,ADE-MM算法無論在尋優(yōu)精度、尋優(yōu)速度還是在尋優(yōu)穩(wěn)定性上都優(yōu)于其他對比算法,特別是在解決高維問題的優(yōu)勢尤為明顯,為解決此類復雜優(yōu)化問題提供了選擇。此外,改進的DE算法已經被應用在路程規(guī)劃、電力系統(tǒng)經濟調度的優(yōu)化問題中,并且在其中加入約束處理方法,希望能更快速、準確地找到最優(yōu)的可行解。

表5 在測試函數(shù)f2下ADE-MM算法與JADE算法30次最優(yōu)解(Nd=30)Tab. 5 Thirty best solutions of ADE-MM algorithm and JADE algorithm in the test function f2(Nd=30)

表6 ADE-MM算法與其他算法平均耗時計算結果(Nd=30)Tab. 6 Average time-consuming calculation results of ADE-MM and other algorithms (Nd=30)