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

李國成,肖慶憲

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

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

李國成1,2,肖慶憲1

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

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

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

1 概述

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

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

2 標準蝙蝠算法和交叉熵優(yōu)化方法

2.1 蝙蝠算法

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

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

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

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

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

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

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

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

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

CE全局隨機優(yōu)化算法的實施過程為:

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

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

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

3 交叉熵蝙蝠算法

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

3.1 算法原理

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

3.2 算法步驟和流程描述

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

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

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

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

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

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

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

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

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

(1)初始化參數(shù),計算種群各維的均值μ^和標準差。

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

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

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

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

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

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

圖1 CEBA算法流程

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

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

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

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

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

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

4 數(shù)值仿真

4.1 測試問題與比較對象

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

表1 測試問題和比較對象

4.2 參數(shù)設置與測試結果

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

表2 測試1的測試結果與對比

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

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

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

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

表3 測試2中d=30時的測試結果與對比

表5 測試3的測試結果與對比

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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

[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] 武慧虹,錢淑渠,徐志丹.克隆選擇免疫遺傳算法對高維0/1背包問題應用[J].計算機應用,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] 陳義雄,梁昔明,黃亞飛.一種改進的混沌量子粒子群優(yōu)化算法[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)化問題的混合蜂群算法[J].計算機科學,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控制器設計[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] 劉長平,葉春明,劉滿成.來自大自然的尋優(yōu)策略:像蝙蝠一樣感知[J].計算機應用研究,2013,30(5): 1320-1322,1356.

[21] 劉長平,葉春明.具有Lévy飛行特征的蝙蝠算法[J].智能系統(tǒng)學報,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ù)學的實踐與認識,2013,43(12):182-190.

[24] 黃光球,趙魏娟,陸秋琴.求解大規(guī)模優(yōu)化問題的可全局收斂蝙蝠算法[J].計算機應用研究,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ī)劃問題的元胞蝙蝠算法[J].計算機應用研究,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.

編輯 索書志

圖15 Zernike矩校正前后對比

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

4 結束語

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

參考文獻

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

[2] 尚雅層,陳 靜,田軍委.高斯擬合亞像素邊緣檢測算法[J].計算機應用,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的實時亞像素Harris角點檢測[J].計算機工程,2010,36(12):213-215.

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

[10] 劉亞威.空間矩亞像素圖像測量算法的研究[D].重慶:重慶大學,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].光學精密工程,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

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

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

2013-09-25

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

中文引用格式:李國成,肖慶憲.求解高維函數(shù)優(yōu)化問題的交叉熵蝙蝠算法[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.