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

王子佳，詹志輝

（1.廣州大學 計算機科學與網絡工程學院,廣東 廣州 510006;2.華南理工大學 計算機科學與工程學院,廣東廣州 510006）

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

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

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

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

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

1 相關工作

1.1 差分進化算法

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

1)變異

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

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

2)交叉

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

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

3)選擇

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

其中f(x)為適應值評估函數。

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

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

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

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

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

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

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

1.3 AED-DDE

1.3.1 基于AED 的自適應無參小生境技術

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

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

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

算法1基于AED 的小生境技術

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

1.3.2 基于PLS 的局部搜索技術

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

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

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

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

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

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

算法2PLS 算法

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

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

2.1 概率評估機制PE

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

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

2.1.1 第一層適應值評估概率

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

在算法運行初期(在0.3×MaxFEs 內)，需要充分挖掘個體的歷史進化信息，因此，在這個階段里，所有的個體都要進行評估。每當產生一個試驗向量ui后，如果試驗向量ui的適應值要好于它最近的父代個體xj，則個體xj的選擇概率PUj會適當地增加，而選擇概率PXj會適當地減小；相反，如果試驗向量ui的適應值要差于它最近的父代個體xj，則個體xj的選擇概率PUj會適當地減小，而選擇概率PXj會適當地增加。我們定義個體xj的選擇概率PUj和PXj的范圍為[0.2,0.8]，且PUj+PXj=1，二者更新式如(11)所示：

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

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

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

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

2.1.2 第二層適應值評估概率

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

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

2.1.3 完整的概率評估機制流程

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

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

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

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

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

算法3PE 算法

2.2 完整的PEDE 算法

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

算法4PEDE 算法

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

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

3 數值實驗分析

3.1 實驗設置

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

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

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

表1 參數設置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]；以及多目標優(yōu)化算法MOMMOP[32]。這些算法都是近年來的多峰值優(yōu)化中的代表性主流成果，時間跨度從2004 年到2021 年。所有的算法采用相同的MaxFEs 設置，以此來保證比較的公平性。

3.2 實驗結果

3.2.1 與主流多峰值優(yōu)化算法實驗結果對比

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

表2 IEEE CEC 2013 測試集在準確度ε=10?4 下的PR 與SR 的實驗結果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個函數上好于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個函數上要略微差于CDE、NCDE、PNPCDE、Self-CCDE、LMCEDA、LMSEDA 和MOMMOP。同時，PEDE 的效果要好于AED-DDE，說明了概率適應值評估機制的有效性。

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

如圖1 所示。

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

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

3.2.2 與多峰值測試集冠軍算法實驗對比

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

PEDE 與NMMSO 在準確度ε=10?4下的PR 與SR 的詳細對比結果如表3 所示，其中最好的PR 實驗結果加粗顯示。

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

表3 PEDE 與NMMSO在準確度ε=10?4 下 的PR 與SR 的實驗結果對比Table3 Experimental results between PEDE and NMMSO in PR and SR at accuracy levelε=10?4

續(xù)表3

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

3.2.3 概率評估機制性能測試

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

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

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

4 結束語

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

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

在未來工作中，我們希望進一步增強PEDE算法在復雜多峰值優(yōu)化問題上的求解性能，并將PEDE 算法應用在多峰值實際優(yōu)化問題當中。