李煥哲，吳志健，郭肇祿，劉會(huì)超，汪慎文

(1.武漢大學(xué)計(jì)算機(jī)學(xué)院軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430072; 2．河北地質(zhì)大學(xué)信息工程學(xué)院,河北石家莊 050031;3.江西理工大學(xué)理學(xué)院,江西贛州 341000)

?

基于兩階段搜索算法的多峰函數(shù)優(yōu)化

李煥哲1,2，吳志健1，郭肇祿3，劉會(huì)超1，汪慎文2

(1.武漢大學(xué)計(jì)算機(jī)學(xué)院軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北武漢 430072; 2．河北地質(zhì)大學(xué)信息工程學(xué)院,河北石家莊 050031;3.江西理工大學(xué)理學(xué)院,江西贛州 341000)

多峰優(yōu)化問(wèn)題需要搜索多個(gè)最優(yōu)值(全局最優(yōu)/局部最優(yōu)),這給傳統(tǒng)的優(yōu)化算法帶來(lái)很大程度上的挑戰(zhàn).本文提出了一種兩階段算法求解多峰優(yōu)化問(wèn)題.第一階段采用帶有鄰域變異策略的排擠差分演化算法進(jìn)行粗粒度搜索,在適應(yīng)度景觀上盡可能多的找到最優(yōu)解的大概位置.搜索一定代數(shù)之后,調(diào)用DMC聚類方法把搜索種群劃分成多個(gè)聚類,然后在每個(gè)聚類上調(diào)用協(xié)方差矩陣自適應(yīng)演化策略算法進(jìn)行精細(xì)搜索.另外,本文還提出搜索點(diǎn)補(bǔ)充策略用于平衡每個(gè)聚類的大小及增加算法初期的搜索能力.我們提出的方法和9個(gè)較新的經(jīng)典算法在兩個(gè)基準(zhǔn)測(cè)試集上進(jìn)行了大量對(duì)比測(cè)試,結(jié)果表明新算法是有效的,在大多數(shù)測(cè)試函數(shù)上都優(yōu)于其它算法.

排擠差分演化;協(xié)方差矩陣自適應(yīng)演化策略;多峰優(yōu)化;小生境;鄰域變異

1　引言

在實(shí)際工程實(shí)踐中,有一類問(wèn)題需要同時(shí)搜索多個(gè)最優(yōu)解,這類問(wèn)題通常被稱為多峰優(yōu)化問(wèn)題.例如模式匹配與識(shí)別、神經(jīng)元的結(jié)構(gòu)及權(quán)重優(yōu)化、模糊系統(tǒng)結(jié)構(gòu)和參數(shù)優(yōu)化等,都是多峰優(yōu)化的應(yīng)用場(chǎng)景.但是,傳統(tǒng)的演化算法[1,2]最初被設(shè)計(jì)用于搜索單一的全局最優(yōu)解,由于全局選擇方案的使用使得種群一般會(huì)收斂到單一最優(yōu)解.因此,傳統(tǒng)的演化算法并不適用于直接求解多峰優(yōu)化問(wèn)題.為了解決這個(gè)問(wèn)題,人們經(jīng)常把傳統(tǒng)的演化算法與某種技術(shù)(例如重啟技術(shù)、多種群技術(shù)、小生境技術(shù)、雙目標(biāo)技術(shù))相結(jié)合來(lái)求解多峰優(yōu)化問(wèn)題.在眾多的技術(shù)中,小生境(Niching)技術(shù)[3,4]是使用最為廣泛的技術(shù)之一.近幾十年中,在演化計(jì)算領(lǐng)域較為流行的小生境技術(shù)主要包括排擠技術(shù)、清除技術(shù)、適應(yīng)度共享技術(shù)、物種生成技術(shù)、聚類技術(shù)和受限的錦標(biāo)賽選擇技術(shù).

排擠技術(shù)(Crowding)由De Jong在1975年提出,用于求解多峰優(yōu)化問(wèn)題.2004年,Thomsen把排擠技術(shù)引入差分演化算法,稱之為CDE(Crowding Differential Evolution),來(lái)求解多峰優(yōu)化問(wèn)題.2012年,Qu等[5]把鄰域變異策略引入CDE,提出了NCDE算法.在NCDE(Neighborhood-based CDE)算法中,實(shí)驗(yàn)向量的生成被限制在一定數(shù)量的相似個(gè)體(以歐氏距離度量相似性)之間,通過(guò)這種方法,每個(gè)個(gè)體都向離它最近的更好個(gè)體演化并且降低了在不同小生境之間生成實(shí)驗(yàn)向量的概率,這有助于更好的保持種群的多樣性.NCDE算法有兩個(gè)主要優(yōu)點(diǎn):其一,它具有很強(qiáng)的全局搜索能力以及良好的保持種群多樣性的能力.其二,NCDE是一種隱式小生境技術(shù),在保持種群多樣性上對(duì)種群的大小要求不高,在極端情況下,甚至每個(gè)個(gè)體都可以獨(dú)立保持一個(gè)小生境.但是,NCDE這種低選擇壓力機(jī)制無(wú)疑會(huì)降低它的收斂速度.此外,為了提高局部搜索能力,交叉概率CR通常會(huì)被設(shè)置為一個(gè)較小的值,例如0.1,這有可能降低其在不可分問(wèn)題上的性能.

Hansen等在1996年首先把協(xié)方差矩陣自適應(yīng)(Covariance Matrix Adaptation,CMA)方法引入演化策略(Evolution Strategy,ES),以達(dá)到對(duì)搜索空間的任意可逆線性變換具有不變性和讓搜索分布形狀適應(yīng)問(wèn)題的實(shí)際適應(yīng)度景觀的目的.CMA-ES[7]算法克服了一些傳統(tǒng)演化算法相關(guān)的典型問(wèn)題,例如在嚴(yán)重縮放和高度不可分問(wèn)題上的低性能、對(duì)大種群的內(nèi)在需求以及種群的早熟問(wèn)題.然而,在其本質(zhì)上,CMA-ES算法是一種局部搜索算法,它具有很強(qiáng)的局部搜索能力,但在全局搜索能力上相對(duì)較弱[8].

基于以上的分析,為了彌補(bǔ)NCDE收斂速度慢及CMA-ES全局搜索能力弱的缺點(diǎn),我們提出了一種基于NCDE和CMA-ES的兩階段雜交算法.在第一階段充分發(fā)揮NCDE算法全局搜索能力強(qiáng)的特點(diǎn)進(jìn)行粗粒度搜索,盡可能多的定位最優(yōu)解的大概位置.在NCDE演化一定代數(shù)之后,調(diào)用DMC聚類方法識(shí)別當(dāng)前種群中形成的聚類.然后,根據(jù)識(shí)別出的聚類數(shù)量,相同數(shù)量的CMA-ES實(shí)例被生成,每一個(gè)CMA-ES實(shí)例對(duì)應(yīng)一個(gè)不同的聚類.每個(gè)聚類的最好搜索點(diǎn)作為CMA-ES的起始搜索點(diǎn),每個(gè)聚類與其最近相鄰聚類歐氏距離的六分之一作為CMA-ES的起始搜索步長(zhǎng),每個(gè)實(shí)例被獨(dú)立的運(yùn)行直到終止條件滿足.為了充分地利用剩余的函數(shù)評(píng)價(jià)次數(shù),算法采用了CMA-ES實(shí)例重新初始化和檔案存儲(chǔ)機(jī)制.

2　相關(guān)工作介紹

因?yàn)楸疚奶岢龅乃惴▽⒁玫綑z測(cè)多峰算法、NBC聚類、DMC聚類和CMA-ES算法,為了便于闡述提出的算法,下面簡(jiǎn)要介紹一下關(guān)于這幾種算法的相關(guān)工作.

2.1檢測(cè)多峰算法

檢測(cè)多峰算法(Detect Multimodal,DM)[9]用于檢測(cè)搜索空間中的兩個(gè)點(diǎn)是否跟蹤同一個(gè)最優(yōu)值,即驗(yàn)證這兩個(gè)點(diǎn)之間是否存在一個(gè)山谷.如果有一個(gè)山谷存在,這意味著它們沒(méi)有跟蹤同一個(gè)最優(yōu)值.假設(shè)求解最大化問(wèn)題,為了檢測(cè)兩個(gè)點(diǎn)之間是否存在山谷,需要生成一些內(nèi)部插值點(diǎn)并均勻地插入兩個(gè)測(cè)試點(diǎn)之間.如果所有插值點(diǎn)的函數(shù)值都高于兩個(gè)測(cè)試點(diǎn)的最小函數(shù)值,則可認(rèn)為這兩個(gè)測(cè)試點(diǎn)跟蹤同一個(gè)最優(yōu)值.DM方法消耗評(píng)價(jià)次數(shù),為了減少評(píng)價(jià)次數(shù)的消耗,插值點(diǎn)個(gè)數(shù)不適于設(shè)置過(guò)大的值,大多數(shù)情況下取值在2到10之間即可.

2.2NBC聚類

NBC(Nearest-Better Clustering)聚類方法由Preuss[8]提出,它被認(rèn)為是一個(gè)無(wú)參數(shù)的聚類方法.NBC方法通過(guò)連接每一個(gè)個(gè)體到離它最近且更好的鄰近個(gè)體來(lái)構(gòu)造一個(gè)生成樹(shù)(如果存在多個(gè)全局最優(yōu)值,則構(gòu)造成樹(shù)林),然后根據(jù)一系列規(guī)則修剪樹(shù)(移除個(gè)體之間的邊),最后修剪完成后的結(jié)果即為最終的聚類結(jié)果.第一個(gè)修剪規(guī)則是刪除那些比φ×μdist長(zhǎng)的邊,μdist代表所有邊的平均長(zhǎng)度,φ是一個(gè)權(quán)重系數(shù),通常被設(shè)置為2.然而這個(gè)規(guī)則在高維問(wèn)題中是不可靠的,通常會(huì)低估吸引盆的個(gè)數(shù).為了克服這個(gè)問(wèn)題,Preuss接著又提出了第二個(gè)修剪規(guī)則.當(dāng)一個(gè)個(gè)體具有3個(gè)或更多內(nèi)向邊時(shí),如果它的外向邊長(zhǎng)度大于β×μdist,則移除這個(gè)外向邊.μdist代表該個(gè)體所有內(nèi)向邊的中位數(shù),β為權(quán)重系數(shù).假定求解最大化問(wèn)題,nearest-better距離可被定義為dnb(xi,P)=min{dist(xi,xj)|f(xj)>f(xi)∧?xj∈P},f(·)代表評(píng)價(jià)函數(shù).

2.3DMC聚類

DMC(Detect-Multimodal Clustering)聚類方法由Stoean[9]提出,該方法采用檢測(cè)多峰算法進(jìn)行聚類識(shí)別.這種聚類方法不依賴于小生境半徑或個(gè)體的索引值,它依賴于適應(yīng)度景觀上的種群拓?fù)浣Y(jié)構(gòu)來(lái)劃分聚類,是一種基于種群拓?fù)浣Y(jié)構(gòu)的聚類方法.這一特性使得該方法的聚類結(jié)果可以是不規(guī)則形狀的.與NBC聚類方法相比,DMC方法需要指定內(nèi)部插值點(diǎn)的個(gè)數(shù)(參數(shù)IP),并且消耗額外的評(píng)價(jià)次數(shù)才能識(shí)別聚類.但是,如果設(shè)置一個(gè)合理的IP值,DMC方法能夠取得比NBC方法更準(zhǔn)確的聚類劃分結(jié)果.

2.4CMA-ES算法

CMA-ES是一種可用于求解非線性和非凸問(wèn)題,無(wú)需求導(dǎo)的隨機(jī)局部搜索算法.它采用基于統(tǒng)計(jì)的方法更新協(xié)方差矩陣和變異步長(zhǎng),以達(dá)到去隨機(jī)化的目的.基于協(xié)方差矩陣自適應(yīng)的學(xué)習(xí)機(jī)制使其對(duì)搜索空間的任意可逆線性變換具有不變性,對(duì)于病態(tài)的、高度不可分的問(wèn)題有優(yōu)秀的求解能力.CMA-ES有多種變體,最常見(jiàn)是(μw,λ)-CMA-ES,表示從λ個(gè)子個(gè)體中選擇最好的μ個(gè)個(gè)體作為父?jìng)€(gè)體生成下一代的加權(quán)均值向量m.新的搜索點(diǎn)通過(guò)隨機(jī)抽取一個(gè)多元正態(tài)分布來(lái)產(chǎn)生變異,其公式如下:

(1)

3　提出的算法

本節(jié)我們提出基于NCDE和CMA-ES的兩階段算法,在第一階段中分別采用NBC聚類和DMC聚類方法進(jìn)行聚類識(shí)別,以分析這兩種聚類方法的性能.分別稱這兩種新算法為NBC-CMA和DMC-CMA.

3.1NBC和DMC聚類性能比較

下面比較NBC和DMC在不考慮評(píng)價(jià)次數(shù)消耗的情況下,它們之間聚類性能的差異.參數(shù)IP(插入點(diǎn)數(shù)量)設(shè)置為10,兩種聚類方法在測(cè)試集1中的6個(gè)函數(shù)上進(jìn)行對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)考察兩種聚類算法隨演化代數(shù)的增加,它們聚類性能上的變化.在NCDE算法運(yùn)行過(guò)程中,每隔一定代數(shù)記錄聚類算法識(shí)別的聚類數(shù)目,對(duì)每個(gè)函數(shù)兩種方法分別獨(dú)立運(yùn)行50次,以平均找到的聚類數(shù)目作為比較對(duì)象,實(shí)驗(yàn)結(jié)果如圖1所示.

曲線上的數(shù)字代表該函數(shù)所對(duì)應(yīng)的種群大小,在函數(shù)F6(2D,3D)、F7(2D)和F12(5D)上,DMC表現(xiàn)出了更優(yōu)秀和穩(wěn)定的聚類性能.盡管在F7(2D)上NBC取得了更多的聚類數(shù)量,但是DMC的結(jié)果更接近F7(2D)函數(shù)真實(shí)的最優(yōu)值數(shù)量.在F12函數(shù)上,可以看到DMC識(shí)別的聚類數(shù)目多于NBC,并且它們的聚類性能在迭代初期都非常差,NBC的聚類性能接近于1.但隨著演化代數(shù)的增加,它們的聚類性能逐漸增強(qiáng).在沒(méi)有考慮評(píng)價(jià)次數(shù)的情況下,DMC的性能似乎優(yōu)于NBC算法.但是,在大種群的情況下DMC算法會(huì)消耗大量的評(píng)價(jià)次數(shù),因此在這種情況下DMC算法并不適于被頻繁使用.另外,從下面子圖1(c)中的函數(shù)F6可以看到,NCDE算法有優(yōu)秀的保持種群多樣性的能力,由DMC識(shí)別出的平均聚類數(shù)量幾乎接近于對(duì)應(yīng)的種群數(shù)量,這意味著種群中的每個(gè)個(gè)體幾乎獨(dú)立維護(hù)著一個(gè)不同的吸引盆.這是我們選擇NCDE算法作為第一階段算法的一個(gè)原因.

3.2搜索點(diǎn)補(bǔ)充策略

算法1SPRS策略

輸入:MINindi,C,R

1.從聚類集合C中分別選擇包含最多和最少搜索點(diǎn)數(shù)量的聚類cmax和cmin

2.如果cmin中的搜索點(diǎn)數(shù)目大于等于MINindi,則算法終止

3.從聚類cmax中選擇一對(duì)具有最大相似性(以歐氏距離度量)的搜索點(diǎn)

4.從被選擇的一對(duì)搜索點(diǎn)中選擇適應(yīng)度較低的搜索點(diǎn)pk,并把它加入到cmin中

5.根據(jù)公式(2)計(jì)算重新初始化半徑rreinit

6.在半徑rreinit內(nèi)均勻隨機(jī)地初始化搜索點(diǎn)pk

7.跳轉(zhuǎn)到step1

為了在演化初期增強(qiáng)搜索新峰的能力、平衡子種群的大小以及保持子種群的穩(wěn)定性,本節(jié)提出了搜索點(diǎn)補(bǔ)充策略(Search Point Replenishment Strategy,SPRS).它的主要思想是在演化初期增加小生境間搜索點(diǎn)的遷移,通過(guò)搜索點(diǎn)遷移來(lái)達(dá)到增大搜索空間和平衡子種群的目的.對(duì)SPRS的使用有以下幾點(diǎn)需要注意:(1)SPRS僅在算法的運(yùn)行初期有效,因?yàn)橹挥休^大的初始化半徑才可擴(kuò)大搜索空間以增加發(fā)現(xiàn)新最優(yōu)值的概率.相反,在算法后期,由于初始化半徑的收縮,調(diào)用SPRS已不能起到擴(kuò)大搜索空間的目的,對(duì)SPRS的調(diào)用變得沒(méi)有必要.(2)沒(méi)有必要每次迭代都調(diào)用SPRS,為了節(jié)省計(jì)算開(kāi)銷,可以以指數(shù)遞增方式調(diào)用SPRS.其偽代碼如算法1所示.

其中,MINindi是聚類中允許的最少搜索點(diǎn)數(shù)量,它可由種群數(shù)量除以聚類數(shù)目CN求得.聚類集合C和聚類數(shù)量CN由NBC或DMC方法獲得.R用于計(jì)算重新初始化半徑rreinit.

(2)

dn(cmin,C)計(jì)算cmin到離它最近的聚類之間的距離(兩個(gè)聚類中最好搜索點(diǎn)之間的距離),cmin代表包含最少搜索點(diǎn)的聚類.R為收縮因子用于限制重新初始化半徑的大小,如果演化代數(shù)小于4,R=1,否則R=iter-3,iter為當(dāng)前演化代數(shù).這樣做的目的是保證在算法運(yùn)行早期有更大的初始化半徑,隨著演化代數(shù)的增加,初始化半徑逐漸縮小.

圖2給出NBC-CMA算法在F7-2D函數(shù)上第32次迭代后,調(diào)用SPRS和不調(diào)用SPRS的種群快照結(jié)果.圖2(a)在搜索新的最優(yōu)值上明顯優(yōu)于圖2(b),而且圖2(a)上每個(gè)聚類的個(gè)體數(shù)量更均衡,這有利于保持聚類的穩(wěn)定性.

3.3提出的算法框架

在算法的迭代過(guò)程中,算法分兩個(gè)階段執(zhí)行,在第一階段執(zhí)行NCDE算法進(jìn)行粗粒度搜索,當(dāng)滿足一定條件時(shí)SPRS會(huì)被調(diào)用.首先,當(dāng)前聚類數(shù)量要大于問(wèn)題維度D;其次,只有當(dāng)前迭代次數(shù)等于閾值α?xí)r.這樣做可以使得對(duì)SPRS的調(diào)用隨演化的進(jìn)行逐漸減少.第三,為了進(jìn)一步限制對(duì)SPRS的調(diào)用,如果當(dāng)前消耗的評(píng)價(jià)次數(shù)大于等于總評(píng)價(jià)次數(shù)的五分之一時(shí),則不再調(diào)用SPRS.

α=(max(2,log2(D)))t,t=2,…,n

(3)

下面要解決何時(shí)轉(zhuǎn)入第二階段的問(wèn)題,我們引入了一個(gè)自適應(yīng)的啟發(fā)式參數(shù)θ,當(dāng)已消耗的評(píng)價(jià)次數(shù)大于等于閾值θ時(shí),終止第一階段并轉(zhuǎn)入第二階段的準(zhǔn)備階段.公式中的MaxFEs代表允許的最大評(píng)價(jià)次數(shù).

θ=MaxFEs/max(2,5-log2(D))

(4)

在第二階段開(kāi)始前的準(zhǔn)備階段,需要精確的對(duì)種群劃分聚類,所以此時(shí)調(diào)用DMC方法進(jìn)行聚類劃分,以期望獲得更準(zhǔn)確的劃分結(jié)果.然后和已獲得聚類數(shù)目相同的(μw,λ)-CMA-ES實(shí)例被生成,每一個(gè)CMA-ES實(shí)例對(duì)應(yīng)一個(gè)聚類并覆蓋搜索空間中的一個(gè)不同區(qū)域.取聚類中的最好搜索點(diǎn)作為CMA-ES實(shí)例的起始搜索點(diǎn),并定義當(dāng)前實(shí)例與它最鄰近實(shí)例之間歐氏距離的二分之一為覆蓋距離,則取覆蓋距離的三分之一作為當(dāng)前實(shí)例的起始步長(zhǎng),這樣做的目的在于希望在CMA-ES隨機(jī)抽取的搜索點(diǎn)中,有99%的搜索點(diǎn)落在覆蓋距離之內(nèi).這樣可以從統(tǒng)計(jì)上避免鄰近CMA-ES實(shí)例間覆蓋范圍的相互重疊.為了充分利用剩余的評(píng)價(jià)次數(shù),引入了CMA-ES實(shí)例重新初始化和檔案存儲(chǔ)機(jī)制,當(dāng)一個(gè)實(shí)例被終止并且有剩余的評(píng)價(jià)次數(shù)時(shí),該實(shí)例被會(huì)重新隨機(jī)初始化并重新啟動(dòng)它.算法框架的偽代碼如算法2所示.

算法2算法框架

1.初始化種群

2.執(zhí)行聚類方法識(shí)別聚類

3.如果CN>D,則執(zhí)行SPRS,否則跳過(guò)該步

4.converged=false,iter=0,t=2

5.while終止條件沒(méi)有滿足do

(a)if not converged then

①如果CN>D∩iter=α∩FEs

②執(zhí)行NCDE算法

③如果FEs>=θ,則執(zhí)行DMC劃分聚類并初始化CMA-ES實(shí)例,并令converged=true

(b)else

①分別執(zhí)行所有CMA-ES實(shí)例

②若條件滿足執(zhí)行檔案存儲(chǔ)和實(shí)例重啟

(c)iter=iter+1

6.end while

FEs代表目前消耗的評(píng)價(jià)次數(shù),CN為NBC或DMC聚類算法返回的聚類數(shù)目.

3.4時(shí)間復(fù)雜度分析

本文提出算法的復(fù)雜性與NCDE、CMA-ES、NBC、DMC和SPRS等算法復(fù)雜性有關(guān).NCDE和NBC的復(fù)雜性為O(n2log(n)),n為種群大小.CMA-ES的復(fù)雜性為O(n3),n為問(wèn)題的維度.而DMC聚類方法的復(fù)雜性難于確定,因?yàn)樗c函數(shù)評(píng)價(jià)有關(guān).在不考慮函數(shù)評(píng)價(jià)的情況下,DMC的復(fù)雜性小于等于NBC的復(fù)雜性,相等只出現(xiàn)在找到的最大聚類數(shù)量等于種群數(shù)量時(shí).在評(píng)價(jià)函數(shù)不是特別復(fù)雜的情況下,由于本文提出的算法框架對(duì)DMC和NBC聚類方法僅調(diào)用幾次,并且它們的復(fù)雜度并不占主導(dǎo)因素,可以把它們忽略.對(duì)于SPRS方法,它的復(fù)雜性在O(1)到O(n3)之間,其中n為種群大小.在大多數(shù)情況下,由于SPRS僅被調(diào)用幾次,SPRS的運(yùn)行時(shí)間是可以忽略的,但在種群中僅包含少數(shù)幾個(gè)聚類,且聚類中的個(gè)體數(shù)量極不均勻的情況下,SPRS對(duì)算法運(yùn)行時(shí)間有一定影響.根據(jù)上面的分析,本文提出算法的復(fù)雜性主要取決于NCDE和CMA-ES算法的復(fù)雜性.NCDE算法的復(fù)雜性依賴于種群的大小,而CMA-ES算法的復(fù)雜性依賴于問(wèn)題維度的大小.一般來(lái)說(shuō),在低維問(wèn)題上NCDE算法的復(fù)雜性占主導(dǎo)因素(因?yàn)榉N群大小遠(yuǎn)大于問(wèn)題維度),而在高維問(wèn)題上CMA-ES算法的復(fù)雜性占主導(dǎo)因素(即當(dāng)O(Nn3)>O((NP)2log(NP))時(shí),N為小生境數(shù)量,n為問(wèn)題維度,NP為種群大小).因此,在低維問(wèn)題上本文提出的算法的運(yùn)行時(shí)間少于原始NCDE算法,而在高維問(wèn)題上我們提出的算法的運(yùn)行時(shí)間可能會(huì)大于NCDE算法,這取決于種群大小和問(wèn)題的維度.

4　實(shí)驗(yàn)設(shè)置與性能評(píng)價(jià)

4.1測(cè)試函數(shù)

為了評(píng)估提出算法的性能,本文使用了兩個(gè)基準(zhǔn)測(cè)試集.以CEC2013會(huì)議競(jìng)賽設(shè)計(jì)的20個(gè)多峰基準(zhǔn)測(cè)試函數(shù)為測(cè)試集1,用以檢驗(yàn)算法搜索全部全局最優(yōu)解的能力.另外,又選擇了其它7個(gè)常用測(cè)試函數(shù)作為測(cè)試集2,用以檢驗(yàn)算法同時(shí)搜索全部全局最優(yōu)解及部分局部最優(yōu)解的能力.有關(guān)測(cè)試集1的詳細(xì)介紹請(qǐng)參考文獻(xiàn)[10].測(cè)試集2共包含7個(gè)測(cè)試函數(shù),它們是:

F1:Waves (2D)

F2:Shubert (2D)

F3:Modified Shekel (2D)

F4:Modified Shekel (5D)

F5:Rastrigin (4D)

F6:Szu (6D)

F7:Ackley (5D)

所有這些函數(shù)均為最大化問(wèn)題.F1和F2選自文獻(xiàn)[9].F3到F7選自文獻(xiàn)[11].

4.2性能評(píng)價(jià)

本文使用文獻(xiàn)[10]中所規(guī)定的性能評(píng)價(jià)方法對(duì)算法進(jìn)行定量評(píng)價(jià).這些評(píng)價(jià)方法需要在給定的精度要求下,運(yùn)行被測(cè)算法多次,然后通過(guò)對(duì)多次運(yùn)行結(jié)果進(jìn)行計(jì)算得到評(píng)價(jià)指標(biāo).

峰比率(Peak Ratio,PR)按式(5)計(jì)算,NPFi代表算法第i次運(yùn)行結(jié)束后找到的最優(yōu)值數(shù)量,NKP是已知最優(yōu)值數(shù)量,PR度量在NR次運(yùn)行中找到已知最優(yōu)值數(shù)量的平均百分比.

(5)

4.3實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)中所有算法代碼均由Visual C++2012編寫(xiě),操作系統(tǒng)為Window7,CPU為Intel 酷睿i7-4790k.為了檢驗(yàn)NBC-CMA和DMC-CMA算法的性能,我們選擇了9個(gè)對(duì)等的算法進(jìn)行比較.它們是NEA[8]、TN-CMA-ES[12]、S-CMA[13]、IPOP-CMA-ES[14]、CCDE[15]、NCDE[5]、LIPS[16]、FERPSO[17]和PNA-NSGA-II[18].其中IPOP-CMA-ES是基于重啟機(jī)制、時(shí)間上串行運(yùn)行的算法,原則上空間上并行化的算法性能應(yīng)不次于它,這里以它作為一個(gè)測(cè)試基準(zhǔn),來(lái)檢驗(yàn)所有算法的性能.

除了TN-CMA-ES和PNA-NSGA-II(它們的實(shí)驗(yàn)結(jié)果引自相應(yīng)參考文獻(xiàn))算法以外,剩余所有算法都在5種精度e={1.0e-1,1.0e-2,1.0e-3,1.0e-4,1.0e-5}中的每一種精度下獨(dú)立運(yùn)行50次.最大允許的評(píng)價(jià)次數(shù)根據(jù)問(wèn)題選擇:

5.0e+04用于T1-F1到T1-F5(1D or 2D)

2.0e+05用于T1-F6到T1-F11(2D)

4.0e+05用于T1-F6到T1-F12(≥3D)

3.0e+04用于T2-F1到T2-F4(2D or 5D)

1.0e+05用于T2-F5到T2-F6(4D or 6D)

2.0e+05用于T2-F7(5D)

測(cè)試基準(zhǔn)為每個(gè)函數(shù)提供了指定的參數(shù),其中部分參數(shù)作為被執(zhí)行算法的輸入使用,測(cè)試集1的參數(shù)見(jiàn)文獻(xiàn)[10],測(cè)試集2的參數(shù)見(jiàn)表1.一般來(lái)說(shuō),種群的大小對(duì)大多數(shù)算法的性能都有影響,為了保證比較的公平性,所有算法都在不同種群大小下(以步長(zhǎng)50遞增)被執(zhí)行多次.對(duì)于每一個(gè)種群大小,所有算法都被獨(dú)立執(zhí)行50次并計(jì)算其PR值及平均找到的最優(yōu)值個(gè)數(shù),然后從所有運(yùn)行結(jié)果中選擇最好運(yùn)行結(jié)果作為最終結(jié)果參與比較.

我們提出的算法共引入了3個(gè)新參數(shù)IP,α和θ,DMC-CMA和NBC-CMA的參數(shù)IP分別被設(shè)置為固定值6和8.α和θ是兩個(gè)自適應(yīng)參數(shù),不需要設(shè)置.對(duì)于NEA和S-CMA算法,它們的最大允許小生境數(shù)量設(shè)置為要搜索的最優(yōu)值數(shù)量.為了保證和其它CMA算法比較的公平性,在原IPOP-CMA-ES和S-CMA算法的基礎(chǔ)上為其增加了檔案存儲(chǔ)機(jī)制.其它算法的參數(shù)均取其默認(rèn)值.

表1　測(cè)試集2性能評(píng)價(jià)所需的參數(shù)

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

在兩個(gè)測(cè)試集27個(gè)函數(shù)上,求解精度為1.0e-5時(shí),所有算法對(duì)每個(gè)種群大小都獨(dú)立運(yùn)行50次.圖3展示了在最好種群下部分函數(shù)的實(shí)驗(yàn)情況.對(duì)全部測(cè)試函數(shù)選擇最好種群下的實(shí)驗(yàn)結(jié)果分別列在表2和表3中.對(duì)每個(gè)函數(shù)最好實(shí)驗(yàn)結(jié)果以粗體顯示,每種算法的秩顯示在小括號(hào)中,算法的秩和列在表格的最后一行.為了確定DMC-CMA算法的優(yōu)勢(shì)相對(duì)于其它算法在統(tǒng)計(jì)上的顯著性,從實(shí)驗(yàn)結(jié)果中選擇所有算法的最好實(shí)驗(yàn)結(jié)果,對(duì)50次運(yùn)行中所有求得的50組最優(yōu)值個(gè)數(shù),在DMC-CMA和其它算法之間以0.05為顯著性水平執(zhí)行Wilcoxon秩和檢驗(yàn).若兩組算法性能存在顯著性差異,則比較它們的平均找到的最優(yōu)值個(gè)數(shù).“-”、“+”和“≈”分別代表相應(yīng)算法的性能劣于、優(yōu)于和近似于DMC-CMA算法.最終秩和檢驗(yàn)的結(jié)果列于表2和表3中.

從表2和表3可以看到,DMC-CMA和NBC-CMA有近似的性能,DMC-CMA的性能略優(yōu)于NBC-CMA,二者僅在個(gè)別函數(shù)上有所區(qū)別.DMC-CMA和NBC-CMA的性能明顯優(yōu)于其它算法,這說(shuō)明我們提出的方法是有效的,具有更好的適應(yīng)性.根據(jù)表2和表3的秩和可以看到,DMC-CMA和NBC-CMA性能最好,NEA和S-CMA次之.從整體上看,IPOP-CMA-ES在一定程度上受隨機(jī)性的影響,因?yàn)樗看沃貑⑦\(yùn)行的初始搜索點(diǎn)是隨機(jī)從搜索空間中選取.因此,對(duì)于一些包含大量最優(yōu)值的函數(shù),IPOP-CMA-ES僅通過(guò)多次重啟很難獲得全部最優(yōu)值.例如在T1-F6(2D,3D)、T1-F7(2D,3D)和測(cè)試集2上.然而在復(fù)合函數(shù)上,IPOP-CMA-ES的性能是可接受的,這證明了CMA-ES算法在病態(tài)和高度不可分的復(fù)雜問(wèn)題上的優(yōu)秀能力.FERPSO和PNA-NSGA-II算法在低維問(wèn)題上性能較好,但在高維問(wèn)題上它們的性能明顯劣于其它算法.另外,FERPSO在搜索局部最優(yōu)值上表現(xiàn)最差,這是因?yàn)樵撍惴ㄊ沟妹總€(gè)粒子向離它最近且適應(yīng)度最好的鄰近個(gè)體移動(dòng),這使得粒子更多的向全局最優(yōu)值移動(dòng),容易丟失局部最優(yōu).CCDE、LIPS和NCDE算法有近似的性能,它們都采用了基于鄰域變異的策略,都有很好的保持種群多樣性的能力,具有很好的算法穩(wěn)定性和一致性.NEA、S-CMA、TN-CMA-ES都采用了CMA-ES算法和相應(yīng)的聚類識(shí)別技術(shù)進(jìn)行最優(yōu)值搜索,多數(shù)函數(shù)上它們有近似的性能,在總體上NEA和S-CMA的性能優(yōu)于TN-CMA-ES.在復(fù)合函數(shù)上它們都有不錯(cuò)的表現(xiàn),近一步證明了CMA-ES算法有較強(qiáng)的局部搜索能力及解決復(fù)雜問(wèn)題的能力.在測(cè)試集2上,NEA算法整體上優(yōu)于S-CMA算法,表現(xiàn)了出了更強(qiáng)的局部搜索能力.雖然DMC-CMA和NBC-CMA有近似的性能,但在某些函數(shù)上它們有著不同的性能.DMC-CAM在T1-F7(3D)、T1-F12(10D)函數(shù)上明顯優(yōu)于NBC-CMA算法,而NBC-CMA在T2-F7(5D)函數(shù)上優(yōu)勢(shì)明顯.

5.1求解精度的影響

為了檢驗(yàn)算法在不同求解精度下的性能差異,所有算法在最好種群規(guī)模下,對(duì)5種求解精度(1.0e-1到1.0e-5)中的每一種精度獨(dú)立運(yùn)行50次.兩個(gè)測(cè)試集中的部分函數(shù)的實(shí)驗(yàn)結(jié)果繪制在圖4中.結(jié)果表明DMC-CMA、NBC-CMA和IPOP-CMA-ES是最少受到求解精度影響.我們提出的算法因?yàn)椴捎昧藘呻A段搜索,這一策略能夠增加搜索的準(zhǔn)確性,減少搜索的隨機(jī)性,同時(shí)在已找到的吸引盆上利用CMA-ES進(jìn)行局部精確搜索能夠增加收斂速度,減少評(píng)價(jià)次數(shù)的消耗.算法的這些特性能夠減少受求解精度改變的影響.

5.2收斂速度比較

為了比較所有算法的收斂速度,在求解精度1.0e-5下,所有算法在最好種群下獨(dú)立執(zhí)行50次,每次運(yùn)行時(shí)記錄每次迭代后找到的最優(yōu)值數(shù)量.為了便于統(tǒng)計(jì),讓FEs以一定間隔遞增,把每次迭代后找到的最優(yōu)值數(shù)量記錄于當(dāng)前FEs下,然后計(jì)算所有算法50次運(yùn)行后在不同F(xiàn)Es下的PR值.從兩個(gè)測(cè)試集中選擇11個(gè)函數(shù)進(jìn)行實(shí)驗(yàn),部分實(shí)驗(yàn)結(jié)果繪制在圖5中.從圖5可以看到DMC-CMA和NBC-CMA算法在運(yùn)行初期收斂速度較慢,這是因?yàn)镹CDE方法本身就是一個(gè)收斂速度慢的算法,在調(diào)用SPRS后可能會(huì)毀壞已收斂的種群結(jié)構(gòu),導(dǎo)致進(jìn)一步降低收斂速度.但是當(dāng)算法轉(zhuǎn)入第二階段后,算法的性能有一個(gè)明顯的提升.這是因?yàn)樵诘诙A段中使用多個(gè)CMA-ES實(shí)例在前面已找到的吸引盆上進(jìn)行精細(xì)搜索.搜索的準(zhǔn)確性及CMA-ES算法的快速收斂特點(diǎn)使得我們提出的算法在第二階段具有良好的收斂速度.與原始的NCDE算法相比,DMC-CMA和NBC-CMA在函數(shù)T2-F5(4D)、T2-F6(6D)和T2-F7(5D)上收斂速度更慢,但在其它函數(shù)上,DMC-CMA和NBC-CMA的收斂速度明顯好于原始的NCDE算法.在函數(shù)T1-F6(2D)、T1-F6(3D)、T2-F5(4D)、T2-F6(6D)和T2-F7(5D)上,CCDE算法表現(xiàn)出了優(yōu)于DMC-CMA和NBC-CMA的收斂速度.

表2　測(cè)試集1最好結(jié)果的PR值,求解精度為1.0e-5

表3　測(cè)試集2最好結(jié)果的PR值,求解精度為1.0e-5

函數(shù)CCDEDMC-CMAFERPSOIPOP-CMALIPSNBC-CMANCDENEAS-CMAF1(2D)0.632(5)-0.992(2)0.122(9)-0.460(8)-0.600(7)-0.996(1)≈0.612(6)-0.856(4)-0.860(3)-F2(2D)0.932(4)-0.998(1)0.469(8)-0.553(7)-0.992(3)≈0.994(2)≈0.399(9)-0.809(6)-0.893(5)-F3(2D)0.922(5)-0.998(1)0.138(9)-0.558(8)-0.998(1)≈0.998(1)≈0.912(6)-0.930(4)-0.912(6)-F4(5D)0.343(8)-1.000(1)0.123(9)-0.540(6)-0.823(4)-1.000(1)≈0.393(7)-0.823(4)-0.998(3)≈F5(4D)1.000(1)≈1.000(1)0.012(9)-0.306(7)-0.051(8)-1.000(1)≈0.999(5)≈1.000(1)≈0.986(6)-F6(6D)1.000(1)+0.998(3)0.016(8)-0.189(7)-0.478(6)-0.997(4)≈1.000(1)+0.631(5)-0.000(9)-F7(5D)1.000(1)+0.874(4)0.004(9)-0.009(8)-0.036(7)-1.000(1)+0.999(3)+0.600(5)-0.088(6)-秩和251361513611372938

6　結(jié)論

本文提出了一個(gè)基于NCDE和CMA-ES算法的兩階段雜交算法求解實(shí)值多峰優(yōu)化問(wèn)題.提出的算法充分利用了它們的兩個(gè)明顯特點(diǎn),即NCDE具有較強(qiáng)的保持種群多樣性的能力和CMA-ES具有優(yōu)秀的局部搜索能力.NCDE為了保持種群的多樣性,降低了收斂速度,而第二階段的CMA-ES所具有的快速收斂能力恰好彌補(bǔ)了這一劣勢(shì),既保證了種群的多樣性,又保證了快速收斂.為了在第一階段搜索后準(zhǔn)確定位當(dāng)前種群搜索到的最優(yōu)值位置,我們引入了DMC聚類方法來(lái)劃分聚類,該聚類方法雖然消耗了一定數(shù)量的評(píng)價(jià)次數(shù),但可以獲得更準(zhǔn)確的聚類結(jié)果.為了增強(qiáng)種群在演化初期的搜索能力及保持種群的穩(wěn)定性,我們引入了搜索點(diǎn)補(bǔ)充策略.該策略在一些低維函數(shù)上取得到明顯優(yōu)勢(shì),尤其在T1-F7(2D)、T1-F7(3D)、T2-F1(2D)和T2-F7(5D)函數(shù)上.大量的實(shí)驗(yàn)表明我們提出的算法在大多數(shù)測(cè)試函數(shù)上優(yōu)于其它算法,表現(xiàn)出了優(yōu)秀的性能和適應(yīng)性.在兩個(gè)測(cè)試集上的實(shí)驗(yàn)同時(shí)也表明我們提出的算法不僅在搜索全局最優(yōu)值上有優(yōu)良的性能,而且在搜索局部最優(yōu)值上也性能優(yōu)異.

下一步的工作將繼續(xù)完善算法框架,與更多的多峰算法在更廣泛的基準(zhǔn)測(cè)試函數(shù)上進(jìn)行比較研究.另外,將提出的算法嘗試應(yīng)用到動(dòng)態(tài)環(huán)境下的多峰優(yōu)化問(wèn)題.

[1]周新宇,吳志健,等.一種精英反向?qū)W習(xí)的粒子群優(yōu)化算法[J].電子學(xué)報(bào),2013,41(8):1647-1652.

Zhou Xin-yu,Wu Zhi-jian,et al.Elite opposition-based particle swarm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.(in Chinese)

[2]彭虎,吳志健,等.基于精英區(qū)域?qū)W習(xí)的動(dòng)態(tài)差分進(jìn)化算法[J].電子學(xué)報(bào),2014,42(8):1522-1530.

Peng Hu,Wu Zhi-jian,et al.Dynamic differential evolution algorithm based on elite local learning[J].Acta Electronica Sinica,2014,42(8):1522-1530.(in Chinese)

[3]李康順,韋蘊(yùn)珊,等.小生境演化算法下的WDCT圖像壓縮方法[J].電子學(xué)報(bào),2014,(4):809-814.

Li Kang-shun,Wei Yun-shan,et al.WDCT image compre-ssion based on niching evolutionary algorithm[J].Acta Electronica Sinica,2014,42(4):809-814.(in Chinese)

[4]鄭金華,劉磊,等.一種自適應(yīng)小生境分布性保持策略[J].電子學(xué)報(bào),2012,40(11):2330-2335.

Zheng Jin-hua,Liu Lei,et al.An adaptive niche for keeping the diversity of solutions in multi-objective evolutionary algorithm[J].Acta Electronica Sinica,2012,40(11):2330-2335.(in Chinese)

[5]Qu B Y,Suganthan P N,Liang J J.Differential evolution with neighborhood mutation for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2012,16(5):601-614.

[6]Hansen N,Ostermeier A.Completely derandomized self-adaptation in evolution strategies[J].Evolutionary Computation,2001,9(2):159-195.

[7]Hansen N.The CMA Evolution Strategy:A Comparing Review[M].Berlin:Springer,2006.75-102.

[8]Preuss M.Niching the CMA-ES via nearest-better clustering[A].Proceedings of the 12th Annual Conference Companion On Genetic and Evolutionary Computation[C].Portland:ACM,2010.1711-1718.

[9]Stoean C,Preuss M,Stoean R,et al.Multimodal optimization by means of a topological species conservation algorithm[J].IEEE Transactions on Evolutionary Computation,2010,14(6):842-864.

[10]Li X D,et al.Benchmark Functions for CEC′2013 Special Session and Competition on Niching Methods for Multim-odal Function Optimization[R].Melbourne:RMIT University,Evolutionary Computation and Machine Learning Group,2013.1-10.

[11]Vitela J E,Castaos O.A sequential niching memetic algorithm for continuous multimodal function optimization[J].Applied Mathematics and Computation,2012,218(17):8242-8259.

[12]Pereira M W,et al.A topological niching covariance matrix adaptation for multimodal optimization[A].Proc of IEEE Congress on Evolutionary Computation[C].Betjing:IEEE,2014.2562-2569.

[13]Shir O M,Emmerich M,Back T.Adaptive niche radii and niche shapes approaches for niching with the CMA-ES[J].Evolutionary Computation,2010,18(1):97-126.

[14]Auger A,Hansen N.A restart CMA evolution strategy with increasing population size[A].Proc of IEEE Congress on Evolutionary Computation[C].Edinburgh,Scotland:IEEE,2005.1769-1776.

[15]Gao W,Yen G G,Liu S.A cluster-based differential evolution with self-adaptive strategy for multimodal optimization[J].IEEE Transactions on Cybernetics,2014,44(8):1314-1327.

[16]Qu B Y,Suganthan P N.A distance-based locally informed particle swarm model for multimodal optimization[J].IEEE Transactions on Evolutionary Computation,2013,17(3):387-402.

[17]Li X D.A Multimodal particle swarm optimizer based on fitness euclidean-distance ratio[A].Proc of The 9th Annual Conference on Genetic and Evolutionary Computation[C].London:ACM,2007.78-85.

[18]Bandaru S,Deb K.A parameterless-niching-assisted bi-objective approach to multimodal optimization[A].Proc of IEEE Congress on Evolutionary Computation[C].Cancun:IEEE,2013.95-102.

李煥哲男,1975年生,河北唐山人,武漢大學(xué)計(jì)算機(jī)學(xué)院博士研究生,研究方向:智能計(jì)算、機(jī)器學(xué)習(xí).

E-mail:lihuanzhe@whu.edu.cn

吳志健男,1963年生,教授,博士生導(dǎo)師,武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室副主任,研究方向:智能計(jì)算、 并行計(jì)算和智能信息處理.

E-mail:zhijianwu@whu.edu.cn

郭肇祿男,1984年生,江西南康人,博士,研究方向?yàn)橹悄苡?jì)算、并行計(jì)算和機(jī)器學(xué)習(xí).

E-mail:gzl@whu.edu.cn

劉會(huì)超男,1982年生,河南駐馬店人,博士生,研究方向?yàn)橹悄苡?jì)算.

E-mail:huichaoliu@whu.edu.cn

汪慎文男,1979年生,副教授,博士后,研究方向?yàn)橹悄苡?jì)算與機(jī)器學(xué)習(xí)等.

E-mail:wangshenwen@whu.edu.cn

Multimodal Function Optimization Based on Two-Stage Search Algorithm

LI Huan-zhe1,2,WU Zhi-jian1,GUO Zhao-lu3,LIU Hui-chao1,WANG Shen-wen2

(1.StateKeyLabofSoftwareEngineering,ComputerSchool,WuhanUniversity,Wuhan,Hubei430072,China;2.SchoolofInformationEngineering,HebeiGEOUniversity,Shijiazhuang,Hebei050031,China;3.SchoolofScience,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China)

Multimodal optimization aims to search multiple optima (global and/or local optima) simultaneously,which gives rise to a challenging task for traditional optimization algorithms.This paper proposes a two-stage algorithm to solve multimodal optimization problems.In the first stage,NCDE with neighborhood mutation strategy tries its best to find as many approximate positions of optimal solutions as possible on the fitness landscape.After NCDE runs a certain number of iterations,DMC method is employed to divide the entire population into multiple clusters,and then CMA-ES algorithm is used to perform fine search on each cluster which is found by NCDE.Additionally,search point replenishment strategy is put forward to balance cluster size and to increase search capability of our algorithm in the beginning of the running.Extensive comparative experiments is made between our proposed approach and 9 state-of-the-art algorithms on two benchmark sets,the results show that the new algorithm is effective and superior to the other algorithms on the majority of test functions.

crowding differential evolution;covariance matrix adaptation evolution strategy;multimodal optimization;niching;neighborhood mutation

2015-07-27;修回日期:2015-09-20;責(zé)任編輯:梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61364025,No.61402481);江西省自然科學(xué)基金(No.20151BAB217010);河北省自然科學(xué)基金(No.F2015403046);武漢大學(xué)軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(No.SKLSE2014-10-04);河北省科學(xué)技術(shù)支撐項(xiàng)目(No.12210319)

TP18

A

0372-2112 (2016)06-1481-09