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

孟 磊，張 婷，董 澤

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

1 引言

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

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

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

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

2 基本分布估計算法

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

1) 初始化

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

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

(1)

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

2) 選擇

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

3) 構建概率模型

(2)

(3)

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

第i維高斯概率密度函數(shù)為

(4)

4) 采樣

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

3 改進的分布估計算法

3.1 精英選擇

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

popb(1：λ1m)=xb1；

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

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

3.2 二次反向反射搜索

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

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

定義1(反向點)

設區(qū)間[lb，ub]上存在任意實數(shù)y，它的反向點yo為

yo=lb+ub-y

(5)

(6)

定義2(二次反向點)

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

yqo=rand[ym，yo]

(7)

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

(8)

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

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

yqro=rand[y，ym]

(9)

(10)

基于二次反向反射搜索的優(yōu)化算法：

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

3.3 改進算法

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

g=0；∥g代表進化代數(shù)

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

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

依據(jù)精英選擇策略來生成優(yōu)勢群體popb；

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

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

until 滿足算法終止條件；

output 優(yōu)化結果及最優(yōu)個體值。

4 仿真分析

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

4.1 測試函數(shù)及算法參數(shù)設置

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

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

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

表1 測試函數(shù)

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

4.2 實驗結果及分析

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

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

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

3) 穩(wěn)定性：對于某個固定的評價次數(shù)，算法獨立運行多次，統(tǒng)計多次運行所得到的最優(yōu)解的精度，得到其方差(或者標準差)作為穩(wěn)定性的評價依據(jù)；

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

4.2.1 收斂精度和穩(wěn)定性評價

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

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

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

4.2.2 收斂速度和魯棒性評價

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

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

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

5 結論

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