一種基于精英選擇和反向學習的分布估計算法

孟 磊，張 婷，董 澤

(1.大唐環境產業集團股份有限公司，北京100048；2.國電新能源技術研究院有限公司，北京 102209；3.華北電力大學河北省發電過程仿真與優化控制工程技術研究中心，河北 保定 071003)

1 引言

分布估計算法(Estimation of Distribution Algorithm，EDA)是一種結合統計學知識和進化原理的群體優化算法，其概念最早由德國學者H. Mühlenbein和G. Paa?提出[1]。它基于統計學原理，通過對搜索空間內優秀個體的概率分布進行估計和采樣，產生新一代群體，如此不斷進化，完成尋優。

1996年分布估計算法的概念被提出，自此之后，對該算法的研究層出不窮，總結主要有三類：一是研究算法在解決不同問題上的應用，諸如多目標優化問題[2,3]、調度問題[4,5]、生物信息學問題[6,7]以及工程應用問題[8,9]等；二是對算法本身的理論研究，例如Rastegar分析了cGA(compact Genetic Algorithm)和PBIL(Population-based Incremental Learning)算法收斂到其最優解的概率，并得到了這兩種算法的收斂條件[10]；Chen 等分析了EDA算法的運算時間與所求優化問題規模的關系[11]；Lima等研究了利用貝葉斯優化方法建立的概率模型與問題結構之間關系[12]等；三是對算法的改進。在EDA算法的改進方面，大體有三種：以概率模型為改進主體[13,14]、著重保持種群的多樣性[15,16]以及融合算法，其中，融合算法指的是與其他算法的融合[4,17,18]。

以概率模型為主體的改進算法中，一些算法選擇了復雜度更高的概率模型。此種改進措施在提高算法性能的同時，帶來了一些其他問題，例如，內存消耗的加劇以及計算復雜性的增加。EDA算法產生新個體的方式是通過對優秀個體概率分布的擬合，進而采樣隨機產生。過擬合在保持種群多樣性方面是不利因素，容易使算法陷入早熟風險。對于EDA算法來說，種群多樣性的保持是一個很重要的問題。

本文提出一種基于精英選擇和反向學習的改進分布估計算法，采用最基本的高斯分布作為概率模型，通過引入精英選擇策略和反向學習機制改善算法性能。在提高算法收斂速度方面，精英選擇貢獻了很大力量，面對精英選擇帶來的種群多樣性減少問題，通過二次反向反射搜索來彌補。二者結合，加速算法收斂到全局最優解。算法性能的驗證通過對經典Benchmark測試函數的仿真來實現，與之對比的算法選擇性能比較好的EE-EDA算法和基本經典的EDA算法。

2 基本分布估計算法

分布估計算法主要采用統計方法構建優秀個體的概率模型，該概率模型能夠反映變量之間的關系，對該概率模型采樣以此產生新種群，不斷迭代進化，最終實現搜索空間內的尋優。其中的關鍵步驟主要如下[25]：

1) 初始化

設置種群規模PS，最大進化代數Gmax，搜索空間維數D。初始種群通過在搜索空間范圍內通過均勻分布隨機產生

pop(xi)0=ai+(bi-ai)×rand(1，PS)

(1)

其中：ai和bi分別是第i維變量xi的下限和上限，rand(1，PS)代表在[0，1]區間上依據均勻分布的方式隨機產生PS個個體。

2) 選擇

對種群中每個個體計算其適應值，然后按照適應值大小進行排序，選擇適應值較優越的個體，構成規模為m=λ×PS的優勢群體。

3) 構建概率模型

(2)

(3)

其中：xij是優勢群體中第j個個體第i維的值，i=1，2，…，D，j=1，2，…，m。

第i維高斯概率密度函數為

(4)

4) 采樣

在搜索空間范圍內依據式(4)所表示的概率分布模型隨機采樣生成規模為PS個個體的種群，這就是下一代種群。

3 改進的分布估計算法

3.1 精英選擇

基本分布估計算法產生下一代種群的方式是通過對優勢群體的概率分布模型進行采樣生成，而優勢群體的選擇是直接將種群中每個個體按照適應值的大小排序，以截斷的方式選擇適應值比較優的前m個個體。這種經典的截斷選擇，操作簡單，并且在這m個個體中，無論適應值大小，每個個體所起的作用均等(均為1/m)。在粒子群算法(Particle Swarm Optimization，PSO)的種群更新策略中，通過個體最優和種群最優共同來對迭代速度進行更新，尋優速度非常快，但其弊端亦非常明顯：易導致收斂到局部最優。受此啟發，提出一種精英選擇策略，對適應值比較優的個體的作用進行強化，同時需要對種群的多樣性進行兼顧，盡量減小陷入局部最優的風險，提高算法的尋優性能。

popb(1：λ1m)=xb1；

popb((λ1+1)m：(λ1+λ2)m)=xb2；

該算法打破優勢群體中每個個體比重相同的狀況，使得適應值最好的5個個體在優勢群體中占的比例增加，然而，受啟發于PSO算法易陷入局部最優的特點，優勢群體并不單單只由這5個個體構成，兼顧收斂速度和種群多樣性，從而提高算法性能。

3.2 二次反向反射搜索

2005年，Tizhoosh提出反向學習(Opposition-based learning， OBL)的概念[19]，隨之機器學習領域整合采用了該機制，使得算法性能得到明顯改善。二次反向點的概念由Rahnamayan等提出，并用之于差分進化(Differential Evolution， DE)算法中[20]。2009年，Ergezer提出二次反向反射的概念，并將其用于BBO(Biogeography-based Optimization)算法中[21]。他通過數學分析和仿真證明了其在所有反向學習算法中的優勢，說明了其在優化算法收斂速度和全局搜索能力提高方面的強大作用。

這些算法的描述和概念簡介如下：

定義1(反向點)

設區間[lb，ub]上存在任意實數y，它的反向點yo為

yo=lb+ub-y

(5)

(6)

定義2(二次反向點)

設區間[lb，ub]上存在任意實數y，它的反向點為yo，那么，它的二次反向點yqo為

yqo=rand[ym，yo]

(7)

其中：ym=(lb+ub)/2，rand[ym，yo]為ym和yo之間隨機生成的數。

(8)

定義3(二次反向反射點)

設區間[lb，ub]上存在任意實數y，yo為它的反向點，yqo為它的二次反向點，那么，它的二次反向反射點yqro為

yqro=rand[y，ym]

(9)

(10)

基于二次反向反射搜索的優化算法：

在優化算法中使用二次反向反射搜索算子時，假設Y=(y1，y2，…，yn)為n維搜索空間其中的一個可能解，Yqro是它的二次反向反射解，f(·)是該優化算法的適應度函數，當f(Yqro)

3.3 改進算法

改進后的算法稱之為EEQO-EDA，算法的偽代碼如下：

g=0；∥g代表進化代數

repeatg=g+1;

對兩個種群的適應值進行計算f(X)，f(Xqro)；

forj=1：PS

iffj(Xqro)

X=Xqro;

fj=fj(Xqro);

else

X=X;

fj=fj(X);

end

end

依照從小到大的規則對fj進行排序；

依據精英選擇策略來生成優勢群體popb；

依照式式(2)～(4)來建立概率模型；

采用隨機采樣的方式對概率模型采樣來生成下一代種群pop(xi)；

until 滿足算法終止條件；

output 優化結果及最優個體值。

4 仿真分析

為了驗證本文改進算法的性能，選擇了7個標準函數進行仿真測試，并選擇標準EDA和已發表的性能很好的EE-EDA[22](EDA with extreme elitism selection)進行對比。運行環境是Windows 7系統，處理器是Inter(R) Core(TM)2 Duo CPU T6570，仿真軟件是MATLAB R2015a。

4.1 測試函數及算法參數設置

本文所采用的測試函數為標準測試函數，取自文獻[23]，函數特性如表1。

表1中，這些測試函數大體上分為兩種：1)f1～f4是單極值的函數，這類函數不存在收斂到其他局部最優值的情況，可以用來對算法的尋優速度進行測試；2)f5～f7是多極值函數，這類函數存在多個局部最優值，尋優結果可能為某個局部最優值，而非全局最優，這類函數可以用來對算法的全局搜索能力進行測試，測試算法逃離或者避免陷入局部最優值的能力。

在仿真實驗中，當采用某個測試函數進行測試時，所有算法的概率模型是相同的，種群規模PS以及最大迭代次數Gmax，對于所有算法是相同的；但是，不同的測試函數之間，算法的PS和Gmax可能不同。這是由算法本身所具有的特性來決定的：有些測試函數的形狀整體形如深谷，但是，谷底卻比較平緩，對于此類函數來說，尋優算法的最大迭代次數可以設置的大些；有些測試函數的形狀起伏較多，即存在多個局部極值點，對于此類函數，尋優算法的種群規?？梢栽O置的大些，一定程度上增加種群的多樣性。最后，對于所有算法而言，優勢群體的選擇比例設置為λ=0.5，也就是說優勢群體的數量m=λ×PS=0.5PS

表1 測試函數

算法的參數設置：1) 標準EDA和EE-EDA根據式(1)采用均勻分布的方式隨機生成初始種群；2) EEQO-EDA初始種群的生成根據式(1)和二次反向反射搜索相結合；3) 優勢群體的產生，標準EDA利用截斷選擇生成；4) EE-EDA利用精英選擇來生成優勢群體，并且依據文獻[22]的分析，適應值比較優越的5個個體在優勢群體中所占據的個數分別為25，20，15，10，5，也就是說，λ1m=25，λ2m=20，λ3m=15，λ4m=10，λ5m=5；5) EEQO-EDA利用精英選擇和二次反向反射搜索相結合的方法來對種群進行更新，而其中精英選擇部分的參數設置則采用與EE-EDA一致的方式。

4.2 實驗結果及分析

為了評價各個對比算法的性能，本文中選擇了以下指標[24]：

1) 收斂精度：當算法的迭代過程達到某一評價次數時，各個尋優算法在測試函數上所能得到的最優解的精度；

2) 收斂速度：在不同的終止評價次數下，對于同一個測試函數，各個優化算法所能獲得的最優解的精度。假如對于不同的評價次數，某個優化算法所能獲得的最優解的精度都比較高，那么，可認為對于該測試函數，該優化算法的收斂速度是更快的；

3) 穩定性：對于某個固定的評價次數，算法獨立運行多次，統計多次運行所得到的最優解的精度，得到其方差(或者標準差)作為穩定性的評價依據；

4)魯棒性：對于某個固定的評價次數，算法獨立運行多次，能夠獲得不低于預設的最優解精度的概率。

4.2.1 收斂精度和穩定性評價

針對每一個單獨的測試函數，種群規模和最大迭代次數一定時，對所有優化算法每次尋優所得到的全局最優解進行統計，獲得其平均值和標準差。每一個測試函數在每一個優化算法下獨立運行25次，對這25次的運行結果進行統計，獲得如表2所示結果。

實驗結果中，認為均值反映了優化算法的收斂精度，認為標準差是穩定性的反映。表2可以看出，在與之對比的EE-EDA和標準EDA算法中，本文所提出的EEQO-EDA在對所選擇的7個測試函數尋優的過程中全部都取得了最好的優化結果。其中，對于體現收斂速度的單極值測試函數f1和f3，體現全局尋優能力的多極值測試函數f6和f7，利用本文所提算法，均收斂到其理論最優解。對于測試函數f2和f4，本文所提的算法雖然沒有獲得其理論最優值，然而，與EE-EDA和EDA相比，本文所提EEQO-EDA算法在收斂精度和穩定性上的優勢依然非常明顯。對于多極值測試函數f5，EEQO-EDA算法所得到的最優解在收斂精度上依然優于其他兩種算法。而對于EE-EDA和標準EDA來說，除去測試函數f6，在其余測試函數上，EE-EDA在收斂精度和穩定性方面具有明顯優勢?？梢缘贸鲆韵陆Y論：1)與EE-EDA和標準EDA算法相比，本文所提出的算法具有最優越的收斂精度和穩定性；2)對于多數測試函數而言，將精英選擇融合之后的EDA算法(EE-EDA)在收斂精度和穩定性方面具有明顯的提高；3)對于融合精英選擇的EE-EDA算法，本文所提出的算法在彌補EE-EDA算法不足的同時，使得算法的收斂精度和穩定性顯現出明顯的提高。

表2 固定迭代次數下，三種算法的收斂精度及標準差對比

4.2.2 收斂速度和魯棒性評價

為了定量評價算法的收斂速度，對評價次數在6000、30000和60000時算法在函數上所能獲得的最優解的精度進行統計對比；為了定量評價算法的魯棒性，對于各個測試函數，預設一個收斂精度，設置最大評價次數為90000，當達到最大評價次數時，對各個算法達到預設精度的概率進行對比。對于各項試驗，令三種優化算法在每個測試函數上獨立運行25次，然后對運行結果進行統計，如表3所示。

表3 三種算法的收斂速度及成功率對比

從表3可以得出：1)在收斂速度方面，與EE-EDA和標準EDA算法相比，本文所提出的算法對于不同的測試函數，在不同的評價次數下，所得到的最優值的精度為最高，并且優勢明顯，這在一定程度上，可以認為本文所提出的算法在收斂速度上是優于EE-EDA和標準EDA算法的；對于EE-EDA和標準EDA算法之間的對比，可以看出，除去測試函數f7，對于相同的評價次數，在不同的測試函數下，EE-EDA所能得到的最優解的精度優于標準EDA算法，或者與標準EDA算法持平，這在一定程度上，我們可以認為EE-EDA算法在收斂速度上是優于標準EDA算法的。2)在魯棒性方面，當算法達到最大評價次數時，本文所提出的算法在所有測試函數上每次都能達到預設精度，成功率為100%；而對于EE-EDA而言，對于測試函數f5和f6，當達到最大評價次數時，收斂到其預設精度的概率分別為64%和80%，對于測試函數f2，在達到最大評價次數時，均不能收斂到其預設精度，對于其余測試函數，均能在最大評價次數之內收斂到其預設精度；對于標準EDA而言，對于測試函數f2和f6，當達到最大評價次數時，收斂到其預設精度的概率分別為48%和56%，對于測試函數f1、f3和f4，在達到最大評價次數時，均不能收斂到其預設精度，對于其余測試函數，均能在最大評價次數之內收斂到其預設精度。通過對比實驗發現，在一定程度上，可以認為本文所提出的算法在魯棒性上優于EE-EDA和標準EDA。

5 結論

本文在基本EDA算法的基礎上，提出EEQO-EDA算法，將精英選擇和二次反向反射搜索引入到EDA算法。精英選擇機制可大大提高算法的收斂速度，二次反向反射搜索在增加種群多樣性的同時，減弱了算法收斂速度加快帶來的陷入局部最優的風險，二者配合，兼顧收斂速度和全局尋優，使得算法性能得到提高。通過對Benchmark測試函數進行仿真實驗，驗證了其在收斂速度、收斂精度、穩定性以及魯棒性上的優勢。