任志剛 梁永勝 張愛民 龐蓓

分布估計(jì)算法(Estimation of distribution algorithm,EDA)是一類典型的基于模型的進(jìn)化算法.與基于交叉和變異等遺傳操作的其他進(jìn)化算法相比,EDA具有較強(qiáng)的理論基礎(chǔ),而且可以成功求解大量不同類型的連續(xù)和離散優(yōu)化問題,近年來一直是進(jìn)化計(jì)算領(lǐng)域的研究熱點(diǎn)[1?3].

本文重點(diǎn)研究面向連續(xù)問題的EDA,這類算法通常采用高斯概率模型(Gaussian probability model,GPM)描述優(yōu)解的分布.根據(jù)對(duì)各變量之間相關(guān)關(guān)系的處理方式,高斯EDA(Gaussian EDA,GEDA)可以分為變量無關(guān)的EDA、部分變量相關(guān)的EDA、全變量相關(guān)的EDA,其代表性算法分別為PBILc(Population based incremental learning)[1]和UMDAc(Univariate marginal distribution algorithm)[1,4]、EGNA(Estimation of Gaussian networks algorithm)[4?5]、EMNAg(Estimation of multivariate normal density algorithm)[1].

GPM為EDA的理論分析提供了諸多方便,但同時(shí)也有一些不足,其中最顯著的一點(diǎn)是,直接由常用的極大似然估計(jì)(Maximum likelihood estimation,MLE)計(jì)算出的變量方差會(huì)快速減小,導(dǎo)致算法的探索能力急劇下降.已有研究通過保持各方差值至少為1[6]、將估計(jì)出的方差固定地放大一定倍數(shù)[7]、利用協(xié)方差矩陣(Covariance matrix,CM)的特征值修改方差[8]以及根據(jù)采樣解的改進(jìn)情況自適應(yīng)地調(diào)整方差[9?10]等策略來彌補(bǔ)這一不足.其中,Bosman等學(xué)者提出的自適應(yīng)方差縮放策略影響最為廣泛[10].他們建議當(dāng)算法在遠(yuǎn)離均值的位置找到更優(yōu)解時(shí)增大方差,而當(dāng)算法在連續(xù)多次迭代內(nèi)找不到更優(yōu)解時(shí)減小方差.除方差快速減小這一不利因素之外,與CM相對(duì)應(yīng)的概率密度橢球體(Probability density ellipsoid,PDE)的長軸還傾向于與目標(biāo)函數(shù)的改進(jìn)方向相垂直,這會(huì)大大降低GEDA的搜索效率[11?12].Cai等學(xué)者首次發(fā)現(xiàn)了這一現(xiàn)象,并將其與方差收縮問題合并處理,提出了基于概率分布交叉熵的自適應(yīng)方差縮放策略[11].Bosman等學(xué)者則提出了預(yù)期均值偏移策略,該策略嘗試采用兩組分別以預(yù)估均值和偏移均值為中心的較優(yōu)解來估計(jì)CM,從而改變PDE長軸的方向[12].將該策略與前期提出的自適應(yīng)方差縮放策略相結(jié)合后,Bosman等學(xué)者構(gòu)建了一種稱為AMaLGaM的有效EDA[13].

除上述研究之外,文獻(xiàn)[14?16]分別通過引入混沌變異算子、正則化技術(shù)、多群體–多模型方法來增強(qiáng)GPM 對(duì)不同問題的適應(yīng)性;文獻(xiàn)[17?19]則放棄GPM,分別采用直方圖模型、粒子濾波、Copula函數(shù)來估計(jì)優(yōu)解的概率分布;文獻(xiàn)[20]在直方圖模型的基礎(chǔ)上,進(jìn)一步利用局部搜索技術(shù)提升EDA的優(yōu)化性能;文獻(xiàn)[21]則嘗試采用有監(jiān)督學(xué)習(xí)方法估計(jì)優(yōu)解的條件概率分布,并借助Gibbs采樣技術(shù)提高搜索效率.這些研究工作在改進(jìn)EDA性能的同時(shí),也將算法模型復(fù)雜化,并引入了較多難以設(shè)置的自由參數(shù).

本文在分析傳統(tǒng)GEDA性能弱化原因的基礎(chǔ)上,提出一種簡單高效的GEDA.該算法在每次迭代中首先根據(jù)選擇出的優(yōu)秀樣本預(yù)估出一加權(quán)均值,然后顯式地利用預(yù)估均值的目標(biāo)函數(shù)值將其偏移至一個(gè)更有希望的解區(qū)域中,最后根據(jù)所選優(yōu)秀樣本關(guān)于偏移后均值的二階混合矩來估計(jì)CM.這一簡單操作可以在不增大算法計(jì)算量的前提下,自適應(yīng)地調(diào)整PDE的位置、大小和長軸方向,使之盡可能與當(dāng)前解區(qū)域的結(jié)構(gòu)特征相契合,從而提高算法的搜索效率.根據(jù)CM 的計(jì)算方式,本文將所提算法命名為基于一般二階混合矩的高斯分布估計(jì)算法(General-second-order-mixed-moment based GEDA,GSM-GEDA).

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

作為一種基于模型的進(jìn)化算法,EDA假設(shè)待解決問題的優(yōu)解服從某種概率分布,并利用根據(jù)當(dāng)前群體中的較優(yōu)解估計(jì)出的概率分布來產(chǎn)生下一代群體,從而驅(qū)動(dòng)算法進(jìn)化.基本EDA的步驟如下:

步驟1.設(shè)置算法參數(shù),初始化群體.

步驟2.根據(jù)目標(biāo)函數(shù)評(píng)價(jià)當(dāng)前群體中各個(gè)解的質(zhì)量.

步驟3.根據(jù)選擇規(guī)則選出優(yōu)秀樣本集合.

步驟4.根據(jù)優(yōu)秀樣本集估計(jì)概率分布模型.

步驟5.根據(jù)概率分布模型進(jìn)行采樣,構(gòu)建新群體.

步驟6.更新獲得的最優(yōu)解并判斷是否滿足終止條件.若滿足,則輸出最優(yōu)結(jié)果;否則,轉(zhuǎn)至步驟2.

連續(xù)型EDA通常采用GPM描述優(yōu)解的分布.對(duì)于n維的隨機(jī)列向量x,GPM的聯(lián)合概率密度函數(shù)可以表示為

其中,μ和C分別表示x的均值和CM.在每次迭代中,GEDA通常根據(jù)截?cái)噙x擇規(guī)則選出優(yōu)秀樣本集S,并采用MLE來估計(jì)μ和C:

EMNAg算法采用式(1)～(3)所示的GPM及參數(shù)估計(jì)方法來綜合描述所有變量之間的相關(guān)關(guān)系.文獻(xiàn)[22]的研究表明,諸如EGNA等基于高斯圖的、部分變量相關(guān)的EDA可以納入到全變量相關(guān)的EDA框架之下.UMDAc和PBILc則通過忽略各變量間的相關(guān)關(guān)系,換取了具有較少參數(shù)的對(duì)角型CM.

上述三類GEDA針對(duì)各類型問題的求解性能雖有不同,但它們都采用MLE估計(jì)概率分布參數(shù),由此具有兩個(gè)共性特點(diǎn):1)各變量的方差會(huì)隨著算法迭代而快速減小[6,7,9?11];2)與CM 相對(duì)應(yīng)的PDE的長軸傾向于與目標(biāo)函數(shù)的改進(jìn)方向相垂直[11?13].圖1給出了該現(xiàn)象的示意圖,造成該現(xiàn)象的主要原因是,GEDA在每次迭代中選出的優(yōu)秀樣本主要分布在由目標(biāo)函數(shù)等值線切割原PDE所形成的半橢球體內(nèi).該半橢球體的長軸平行于目標(biāo)函數(shù)等值線;相應(yīng)地,根據(jù)半橢球體內(nèi)的優(yōu)秀樣本以及MLE新估計(jì)出的PDE的長軸也平行于目標(biāo)函數(shù)等值線,即傾向于與目標(biāo)函數(shù)的改進(jìn)方向相垂直.另一方面,該半橢球體內(nèi)靠近原PDE中心的樣本較多,而遠(yuǎn)離原PDE中心的樣本較少,那么根據(jù)這些樣本新估計(jì)出的PDE自然會(huì)發(fā)生收縮現(xiàn)象.傳統(tǒng)GEDA的這種特性大大降低了算法的搜索效率,導(dǎo)致算法即使在斜坡型解區(qū)域中也可能早熟收斂[9].

2 基于一般二階混合矩的高斯分布估計(jì)算法(GSM-GEDA)

在GEDA中,PDE的位置、大小和長軸方向分別決定了算法的搜索中心、范圍和主要搜索方向.我們期望PDE位于易于發(fā)現(xiàn)更優(yōu)解的解區(qū)域中,其大小能夠根據(jù)當(dāng)前解區(qū)域的結(jié)構(gòu)特征自適應(yīng)地變化,其長軸方向與目標(biāo)函數(shù)的改進(jìn)方向相一致.GSMGEDA通過修改均值和CM的估計(jì)方法來實(shí)現(xiàn)這一目的.

圖1 傳統(tǒng)GEDA中PDE的變化示意圖Fig.1 Schematic for the change of PDE of traditional GEDA

2.1 均值估計(jì)方法

在每次迭代中,為了盡可能獲得一個(gè)有前途的搜索中心,GSM-GEDA根據(jù)如下兩個(gè)步驟估計(jì)均值:

1)采用加權(quán)樣本預(yù)估均值.由式(2)估計(jì)出的均值實(shí)際上是優(yōu)秀樣本的算術(shù)平均,如果對(duì)較優(yōu)樣本賦予較大權(quán)重則有利于改進(jìn)所估計(jì)均值的質(zhì)量.具體地,GSM-GEDA首先根據(jù)下式為GPM預(yù)估出一均值:

其中,S(i)表示集合S中第i個(gè)最優(yōu)解.由式(4)可知,S(i)的權(quán)重與其排序的對(duì)數(shù)值成反比;排序越靠前,其權(quán)重越大.數(shù)值測(cè)試表明,在大多數(shù)情況下都優(yōu)于.

2)沿目標(biāo)函數(shù)的改進(jìn)方向偏移預(yù)估均值.具體為:

其中,t表示第t次迭代中偏移后的均值;表示當(dāng)前預(yù)估均值t與上次迭代中偏移后均值之間的差異,它反映了算法的進(jìn)化方向;f(·)表示需要極小化的目標(biāo)函數(shù).通過顯式地比較與可以獲得f(·)的一個(gè)改進(jìn)方向.若優(yōu)于式(6)嘗試沿的方向?qū)⑵浦疗淠康氖前l(fā)揮算法的搜索慣性,提高搜索效率,其中的ηf稱為前向偏移系數(shù);最終能被接受的前提條件是相反地,若t差于式(6)則嘗試沿的反方向?qū)⑵浦疗淠康氖羌皶r(shí)修正算法的進(jìn)化方向,使其與目標(biāo)函數(shù)的改進(jìn)方向相一致,其中ηb稱為反向偏移系數(shù);也僅在優(yōu)于的情況下才會(huì)被最終接受.當(dāng)進(jìn)行反向偏移時(shí),一個(gè)合理的設(shè)置是允許最遠(yuǎn)偏移至因此0＜ηb≤1;另一方面,大量測(cè)試表明,當(dāng)ηf≥1時(shí),可以前向偏移至一理想位置.綜合以上兩個(gè)因素,一般可以設(shè)置ηb=1/ηf.第2.2節(jié)將理論分析ηf對(duì)算法性能的影響;第3.1節(jié)將實(shí)驗(yàn)測(cè)試ηf對(duì)算法最終求解質(zhì)量的影響,并給出取值方案.

2.2 協(xié)方差矩陣估計(jì)方法

GEDA根據(jù)優(yōu)秀樣本估計(jì)CM 的本質(zhì)目的并不是準(zhǔn)確獲得樣本自身的分布特征,而是希望利用這些樣本為下一次迭代確定一個(gè)合理的搜索范圍和方向.由第1節(jié)的分析可知,與式(3)所示估計(jì)相對(duì)應(yīng)的PDE的大小和長軸方向是不理想的.另一方面,由概率論中關(guān)于矩的知識(shí)可知,隨機(jī)向量的CM 即為它的二階混合中心矩.那么在樣本不變的前提下,改變矩中心是調(diào)整PDE大小和長軸方向的一個(gè)簡單方法.對(duì)于GSM-GEDA來說,一個(gè)自然選擇是采用偏移后的均值代替式(3)中的MLE均值,即:

上式表示對(duì)以偏移后的均值這一一般位置為中心的二階混合矩的估計(jì).

由式(5)和(6)可知,不差于;由式(4)可知,通常優(yōu)于;相應(yīng)地,一般會(huì)優(yōu)于.那么,代表了目標(biāo)函數(shù)的一個(gè)改進(jìn)方向.與式(3)所示估計(jì)相比,式(7)給出的估計(jì)可以隨的改變而自適應(yīng)地調(diào)整PDE的大小(體積),并且可以使PDE的長軸方向趨近于目標(biāo)函數(shù)的改進(jìn)方向().為此給出以下定理和推論:

定理1.對(duì)于選定的優(yōu)秀樣本,若那么由所確定的PDE的體積不小于由確定的PDE的體積.

證明.由高斯分布的性質(zhì)可知,PDE的各個(gè)軸的方向分別與CM的各特征向量相一致,而各半軸長度ad(d=1,2,···,n)由CM 的相應(yīng)特征值λd確定:另一方面,由文獻(xiàn)[23]可知,PDE的體積與各半軸長度的乘積成正比.記的特征值分別為那么定理1成立的充要條件是,當(dāng)為證明這一點(diǎn),對(duì)做如下變化:

很明顯,矩陣的秩1修正[24].文獻(xiàn)[25]中的引理1.4對(duì)秩1修正后對(duì)角型矩陣的特征多項(xiàng)式進(jìn)行了討論,根據(jù)該引理可以推得也即的特征多項(xiàng)式:

其中,I表示相應(yīng)階數(shù)的單位陣.令式(10)中的λ=0,可得:

推論1.對(duì)于選定的優(yōu)秀樣本,若且樣本數(shù)量大于問題維數(shù)(即|S|＞n),那么由所確定的PDE的體積將大于由所確定的PDE的體積.

推論2.對(duì)于選定的優(yōu)秀樣本,到的馬氏距離越大,那么由所確定的PDE的體積越大.

證明.重新考慮式(11):證.

由上式可知,越大,越大.由此得

注1.推論1從理論上給出了保證由所確定的PDE的體積大于由所確定的PDE的體積的充要條件.由上文分析可知,GSM-GEDA在每次迭代中采用的通常不等于且優(yōu)于;另一方面,GSM-GEDA及傳統(tǒng)GEDA通常都設(shè)置群體規(guī)模遠(yuǎn)大于問題維數(shù),那么從中選出的優(yōu)秀樣本的數(shù)量一般都滿足|S|＞n.由此可知,GSM-GEDA能夠使推論1成立.這意味著,對(duì)于相同的選定樣本,GSM-GEDA的探索能力強(qiáng)于傳統(tǒng)GEDA.

注 2.推論2告訴我們,若要增強(qiáng)GSMGEDA 的探索能力,只需增大從到的馬氏距離也即增大對(duì)于選定的優(yōu)秀樣本,是固定的.若要增大要求增大的各分量d(d=1,2,···,n),即在矩陣的各特征向量上的投影.根據(jù)式(6)可知,在優(yōu)秀樣本選定的情況下,通過調(diào)整偏移系數(shù)ηf可以改變位置,進(jìn)而調(diào)整的大小.ηf越大,傾向于增大,那么GSM-GEDA的探索能力會(huì)相應(yīng)增強(qiáng).

定理2.對(duì)于選定的優(yōu)秀樣本,若,那么與由所確定的PDE長軸之間的夾角不大于其與由所確定的PDE長軸之間的夾角.

將n代入式(10)可知:

進(jìn)一步有

即由此可知,若定理2成立.

注3.在上述證明過程中,對(duì)于情況1可以推得依然分別是的特征值、特征向量;僅當(dāng)較小,對(duì)其他特征值的調(diào)整幅度較小,使得仍為的主特征值時(shí),才有對(duì)于情況2,僅當(dāng)即時(shí),才有因此,在絕大部分情況下,由于PDE的長軸,即CM的主特征向量決定了GEDA的主要搜索方向,那么定理2意味著,在采用作為CM的估計(jì)之后,GEDA的主要搜索方向更靠近目標(biāo)函數(shù)的改進(jìn)方向,因此更容易找到較優(yōu)解.

2.3 GSM-GEDA的步驟

GSM-GEDA在基本EDA的框架之下,采用GPM描述優(yōu)解的分布,并采用了一種新的GPM參數(shù)估計(jì)方法,其具體步驟如下:

步驟1.設(shè)置算法參數(shù),包括群體規(guī)模m、優(yōu)秀樣本比例系數(shù)τ以及前向偏移系數(shù)ηf;記迭代次數(shù)t=1,并采用偽均勻分布隨機(jī)生成m個(gè)解,初始化群體Mt.

步驟2.根據(jù)目標(biāo)函數(shù)f(·)評(píng)價(jià)Mt中各個(gè)解的質(zhì)量.

步驟3.根據(jù)截?cái)噙x擇規(guī)則,從Mt中選出前個(gè)優(yōu)解,賦予優(yōu)秀樣本集St.

步驟4.根據(jù)優(yōu)秀樣本集St估計(jì)概率分布參數(shù):1)根據(jù)式(4)計(jì)算加權(quán)的預(yù)估均值t;2)根據(jù)式(5)和(6)對(duì)t進(jìn)行偏移,獲得最終的估計(jì)均值t;3)根據(jù)式(7)估計(jì)協(xié)方差矩陣t.

步驟5.根據(jù)高斯概率模型新生成m?2個(gè)解,并記由這些解構(gòu)成的集合為采用精英策略更新群體

步驟6.更新t=t+1,判斷是否滿足終止條件.若滿足,則輸出最優(yōu)結(jié)果;否則,轉(zhuǎn)至步驟2.

其中,步驟5采用常用的精英策略將當(dāng)前群體中的最優(yōu)個(gè)體保留到下一代群體中.此外,經(jīng)過顯式評(píng)價(jià)后的t也可以看作一個(gè)完整的解樣本,并且其解質(zhì)量通常較高,因此也將它保留到下一代群體中.

GSM-GEDA與傳統(tǒng)GEDA的區(qū)別主要體現(xiàn)在步驟4中的概率分布參數(shù)估計(jì)方法.從式 (4)～(7)可以看出,新提出的均值、CM 估計(jì)方法的計(jì)算時(shí)間復(fù)雜度分別為 O(τmn)=O(mn)、O(τmn2)=O(mn2),這與常用的 MLE的計(jì)算復(fù)雜度相同.這意味著GSM-GEDA可以以相同的計(jì)算復(fù)雜度獲得具有更好理論性質(zhì)的GPM,即可以避免PDE快速收縮,從而保證算法具有適度的探索能力;并且可以使PDE的長軸方向趨近于目標(biāo)函數(shù)的改進(jìn)方向,進(jìn)而提高算法的搜索效率.

3 實(shí)驗(yàn)與分析

為了評(píng)估GSM-GEDA的性能,采用IEEE CEC 2005標(biāo)準(zhǔn)函數(shù)庫[27]中的前14個(gè)函數(shù)對(duì)其進(jìn)行了測(cè)試.其中,f1～f5是單模函數(shù),f6～f12是基本的多模函數(shù),f13～f14是擴(kuò)展的多模函數(shù).這些函數(shù)大多都經(jīng)過了旋轉(zhuǎn)、偏移操作,分別使得各變量之間相互關(guān)聯(lián)、最優(yōu)解偏離搜索中心,從而保證函數(shù)的優(yōu)化難度.在實(shí)驗(yàn)中,所有函數(shù)的維數(shù)都設(shè)置為30,每個(gè)函數(shù)在每種算法上獨(dú)立測(cè)試25次,每次測(cè)試均以完成300000次目標(biāo)函數(shù)評(píng)價(jià)作為終止條件,并采用所獲優(yōu)解與實(shí)際最優(yōu)解之間的差值(函數(shù)誤差值)在25次測(cè)試中的均值和標(biāo)準(zhǔn)差來衡量算法性能.

3.1 參數(shù)影響及其設(shè)置

GSM-GEDA一共包括3個(gè)參數(shù),即群體規(guī)模m、優(yōu)秀樣本比例系數(shù)τ以及前向偏移系數(shù)ηf.對(duì)于m和τ這兩個(gè)常規(guī)參數(shù),文獻(xiàn)中已進(jìn)行了較多研究[1,13],本文將其設(shè)置為常規(guī)值m=1200、τ=0.35.本節(jié)重點(diǎn)考察新參數(shù)ηf對(duì)GSM-GEDA的性能的影響.由第2節(jié)可知,ηf決定了預(yù)估均值eμ的偏移程度,從而改變PDE的中心位置、大小和長軸方向,最終影響GSM-GEDA的性能.

圖2以函數(shù)f2、f10為例,給出了當(dāng)ηf以0.25為間隔從0.5增大到3.5時(shí),GSM-GEDA的性能變化情況.從圖中可以看出,當(dāng)ηf在0.5～3.5這么一個(gè)較大的范圍內(nèi)變化時(shí),GSM-GEDA的性能變化并不劇烈.特別地,對(duì)于f2,GSM-GEDA求得的解總是非常接近最優(yōu)解.這說明GSM-GEDA的優(yōu)化性能關(guān)于ηf的魯棒性較強(qiáng).另一方面,在不考慮隨機(jī)因素的情況下,GSM-GEDA的性能總是隨著ηf的增大先變好后變差.對(duì)于f2這一單模函數(shù),當(dāng)ηf≈1.0時(shí),GSM-GEDA取得較優(yōu)結(jié)果;對(duì)于多模函數(shù)f10,當(dāng)ηf≈2.75時(shí),GSM-GEDA的表現(xiàn)較好.實(shí)驗(yàn)表明,上述結(jié)論基本上也適用于其他測(cè)試函數(shù).對(duì)于待優(yōu)化的一般黑箱函數(shù),并沒有先驗(yàn)信息確定其為單模還是多模.為兼顧兩類函數(shù)的求解質(zhì)量,我們建議在1.0～2.75之間為ηf取值;本文選取ηf=2.0.

圖2 GSM-GEDA的性能隨ηf的變化情況Fig.2 The performance variation of GSM-GEDA with regard to ηf

3.2 均值?協(xié)方差矩陣估計(jì)方法的有效性分析

第2節(jié)理論證明了新提出的均值–協(xié)方差矩陣估計(jì)方法可以增大PDE的體積,使PDE的長軸方向趨近于目標(biāo)函數(shù)的改進(jìn)方向,本節(jié)將通過數(shù)值實(shí)驗(yàn)驗(yàn)證這一點(diǎn).實(shí)驗(yàn)設(shè)置如下:在GSM-GEDA的每次迭代中,除了根據(jù)式(4)～(7)所示的新方法估計(jì)CM 之外,還利用相同的優(yōu)秀樣本,根據(jù)式(2)～(3)所示的傳統(tǒng)MLE方法估計(jì)CM,從而滿足定理1和2的限定條件.為描述方便,將這種依附于GSM-GEDA但采用傳統(tǒng)估計(jì)方法的算法稱為quasi-GSM-GEDA.此外,還將EMNAg[1]作為對(duì)比算法.除參數(shù)估計(jì)方法之外,EMNAg的其他設(shè)置與GSM-GEDA完全相同.

圖3和4以函數(shù)f2、f10為例,分別給出了各算法的PDE的長軸長度、長軸與目標(biāo)函數(shù)改進(jìn)方向之間的夾角余弦(簡記為cos(A1))隨迭代次數(shù)的變化情況.從圖3中可以看出,GSM-GEDA和quasi-GSM-GEDA的PDE的長軸長度都隨迭代次數(shù)的增大而逐漸減小,但前者的長度始終不小于后者,該現(xiàn)象在前期迭代過程中尤為明顯.實(shí)際上,上述結(jié)論對(duì)于PDE的其他軸也是成立的,這與定理1所述內(nèi)容一致.從圖4中可以看出,GSM-GEDA的cos(A1)值始終不小于quasi-GSM-GEDA的相應(yīng)值,這說明GSM-GEDA的PDE的長軸與之間的夾角不大于quasi-GSM-GEDA的相應(yīng)夾角,這與定理2所述內(nèi)容一致.

圖3 長軸長度隨迭代次數(shù)的變化情況Fig.3 The variation of long axis length with regard to iteration times

圖4 長軸與目標(biāo)函數(shù)改進(jìn)方向之間的夾角余弦隨迭代次數(shù)的變化情況Fig.4The variation of the cosine value of the angle between long axis and with regard to iteration times

圖5 長軸與最速下降方向之間的夾角余弦隨迭代次數(shù)的變化情況Fig.5 The variation of the cosine value of the angle between long axis and the steepest descent direction with regard to iteration times

圖6 函數(shù)誤差值隨迭代次數(shù)的變化情況Fig.6 The variation of the function error value with regard to iteration times

從圖3中還可以看出,與EMNAg相比,GSMGEDA的PDE的長軸長度在前期迭代過程中保持了較大值,這有利于算法進(jìn)行探索性搜索;在中后期迭代過程中,GSM-GEDA的PDE的長軸收縮到一個(gè)較小的尺度范圍內(nèi),這有利于算法進(jìn)行精細(xì)搜索.為了進(jìn)一步說明GSM-GEDA與EMNAg的性能差異,圖5和6分別給出了兩算法的PDE的長軸與目標(biāo)函數(shù)的最速下降方向(即從PDE的中心指向最優(yōu)解的方向)之間的夾角余弦(簡記為cos(A2))、所求得的最小函數(shù)誤差值隨迭代次數(shù)的變化情況.從圖5中可以看出,對(duì)于f2這一單模函數(shù),GSMGEDA的cos(A2)值始終大于EMNAg的相應(yīng)值,說明GSM-GEDA能夠探測(cè)到較好的搜索方向.從圖6中可以看出,GSM-GEDA在經(jīng)過大概200次迭代后基本上獲得了f2的最優(yōu)解;EMNAg在經(jīng)過大概15次迭代后便早熟收斂,無法獲得理想解.對(duì)于多模函數(shù)f10,GSM-GEDA在中前期迭代過程中的cos(A2)值也大于EMNAg的相應(yīng)值,盡管兩算法都陷入了局部優(yōu)解,但GSM-GEDA獲得的終解遠(yuǎn)優(yōu)于EMNAg.

圖6還給出了AMaLGaM[13]獲得的最小函數(shù)誤差值的進(jìn)化情況.AMaLGaM利用預(yù)期均值偏移策略和自適應(yīng)方差縮放策略改進(jìn)了傳統(tǒng)GEDA,是當(dāng)前性能最為優(yōu)越的EDA之一.從圖6中可以看出,AMaLGaM和GSM-GEDA在不同程度上消弱了EMNAg的早熟收斂問題.在給定的目標(biāo)函數(shù)評(píng)價(jià)次數(shù)內(nèi),GSM-GEDA求得的f2、f10的終解分別優(yōu)于、接近于AMaLGaM所得結(jié)果,其收斂速度也快于AMaLGaM.

3.3 與其他算法的比較

為了綜合衡量GSM-GEDA的性能,將其與 6種已有算法進(jìn)行了比較,包括 EMNAg[1]、AMaLGaM[13]、 CMA-ES[28]、 CLPSO[29]、CoBiDE[30]以及MPEDE[31].選擇這6種算法作為對(duì)比算法的原因在于:EMNAg和AMaLGaM分別是傳統(tǒng)GEDA和先進(jìn)GEDA的典型代表,可以為衡量GSM-GEDA的性能提供基準(zhǔn);CMAES、CLPSO、CoBiDE分別是進(jìn)化策略算法、粒子群算法、差分進(jìn)化算法的代表算法,并被多次用作對(duì)比算法,而且CoBiDE中的交叉算子也涉及了CM的估計(jì)問題;MPEDE是一種新近提出的差分進(jìn)化算法,一定程度上反映了當(dāng)前函數(shù)智能優(yōu)化方面的發(fā)展水平.

為了保證比較的公平性,EMNAg、AMaLGaM以及GSM-GEDA的參數(shù)m、τ取為相同值,AMaLGaM 也選用全變量相關(guān)的GPM 模型;AMaLGaM的其余參數(shù)以及其他4種算法的參數(shù)均按照相應(yīng)的原文獻(xiàn)進(jìn)行取值.表1給出了各算法最終所獲優(yōu)解的函數(shù)誤差值在25次獨(dú)立測(cè)試中的均值和標(biāo)準(zhǔn)差,表中還采用了下式所示的Cohen′sd效應(yīng)量[32]衡量GSM-GEDA與其他6種算法之間的性能差異:

其中,分別表示樣本集a的均值、標(biāo)準(zhǔn)差、樣本數(shù)量.通常當(dāng)|d|＜0.2時(shí),認(rèn)為兩樣本集的均值差異較小[32],這里意味著兩個(gè)被測(cè)算法的性能無顯著差異,在表1中用符號(hào)“≈”標(biāo)識(shí).反過來,若根據(jù)效應(yīng)量判斷出某算法顯著優(yōu)于或差于GSM-GEDA,則在表1中分別用符號(hào)“+”、“?”來標(biāo)識(shí).

從表1中可以看出,對(duì)于單模函數(shù)f1～f5,GSM-GEDA的性能比較理想.盡管針對(duì)f1、f2的優(yōu)化結(jié)果差于差分進(jìn)化算法,但其獲得的解也已充分接近最優(yōu)解.對(duì)于基本的多模函數(shù)f6～f12,GSM-GEDA在3個(gè)函數(shù)上的性能優(yōu)于其他所有算法;特別地,它可以獲得f7、f11的最優(yōu)解.對(duì)于f6、f9,3種EDA的表現(xiàn)都不太理想;對(duì)于f8,所有被測(cè)算法的性能差異不大;對(duì)于f10,GSM-GEDA的表現(xiàn)僅次于AMaLGaM,優(yōu)于其他5種算法.對(duì)于擴(kuò)展的多模函數(shù),GSM-GEDA在f13上的表現(xiàn)與CoBiDE接近,僅次于CLPSO;在f14上的表現(xiàn)優(yōu)于其他所有算法.根據(jù)表1最后一行的統(tǒng)計(jì)結(jié)果可知,GSM-GEDA 分別在14、9、12、9、9、9個(gè)函數(shù)上的性能顯著優(yōu)于EMNAg、AMaLGaM、CMAES、CLPSO、CoBiDE、MPEDE,表現(xiàn)出良好的全局尋優(yōu)能力.

表1 7種算法最終求得的函數(shù)誤差值的均值和標(biāo)準(zhǔn)差Table 1 The mean and standard deviation of the function error values obtained by 7 algorithms

4 結(jié)論

概率密度橢球體(PDE)的位置、大小和長軸方向是影響高斯分布估計(jì)算法(GEDA)性能的關(guān)鍵.本文在分析傳統(tǒng)GEDA性能弱化原因的基礎(chǔ)上,提出了一種基于一般二階混合矩的高斯分布估計(jì)算法(GSM-GEDA).該算法以沿目標(biāo)函數(shù)改進(jìn)方向偏移后的加權(quán)均值作為協(xié)方差矩陣(二階混合中心矩)的矩中心,一方面將PDE引導(dǎo)至一個(gè)更有希望的解區(qū)域;另一方面可以自適應(yīng)地增大PDE的大小,并使PDE的長軸方向趨近于目標(biāo)函數(shù)的改進(jìn)方向.理論分析和數(shù)值實(shí)驗(yàn)均證明了上述結(jié)論的正確性.此外,在14個(gè)標(biāo)準(zhǔn)函數(shù)上的數(shù)值測(cè)試還表明,GSM-GEDA的求解質(zhì)量優(yōu)于現(xiàn)有的GEDA以及其他一些先進(jìn)的進(jìn)化算法.下一步工作將研究設(shè)計(jì)更為系統(tǒng)化的均值偏移策略,并在實(shí)際的復(fù)雜優(yōu)化問題中檢驗(yàn)GSM-GEDA的有效性.

References

1 Larranaga P,Lozano J A.Estimation of Distribution Algorithms:A New Tool for Evolutionary Computation.New York,USA:Springer,2001.57?100

2 Hauschild M,Pelikan M.An introduction and survey of estimation of distribution algorithms.Swarm and Evolutionary Computation,2011,1(3):111?128

3 Wang Sheng-Yao,Wang Ling,Fang Chen,Xu Ye.Advances in estimation of distribution algorithms.Control and Deci-sion,2012,27(7):961?966,974(王圣堯,王凌,方晨,許燁.分布估計(jì)算法研究進(jìn)展.控制與決策,2012,27(7):961?966,974)

4 Larraaga P,Etxeberria R,Lozano J A,Pe?na J M.Optimization in continuous domains by learning and simulation of Gaussian networks.In:Proceedings of 2000 Genetic and Evolutionary Computation Conference.Las Vegas,USA:Morgan Kaufmann,2000.201?204

5 Lu Q,Yao X.Clustering and learning Gaussian distribution for continuous optimization.IEEE Transactions on Systems,Man,and Cybernetics,Part C:(Applications and Reviews),2005,35(2):195?204

6 Yuan B,Gallagher M.On the importance of diversity maintenance in estimation of distribution algorithms.In:Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation.New York,USA:ACM,2005.719?726

7 Po?k P.Preventing premature convergence in a simple EDA via global step size setting.Parallel Problem Solving from Nature—PPSN X.Lecture Notes in Computer Science.Berlin,Heidelberg,Germany:Springer-Verlag,2008:.549?558

8 Dong W S,Yao X.Uni fied Eigen analysis on multivariate Gaussian based estimation of distribution algorithms.Information Sciences,2008,178(15):3000?3023

9 Ocenasek J,Kern S,Hansen N,Koumoutsakos P.A mixed bayesian optimization algorithm with variance adaptation.Parallel Problem Solving from Nature—PPSN VIII.Lecture Notes in Computer Science.,Berlin,Heidelberg,Germany:Springer-Verlag,2004.352?361

10 Bosman P A N,Grahl J,Rothlauf F.SDR:a better trigger for adaptive variance scaling in normal EDAs.In:Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation.New York,USA:ACM,2007.492?499

11 Cai Y P,Sun X M,Xu H,Jia P F.Cross entropy and adaptive variance scaling in continuous EDA.In:Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation.New York,USA:ACM,2007.609?616

12 Bosman P A N,Grahl J,Thierens D.Enhancing the performance of maximum-likelihood Gaussian EDAs using anticipated mean shift.Parallel Problem Solving from Nature—PPSN X.Lecture Notes in Computer Science.Berlin,Heidelberg,Germany:Springer-Verlag,2008:.133?143

13 Bosman P A N,Grahl J,Thierens D.Benchmarking parameter-free AMaLGaM on functions with and without noise.Evolutionary Computation,2013,21(3):445?469

14 Cheng Yu-Hu,Wang Xue-Song,Hao Ming-Lin.An estimation of distribution algorithm with diversity preservation.Acta Electronica Sinica,2010,38(3):591?597(程玉虎,王雪松,郝名林.一種多樣性保持的分布估計(jì)算法.電子學(xué)報(bào),2010,38(3):591?597)

15 Karshenas H,Santana R,Bielza C,Larra?naga P.Regularized continuous estimation of distribution algorithms.Applied Soft Computing,2013,13(5):2412?2432

16 Yang P,Tang K,Lu X F.Improving estimation of distribution algorithm on multi-modal problems by detecting promising areas.IEEE Transactions on Cybernetics,2015,45(8):1438?1449

17 Ding N,Zhou S D,Sun Z Q.Histogram-based estimation of distribution algorithm:a competent method for continuous optimization.Journal of Computer Science and Technology,2008,23(1):35?43

18 Zhang Jian-Hua,Zeng Jian-Chao.Estimation of distribution algorithm based on sequential importance sampling particle filters.Acta Electronica Sinica,2010,38(12):2929?2932(張建華,曾建潮.基于序貫重點(diǎn)采樣粒子濾波的分布估計(jì)算法.電子學(xué)報(bào),2010,38(12):2929?2932)

19 Wang Li-Fang,Zeng Jian-Chao,Hong Yi.Estimation of distribution algorithm modeling and sampling by means of Copula.Control and Decision,2011,26(9):1333?1337,1342(王麗芳,曾建潮,洪毅.利用Copula函數(shù)估計(jì)概率模型并采樣的分布估計(jì)算法.控制與決策,2011,26(9):1333?1337,1342)

20 Zhou A M,Sun J Y,Zhang Q F.An estimation of distribution algorithm with cheap and expensive local search.IEEE Transactions on Evolutionary Computation,2015,19(6):807?822)

21 Zhang Fang,Lu Hua-Xiang.General stochastic model for algorithm of distribution estimation with conditional probabilities and Gibbs sampling.Control Theory&Applications,2013,30(3):307?315(張放,魯華祥.利用條件概率和Gibbs抽樣技術(shù)為分布估計(jì)算法構(gòu)造通用概率模型.控制理論與應(yīng)用,2013,30(3):307?315)

22 Zhong Wei-Cai,Liu Jing,Liu Fang,Jiao Li-Cheng.Estimation of distribution algorithm based on generic Gaussian networks.Journal of Electronics and Information Technology,2005,27(3):467?470(鐘偉才,劉靜,劉芳,焦李成.建立在一般結(jié)構(gòu)Gauss網(wǎng)絡(luò)上的分布估計(jì)算法.電子與信息學(xué)報(bào),2005,27(3):467?470)

23 Zhao Hong.Areas(Volumes)ofn-dimension ellipsoid by quadratic curve(surface)enclosed.Mathematics in Practice and Theory,2013,43(10):279?282(趙虹.n元橢球面的判定及所圍橢球體的體積.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(10):279?282)

24 Bunch J R,Nielsen C P,Sorensen D C.Rank-one modi fication of the symmetric eigenproblem.Numerische Mathematik,1978,31(1):31?48

25 Yin Qing-Xiang.The inverse problem of rank-1 modi fication of real symmetric matrices.Journal of Nantong Institute of Technology(Natural Science),2003,2(4):11?14(殷慶祥.實(shí)對(duì)稱矩陣的秩1修正的特征反問題.南通工學(xué)院學(xué)報(bào)(自然科學(xué)版),2003,2(4):11?14)

26 Xie Ping-Min,Chen Tu-Hao.The positive de finiteness of the covariance matrix of continuous sample.Acta Scientiarum Naturalium Universitatis Sunyatseni,1990,29(1):102?104(謝平民,陳圖豪.連續(xù)型樣本協(xié)差陣的正定性.中山大學(xué)學(xué)報(bào)(自然科學(xué)版),1990,29(1):102?104)

27 Suganthan P N,Hansen N,Liang J J,Deb K,Chen Y P,Auger A,Tiwari S.Problem De finitions and Evaluation Criteria for the CEC 2005 Special Session on Real Parameter Optimization,Technical Report,Nanyang Technological University,Singapore,2005.

28 Hansen N,Ostermeier A.Completely derandomized selfadaptation in evolution strategies.Evolutionary Computation,2001,9(2):159?195

29 Liang J J,Qin A K,Suganthan P N,Baskar S.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions.IEEE Transactions on Evolutionary Computation,2006,10(3):281?295

30 Wang Y,Li H X,Huang T W,Li L.Differential evolution based on covariance matrix learning and bimodal distribution parameter setting.Applied Soft Computing,2014,18:232?247

31 Wu G H,Mallipeddi R,Suganthan P N,Wang R,Chen H K.Differential evolution with multi-population based ensemble of mutation strategies.Information Sciences,2016,329:329?345

32 Cohen J.Statistical Power Analysis for the Behavioral Sciences(Second Edition).Hillsdale,NJ:Lawrence Erlbaum Associates,1988.