孫成碩,戚志東,葉偉琴,單 梁
南京理工大學(xué) 自動(dòng)化學(xué)院,南京 210094
元啟發(fā)式算法是基于計(jì)算智能的機(jī)制求解復(fù)雜優(yōu)化問(wèn)題最優(yōu)解的方法,也稱為智能優(yōu)化算法。智能優(yōu)化是對(duì)生物、物理、化學(xué)、社會(huì)、藝術(shù)等系統(tǒng)或領(lǐng)域中相關(guān)行為、功能、經(jīng)驗(yàn)、機(jī)理的認(rèn)識(shí),揭示優(yōu)化算法的設(shè)計(jì)原理,在特定問(wèn)題特征的引導(dǎo)下提煉相應(yīng)的特征模型,設(shè)計(jì)智能化的迭代搜索型優(yōu)化算法。常見(jiàn)的元啟發(fā)式算法有粒子群優(yōu)化(PSO)算法[1-2]、差分進(jìn)化算法[3-4]、布谷鳥(niǎo)算法[5]、螢火蟲(chóng)算法[6]等。PSO算法是一種基于群體智能的全局隨機(jī)尋優(yōu)算法,通過(guò)模仿鳥(niǎo)類的覓食行為,將問(wèn)題的搜索空間類比于鳥(niǎo)類的飛行空間,每一只鳥(niǎo)可以抽象為一顆微粒,最優(yōu)解相當(dāng)于鳥(niǎo)尋找的食物。差分進(jìn)化算法是通過(guò)選擇、交叉、變異更新種群個(gè)體,尋找最優(yōu)解。布谷鳥(niǎo)搜索算法(CS)是2009年劍橋大學(xué)楊新社所提出的一種群智能優(yōu)化算法,它是通過(guò)模擬某些種屬布谷鳥(niǎo)的寄生育雛這一生物習(xí)性,來(lái)有效地求解最優(yōu)問(wèn)題的算法。螢火蟲(chóng)算法(FA)是把空間各點(diǎn)看成螢火蟲(chóng),利用發(fā)光強(qiáng)的螢火蟲(chóng)會(huì)吸引發(fā)光弱的螢火蟲(chóng)的特點(diǎn)。在發(fā)光弱的螢火蟲(chóng)向發(fā)光強(qiáng)的螢火蟲(chóng)移動(dòng)的過(guò)程中,完成位置的迭代,從而找出最優(yōu)位置。螢火蟲(chóng)算法被應(yīng)用到幾乎所有領(lǐng)域科學(xué)和工程,如數(shù)字圖像壓縮和圖像處理、特征值優(yōu)化、工程結(jié)構(gòu)設(shè)計(jì)、調(diào)度和旅行商問(wèn)題[6-9]。近年來(lái),一些新興的元啟發(fā)式優(yōu)化算法也不斷提出,如飛蛾優(yōu)化算法、麻雀搜索算法等。飛蛾優(yōu)化算法(MFO)[10]是飛蛾根據(jù)光照方向來(lái)和自身夾角來(lái)調(diào)整飛行方向,產(chǎn)生螺旋式逼近光源的飛行路徑來(lái)搜尋最優(yōu)解。麻雀搜索算法(SSA)[11]主要是受麻雀的覓食行為和反捕食行為的啟發(fā),通過(guò)發(fā)現(xiàn)者與加入者的位置更新來(lái)尋找全局最優(yōu)解。
受美國(guó)帝王蝶在遷徙行為的影響,Wang等[12]提出了帝王蝶優(yōu)化算法(MBO)。MBO優(yōu)化算法通過(guò)調(diào)整算子與遷移算子進(jìn)行粒子位置更新,兩個(gè)算子同時(shí)進(jìn)行,一方面增加了粒子的多樣性,另一方面權(quán)衡了粒子的集中性。適合并行處理問(wèn)題,且在多領(lǐng)域廣泛運(yùn)用[13-14]。
在一般問(wèn)題處理中,MBO具有較好的收斂性與較快的運(yùn)行速度,能較為準(zhǔn)確地找到最優(yōu)解。但由于其調(diào)整算子的調(diào)整率與遷移率不變,易使問(wèn)題陷入局部最優(yōu)解。同時(shí),在一些復(fù)雜的測(cè)試中,MBO搜尋不到最優(yōu)的解。故如何避免MBO陷入局部最優(yōu)解同時(shí)不能增加運(yùn)行的復(fù)雜度成為該算法研究方向。
孫林等[15]通過(guò)交叉遷移和共享調(diào)整對(duì)原始MBO算法的局部最優(yōu)解進(jìn)行了處理,使其更高效地尋找到全局最優(yōu)解。Ghanem等[16]將人工蜂群算法與MBO算法結(jié)合形成新的元啟發(fā)式算法。作為新興的一種算法,上述的改進(jìn)方法可以提高M(jìn)BO尋優(yōu)的性能,但是仍存在問(wèn)題,如遷移算子更新方式單一,種群的多樣性不足,搜索的位置有限等。
針對(duì)上述問(wèn)題,本文基于帝王蝶優(yōu)化算法,提出了變異反向?qū)W習(xí)的自適應(yīng)的MBO算法(adaptive monarch butterfly algorithm based on mutation reverse learning,ALMBO)。首先,在MBO的遷移算子中引入變異反向?qū)W習(xí)策略,對(duì)蝴蝶的位置進(jìn)行變異更新,增加種群的多樣性,避免算法陷入局部最優(yōu)解。然后,將MBO的調(diào)整算子改成自適應(yīng)的調(diào)整算子,使MBO中的調(diào)整算子隨著迭代次數(shù)的變化進(jìn)行線性調(diào)整,提高了算法適應(yīng)度,增強(qiáng)算法的尋優(yōu)能力。通過(guò)實(shí)驗(yàn)對(duì)比本文所提出的算法與其他類似算法的尋優(yōu)能力,驗(yàn)證ALMBO的有效性。
帝王蝶作為最常見(jiàn)的北美蝴蝶之一,其翅膀上橙色和黑色花紋很容易辨認(rèn)。研究者們發(fā)現(xiàn),帝王蝶每年春天都會(huì)遷移數(shù)千英里從加拿大南部飛往墨西哥的中部地區(qū),到了秋季又會(huì)往相反的方向飛行,其遷徙能力在蝴蝶綱目中首屈一指。
MBO是模仿帝王蝶的遷移行為來(lái)解決各種優(yōu)化問(wèn)題,可將其遷移規(guī)律理想化為如下假設(shè):
(1)所有的帝王蝶只分布在Land1和Land2中。Land1和Land2是種群所在地。
(2)每只小帝王蝶個(gè)體是由Land1和Land2的帝王蝶的遷移算子生成的。
(3)保持種群數(shù)不變,即老的帝王蝶在更新為新的小帝王蝶時(shí)死去。但若新的小帝王蝶適應(yīng)度不如老的帝王蝶,則拋棄新的小帝王蝶,保留老的帝王蝶。
(4)適應(yīng)值最優(yōu)的帝王蝶會(huì)自動(dòng)遷移到下一代,保證其帝王蝶的質(zhì)量。
新的帝王蝶是通過(guò)遷移算子從Land1和Land2的帝王蝶中產(chǎn)生。Land1中的帝王蝶代表種群1,Land2中的帝王蝶代表種群2。其中種群1的數(shù)量為:
其中,NP為L(zhǎng)and1和Land2總的種群數(shù),p為種群1與種群2中帝王蝶的比例,p=5/12,ceil(x)為舍入到大于或等于x的最接近的整數(shù)。
設(shè)定Land1和Land2中的子群分別稱為亞種群1和亞種群2,則遷移過(guò)程可以表示為:
其中,rand為[0,1]的隨機(jī)數(shù),peri表示為遷移周期,取值為1.2。
MBO中的調(diào)整算子是用來(lái)更新亞種群2中帝王蝶的位置。其位置更新可以表示為:
原始MBO中,帝王蝶每次位置更新是基于亞種群1和亞種群2中已有的粒子進(jìn)行重新選擇,但個(gè)體的數(shù)量有限,選擇性與隨機(jī)性不大。生成的粒子不具有多樣性,且生成的粒子易陷入局部最優(yōu)解。故本節(jié),受遺傳算法中變異概率思想的啟發(fā),將變異概率與反向?qū)W習(xí)策略進(jìn)行結(jié)合,對(duì)帝王蝶的位置進(jìn)行干擾更新,增加種群的多樣性同時(shí)加快了收斂的速度。
反向?qū)W習(xí)(opposition-based learning,OBL)是Tizhoosh[17]于2005年提出的數(shù)學(xué)方法,其本質(zhì)使通過(guò)估計(jì)和比較可行解及其反向解,選擇最好的解進(jìn)入下一次迭代。反向?qū)W習(xí)的數(shù)學(xué)表征為:
其中,a,b分別是(a,b)區(qū)間中的上下限,c是源數(shù),P是源數(shù)的反向數(shù)字。
反向?qū)W習(xí)的引入使收斂速度加快。優(yōu)化算法的計(jì)算時(shí)間與初始種群中個(gè)體與最優(yōu)個(gè)體的距離有關(guān),個(gè)體若在最優(yōu)值附近出生,則這一次的迭代計(jì)算中種群的所有個(gè)體都會(huì)進(jìn)行快速的收斂。而純隨機(jī)生成的個(gè)體由于沒(méi)有進(jìn)行過(guò)估計(jì),收斂速度是無(wú)法預(yù)知的。
故本文將變異反向?qū)W習(xí)融入MBO算法中,其數(shù)學(xué)表達(dá)式為:
在原始的MBO優(yōu)化算法中,遷移率p與調(diào)整率BAR是一個(gè)固定值,在整個(gè)迭代中都不會(huì)發(fā)生變化。這樣就使得在Land1和Land2中的帝王蝶通過(guò)調(diào)整算子進(jìn)行局部更新時(shí),易陷入局部最優(yōu)解。同時(shí),調(diào)整算子生成的所有亞種群個(gè)體都直接被接受,繼承的方式過(guò)于簡(jiǎn)單。因此,為使種群多樣化,將自適應(yīng)的策略引入到調(diào)整算子中,形成自適應(yīng)調(diào)整算子,其公式如下:
其中,t m是當(dāng)前最大迭代次數(shù),BARmax、BARmin是調(diào)整率的上下界,其范圍為[0,1]。為擴(kuò)大參數(shù)選取的范圍,設(shè)定BARmax=0.8,BARmin=0.2。同時(shí),在第一次迭代的過(guò)程中,遷移率p與調(diào)整率BAR取5/12。
柯西變異的理論基礎(chǔ)是柯西分布函數(shù),一維柯西分布的概率密度如圖1所示。
圖1 概率密度曲線Fig.1 Probability density curve
柯西分布在兩端趨于0的速度較緩,且過(guò)程較為平穩(wěn),其原點(diǎn)附近的峰值與高斯原點(diǎn)附近的值相比較小,所以柯西變異在擾動(dòng)能力方面比高斯變異更強(qiáng)。引入柯西變異擾動(dòng)可以提高算法全局的搜索能力,防止陷入局部最優(yōu)解。在每次更新的種群中,將排序在最后的5只帝王蝶進(jìn)行柯西變異,使變異個(gè)體附近生成更大的擾動(dòng),使整個(gè)群體在更大的范圍內(nèi)進(jìn)行尋優(yōu)。其算法表達(dá)式為:
其中,柯西隨機(jī)變量生成函數(shù)為η=tan(π(ξ-0.5)),ξ∈rand(0,1)。
由于MBO易陷入局部最優(yōu)解,故本文針對(duì)這一問(wèn)題,提出了變異反向?qū)W習(xí)策略擴(kuò)大種群的多樣性,提高其收斂性。同時(shí),對(duì)于原始MBO算法中遷移率與調(diào)整率固定,本文提出了自適應(yīng)的調(diào)整算子,在優(yōu)化的過(guò)程中對(duì)帝王蝶的調(diào)整率進(jìn)行線性調(diào)整,增強(qiáng)算法的尋優(yōu)能力。最后,將每次適應(yīng)度排在最后的5個(gè)粒子進(jìn)行柯西變異擾動(dòng),擺脫其局部最優(yōu)解,更大程度上激發(fā)粒子尋找全局最優(yōu)解的潛力。算法的流程圖如圖2所示。
圖2 ALMBO算法流程圖Fig.2 Flow chart of ALMBO algorithm
時(shí)間復(fù)雜度反映了算法的運(yùn)行效率。設(shè)種群數(shù)為N,亞種群1規(guī)模為N1,則亞種群2規(guī)模為N-N1,優(yōu)化問(wèn)題維度為D維,參數(shù)初始化為O(1),計(jì)算函數(shù)適應(yīng)度為O(N),迭代過(guò)程中種群復(fù)雜O(ND)。其復(fù)雜度計(jì)算公式如下:
(1)計(jì)算帝王蝶函數(shù)的適應(yīng)度所需為O(N)。
(2)排序的時(shí)間復(fù)雜度為O(N2)。
(3)帝王蝶分成了2個(gè)子群,時(shí)間復(fù)雜度為O(N)。
(4)在遷移算子中的引入變異反向?qū)W習(xí)策略,有2個(gè)內(nèi)循環(huán),時(shí)間復(fù)雜度為O(DN1)。
(5)在調(diào)整算子中引入自適應(yīng)策略,存在2個(gè)內(nèi)循環(huán),時(shí)間復(fù)雜度為O(D(N-N1))。優(yōu)化算法ALMBO總時(shí)間復(fù)雜度為:
上述分析可知,ALMBO算法在時(shí)間復(fù)雜度上與原始MBO時(shí)間復(fù)雜度是相當(dāng)?shù)摹?/p>
引理1波萊爾-坎泰利(Borel-Cantelli)設(shè)B1,B2,…,B n是概率空間上相互獨(dú)立的事件系列,p(B k)是每個(gè)事件系列對(duì)應(yīng)的概率,則有:
定理1ALMBO算法中的解序列{X t,t≥0}是有限狀態(tài)空間的齊次馬爾科夫鏈。
證明ALMBO算法在狀態(tài)轉(zhuǎn)移過(guò)程中都是在有限空間中進(jìn)行的,算法中的變異反向?qū)W習(xí)遷移,自適應(yīng)調(diào)整,柯西變異干擾等操作都是滿足獨(dú)立隨機(jī)的過(guò)程,并且整個(gè)迭代進(jìn)化過(guò)程都是采取的保留最優(yōu)個(gè)體的機(jī)制,第t+1代的種群Qt+1只是受第t代種群Q t的影響,與種群之前的信息無(wú)關(guān)。因此{(lán)X t,t≥0}是有限狀態(tài)空間的齊次馬爾科夫鏈。
引理2在ALMBO算法的狀態(tài)空間中,存在常數(shù)μ∈(0,1),使條件p ij<μ成立,p ij表示從狀態(tài)空間A i轉(zhuǎn)移到狀態(tài)空間A j的概率[19]。
定理2ALMBO優(yōu)化算法以概率1收斂到全局最優(yōu)解。
實(shí)驗(yàn)選取文獻(xiàn)[20]、文獻(xiàn)[21]中典型的8個(gè)基準(zhǔn)函數(shù)測(cè)試ALMBO的性能,如表1所示。同時(shí)為驗(yàn)證其性能,選擇飛蛾優(yōu)化算法(MFO)、麻雀搜索算法(SSA)、PSO優(yōu)化算法以及MBO算法進(jìn)行比較。實(shí)驗(yàn)環(huán)境為Windows10,64位操作系統(tǒng),CPU為Inter Core i5-6500H,主頻為3.2 GHz,內(nèi)存8 GB,算法是使用MATLAB-2014b,使用M語(yǔ)言編寫。為保證對(duì)比的公平性,算法基本參數(shù)設(shè)置相同:種群規(guī)模為50,測(cè)試函數(shù)維數(shù)30/50,最大迭代次數(shù)為1 000次,各算法獨(dú)立運(yùn)行50次。
表1 基準(zhǔn)函數(shù)Table 1 Benchmark function
5種優(yōu)化算法的8個(gè)基準(zhǔn)函數(shù)的測(cè)試結(jié)果如表2和表3所示。通過(guò)對(duì)表2和表3的結(jié)果分析,MFO、SSA、MBO對(duì)于單峰函數(shù)問(wèn)題求解上具有較強(qiáng)的搜索能力,精度較高。在對(duì)于多峰函數(shù)優(yōu)化問(wèn)題求解時(shí),其局限性就體現(xiàn)出來(lái),其求解精度不理想。PSO優(yōu)化算法同樣如此,對(duì)于多峰函數(shù)尋優(yōu)效果更差。而本文所提出的ALMBO算法無(wú)論在30維或50維,多峰或單峰在求解精度上都比其他四種優(yōu)化算法要高。對(duì)于30維的f2、f3與f5函數(shù)可以搜到理論最優(yōu)值0。ALMBO在多次尋優(yōu)的平均值與標(biāo)準(zhǔn)差都優(yōu)于其余四種算法,但在50維f7多峰函數(shù)的尋優(yōu)中,其余四種算法陷入了局部最優(yōu)解,故每次尋優(yōu)結(jié)果相近,標(biāo)準(zhǔn)差小。ALMBO雖標(biāo)準(zhǔn)差大于其余四種函數(shù),但其可以跳出局部最優(yōu)解,尋優(yōu)精度高于其余四種算法。故認(rèn)為引入變異反向?qū)W習(xí)與自適應(yīng)策略有助于算法搜尋最優(yōu)值,規(guī)避了局部最優(yōu)解,防止算法在不同程度上早熟。同時(shí),在種群更新中引入柯西變異干擾,保持了其多樣性,獲得了較好的尋優(yōu)能力。
表2 30維結(jié)果分析Table 2 Analysis of 30 dimensional results
表3 50維結(jié)果分析Table 3 Analysis of 50 dimensional results
在尋優(yōu)時(shí)間上,PSO算法因其算法結(jié)構(gòu)簡(jiǎn)單,故平均耗時(shí)最短。MBO與ALMBO引入了調(diào)整算子與遷移算子,同時(shí)ALMBO在算子上進(jìn)行了處理,故這兩種優(yōu)化算法的平均耗時(shí)比PSO、MFO要長(zhǎng)。但從表2可以看出,在30維情況下,ALMBO的平均耗時(shí)與MBO相比不超過(guò)0.3 s。在50維情況下,ALMBO的平均耗時(shí)與MBO相比不超過(guò)0.4 s,雖稍犧牲了些尋優(yōu)時(shí)間,但其時(shí)間在可接受的范圍內(nèi)。
上一節(jié)通過(guò)最優(yōu)值、平均值與平均耗時(shí)等指標(biāo)對(duì)5種優(yōu)化算法進(jìn)行了比較,但僅通過(guò)50次獨(dú)立運(yùn)行的最優(yōu)值、平均值是不能較信服地說(shuō)明ALMBO算法的優(yōu)越性,故需要進(jìn)行統(tǒng)計(jì)檢驗(yàn)來(lái)說(shuō)明本文所提出的算法與其他算法相比有顯著性的差異。采用Wilcoxon秩和檢驗(yàn)來(lái)驗(yàn)證ALMBO每次運(yùn)行結(jié)果在p=5%的顯著性水平下與其他算法是否有顯著性差異,當(dāng)p>5%時(shí),可以認(rèn)為接受假定H0,即認(rèn)為兩種優(yōu)化算法之間不存在顯著性差異,算法尋優(yōu)能力相當(dāng);當(dāng)p<5%時(shí),則拒絕假設(shè)H0,即兩種算法之間存在顯著性差異。表4是ALMBO與MFO、SSA、PSO、MBO在顯著性水平p=5%,維度50維下的比較結(jié)果。由于算法自身無(wú)法跟自身性能相比,故用N/A來(lái)表示。從表4可以看出,檢驗(yàn)的p值大部分都遠(yuǎn)小于5%,故認(rèn)為ALMBO與其他四種算法存在顯著性差異,并且ALMBO的算法顯著性更佳。
表4 Wilcoxon秩和檢驗(yàn)的p值Table 4 Wilcoxon rank and p value
圖3給出了在30維的條件下8個(gè)基準(zhǔn)函數(shù)的平均收斂曲線圖。為方便地觀察收斂的情況,對(duì)尋優(yōu)的適應(yīng)度值(縱坐標(biāo))取10為底的對(duì)數(shù)。由圖3(a)至(h)中可以看出,對(duì)于單峰函數(shù)(圖(a)~(e)),MFO、PSO等可以達(dá)到較高的精度,而對(duì)于多峰函數(shù),其收斂精度明顯下降。而無(wú)論是單峰函數(shù)還是多峰函數(shù),對(duì)于每一個(gè)基準(zhǔn)函數(shù),ALMBO比其他優(yōu)化算法的收斂精度和速度都要好。圖(c)與圖(e)分別為在迭代次數(shù)300次與500次內(nèi)搜索到最優(yōu)值0,故在圖中后部分沒(méi)有顯示。由此說(shuō)明,ALMBO具有較強(qiáng)的搜索能力,能夠快速地跳出局部最優(yōu)解向全局最優(yōu)解靠近。
圖3 f1~f8平均收斂曲線Fig.3 Mean convergence curves of f1~f8 strategies
本文在原始帝王蝶算法的基礎(chǔ)上,引入了變異方向?qū)W習(xí)策略、自適應(yīng)權(quán)重以及柯西變異,提出了一種改進(jìn)的變異反向?qū)W習(xí)的自適應(yīng)帝王蝶優(yōu)化算法。并將ALMBO與MFO、SSA、PSO、MBO算法在30維/50維的8個(gè)基準(zhǔn)函數(shù)進(jìn)行對(duì)比檢驗(yàn),同時(shí),還運(yùn)用了Wilcoxon秩和檢驗(yàn)的方法,通過(guò)顯著性水平來(lái)驗(yàn)證ALMBO算法的優(yōu)越性。實(shí)驗(yàn)表明,ALMBO可以獲得更好的全局最優(yōu)解與收斂速度。在未來(lái)的研究中,考慮將算法應(yīng)用到系統(tǒng)辨識(shí)與滾動(dòng)優(yōu)化中,以進(jìn)一步驗(yàn)證算法的性能。