基于概率評估差分進(jìn)化的多峰值優(yōu)化

王子佳，詹志輝

（1.廣州大學(xué) 計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院,廣東 廣州 510006;2.華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,廣東廣州 510006）

許多實(shí)際優(yōu)化問題中具有多個全局最優(yōu)解，如蛋白質(zhì)結(jié)構(gòu)檢測[1]、電磁系統(tǒng)設(shè)計(jì)[2]、結(jié)構(gòu)優(yōu)化[3]和多行人檢測[4-6]等。例如，多行人檢測通常要求算法在一張給定的圖片中盡可能多地檢測到多個行人。此類問題被稱為多峰值優(yōu)化問題。求解多峰值優(yōu)化問題具有很多實(shí)際益處。如果能同時(shí)找到一個實(shí)際問題的多個最優(yōu)解，就能用多種方式來保持系統(tǒng)的最優(yōu)性能。當(dāng)其中某個最優(yōu)解因?yàn)閷?shí)際物理?xiàng)l件無法實(shí)現(xiàn)時(shí)，可以很快地切換到另一個最優(yōu)解。

演化算法[7-14]因其基于種群的進(jìn)化機(jī)制，擁有多個候選解，在求解多峰值優(yōu)化問題中具有潛在的優(yōu)勢。然而，傳統(tǒng)的演化算法僅僅是尋求問題的一個最優(yōu)解。為了求解多峰值優(yōu)化問題，最主流的思想便是小生境策略[15-28]，就是將整個種群劃分為多個子種群，如Crowding[15]、Speciation[16]、聚類[17-18]、Hill-valley[23]等。但是，現(xiàn)有的小生境策略對它們各自的小生境參數(shù)特別敏感，以及為了提升種群劃分的準(zhǔn)確性，算法需要采樣并評估足夠多的中間點(diǎn)，消耗了大量的適應(yīng)值評估次數(shù)(fitness evaluations,FEs)。

在我們先前發(fā)表于IEEE Transactions on Cybernetics 的研究中[29]，提出了一種自適應(yīng)分布估計(jì)的差分進(jìn)化算法(adaptive estimation distribution distributed differential evolution,AED-DDE)，算法提出了一種基于自適應(yīng)分布估計(jì)(adaptive estimation distribution，AED)的無參數(shù)小生境策略，并提出了概率局部搜索機(jī)制(probabilistic local search，PLS)來提升算法求解精度。AED-DDE 算法在多峰值優(yōu)化問題上已經(jīng)取得了很好的實(shí)驗(yàn)效果。然而，如何在極其有限的適應(yīng)值評估次數(shù)內(nèi)找到問題的多個全局最優(yōu)解，依然為AED-DDE 以及其他演化算法帶來了巨大的挑戰(zhàn)。如果可以分析個體的歷史更新經(jīng)驗(yàn)，對個體進(jìn)行選擇性評估，減少算法運(yùn)行過程中無效或低效的適應(yīng)值評估，算法性能將會得到進(jìn)一步的提高。

本文基于之前AED-DDE 的工作，進(jìn)一步提出了概率評估機(jī)制(probabilistic evaluation,PE)，并將這個機(jī)制應(yīng)用在AED-DDE 算法中，稱為PEDE。在PEDE 算法中，每個個體會通過歷史經(jīng)驗(yàn)的學(xué)習(xí)，被賦予第一層的適應(yīng)值評估概率，并根據(jù)該個體的適應(yīng)值賦予第二層的適應(yīng)值評估概率。每個個體在進(jìn)化過程中會根據(jù)該個體的雙層適應(yīng)值評估概率進(jìn)行選擇性評估。被評估的個體更新個體的適應(yīng)值，同時(shí)學(xué)習(xí)這個更新過程來調(diào)整自身的適應(yīng)值評估概率；而未被評估的個體則直接根據(jù)該個體的歷史經(jīng)驗(yàn)進(jìn)行個體更新。通過概率適應(yīng)值評估機(jī)制，可以節(jié)省FEs 來增加算法的迭代次數(shù)，從而提升算法求解精度。同時(shí)，通過概率評估機(jī)制，可以充分學(xué)習(xí)到個體的歷史經(jīng)驗(yàn)，更加方便種群的搜索。

在多峰值優(yōu)化測試集IEEE CEC 2013 上的實(shí)驗(yàn)結(jié)果顯示，相比于其他的多峰值優(yōu)化算法，PEDE算法取得了更好的實(shí)驗(yàn)結(jié)果。同時(shí)，將概率評估機(jī)制應(yīng)用到了其他基于DE 的多峰值優(yōu)化算法中，算法效果都有了一定的提升。

1 相關(guān)工作

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

差分進(jìn)化算法(differential evolution，DE)最初是由Storn 和Price 提出[30]。它通過群體內(nèi)個體之間的差異來優(yōu)化群體的搜索方向。DE 算法在進(jìn)化過程中有變異、交叉、選擇等操作，具體來說：

1)變異

在每一代中，每個個體xi稱為目標(biāo)向量，它通過變異操作產(chǎn)生它自身的變異向量vi。3 種常用的變異策略如式(1)～(3)所示：

其中，r1、r2和r3是3個不同的{1,2,…,N}中的整數(shù)(N代表種群規(guī)模)，并且都與i不同。放大系數(shù)F是一個正實(shí)數(shù)的控制參數(shù)，用來放大差分向量。xbest是指當(dāng)前種群中適應(yīng)值最好的個體。

2)交叉

在變異操作后，DE 通常會在個體xi和它自身的變異向量vi上執(zhí)行二元交叉操作，來產(chǎn)生試驗(yàn)向量ui，如式(4)所示：

其中，jrand是{1,2,…,D}中的一個隨機(jī)整數(shù)(D代表問題維度)，用來保證試驗(yàn)向量ui至少有一維不同于xi。參數(shù)CR 是交叉概率，用來決定試驗(yàn)向量ui從變異向量vi的繼承比例。

3)選擇

為了判斷試驗(yàn)向量ui是否可以進(jìn)入下一代，試驗(yàn)向量ui會與個體xi進(jìn)行比較。其中擁有較好適應(yīng)值的個體進(jìn)入下一代。例如，對于一個最大化問題來說，擁有較大適應(yīng)值的個體會進(jìn)入下一代，如式(5)所示：

其中f(x)為適應(yīng)值評估函數(shù)。

而在多數(shù)基于DE 的多峰值優(yōu)化算法中，普遍使用的選擇操作是將試驗(yàn)向量ui與距離ui最近的個體xj進(jìn)行比較，擁有較好適應(yīng)值的個體進(jìn)入下一代，如式(6)所示：

1.2 多峰值優(yōu)化算法

在求解多峰值優(yōu)化問題中，最主流的思想便是小生境策略[15-28]，就是將整個種群劃分為多個子種群，每個子種群分別去尋找該問題的一個或多個全局最優(yōu)解，如Crowding[15]、Speciation[16]、聚類[17-18]、Hill-valley[23]等。但是，現(xiàn)有的小生境策略對它們各自的小生境參數(shù)特別敏感，以及為了提升種群劃分的準(zhǔn)確性，算法需要采樣并評估足夠多的中間點(diǎn)，消耗了大量的FEs。

基于小生境策略，Zhang 等[19]提出了一種基于局部敏感哈希的小生境技術(shù)用來減小算法運(yùn)行過程中的計(jì)算復(fù)雜度。Zhao 等[20]提出了基于局部二值模式的小生境技術(shù)，并設(shè)計(jì)了一種參數(shù)自適應(yīng)的DE 算法。Chen 等[21]設(shè)計(jì)了一種基于個體的分布式框架，在每個個體周圍產(chǎn)生虛擬個體來形成小生境。Wang 等[22]設(shè)計(jì)了一種基于最小生成樹拓?fù)浣Y(jié)構(gòu)的差分進(jìn)化算法，充分捕捉個體進(jìn)化過程中的全局信息和局部信息。此外，Wang等[24]還設(shè)計(jì)了一種基于AP 聚類的無參小生境技術(shù)，在避免了小生境參數(shù)敏感度的同時(shí)，也免去了FEs 的消耗。

除了研究小生境策略，許多研究人員嘗試提出新的變異策略來提升多峰值優(yōu)化算法的性能。Biswas 等[25]提出了基于局部信息分享機(jī)制的DE算法(local information DE，LoICDE 和LoISDE)。同時(shí)，Biswas 等[26]進(jìn)一步提出了基于鄰近度和父代中心的DE 算法(parent-centric normalized mutation with proximity-based crowding DE，PNPCDE)，充分利用鄰居的進(jìn)化信息。Wang 等[27]則針對多峰值優(yōu)化問題中的選擇操作，提出了一種基于AP 聚類的概率選擇操作技術(shù)。

除了DE，還有很多演化算法用來求解多峰值優(yōu)化問題。例如，在文獻(xiàn)[31]中，基于聚類的小生境技術(shù)被應(yīng)用在了分布估計(jì)算法中，稱之為局部多峰值分布估計(jì)算法(locally multimodal estimation of distribution algorithm，LMCEDA 和LMSEDA)。

此外，也有一些研究人員通過使用多目標(biāo)轉(zhuǎn)化的方法來求解多峰值優(yōu)化問題。Wang 等[32]設(shè)計(jì)了一種獨(dú)特的轉(zhuǎn)化方式，在每個維度上都設(shè)計(jì)了兩個互相沖突的目標(biāo)，算法稱之為(multiobjective optimization for multimodal optimization problem，MOMMOP)。

1.3 AED-DDE

1.3.1 基于AED 的自適應(yīng)無參小生境技術(shù)

AED-DDE 算法提出了一種基于AED 的自適應(yīng)無參小生境技術(shù)，每個個體將找到一個適合該個體本身的小生境大小，并形成一個小生境來尋找一個全局最優(yōu)解。具體來說，每個個體xi會首先選擇距離該個體最近的3個個體來形成一個初始的小生境（個體xi的初始小生境大小Mi設(shè)置為3）。接著，算法采用高斯分布來估計(jì)該小生境的分布。小生境Ni的分布估計(jì)Di如式(7)所示:

式中：μi和σi表示小生境Ni的各維度均值和方差；xk表示小生境Ni中的第kth個個體；Mi表示小生境Ni的大小（初始化中Mi=3）。

在估計(jì)完小生境Ni的分布Di后，AED 使用范圍μi±3σi來判斷一個給定的個體是否可以被分布Di擬合。算法首先選擇距離個體xi第4th近的個體來觀察個體是否能落在范圍μi±3σi中。如果個體不能落在范圍μi±3σi中，這就意味著個體距離個體xi較遠(yuǎn)。這樣，個體應(yīng)當(dāng)被小生境Ni排除，小生境Ni應(yīng)當(dāng)保持大小Mi=3，從而避免誤導(dǎo)進(jìn)化。

算法1基于AED 的小生境技術(shù)

經(jīng)過基于AED 的小生境技術(shù)后，每個個體將找到適合該個體本身的小生境大小，從而自適應(yīng)地形成多個小生境。不同的小生境協(xié)同共進(jìn)化，執(zhí)行基本DE 算法的變異和交叉操作來得到試驗(yàn)向量，而后使用式(6)執(zhí)行選擇操作。

1.3.2 基于PLS 的局部搜索技術(shù)

為了進(jìn)一步提高解的準(zhǔn)確度，更加精確地找到問題的所有全局最優(yōu)解，算法提出了概率局部搜索技術(shù)(probabilistic local search，PLS)。

在PLS 中，算法使用了基于高斯分布的局部搜索技術(shù)，如式(8)所示:

式中：xnew是高斯分布在個體x周圍新采樣的個體；高斯分布N(x,σ)表示以個體x作為均值，σ作為標(biāo)準(zhǔn)差。標(biāo)準(zhǔn)差σ的設(shè)置如式(9)所示：

在PLS 中，算法為適應(yīng)值好的個體分配較高的局部搜索概率。首先，按照個體的適應(yīng)值對個體進(jìn)行由壞到好的排序。接著，算法設(shè)置第ith個個體執(zhí)行局部搜索的概率為

式中：ri表示第ith個個體在適應(yīng)值排序中的位置；N表示種群規(guī)模。

在執(zhí)行局部搜索操作時(shí)，每個個體在各自的周圍采樣2個點(diǎn)。完整的PLS 算法偽代碼如算法2 所示。

算法2PLS 算法

2 概率評估的差分進(jìn)化算法(PEDE)

AED-DDE 算法在多峰值優(yōu)化問題上已經(jīng)取得了很好的實(shí)驗(yàn)結(jié)果。然而，在極其有限的適應(yīng)值評估次數(shù)內(nèi)，AED-DDE 算法的性能仍然可以進(jìn)一步提高。本文提出的PEDE 算法基于之前的研究工作AED-DDE[29]，并在AED-DDE 算法的基礎(chǔ)上引入了概率評估機(jī)制。

2.1 概率評估機(jī)制PE

首先，在算法進(jìn)化過程中，AED-DDE 并沒有考慮利用個體的歷史進(jìn)化信息。例如，如果一個個體xj持續(xù)被更新，就說明產(chǎn)生的試驗(yàn)向量ui可以經(jīng)常性地替換個體xj，那么個體xj的適應(yīng)值很有可能并不好或者處于非最優(yōu)區(qū)域；相反，如果一個個體xj很久沒有被更新，就說明產(chǎn)生的試驗(yàn)向量ui很難替換個體xj，那么個體xj的適應(yīng)值很可能已經(jīng)非常好或者已經(jīng)找到了最優(yōu)解。如果我們可以充分挖掘并利用這些個體的歷史進(jìn)化信息來幫助種群的搜索，算法性能會進(jìn)一步地提高。

其次，在有限的適應(yīng)值評估次數(shù)內(nèi)，并沒有必要對所有的個體都進(jìn)行評估。例如，如果一個個體xj持續(xù)被更新，就說明產(chǎn)生的試驗(yàn)向量ui可以經(jīng)常性地替換該個體，那么可以近似認(rèn)為，在不評估試驗(yàn)向量ui的情況下，試驗(yàn)向量ui的適應(yīng)值大概率是要好于個體xj的；同樣地，如果一個個體xj很久沒有被更新，就說明產(chǎn)生的試驗(yàn)向量ui很難替換個體xj，那么我們可以近似認(rèn)為，在不評估試驗(yàn)向量ui的情況下，試驗(yàn)向量ui的適應(yīng)值大概率是要差于個體xj的。也就是說，在這兩種情況下，可以不去評估試驗(yàn)向量ui，直接利用個體的進(jìn)化信息就可以近似選擇出適應(yīng)值更好的個體。這個歷史經(jīng)驗(yàn)信息的積累就當(dāng)作為我們第一層適應(yīng)值評估概率的基礎(chǔ)。

2.1.1 第一層適應(yīng)值評估概率

首先為每個個體賦予第一層適應(yīng)值評估概率PFj和兩個選擇概率PXj和PUj，分別代表個體j的第一層適應(yīng)值評估概率，選擇自身xj進(jìn)入下一代的概率，以及選擇試驗(yàn)向量ui進(jìn)入下一代的概率，三者均初始化為0.5。

在算法運(yùn)行初期(在0.3×MaxFEs 內(nèi))，需要充分挖掘個體的歷史進(jìn)化信息，因此，在這個階段里，所有的個體都要進(jìn)行評估。每當(dāng)產(chǎn)生一個試驗(yàn)向量ui后，如果試驗(yàn)向量ui的適應(yīng)值要好于它最近的父代個體xj，則個體xj的選擇概率PUj會適當(dāng)?shù)卦黾樱x擇概率PXj會適當(dāng)?shù)販p小；相反，如果試驗(yàn)向量ui的適應(yīng)值要差于它最近的父代個體xj，則個體xj的選擇概率PUj會適當(dāng)?shù)販p小，而選擇概率PXj會適當(dāng)?shù)卦黾印Ｎ覀兌x個體xj的選擇概率PUj和PXj的范圍為[0.2,0.8]，且PUj+PXj=1，二者更新式如(11)所示：

而個體的第一層適應(yīng)值評估概率PFj則是根據(jù)選擇概率PUj和PXj，選擇二者中的最小值，如式(12)所示：

也就是說，假如個體xj的選擇概率PUj很大而選擇概率PXj很小，那么該個體的第一層適應(yīng)值評估概率就會設(shè)置為PXj，即很小的值。因?yàn)閤j的選擇概率PUj很大，也就是說，根據(jù)前期經(jīng)驗(yàn)，產(chǎn)生的試驗(yàn)向量ui是有很大概率可以替換掉個體xj的，那么即使不對試驗(yàn)向量ui進(jìn)行評估，也可以近似認(rèn)為試驗(yàn)向量ui是有很大概率可以替換掉個體xj，故而將個體xj的第一層適應(yīng)值評估概率PFj設(shè)置為較小的值PXj。同理，假如個體xj的選擇概率PUj很小而選擇概率PXj很大，那么該個體的第一層評估概率就會設(shè)置為PUj。因?yàn)閤j的選擇概率PUj很小，也就是說根據(jù)前期經(jīng)驗(yàn)，產(chǎn)生的試驗(yàn)向量ui是幾乎不可能替換掉個體xj的，那么即使不對試驗(yàn)向量ui進(jìn)行評估，我們可以近似認(rèn)為試驗(yàn)向量ui是幾乎不可能替換掉個體xj，故而將個體xj的第一層適應(yīng)值評估概率PFj設(shè)置為較小的值PXj。很顯然，個體的第一層適應(yīng)值評估概率PFj的取值范圍就是[0.2，0.5]。

PFj的取值越大，則說明個體xj前期的適應(yīng)值評估經(jīng)驗(yàn)越弱，選擇概率越模糊。當(dāng)PFj=0.5時(shí)，也就是個體xj前期的適應(yīng)值評估經(jīng)驗(yàn)幾乎為0，此時(shí)如果仍然依賴個體xj前期的適應(yīng)值評估經(jīng)驗(yàn)，很有可能誤導(dǎo)種群的進(jìn)化。也就是說，我們希望當(dāng)PFj=0.5 時(shí)，個體xj必須被評估。所以進(jìn)一步在PFj上增加了拉伸操作，如式(13)所示：

即將個體的第一層適應(yīng)值評估概率PFj的取值范圍由[0.2，0.5]線性拉伸到[0.4，1]，增加前期適應(yīng)值評估經(jīng)驗(yàn)較弱個體的適應(yīng)值評估概率。

2.1.2 第二層適應(yīng)值評估概率

除了個體的歷史經(jīng)驗(yàn)信息以外，還需要考慮的就是個體當(dāng)前的適應(yīng)值。顯然，當(dāng)評估次數(shù)極其有限時(shí)，自然是希望將這有限的適應(yīng)值評估次數(shù)用在更有可能尋找到問題最優(yōu)解的個體上。適應(yīng)值越好的個體，接近最優(yōu)解的概率也相應(yīng)越高。因此，在這里基于每個個體的適應(yīng)值，為每個個體xj設(shè)計(jì)了第2 層的適應(yīng)值評估概率PSj。具體的設(shè)計(jì)思路與AED-DDE 算法中的PLS 策略類似，按照個體的適應(yīng)值對個體進(jìn)行由壞到好的排序。接著，設(shè)置個體xj的第二層的適應(yīng)值評估概率PSj如式(14)所示：

式中：rj表示第jth個個體在適應(yīng)值排序中的位置。也就是說，適應(yīng)值越好的個體就擁有更好的第二層的適應(yīng)值評估概率PSj。

2.1.3 完整的概率評估機(jī)制流程

在我們的算法設(shè)計(jì)中，使用兩個適應(yīng)值評估概率的最大值作為個體最終的適應(yīng)值評估概率Pj，如式(15)所示。

具體來說，如果個體xj的第1 層適應(yīng)值評估概率PFj很小但是第2 層的適應(yīng)值評估概率PSj很高，這說明個體xj具有很好的適應(yīng)值，尋找到最優(yōu)解的概率也會很高，此時(shí)，即使個體xj的第一層適應(yīng)值評估概率PFj很小，依然為個體xj設(shè)置較大的適應(yīng)值評估概率，加快算法找到問題最優(yōu)解的速率。同樣，如果個體xj的第一層適應(yīng)值評估概率PFj很高但是第2 層的適應(yīng)值評估概率PSj很小，這說明個體xj雖然適應(yīng)值較差，但個體xj前期的適應(yīng)值評估經(jīng)驗(yàn)較弱，選擇概率較為模糊，此時(shí)，為了提升算法的準(zhǔn)確性，同樣為個體xj設(shè)置較大的適應(yīng)值評估概率，進(jìn)一步豐富并優(yōu)化個體xj的歷史評估經(jīng)驗(yàn)，方便后續(xù)算法性能的提升。這兩個適應(yīng)值評估概率的結(jié)合，可以進(jìn)一步增強(qiáng)算法的優(yōu)化性能。

在算法運(yùn)行初期結(jié)束后，就開始采用概率評估機(jī)制。在這個階段中，每個個體xj會根據(jù)自身的適應(yīng)值評估概率Pj來選擇性評估。如果該個體xj滿足自身的適應(yīng)值評估概率Pj，則對產(chǎn)生的試驗(yàn)向量ui進(jìn)行適應(yīng)值評估，通過比較ui與xj的適應(yīng)值來判斷是否對xj進(jìn)行更新，并采用上述方法相應(yīng)地更新個體xj的選擇概率PUj和PXj以及第1 層的適應(yīng)值評估概率PFj。

若是該個體xj并不滿足自身的適應(yīng)值評估概率Pj，則不對產(chǎn)生的試驗(yàn)向量ui進(jìn)行適應(yīng)值評估，而是根據(jù)前期積累的歷史經(jīng)驗(yàn)，直接根據(jù)選擇概率PUj和PXj來判斷是否對xj進(jìn)行更新，即如果個體xj滿足自身的選擇概率PXj，則直接忽略試驗(yàn)向量ui，不對個體xj進(jìn)行更新。如果個體xj滿足自身的選擇概率PUj，則直接用試驗(yàn)向量ui替換掉個體xj。然而，由于此時(shí)并沒有對試驗(yàn)向量ui進(jìn)行適應(yīng)值評估，試驗(yàn)向量ui沒有相應(yīng)的適應(yīng)值，在這種情況下，即使個體xj更新了，依然使用它之前的適應(yīng)值作為更新后個體的新適應(yīng)值。同時(shí)，由于并沒有對個體的適應(yīng)值進(jìn)行評估，此時(shí)個體xj的選擇概率PUj和PXj以及第一層的適應(yīng)值評估概率PFj不進(jìn)行更新。

綜上，概率評估機(jī)制所節(jié)省下來的FEs 可以提供給那些更需要評估的個體，增加種群的迭代次數(shù)，提升算法的求解精度；同時(shí)，概率評估機(jī)制充分捕捉了算法運(yùn)行過程中每個個體的歷史經(jīng)驗(yàn)信息，實(shí)現(xiàn)了信息的充分利用，有利于算法的進(jìn)一步搜索；最后，雙層概率的結(jié)合使用互為補(bǔ)充，從多方面決定個體的適應(yīng)值評估概率，豐富了算法的設(shè)計(jì)，進(jìn)一步提升了算法的優(yōu)化性能。完整的概率評估機(jī)制PE 的算法偽代碼如算法3 所示。

算法3PE 算法

2.2 完整的PEDE 算法

結(jié)合AED-DDE 算法與以上的概率評估機(jī)制PE，完整的PEDE 算法偽代碼如算法4 所示。

算法4PEDE 算法

1)結(jié)合了AED-DDE 算法中基于AED 的小生境策略以及基于PLS 的局部搜索策略，可以避免種群劃分的困難以及小生境參數(shù)的敏感度，同時(shí)使得算法可以更加精確地找到所有的全局最優(yōu)解。

2)概率評估機(jī)制的提出為算法節(jié)省FEs，便于算法將及其有限的FEs 提供給那些更需要評估的個體，同時(shí)增加種群的迭代次數(shù)，提升算法的求解精度。

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

3.1 實(shí)驗(yàn)設(shè)置

采用目前最主流的多峰值優(yōu)化測試集IEEE CEC 2013[33]來測試PEDE 的算法性能。

多峰值優(yōu)化問題有兩個重要的評估指標(biāo)，分別是最優(yōu)解尋找率(peak ratio，PR)和成功運(yùn)行率(success rate，SR)。對于一個給定的最大適應(yīng)值評估次數(shù)MaxFEs 和一個準(zhǔn)確度ε，PR 指的是算法多次運(yùn)行中，全局最優(yōu)解的平均找尋率；SR 指的是算法的成功運(yùn)行比率，其中一次成功運(yùn)行表示算法可以在當(dāng)次運(yùn)行中找到該問題的所有全局最優(yōu)解。

PEDE 的種群規(guī)模N的設(shè)置如表1 所示，而MaxFEs 的設(shè)置則是引用IEEE CEC 2013 多峰值優(yōu)化測試集的要求。此外，PEDE 中使用的變異策略為 DE/rand/1，放大系數(shù)F與交叉概率CR 分別設(shè)置為0.9 和0.1。所有的算法獨(dú)立運(yùn)行51 次，對比實(shí)驗(yàn)結(jié)果的均值。此外，采用準(zhǔn)確度ε=10?4來測試算法性能，該準(zhǔn)確度的使用最為普遍[15-28]。

表1 參數(shù)設(shè)置Table1 Parameters setting

比較PEDE 與以下15個多峰值優(yōu)化算法，它們分別是小生境策略算法CDE[15]、SDE[16]、NCDE[18]、NSDE[18]、Self-CCDE[17]、Self-CSDE[17]、AED-DDE[29]；新變異策略算法LoICDE[25]、LoISDE[25]、R3PSO[34]、LIPS[35]， PNPCDE[26]、LMCEDA[31]、LMSEDA[31]；以及多目標(biāo)優(yōu)化算法MOMMOP[32]。這些算法都是近年來的多峰值優(yōu)化中的代表性主流成果，時(shí)間跨度從2004 年到2021 年。所有的算法采用相同的MaxFEs 設(shè)置，以此來保證比較的公平性。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 與主流多峰值優(yōu)化算法實(shí)驗(yàn)結(jié)果對比

表2 列舉了PEDE 與其他多峰值優(yōu)化算法在準(zhǔn)確度ε=10?4下PR 與SR 的實(shí)驗(yàn)結(jié)果。為了突出顯示，最好的PR 結(jié)果加粗顯示。此外，Wilcoxon 秩和檢驗(yàn)在α=0.05 下用來做不同算法之間PR 結(jié)果的顯著性分析[36]。符號“+”、“?”和“≈”分別表示算法PEDE 要顯著好于(+)、顯著差于(?)以及無明顯差異(≈)對比算法。從表2 中可以看到，在函數(shù)F1～F6和F10～F12上，只有PEDE 和AED-DDE 可以在每一次運(yùn)行中都找到所有的全局最優(yōu)解，PR 值與SR 值均為1.000，而其他的任何一個算法都不能達(dá)到相同的效果。在函數(shù)F7～F9上，Self-CCDE 和MOMMOP 取得了令人非常滿意的結(jié)果，甚至結(jié)果要好于PEDE，特別是MOMMOP，PR 值與SR 值均為1.000。然而，PEDE 在函數(shù)F7～F9上也取得了很好的結(jié)果，要顯著好于其他的多峰值優(yōu)化算法。同時(shí)，Self-CCDE 和MOMMOP 在函數(shù)F11和F12上的結(jié)果要顯著差于PEDE。在函數(shù)F13上，PEDE 取得了與LIPS 近似的實(shí)驗(yàn)結(jié)果，但要顯著好于其他所有的多峰值優(yōu)化算法。同時(shí)，LIPS 在其他函數(shù)上的結(jié)果都不能優(yōu)于PEDE。在函數(shù)F14～F20上，PEDE 在函數(shù)F14、F16和F20上都取得了最好的實(shí)驗(yàn)結(jié)果。需要注意的是，F(xiàn)20是IEEE CEC 2013 中最復(fù)雜、維度最高的測試函數(shù)，許多算法在F20上甚至不能找到任何一個全局最優(yōu)解。即使PEDE 在函數(shù)F15、F17和F19上的實(shí)驗(yàn)結(jié)果要略微遜色于LMCEDA 和LMSEDA，PEDE 的實(shí)驗(yàn)結(jié)果依然要顯著好于其他的多峰值優(yōu)化算法。同時(shí)，與算法LMCEDA和LMSEDA 相比，PEDE 在其他函數(shù)上的效果要明顯好于LMCEDA 和LMSEDA，尤其是在4個擁有著數(shù)量巨大的全局最優(yōu)解的函數(shù)F6～F9上。

表2 IEEE CEC 2013 測試集在準(zhǔn)確度ε=10?4 下的PR 與SR 的實(shí)驗(yàn)結(jié)果Table2 Experimental results of IEEE CEC 2013 in PR and SR at accuracy levelε=10?4

續(xù)表2

總之，PEDE 分別要在12、19、14、5、16、10、18、13、12、17、13、18、8、7 和8個函數(shù)上好于CDE、SDE、LIPS、AED-DDE、R3PSO、NCDE、NSDE、PNPCDE、Self-CCDE、Self-CSDE、LoICDE、LoISDE、LMCEDA、LMSEDA 和MOMMOP。相反，PEDE 只在1、1、1、2、2、3 和4個函數(shù)上要略微差于CDE、NCDE、PNPCDE、Self-CCDE、LMCEDA、LMSEDA 和MOMMOP。同時(shí)，PEDE 的效果要好于AED-DDE，說明了概率適應(yīng)值評估機(jī)制的有效性。

為了有一個更加直觀的視角來看PEDE 算法的求解效果，在8個可視化函數(shù)上將PEDE 算法最終的種群分布展示出來。

如圖1 所示。

圖1 8個測試函數(shù)上 PEDE 的最終種群分布Fig.1 Final population distribution of PEDE on 8 selected functions

正如我們從圖1 中看到的，PEDE 可以找到問題所有的全局最優(yōu)解。即使當(dāng)問題有數(shù)量巨大的全局最優(yōu)解時(shí)，如圖1(d) 和圖1(e)，在函數(shù)F6和F7上，PEDE 依然可以找到所有的全局最優(yōu)解。當(dāng)求解一些包含有數(shù)量巨大的局部最優(yōu)解的復(fù)雜問題時(shí)，如圖1(g) 和圖1(h)，在函數(shù)F11和F12上，PEDE 可以維持種群多樣性和探索能力，有效地避開局部最優(yōu)解，將所有的全局最優(yōu)解找到。

3.2.2 與多峰值測試集冠軍算法實(shí)驗(yàn)對比

為了進(jìn)一步說明PEDE 算法的優(yōu)越性，在本節(jié)中，比較PEDE 與多峰值優(yōu)化測試集 IEEE CEC 2013 的冠軍算法(niching migratory multi-swarm optimizer,NMMSO[37])。為了公平比較，直接引用NMMSO 算法在多峰值優(yōu)化測試集IEEE CEC 2015 上的實(shí)驗(yàn)數(shù)據(jù)。

PEDE 與NMMSO 在準(zhǔn)確度ε=10?4下的PR 與SR 的詳細(xì)對比結(jié)果如表3 所示，其中最好的PR 實(shí)驗(yàn)結(jié)果加粗顯示。

從表3 中可以看到，PEDE 在7個函數(shù)上的實(shí)驗(yàn)結(jié)果要優(yōu)于NMMSO，而在7個函數(shù)上的實(shí)驗(yàn)結(jié)果要略差于NMMSO。然而，可以看到，PEDE可以在9個函數(shù)上每一次運(yùn)行中都找到問題所有的全局最優(yōu)解（函數(shù)F1～F6和F10～F12），PR 值與SR 值均為1.000，而NMMSO 僅可以在7個函數(shù)上找到問題所有的全局最優(yōu)解（函數(shù)F1～F5、F7和F10）。同時(shí)，在PEDE 差于NMMSO 的測試函數(shù)上，PEDE 也實(shí)現(xiàn)了與NMMSO 近似的實(shí)驗(yàn)結(jié)果。例如，在函數(shù)F14、F17和F19上，NMMSO 的PR 實(shí)驗(yàn)結(jié)果分別是0.720、0.468 和0.450，而PEDE 也實(shí)現(xiàn)了近似的PR 實(shí)驗(yàn)結(jié)果，分別是0.667、0.412 和0.368。此外，在高維復(fù)合函數(shù)F16～F20上，PEDE 在3個函數(shù)上要好于NMMSO，而NMMSO 僅在2個函數(shù)上要好于PEDE。特別地，在函數(shù)F20上，也是多峰值優(yōu)化測試集IEEE CEC 2013 中最復(fù)雜的函數(shù)，PEDE 的實(shí)驗(yàn)結(jié)果要好于NMMSO。

表3 PEDE 與NMMSO在準(zhǔn)確度ε=10?4 下 的PR 與SR 的實(shí)驗(yàn)結(jié)果對比Table3 Experimental results between PEDE and NMMSO in PR and SR at accuracy levelε=10?4

續(xù)表3

總之，PEDE 可以實(shí)現(xiàn)近似甚至好于多峰值優(yōu)化測試集IEEE CEC 2013 的冠軍算法的實(shí)驗(yàn)結(jié)果，特別是在一些復(fù)雜度較高的函數(shù)上。

3.2.3 概率評估機(jī)制性能測試

從表2 中可以看到，PEDE 的效果要好于AED-DDE，說明了概率適應(yīng)值評估機(jī)制的有效性。在本節(jié)中，進(jìn)一步測試概率評估機(jī)制的性能。將概率評估機(jī)制應(yīng)用在其他的多峰值優(yōu)化算法中來測試其性能。由于我們的概率評估機(jī)制適用于DE 算法，因此在這里，將概率評估機(jī)制應(yīng)用在N C D E[18]、LoICDE[25]、Self-CCDE[17]、PNPCDE[26]這4個基于DE 的多峰值優(yōu)化算法中。這4個算法結(jié)合概率評估機(jī)制的算法變種命名為算法-PE，例如，NCDE 算法結(jié)合概率評估機(jī)制的算法變種命名為NCDE-PE。這4個算法與它們相應(yīng)的算法變種在準(zhǔn)確度ε=10?4下的PR 與SR 的詳細(xì)對比結(jié)果如表4 所示。

表4 多峰值優(yōu)化算法及其在概率評估機(jī)制下的變種算法在準(zhǔn)確度ε=10?4 下的PR 與SR 的實(shí)驗(yàn)結(jié)果Table4 Experimental results of multimodal optimization algorithms and their variants with PE in PR and SR at accuracy levelε=10?4

從表4 中可以看到，概率評估機(jī)制都可以在一定程度上提升這4個算法的性能，分別在6、9、7、7個函數(shù)上提升了NCDE、LoICDE、Self-CCDE、PNPCDE 的算法性能，尤其是在函數(shù)F6、F11～F14、F16～F20上，這4個結(jié)合概率評估機(jī)制的算法變種要顯著好于原算法，進(jìn)一步說明了概率評估機(jī)制的有效性與可拓展性。

4 結(jié)束語

本文基于之前的自適應(yīng)分布估計(jì)的差分進(jìn)化算法這一研究工作，進(jìn)一步提出了一種概率評估機(jī)制。概率評估機(jī)制技術(shù)的提出，充分挖掘了個體在搜索和學(xué)習(xí)過程中的歷史經(jīng)驗(yàn)信息，對個體進(jìn)行選擇性評估，節(jié)省算法的適應(yīng)值評估次數(shù)，增加算法迭代次數(shù)，從而提升算法的求解精度。而對個體歷史經(jīng)驗(yàn)的充分學(xué)習(xí)也進(jìn)一步促進(jìn)了種群在搜索空間中的充分探索。

將自適應(yīng)分布估計(jì)的差分進(jìn)化算法與概率評估機(jī)制有機(jī)結(jié)合，充分利用了二者的優(yōu)勢，形成了本文中提出的新算法PEDE。PEDE 不僅在多峰值優(yōu)化測試集上取得了非常好的效果，同時(shí)，還將概率評估機(jī)制應(yīng)用到其他的差分進(jìn)化算法中，效果都有了一定的提升，也說明了概率評估機(jī)制的有效性與可拓展性。

在未來工作中，我們希望進(jìn)一步增強(qiáng)PEDE算法在復(fù)雜多峰值優(yōu)化問題上的求解性能，并將PEDE 算法應(yīng)用在多峰值實(shí)際優(yōu)化問題當(dāng)中。