李國(guó)成,肖慶憲

(1.上海理工大學(xué)管理學(xué)院,上海200093;2.皖西學(xué)院金融與數(shù)學(xué)學(xué)院,安徽六安237012)

求解高維函數(shù)優(yōu)化問(wèn)題的交叉熵蝙蝠算法

李國(guó)成1,2,肖慶憲1

(1.上海理工大學(xué)管理學(xué)院,上海200093;2.皖西學(xué)院金融與數(shù)學(xué)學(xué)院,安徽六安237012)

為改善蝙蝠算法求解高維函數(shù)優(yōu)化問(wèn)題的全局搜索能力,提高其搜索精度,將交叉熵方法和蝙蝠算法相結(jié)合,提出一種交叉熵蝙蝠算法。該算法將基于重要度抽樣和Kullback-Leibler距離的交叉熵全局隨機(jī)優(yōu)化算法應(yīng)用于蝙蝠算法中,采用自適應(yīng)平滑技術(shù)提高算法的收斂速度,利用交叉熵方法的遍歷性、自適應(yīng)性和魯棒性,有效抑制蝙蝠算法的早熟收斂現(xiàn)象。對(duì)經(jīng)典測(cè)試函數(shù)和CEC2005測(cè)試函數(shù)的仿真結(jié)果表明,該算法具有全局搜索能力強(qiáng)、求解精度高和魯棒性好等特性。

高維函數(shù)優(yōu)化;蝙蝠算法;交叉熵;重要度抽樣;自適應(yīng)平滑;協(xié)同演化

1 概述

隨著科學(xué)技術(shù)的快速發(fā)展,人們?cè)诂F(xiàn)實(shí)世界中面臨著更加復(fù)雜多變的系統(tǒng),如電力系統(tǒng)、蛋白質(zhì)結(jié)構(gòu)、醫(yī)學(xué)圖像匹配以及金融市場(chǎng)等。這些復(fù)雜系統(tǒng)的模型參數(shù)優(yōu)化問(wèn)題常常在高維空間進(jìn)行,具有許多在低維空間里不曾有過(guò)的獨(dú)特現(xiàn)象和困難,進(jìn)而為優(yōu)化領(lǐng)域帶來(lái)了新的挑戰(zhàn)。經(jīng)典優(yōu)化方法在處理這類(lèi)問(wèn)題時(shí)隨著維數(shù)的增加,其表現(xiàn)不盡如意[1-3]。近年來(lái),智能優(yōu)化算法的興起與蓬勃發(fā)展為這類(lèi)問(wèn)題的求解開(kāi)辟了新途徑,如遺傳算法(Genetic Algorithms,GA)[4-5]、粒子群優(yōu)化(Particle Swarm Optimization,PSO)[6-8]、微 分 進(jìn) 化 (Differential Evolution,DE)[9]和人工蜂群(Artificial Bee Colony, ABC)算法[10-11]等。這些算法在求解高維函數(shù)優(yōu)化問(wèn)題上取得了一些進(jìn)展,但其維數(shù)上的突破仍然很有限,維數(shù)的增加對(duì)其求解精度和收斂速度有著非常大的影響,無(wú)法徹底解決。

交叉熵[12](Cross-entropy,CE)方法是Rubinstein在研究復(fù)雜隨機(jī)網(wǎng)絡(luò)中的小概率事件估計(jì)問(wèn)題時(shí)提出的一種全局隨機(jī)優(yōu)化方法。該方法以統(tǒng)計(jì)視角,采用重要度抽樣,引入Kullback-Leibler距離來(lái)度量2個(gè)概率分布的交叉熵并使之最小,用以求解組合優(yōu)化、稀有事件估計(jì)以及機(jī)器學(xué)習(xí)等問(wèn)題,具有很好的隨機(jī)性、自適應(yīng)性和魯棒性[13],在復(fù)雜網(wǎng)絡(luò)可靠性分析、組合優(yōu)化以及工程優(yōu)化設(shè)計(jì)和控制等方面取得了很好的應(yīng)用效果[14-15]。文獻(xiàn)[16]將該方法應(yīng)用到多峰值連續(xù)函數(shù)優(yōu)化問(wèn)題,發(fā)現(xiàn)函數(shù)維數(shù)的增加對(duì)其求解精度的影響很小,是求解復(fù)雜高維優(yōu)化問(wèn)題的新途徑。但交叉熵方法如同其他Monte Carlo技術(shù)一樣,存在樣本容量大、收斂速度慢等不足。本文將在保持其優(yōu)良的高維優(yōu)化問(wèn)題求解能力的基礎(chǔ)上積極探尋與其他啟發(fā)式算法進(jìn)行協(xié)同演化以提高其收斂速度。文獻(xiàn)[17]于2010年基于仿生學(xué)提出的一種新型啟發(fā)式算法——蝙蝠算法(Bat Algorithm,BA),該算法很好地融合了粒子群優(yōu)化、和聲搜索和模擬退火等算法的優(yōu)點(diǎn),在多目標(biāo)優(yōu)化、工程優(yōu)化以及生產(chǎn)調(diào)度優(yōu)化等方面取得了很好的應(yīng)用效果[18-20]。本文將交叉熵隨機(jī)優(yōu)化方法嵌入到蝙蝠算法中來(lái)構(gòu)建一種新型啟發(fā)式搜索算法,稱(chēng)為交叉熵蝙蝠算法(Cross-entropy Bat Algorithm,CEBA)。

2 標(biāo)準(zhǔn)蝙蝠算法和交叉熵優(yōu)化方法

2.1 蝙蝠算法

蝙蝠算法[17](Bat Algorithm,BA)是 Yang于2010年基于仿生學(xué)提出的一種新型啟發(fā)式算法。該算法通過(guò)模擬蝙蝠在復(fù)雜環(huán)境中搜尋、定位和捕捉獵物的過(guò)程進(jìn)而形成基于群體的仿生算法。在初始化群體中每個(gè)個(gè)體在搜尋空間中的位置和速度后,其位置和速度迭代更新規(guī)則如下:

其中,fi為蝙蝠i的脈沖頻率;β∈[0,1]為均勻分布的隨機(jī)數(shù);和為其t時(shí)刻飛行速度和位置;x*為t時(shí)刻群體最佳位置。同時(shí),通過(guò)模擬蝙蝠在探尋到獵物后通過(guò)逐漸減弱脈沖音強(qiáng)、增大脈沖發(fā)射次數(shù)來(lái)實(shí)現(xiàn)精度定位獵物過(guò)程來(lái)進(jìn)行局部搜索,具體如下:

蝙蝠仿生算法很好地融合了粒子群優(yōu)化、和聲搜索和模擬退火等算法的優(yōu)點(diǎn),在工程優(yōu)化、生產(chǎn)調(diào)度和約束優(yōu)化等問(wèn)題上取得了很好的應(yīng)用效果[15-17]。但該算法存在早熟收斂現(xiàn)象,其尋優(yōu)精度和收斂速度也有待提高。為此,文獻(xiàn)[21]采用Lévy飛行策略來(lái)改進(jìn)BA的尋優(yōu)精度和全局優(yōu)化性能,文獻(xiàn)[22]通過(guò)引入混沌Lévy飛行來(lái)提高其收斂速度,并改善求解精度;在收斂性和全局優(yōu)化方面,文獻(xiàn)[23]對(duì)BA的收斂性進(jìn)行了研究,文獻(xiàn)[24]通過(guò)采用正交拉丁方原理生成蝙蝠群的初始空間位置和模擬蝙蝠的追隨、自主、避險(xiǎn)和從眾行為來(lái)構(gòu)造可全局收斂的BA,并應(yīng)用于復(fù)雜函數(shù)和高維函數(shù)的優(yōu)化問(wèn)題,其研究結(jié)果表明BA求解高維函數(shù)優(yōu)化問(wèn)題的計(jì)算成本是非常高的,而且精度不高。此外,在離散優(yōu)化問(wèn)題上,文獻(xiàn)[25-26]分別提出了二進(jìn)制蝙蝠算法和元胞蝙蝠算法,極大豐富了BA算法及其應(yīng)用。

2.2 交叉熵隨機(jī)優(yōu)化方法

考慮如下最優(yōu)化問(wèn)題:

交叉熵算法將其關(guān)聯(lián)到相關(guān)的概率估計(jì)問(wèn)題,根據(jù)一族定義在X上的概率密度函數(shù){f(·;v),v∈ν}隨機(jī)化問(wèn)題式(7),得到其輔助隨機(jī)問(wèn)題:

其中,Eu是期望算子;I為示性函數(shù);γ為自適應(yīng)更新參數(shù)。為了減小樣本數(shù)量,CE采用重要度抽樣法,將式(8)轉(zhuǎn)化為:

其中,xi為重要度抽樣密度g(x)生成的樣本。為求得最優(yōu)的重要度抽樣密度,引入Kullback-Leibler距離來(lái)度量2個(gè)概率分布f(x;v)與g(x)間距離即交叉熵,并最小化交叉熵:

從而得到最優(yōu)的g*(x)。

CE全局隨機(jī)優(yōu)化算法的實(shí)施過(guò)程為:

Step 1 根據(jù)預(yù)定義參數(shù)的概率密度函數(shù)生成候選解集;

Step 2 用引導(dǎo)搜索向全局最優(yōu)解逼近的精英解集來(lái)更新概率密度函數(shù)的參數(shù),產(chǎn)生迭代序列,直至滿足終止條件。

CE算法具有預(yù)定義參數(shù)少、迭代操作簡(jiǎn)單和數(shù)值穩(wěn)定性好等優(yōu)點(diǎn),在組合優(yōu)化和工程優(yōu)化設(shè)計(jì)方面有著廣泛的應(yīng)用。

3 交叉熵蝙蝠算法

交叉熵蝙蝠算法是將交叉熵方法嵌入到蝙蝠算法中,通過(guò)協(xié)同演化共同更新種群,有效增強(qiáng)算法搜索過(guò)程中種群的多樣性,提高算法的全局優(yōu)化能力,同時(shí)加快了CE中均值和方差的演化速度,降低了抽樣成本。

3.1 算法原理

基于模型的交叉熵優(yōu)化算法的優(yōu)點(diǎn)在于自適應(yīng)性和魯棒性強(qiáng),具有很好的全局優(yōu)化能力,不足之處是抽樣需要大量樣本,計(jì)算成本高,收斂速度慢。而源自于仿生學(xué)的蝙蝠算法[17]具有很強(qiáng)的局部搜索能力,但也易陷入局部最優(yōu)解狀態(tài),很難得到全局最優(yōu)解。為此,采用融合技術(shù),將CE嵌入到BA中,形成新的啟發(fā)式隨機(jī)搜索算法。新算法CEBA包含BA和CE 2個(gè)優(yōu)化迭代算子,通過(guò)協(xié)同演化來(lái)共同更新種群中每個(gè)個(gè)體所處的位置,對(duì)應(yīng)著優(yōu)化問(wèn)題的候選解,同時(shí)又分別利用種群的信息來(lái)實(shí)現(xiàn)各自迭代過(guò)程中相關(guān)信息的更新。其中,CE算子利用共同更新后的種群來(lái)刷新自己的抽樣概率分布的參數(shù),這樣利用協(xié)同演化的種群來(lái)加速CEBA算法的演化進(jìn)程,大幅減少抽樣樣本數(shù),進(jìn)而降低計(jì)算成本,同時(shí)充分發(fā)揮自己的全局優(yōu)化能力;而B(niǎo)A算子也因協(xié)同演化獲得更好的個(gè)體,極大地豐富了種群的多樣性,從而提高了CEBA算法的收斂速度和增強(qiáng)全局優(yōu)化能力。

3.2 算法步驟和流程描述

基于交叉熵方法和蝙蝠算法所融合而成的新型啟發(fā)式算法(CEBA)的具體算法步驟如下:

Step 1 確定搜索空間,初始化基本參數(shù)。隨機(jī)生成初始種群。假設(shè)在d維搜索空間中,考慮P只蝙蝠,則每只蝙蝠的位置代表優(yōu)化問(wèn)題的候選解,初始種群為:

其中,表示初始時(shí)刻t=0時(shí)蝙蝠i在第n維搜索空間的位置。

Step 2 啟動(dòng)BA優(yōu)化迭代操作,評(píng)估每只蝙蝠的適應(yīng)度,并更新最優(yōu)解Xbest和最優(yōu)值Gbest。

其中,表示蝙蝠i在t時(shí)刻的適應(yīng)度值;fitness(·)為適應(yīng)度函數(shù),用于評(píng)判蝙蝠位置的優(yōu)劣。

Step 3 按式(1)～式(3)調(diào)整每只蝙蝠的頻率,更新速度位置和位置。

Step 4 對(duì)當(dāng)前最優(yōu)解進(jìn)行擾動(dòng)操作:若rand1＞ri,則隨機(jī)游走到某個(gè)最優(yōu)位置的一個(gè)緊鄰位置;否則保持不動(dòng)。

Step 5 執(zhí)行隨機(jī)飛行操作并按式(4)獲得一個(gè)新解,若rand2＜ri且f()＜f(x*),接受新解并分別按式(5)和式(6)更新和。

Step 6 啟動(dòng)CE優(yōu)化迭代操作:

(1)初始化參數(shù),計(jì)算種群各維的均值μ^和標(biāo)準(zhǔn)差。

(2)按Y～N(,2)抽取樣本Y1,Y2,…,YL。

(3)執(zhí)行協(xié)同演化操作:評(píng)估X和Y中所有個(gè)體,更新最優(yōu)解Xbest和最優(yōu)值Gbest;選取最好的P個(gè)個(gè)體來(lái)更新X及fit,并取其中的最好的Ne個(gè)作組成精英群體Xe,計(jì)算其均值和標(biāo)準(zhǔn)差。

(4)均值和標(biāo)準(zhǔn)差更新的平滑化,按下式更新抽樣概率分布參數(shù):

(5)檢查CE迭代終止條件,若滿足,則停止CE迭代;否則轉(zhuǎn)向(2)。

Step 7 檢查BA迭代終止條件,若滿足,則停止,否則轉(zhuǎn)向Step3。

交叉熵蝙蝠算法的流程如圖1所示,主要體現(xiàn)在BA和CE的協(xié)同演化上,從而在優(yōu)勢(shì)互補(bǔ)的同時(shí)又強(qiáng)化各自的優(yōu)勢(shì)。

圖1 CEBA算法流程

3.3 CEBA算法的優(yōu)勢(shì)

如此建立的新型啟發(fā)式隨機(jī)搜索算法在局部收斂和全局優(yōu)化上分別汲取了BA和CE的優(yōu)勢(shì),協(xié)同演化的結(jié)果不僅促成優(yōu)勢(shì)互補(bǔ),而且增強(qiáng)了各自的優(yōu)勢(shì),形成一些新的特質(zhì)和優(yōu)勢(shì),具體如下:

(1)尋優(yōu)精度高、魯棒性強(qiáng)。基于群體的蝙蝠仿生算法和基于模型的交叉熵全局隨機(jī)優(yōu)化算法的有機(jī)融合使得新算法在勘探能力和開(kāi)采能力之間取得了很好的平衡,協(xié)同演化技術(shù)的應(yīng)用使得這種平衡得以完美實(shí)現(xiàn),以Schwefel函數(shù)(維數(shù)為128)為例給出其協(xié)同演化過(guò)程中最優(yōu)解的交替更新如圖2所示。為BA算子對(duì)最優(yōu)解的更新,其余CE算子為對(duì)最優(yōu)解的更新,可見(jiàn)協(xié)同演化技術(shù)能被很好地實(shí)施,因而新算法具有全局勘探能力強(qiáng)和局部搜索精度高的特質(zhì)。

圖2 協(xié)同演化過(guò)程中最優(yōu)解的更新

(2)計(jì)算成本低、收斂速度快。相對(duì)于BA而言, CE算法參數(shù)少,優(yōu)化過(guò)程簡(jiǎn)單,計(jì)算量小;相對(duì)于CE算法而言,BA收斂速度過(guò),局部?jī)?yōu)化能力強(qiáng)。因此將2種算法進(jìn)行融合既通過(guò)BA加快收斂速度、降低CE算法的抽樣數(shù),又使得計(jì)算成本遠(yuǎn)小于BA。

(3)適合于求解高維函數(shù)優(yōu)化問(wèn)題。新算法中的CE具有求解高維函數(shù)優(yōu)化問(wèn)題的特質(zhì),隨著解空間維數(shù)的增加,其計(jì)算成本只涉及概率分布參數(shù)中的均值和方差的刷新,不會(huì)帶來(lái)維數(shù)災(zāi)難,因而適合求解高維函數(shù)優(yōu)化問(wèn)題,這一點(diǎn)事不同于文獻(xiàn)[24]的,而是CE算法的特質(zhì)。

4 數(shù)值仿真

4.1 測(cè)試問(wèn)題與比較對(duì)象

為了測(cè)試CEBA算法求解高維函數(shù)優(yōu)化問(wèn)題時(shí)的性能,采用與文獻(xiàn)[17]相同的標(biāo)準(zhǔn)測(cè)試函數(shù)及文獻(xiàn)[27]提供的經(jīng)典標(biāo)準(zhǔn)測(cè)試函數(shù)和文獻(xiàn)[28]所提供的CEC2005標(biāo)準(zhǔn)測(cè)試函數(shù)來(lái)進(jìn)行測(cè)試和對(duì)比,測(cè)試函數(shù)的具體描述和特征參見(jiàn)文獻(xiàn)[17,27-28]。其中,第1個(gè)函數(shù)集是用來(lái)評(píng)估新算法的優(yōu)化性能,并與標(biāo)準(zhǔn)的BA和CE算法進(jìn)行對(duì)比;第2個(gè)函數(shù)集是用來(lái)對(duì)比新算法和經(jīng)典啟發(fā)式搜索算法求解連續(xù)函數(shù)優(yōu)化問(wèn)題的優(yōu)化性能,算法比較對(duì)象選取常用的GA和PSO算法;第3個(gè)更為復(fù)雜的CEC2005函數(shù)集是用來(lái)驗(yàn)證新算法求解高維函數(shù)優(yōu)化問(wèn)題的可行性和有效性,本文分別選取文獻(xiàn)[23]提出的合作進(jìn)化策略下自適應(yīng)鄰域搜索微分進(jìn)化算法(DECC-G)和文獻(xiàn)[24]所提出的統(tǒng)計(jì)變量互學(xué)習(xí)策略下的合作粒子群優(yōu)化算法(CPSO-SL)作為比較對(duì)象,具體測(cè)試和對(duì)比詳細(xì)情況如表1所示。實(shí)驗(yàn)硬件環(huán)境為Intel(R)Core (TM)i3 CPU M2.27 GHz,2 GB RAM;軟件環(huán)境為Windows 7和Matlab 2012b。

表1 測(cè)試問(wèn)題和比較對(duì)象

4.2 參數(shù)設(shè)置與測(cè)試結(jié)果

測(cè)試1的算法相關(guān)參數(shù)設(shè)置為:BA的種群規(guī)模為100,其他參數(shù)同文獻(xiàn)[17];CE樣本容量Nc和有效樣本數(shù)Ne分別為100和30,BA和CE的最大迭代次數(shù)為1 550;CEBA中BA算子最大迭代次數(shù)為50,其他參數(shù)設(shè)置同前,其CE算子最大迭代次數(shù)為30,其他參數(shù)設(shè)置同前。3種算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行25次,每次的函數(shù)評(píng)價(jià)次數(shù)均為1.55×105,其測(cè)試結(jié)果與對(duì)比如表2所示,表中第1列為10個(gè)測(cè)試函數(shù),平均值反映了算法的尋優(yōu)能力,標(biāo)準(zhǔn)差反映了算法尋優(yōu)能力的穩(wěn)定性,其最優(yōu)值均以粗體標(biāo)識(shí)。

表2 測(cè)試1的測(cè)試結(jié)果與對(duì)比

從表2可以看出,與標(biāo)準(zhǔn)的BA相比,在10個(gè)測(cè)試函數(shù)中CEBA勝出7,其余3個(gè)尋優(yōu)結(jié)果除在F8和F10的標(biāo)準(zhǔn)差略遜外是一樣的;與標(biāo)準(zhǔn)的CE相比, CEBA是完全勝出,即使F8均值是一樣,但標(biāo)準(zhǔn)差CEBA算法要好得多。

測(cè)試2的算法相關(guān)參數(shù)設(shè)置為:GA和PSO種群規(guī)模為100,其中GA的pc和pm分別為0.2和0.8,PSO的加權(quán)因子C1=C2=2,加權(quán)函數(shù)w從0.9線性遞減到0.2,最大迭代次數(shù)均為1 020,迭代停止標(biāo)準(zhǔn)為達(dá)到最大迭代次數(shù);CEBA中BA種群規(guī)模為50,最大迭代次數(shù)為40,其他參數(shù)設(shè)置同文獻(xiàn)[17]; CE樣本容量Nc和有效樣本數(shù)Ne分別為100和30,最大迭代次數(shù)為25。3種算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行25次,每次的函數(shù)評(píng)價(jià)次數(shù)均為1.02×105,測(cè)試和對(duì)比結(jié)果見(jiàn)表3和表4。

測(cè)試3中CEBA算法的BA和CE最大迭代次數(shù)分別為50和200,其他參數(shù)如前文所設(shè),2種維數(shù)對(duì)應(yīng)DECC-G算法的函數(shù)評(píng)價(jià)次數(shù)分別為2.5×106和5×106;而 CEBA算法的函數(shù)評(píng)價(jià)次數(shù)均為1.002 5×106。測(cè)試和對(duì)比結(jié)果如表5所示,為了便于對(duì)比,參照文獻(xiàn)[29]給出CEBA算法的獨(dú)立運(yùn)行25次結(jié)果的平均值。

測(cè)試4中CEBA算法的BA和CE最大迭代次數(shù)分別為50和1 000,其他參數(shù)如前文所設(shè);比較對(duì)象CPSO-SL的2種維數(shù)對(duì)應(yīng)的函數(shù)評(píng)價(jià)次數(shù)分別為1.0×108和2.0×108,而CEBA算法的函數(shù)評(píng)價(jià)次數(shù)均為5.002 5×106。測(cè)試和對(duì)比結(jié)果如表6所示,為了便于對(duì)比,參照文獻(xiàn)[30]給出CEBA算法的30次獨(dú)立運(yùn)行的平均值。

表3 測(cè)試2中d=30時(shí)的測(cè)試結(jié)果與對(duì)比

表5 測(cè)試3的測(cè)試結(jié)果與對(duì)比

從表3和表4可以看出:(1)13個(gè)經(jīng)典測(cè)試函數(shù)2種維數(shù)取值的測(cè)試結(jié)果中CEBA算法所求結(jié)果中除了d=30時(shí)的f2和f9略遜于PSO外全部勝出,表明本文所構(gòu)建的CEBA算法在求解高維函數(shù)優(yōu)化問(wèn)題時(shí)的表現(xiàn)要明顯好于標(biāo)準(zhǔn)的GA和PSO2種算法;(2)CEBA算法的搜索精度是非常高的,標(biāo)準(zhǔn)差都很小,表明該算法穩(wěn)定性好、魯棒性強(qiáng),即使對(duì)于非常復(fù)雜的函數(shù)f5也取得了不錯(cuò)的效果,遠(yuǎn)好于另外2種算法;(3)隨著維數(shù)的增加CEBA算法的尋優(yōu)效能并沒(méi)有發(fā)生明顯地減弱,而GA和PSO優(yōu)化效能卻降低很多。

表5中DECC-G算法的求解結(jié)果來(lái)自文獻(xiàn)[23],可以看出除fcec1外,其他7個(gè)函數(shù)的求解結(jié)果CEBA均勝出,而且明顯好于DECC-G算法,而2種維數(shù)下CEBA的函數(shù)評(píng)價(jià)次數(shù)分別不及DECC-G算法的一半和1/4,以很低的求解成本就獲得很高的求解精度。

表6中CPSO-SL算法的求解結(jié)果來(lái)自文獻(xiàn)[24],在所測(cè)試的10個(gè)CEC2005函數(shù)中,CEBA有7個(gè)勝出,其余3個(gè)求解精度略遜于CPSO-SL算法,但也是相當(dāng)高的,而所有10個(gè)函數(shù)的求解精度都高于1.0E-09,適用所有10個(gè)測(cè)試函數(shù),這要明顯好于CPSO-SL算法,其優(yōu)化性能在其中一些函數(shù)上表現(xiàn)很好而對(duì)另一些的求解結(jié)果就遠(yuǎn)不如CEBA算法。同樣求解成本遠(yuǎn)小于文獻(xiàn)[24]。表5和表6都表明CEBA算法收斂速度快,求解精度高,全局優(yōu)化性能好,具有很好的魯棒性,其原因在于CEBA算法實(shí)現(xiàn)了CE和BA的優(yōu)勢(shì)互補(bǔ),并通過(guò)協(xié)作演化強(qiáng)化了各自的優(yōu)勢(shì),從而提高了算法的搜索精度,增強(qiáng)了算法的穩(wěn)定性。

為了研究BA、CE和CEBA3種算法求解精度對(duì)維數(shù)的敏感性,以Rastrigin函數(shù)為例,解空間維數(shù)以20為起點(diǎn)、步長(zhǎng)為10依次遞增到200,如圖3給出3種算法25次獨(dú)立運(yùn)行求解所得最優(yōu)函數(shù)值的平均值與隨維數(shù)變化的對(duì)應(yīng)關(guān)系與對(duì)比,可見(jiàn)CEBA算法的優(yōu)化效能并不隨解空間的維數(shù)的增加而發(fā)生顯著變化,而標(biāo)準(zhǔn)的BA和CE的在求解高維函數(shù)優(yōu)化時(shí)(維數(shù)大于10),其求解性能就下降很多。此外,在耗時(shí)上,CEBA也是最少的。由此可見(jiàn),改進(jìn)算法的優(yōu)化性能的提高是顯著的,實(shí)際優(yōu)化效果的改善是明顯的。

圖3 不同解空間維數(shù)下3種算法求解精度對(duì)比

為了進(jìn)一步探討本文所構(gòu)建的算法在求解高維函數(shù)優(yōu)化問(wèn)題時(shí)維數(shù)的增加對(duì)算法尋優(yōu)效能的影響以及該算法的收斂性征,本文選取標(biāo)準(zhǔn)的 GA和PSO作為比較對(duì)象。首先以函數(shù)f1為例給出3種算法在解空間維數(shù)以10為起始點(diǎn)、步長(zhǎng)為10依次遞增到200時(shí)所求解得到的最優(yōu)目標(biāo)函數(shù)值變化情況如圖4所示。

圖4 不同解空間維數(shù)下3種算法最優(yōu)目標(biāo)函數(shù)值變化情況

圖4 顯示CEBA算法的求解精度隨著解空間維數(shù)的增加變化不大,表明CEBA算法適合求解高維函數(shù)優(yōu)化問(wèn)題。維數(shù)的增加對(duì)算法求解精度影響最大的是PSO算法,維數(shù)低于20維時(shí),其求解精度最高,但超過(guò)50維時(shí)其求解效果很差,GA算法總體上來(lái)說(shuō),其在求解高維問(wèn)題時(shí)的表現(xiàn)不佳。

其次,以函數(shù)f1和f5為例,在d=30時(shí)描繪出3種算法的收斂特征曲線如圖5和圖6所示,其中,x軸為迭代次數(shù)n;y軸為每次迭代的最優(yōu)函數(shù)值fmin,且y軸采用對(duì)數(shù)刻度。

圖5 f1的3種算法收斂特征曲線對(duì)比

圖6 f5的3種算法收斂特征曲線對(duì)比

從圖5和圖6可以看出,CEBA算法的收斂速度明顯快于GA和PSO 2種算法,同時(shí)其求解精度也是最高的。進(jìn)一步表明CEBA算法不僅提高搜索精度、增強(qiáng)算法穩(wěn)定性,同時(shí)也改善了算法收斂速度。

5 結(jié)束語(yǔ)

針對(duì)高維函數(shù)優(yōu)化這一復(fù)雜問(wèn)題,本文構(gòu)建了一種新的交叉熵蝙蝠協(xié)同演化算法,該算法將交叉熵隨機(jī)優(yōu)化技術(shù)嵌入到蝙蝠算法的迭代過(guò)程中,利用交叉熵方法的隨機(jī)性、自適應(yīng)性和魯棒性改善蝙蝠算法的全局尋優(yōu)能力;同時(shí),利用蝙蝠算法加快交叉熵收斂,實(shí)現(xiàn)協(xié)同演化,從而保證新算法能快速獲得全局最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明,CEBA與標(biāo)準(zhǔn)的BA和CE算法相比,優(yōu)化性能得到很大提高,收斂速度更快,求解精度更高,具有比經(jīng)典的智能算法如GA和PSO更好的尋優(yōu)性能和穩(wěn)定性,搜尋精度高和收斂速度快。同時(shí)與文獻(xiàn)[23]的結(jié)果相比較, CEBA求解精度更高且成本更低,與文獻(xiàn)[24]的結(jié)果相比較,CEBA算法具有更好、更快的全局尋優(yōu)能力。3個(gè)測(cè)試和對(duì)比結(jié)果表明,該算法用于求解復(fù)雜的高維函數(shù)優(yōu)化問(wèn)題是可行性和有效的,即使是超高維問(wèn)題該算法仍然適用。

[1] Schoen F.GlobalOptimization MethodsforHighdimensionalProblems[J].European Journal of Operational Research,1999,119(2):345-352.

[2] Grosan C,Abraham A.A Novel Global Optimization Technique forHigh DimensionalFunctions[J]. International Journal of Intelligent Systems,2009,24(4): 421-440.

[3] Grosan C,Abraham A,Hassainen A E.A Line Search Approach for High Dimensional Function Optimization [J].Telecommunication Systems,2011,46(3):217-243.

[4] Hedar A,Fouad A.Genetic Algorithm with Population Partitioning and Space Reduction for High Dimensional Problems[C]//Proc.of 2009 International Conference on Computer Engineering and Systems.Cairo,Egypt: IEEE Computer Press,2009:151-156.

[5] 武慧虹,錢(qián)淑渠,徐志丹.克隆選擇免疫遺傳算法對(duì)高維0/1背包問(wèn)題應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2013,33 (3):845-848,870.

[6] Jia D L,Zheng G X,Qu B Y,et al.A Hybrid Particle Swarm Optimization Algorithm for High-dimensional Problems[J].Computers&Industrial Engineering, 2011,61(4):1117-1122.

[7] Martins A A,OluyinkaA A.AnAdaptiveVelocity Particle Swarm Optimization for High-dimensional Function Optimization[C]//Proc.of2013 IEEE Congress on Evolutionary Computation.Cancún,The United States of Mexico:IEEE Computer Press,2013: 2352-2359.

[8] 陳義雄,梁昔明,黃亞飛.一種改進(jìn)的混沌量子粒子群優(yōu)化算法[J].計(jì)算機(jī)工程,2013,39(8):253-256.

[9] Yang Z Y,Tang K,Yao X.Differential Evolution for High-dimensional Function Optimization[C]//Proc.of 2007 IEEE Congress on Evolutionary Computation. Singapore:IEEE Computer Press,2007:3523-3530.

[10] 林志毅,王玲玲.求解高維函數(shù)優(yōu)化問(wèn)題的混合蜂群算法[J].計(jì)算機(jī)科學(xué),2013,40(3):279-282.

[11] Ren Y F,Wu Y.An Efficient Algorithm for Highdimensional Function Optimization[J].Soft Computing, 2013,17(6):995-1004.

[12] Rubinstein R Y,Kroese D P.The Cross-entropy Method: A Unified Approach to Combinatorial Optimization, Monte Carlo Simulation and Machine Learning[M]. New York,USA:Springer-Verlag,2004.

[13] Margolin L.On the Convergence of the Cross-Entropy Method[J].Annals of Operations Research,2005, 134(1):201-214.

[14] Kroese D P,Portsky S,Rubinstein R Y.The Cross-entropy Method for Continuous Multi-extremal Optimization[J]. Methodology and Computing in Applied Probability,2006, 8(3):383-407.

[15] 李 潔,柴天佑,宮經(jīng)寬.基于交叉熵算法的PID控制器設(shè)計(jì)[J].控制與決策,2011,26(5):794-796,800.

[16] Yildiz T,Yercan F.The Cross-entropy Method for Combinatorial Optimization Problems of Seaport Logistics Terminal[J].Transport,2010,25(4):411-422.

[17] Yang X S.A New Metaheuristic Bat-inspired Algorithm [M].Berlin,Germany:Springer,2010:65-74.

[18] Yang X S.Bat Algorithm for Multi-objective Optimization [J].International Journal Bio-inspired Computation,2011, 3(5):267-274.

[19] Yang X S,Gandomi A H.Bat Algorithm:A Novel Approach for Global Engineering Optimization[J]. Engineering Computation,2012,29(5):267-289.

[20] 劉長(zhǎng)平,葉春明,劉滿成.來(lái)自大自然的尋優(yōu)策略:像蝙蝠一樣感知[J].計(jì)算機(jī)應(yīng)用研究,2013,30(5): 1320-1322,1356.

[21] 劉長(zhǎng)平,葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統(tǒng)學(xué)報(bào),2013,8(3):240-246.

[22] Lin J H,Chou C W,Yang C H,et al.A Chaotic Levy FlightBatAlgorithm forParameterEstimation in Nonlinear Dynamic Biological Systems[J].Computer and Information Technology,2012,2(2):56-63.

[23] 李枝勇,馬 良,張惠珍.蝙蝠算法收斂性分析[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2013,43(12):182-190.

[24] 黃光球,趙魏娟,陸秋琴.求解大規(guī)模優(yōu)化問(wèn)題的可全局收斂蝙蝠算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(5): 1323-1328.

[25] Nakamura R Y M,Pereira L A M,Costa K A,et al. BBA:A Binary Bat Algorithm for Feature Selection [C]//Proc.of the 25th SIBGRAPI Conference on Graphics,Patterns and Images.[S.l.]:IEEE Publication, 2012:291-297.

[26] 李枝勇,馬 良,張惠珍.0-1規(guī)劃問(wèn)題的元胞蝙蝠算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(10):2903-2906.

[27] Yao X,Liu Y,Lin G M.Evolutionary Programming Made Faster[J].IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.

[28] Suganthan P N,Hansen N,Liang J J,et al.Problem Definitions and Evaluation Criteria for the CEC2005 Special Session on Real-parameter Optimisation[R]. Singapore:Nanyang Technological University,Technical Report:CEC2005005,2005.

[29] Yang Z Y,Tang K,Yao X.Large Scale Evolutionary Optimization Using Cooperative Coevolution[J]. Information Sciences,2008,178(15):2985-2999.

[30] Sun L,Yoshida S,Cheng X C,et al.A Cooperative ParticleSwarm Optimizerwith StatisticalVariable Interdependence Learning[J].Information Sciences, 2012,186(1):20-39.

編輯 索書(shū)志

圖15 Zernike矩校正前后對(duì)比

從圖14、圖15中可以看出,空間矩和Zernike矩校正后算法檢測(cè)的邊緣信息明顯比校正前豐富。而灰度矩校正前后效果不明顯,筆者認(rèn)為實(shí)際圖像存在較大的噪聲,而灰度矩對(duì)噪聲敏感,導(dǎo)致校正效果不明顯。

4 結(jié)束語(yǔ)

本文針對(duì)矩方法邊緣檢測(cè)存在的原理誤差,采用誤差校正表校正誤差,通過(guò)構(gòu)造理想測(cè)試圖片生成誤差校正表,并利用誤差校正表的對(duì)稱(chēng)性減小校正表規(guī)模。實(shí)驗(yàn)結(jié)果表明,校正后比校正前檢測(cè)精度提高了一個(gè)數(shù)量級(jí)。由于校正算法僅進(jìn)行雙線性插值,因此本文算法能夠達(dá)到實(shí)時(shí)檢測(cè)。本文算法僅考慮邊緣距離的誤差,而并未考慮誤差較小的邊緣角度誤差,因此,針對(duì)邊緣角度誤差的校正算法將是下一步的研究?jī)?nèi)容。

參考文獻(xiàn)

[1] Hueckel M H.An Operator Which Locates Edges in Digitized Pictures[J].Journal of the ACM,1971,18 (1):113-125.

[2] 尚雅層,陳 靜,田軍委.高斯擬合亞像素邊緣檢測(cè)算法[J].計(jì)算機(jī)應(yīng)用,2011,31(1):179-181.

[3] Haralick R M.Digital Step Edges from Zero Crossing of Second Directional Derivatives[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,6 (1):58-68.

[4] Zhao Ping,Zhao Wenzhen,Duan Zhenyun,etal. Subpixel-precise Edge Extraction Algorithm Based on FacetModel[C]//Proc.ofthe 4th International Conference on Computational and Information Sciences. [S.l.]:IEEE Press,2012:86-88.

[5] Tabatabai A J,Mitchell O R,Edge Location to Subpixel Values in Digital Imagery[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1984,6(2): 188-201.

[6] Lyvers E P.Subpixel Measurements Using a Moment-based Edge Operator[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(12):1293-1309.

[7] Ghosal S,Mehrotra R.Orthogonal Moment Operators for Subpixel Edge Detection[J].Pattern Recognition,1993, 26(2):295-306.

[8] 朱遵尚,劉肖琳.基于GPU的實(shí)時(shí)亞像素Harris角點(diǎn)檢測(cè)[J].計(jì)算機(jī)工程,2010,36(12):213-215.

[9] 劉 倩,閆宇壯,黃新生.基于邊緣特征的亞像素相關(guān)匹配跟蹤算法[J].計(jì)算機(jī)工程,2011,37(8):201-203.

[10] 劉亞威.空間矩亞像素圖像測(cè)量算法的研究[D].重慶:重慶大學(xué),2003.

[11] Lyvers E P,Mitchell O R.Precision Edge Contrast and Orientation Estimation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(6):927-937.

[12] 賀忠海,廖怡白.理想邊緣產(chǎn)生方法的研究[J].光學(xué)精密工程,2002,10(1):89-93.

編輯 顧逸斐

Cross-entropy Bat Algorithm for Solving High-dimensional Function Optimization Problem

LI Guo-cheng1,2,XIAO Qing-xian1
(1.Business School,University of Shanghai for Science and Technology,Shanghai 200093,China;
2.School of Finance and Mathematics,West Anhui University,Lu’an 237012,China)

In order to enhance the global search ability of bat algorithm in solving high-dimensional function optimization problems,a Cross-entropy Bat Algorithm(CEBA)is proposed by combining bat algorithm with CE method. The CE global stochastic optimization algorithm which is based on importance sampling and Kullback-Leibler divergence,is embedded into bat algorithm.By using adaptive smoothing technique,CEBA improves the rate of convergence.The improved algorithm fully absorbs the ergodicity,adaptability and robustness of CE,adaptively avoids the stagnancy of population,and enhances the global search ability.Simulated results conducted on classical benchmarks and 10 CEC2005 benchmarks show that the proposed algorithm possesses more powerful global search capacity,higher optimization precision and robustness.

high-dimensional function optimization;Bat Algorithm(BA);Cross-entropy(CE);importance sampling; adaptive smoothing;co-evolution

1000-3428(2014)10-0168-07

A

TP183

10.3969/j.issn.1000-3428.2014.10.032

國(guó)家自然科學(xué)基金資助項(xiàng)目(11171221);上海市一流學(xué)科(系統(tǒng)科學(xué))基金資助項(xiàng)目(XTKX2012)。

李國(guó)成(1976-),男,副教授、博士研究生,主研方向:智能計(jì)算;肖慶憲,教授、博士生導(dǎo)師。

2013-09-25

2013-11-27E-mail:ligc313@163.com

中文引用格式:李國(guó)成,肖慶憲.求解高維函數(shù)優(yōu)化問(wèn)題的交叉熵蝙蝠算法[J].計(jì)算機(jī)工程,2014,40(10):168-174,180.

英文引用格式:Li Guocheng,Xiao Qingxian.Cross-entropy Bat Algorithm for Solving High-dimensional Function Optimization Problem[J].Computer Engineering,2014,40(10):168-174,180.