一種基于精英選擇和反向?qū)W習(xí)的分布估計(jì)算法

孟 磊，張 婷，董 澤

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

1 引言

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

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

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

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

2 基本分布估計(jì)算法

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

1) 初始化

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

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

(1)

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

2) 選擇

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

3) 構(gòu)建概率模型

(2)

(3)

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

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

(4)

4) 采樣

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

3 改進(jìn)的分布估計(jì)算法

3.1 精英選擇

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

popb(1：λ1m)=xb1；

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

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

3.2 二次反向反射搜索

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

這些算法的描述和概念簡(jiǎn)介如下：

定義1(反向點(diǎn))

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

yo=lb+ub-y

(5)

(6)

定義2(二次反向點(diǎn))

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

yqo=rand[ym，yo]

(7)

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

(8)

定義3(二次反向反射點(diǎn))

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

yqro=rand[y，ym]

(9)

(10)

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

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

3.3 改進(jìn)算法

改進(jìn)后的算法稱之為EEQO-EDA，算法的偽代碼如下：

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

repeatg=g+1;

對(duì)兩個(gè)種群的適應(yīng)值進(jìn)行計(jì)算f(X)，f(Xqro)；

forj=1：PS

iffj(Xqro)

X=Xqro;

fj=fj(Xqro);

else

X=X;

fj=fj(X);

end

end

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

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

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

采用隨機(jī)采樣的方式對(duì)概率模型采樣來(lái)生成下一代種群pop(xi)；

until 滿足算法終止條件；

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

4 仿真分析

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

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

本文所采用的測(cè)試函數(shù)為標(biāo)準(zhǔn)測(cè)試函數(shù)，取自文獻(xiàn)[23]，函數(shù)特性如表1。

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

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

表1 測(cè)試函數(shù)

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

4.2 實(shí)驗(yàn)結(jié)果及分析

為了評(píng)價(jià)各個(gè)對(duì)比算法的性能，本文中選擇了以下指標(biāo)[24]：

1) 收斂精度：當(dāng)算法的迭代過(guò)程達(dá)到某一評(píng)價(jià)次數(shù)時(shí)，各個(gè)尋優(yōu)算法在測(cè)試函數(shù)上所能得到的最優(yōu)解的精度；

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

3) 穩(wěn)定性：對(duì)于某個(gè)固定的評(píng)價(jià)次數(shù)，算法獨(dú)立運(yùn)行多次，統(tǒng)計(jì)多次運(yùn)行所得到的最優(yōu)解的精度，得到其方差(或者標(biāo)準(zhǔn)差)作為穩(wěn)定性的評(píng)價(jià)依據(jù)；

4)魯棒性：對(duì)于某個(gè)固定的評(píng)價(jià)次數(shù)，算法獨(dú)立運(yùn)行多次，能夠獲得不低于預(yù)設(shè)的最優(yōu)解精度的概率。

4.2.1 收斂精度和穩(wěn)定性評(píng)價(jià)

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

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

表2 固定迭代次數(shù)下，三種算法的收斂精度及標(biāo)準(zhǔn)差對(duì)比

4.2.2 收斂速度和魯棒性評(píng)價(jià)

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

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

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

5 結(jié)論

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