孫成碩，戚志東，葉偉琴，單 梁

南京理工大學 自動化學院，南京 210094

元啟發(fā)式算法是基于計算智能的機制求解復雜優(yōu)化問題最優(yōu)解的方法，也稱為智能優(yōu)化算法。智能優(yōu)化是對生物、物理、化學、社會、藝術等系統(tǒng)或領域中相關行為、功能、經(jīng)驗、機理的認識，揭示優(yōu)化算法的設計原理，在特定問題特征的引導下提煉相應的特征模型，設計智能化的迭代搜索型優(yōu)化算法。常見的元啟發(fā)式算法有粒子群優(yōu)化（PSO）算法[1-2]、差分進化算法[3-4]、布谷鳥算法[5]、螢火蟲算法[6]等。PSO算法是一種基于群體智能的全局隨機尋優(yōu)算法，通過模仿鳥類的覓食行為，將問題的搜索空間類比于鳥類的飛行空間，每一只鳥可以抽象為一顆微粒，最優(yōu)解相當于鳥尋找的食物。差分進化算法是通過選擇、交叉、變異更新種群個體，尋找最優(yōu)解。布谷鳥搜索算法（CS）是2009年劍橋大學楊新社所提出的一種群智能優(yōu)化算法，它是通過模擬某些種屬布谷鳥的寄生育雛這一生物習性，來有效地求解最優(yōu)問題的算法。螢火蟲算法（FA）是把空間各點看成螢火蟲，利用發(fā)光強的螢火蟲會吸引發(fā)光弱的螢火蟲的特點。在發(fā)光弱的螢火蟲向發(fā)光強的螢火蟲移動的過程中，完成位置的迭代，從而找出最優(yōu)位置。螢火蟲算法被應用到幾乎所有領域科學和工程，如數(shù)字圖像壓縮和圖像處理、特征值優(yōu)化、工程結(jié)構設計、調(diào)度和旅行商問題[6-9]。近年來，一些新興的元啟發(fā)式優(yōu)化算法也不斷提出，如飛蛾優(yōu)化算法、麻雀搜索算法等。飛蛾優(yōu)化算法（MFO）[10]是飛蛾根據(jù)光照方向來和自身夾角來調(diào)整飛行方向，產(chǎn)生螺旋式逼近光源的飛行路徑來搜尋最優(yōu)解。麻雀搜索算法（SSA）[11]主要是受麻雀的覓食行為和反捕食行為的啟發(fā)，通過發(fā)現(xiàn)者與加入者的位置更新來尋找全局最優(yōu)解。

受美國帝王蝶在遷徙行為的影響，Wang等[12]提出了帝王蝶優(yōu)化算法（MBO）。MBO優(yōu)化算法通過調(diào)整算子與遷移算子進行粒子位置更新，兩個算子同時進行，一方面增加了粒子的多樣性，另一方面權衡了粒子的集中性。適合并行處理問題，且在多領域廣泛運用[13-14]。

在一般問題處理中，MBO具有較好的收斂性與較快的運行速度，能較為準確地找到最優(yōu)解。但由于其調(diào)整算子的調(diào)整率與遷移率不變，易使問題陷入局部最優(yōu)解。同時，在一些復雜的測試中，MBO搜尋不到最優(yōu)的解。故如何避免MBO陷入局部最優(yōu)解同時不能增加運行的復雜度成為該算法研究方向。

孫林等[15]通過交叉遷移和共享調(diào)整對原始MBO算法的局部最優(yōu)解進行了處理，使其更高效地尋找到全局最優(yōu)解。Ghanem等[16]將人工蜂群算法與MBO算法結(jié)合形成新的元啟發(fā)式算法。作為新興的一種算法，上述的改進方法可以提高MBO尋優(yōu)的性能，但是仍存在問題，如遷移算子更新方式單一，種群的多樣性不足，搜索的位置有限等。

針對上述問題，本文基于帝王蝶優(yōu)化算法，提出了變異反向?qū)W習的自適應的MBO算法（adaptive monarch butterfly algorithm based on mutation reverse learning，ALMBO）。首先，在MBO的遷移算子中引入變異反向?qū)W習策略，對蝴蝶的位置進行變異更新，增加種群的多樣性，避免算法陷入局部最優(yōu)解。然后，將MBO的調(diào)整算子改成自適應的調(diào)整算子，使MBO中的調(diào)整算子隨著迭代次數(shù)的變化進行線性調(diào)整，提高了算法適應度，增強算法的尋優(yōu)能力。通過實驗對比本文所提出的算法與其他類似算法的尋優(yōu)能力，驗證ALMBO的有效性。

1 帝王蝶優(yōu)化算法

帝王蝶作為最常見的北美蝴蝶之一，其翅膀上橙色和黑色花紋很容易辨認。研究者們發(fā)現(xiàn)，帝王蝶每年春天都會遷移數(shù)千英里從加拿大南部飛往墨西哥的中部地區(qū)，到了秋季又會往相反的方向飛行，其遷徙能力在蝴蝶綱目中首屈一指。

MBO是模仿帝王蝶的遷移行為來解決各種優(yōu)化問題，可將其遷移規(guī)律理想化為如下假設：

（1）所有的帝王蝶只分布在Land1和Land2中。Land1和Land2是種群所在地。

（2）每只小帝王蝶個體是由Land1和Land2的帝王蝶的遷移算子生成的。

（3）保持種群數(shù)不變，即老的帝王蝶在更新為新的小帝王蝶時死去。但若新的小帝王蝶適應度不如老的帝王蝶，則拋棄新的小帝王蝶，保留老的帝王蝶。

（4）適應值最優(yōu)的帝王蝶會自動遷移到下一代，保證其帝王蝶的質(zhì)量。

1.1 遷移算子

新的帝王蝶是通過遷移算子從Land1和Land2的帝王蝶中產(chǎn)生。Land1中的帝王蝶代表種群1，Land2中的帝王蝶代表種群2。其中種群1的數(shù)量為：

其中，NP為Land1和Land2總的種群數(shù)，p為種群1與種群2中帝王蝶的比例，p=5/12，ceil(x)為舍入到大于或等于x的最接近的整數(shù)。

設定Land1和Land2中的子群分別稱為亞種群1和亞種群2，則遷移過程可以表示為：

其中，rand為[0，1]的隨機數(shù)，peri表示為遷移周期，取值為1.2。

1.2 調(diào)整算子

MBO中的調(diào)整算子是用來更新亞種群2中帝王蝶的位置。其位置更新可以表示為：

2 變異反向?qū)W習的自適應的MBO算法

2.1 變異反向?qū)W習遷移算子

原始MBO中，帝王蝶每次位置更新是基于亞種群1和亞種群2中已有的粒子進行重新選擇，但個體的數(shù)量有限，選擇性與隨機性不大。生成的粒子不具有多樣性，且生成的粒子易陷入局部最優(yōu)解。故本節(jié)，受遺傳算法中變異概率思想的啟發(fā)，將變異概率與反向?qū)W習策略進行結(jié)合，對帝王蝶的位置進行干擾更新，增加種群的多樣性同時加快了收斂的速度。

反向?qū)W習（opposition-based learning，OBL）是Tizhoosh[17]于2005年提出的數(shù)學方法，其本質(zhì)使通過估計和比較可行解及其反向解，選擇最好的解進入下一次迭代。反向?qū)W習的數(shù)學表征為：

其中，a,b分別是(a,b)區(qū)間中的上下限，c是源數(shù)，P是源數(shù)的反向數(shù)字。

反向?qū)W習的引入使收斂速度加快。優(yōu)化算法的計算時間與初始種群中個體與最優(yōu)個體的距離有關，個體若在最優(yōu)值附近出生，則這一次的迭代計算中種群的所有個體都會進行快速的收斂。而純隨機生成的個體由于沒有進行過估計，收斂速度是無法預知的。

故本文將變異反向?qū)W習融入MBO算法中，其數(shù)學表達式為：

2.2 自適應調(diào)整算子

在原始的MBO優(yōu)化算法中，遷移率p與調(diào)整率BAR是一個固定值，在整個迭代中都不會發(fā)生變化。這樣就使得在Land1和Land2中的帝王蝶通過調(diào)整算子進行局部更新時，易陷入局部最優(yōu)解。同時，調(diào)整算子生成的所有亞種群個體都直接被接受，繼承的方式過于簡單。因此，為使種群多樣化，將自適應的策略引入到調(diào)整算子中，形成自適應調(diào)整算子，其公式如下：

其中，t m是當前最大迭代次數(shù)，BARmax、BARmin是調(diào)整率的上下界，其范圍為[0，1]。為擴大參數(shù)選取的范圍，設定BARmax=0.8，BARmin=0.2。同時，在第一次迭代的過程中，遷移率p與調(diào)整率BAR取5/12。

2.3 柯西變異擾動

柯西變異的理論基礎是柯西分布函數(shù)，一維柯西分布的概率密度如圖1所示。

圖1 概率密度曲線Fig.1 Probability density curve

柯西分布在兩端趨于0的速度較緩，且過程較為平穩(wěn)，其原點附近的峰值與高斯原點附近的值相比較小，所以柯西變異在擾動能力方面比高斯變異更強。引入柯西變異擾動可以提高算法全局的搜索能力，防止陷入局部最優(yōu)解。在每次更新的種群中，將排序在最后的5只帝王蝶進行柯西變異，使變異個體附近生成更大的擾動，使整個群體在更大的范圍內(nèi)進行尋優(yōu)。其算法表達式為：

其中，柯西隨機變量生成函數(shù)為η=tan(π(ξ-0.5))，ξ∈rand(0,1)。

2.4 算法流程圖與步驟

由于MBO易陷入局部最優(yōu)解，故本文針對這一問題，提出了變異反向?qū)W習策略擴大種群的多樣性，提高其收斂性。同時，對于原始MBO算法中遷移率與調(diào)整率固定，本文提出了自適應的調(diào)整算子，在優(yōu)化的過程中對帝王蝶的調(diào)整率進行線性調(diào)整，增強算法的尋優(yōu)能力。最后，將每次適應度排在最后的5個粒子進行柯西變異擾動，擺脫其局部最優(yōu)解，更大程度上激發(fā)粒子尋找全局最優(yōu)解的潛力。算法的流程圖如圖2所示。

圖2 ALMBO算法流程圖Fig.2 Flow chart of ALMBO algorithm

2.5 時間復雜度的分析

時間復雜度反映了算法的運行效率。設種群數(shù)為N，亞種群1規(guī)模為N1，則亞種群2規(guī)模為N-N1，優(yōu)化問題維度為D維，參數(shù)初始化為O(1)，計算函數(shù)適應度為O(N)，迭代過程中種群復雜O(ND)。其復雜度計算公式如下：

（1）計算帝王蝶函數(shù)的適應度所需為O(N)。

（2）排序的時間復雜度為O(N2)。

（3）帝王蝶分成了2個子群，時間復雜度為O(N)。

（4）在遷移算子中的引入變異反向?qū)W習策略，有2個內(nèi)循環(huán)，時間復雜度為O(DN1)。

（5）在調(diào)整算子中引入自適應策略，存在2個內(nèi)循環(huán)，時間復雜度為O(D(N-N1))。優(yōu)化算法ALMBO總時間復雜度為：

上述分析可知，ALMBO算法在時間復雜度上與原始MBO時間復雜度是相當?shù)摹?/p>

2.6 收斂性分析

引理1波萊爾-坎泰利（Borel-Cantelli）設B1,B2,…,B n是概率空間上相互獨立的事件系列，p(B k)是每個事件系列對應的概率，則有：

定理1ALMBO算法中的解序列{X t,t≥0}是有限狀態(tài)空間的齊次馬爾科夫鏈。

證明ALMBO算法在狀態(tài)轉(zhuǎn)移過程中都是在有限空間中進行的，算法中的變異反向?qū)W習遷移，自適應調(diào)整，柯西變異干擾等操作都是滿足獨立隨機的過程，并且整個迭代進化過程都是采取的保留最優(yōu)個體的機制，第t+1代的種群Qt+1只是受第t代種群Q t的影響，與種群之前的信息無關。因此{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)解。

3 實驗及結(jié)果分析

3.1 參數(shù)設定

實驗選取文獻[20]、文獻[21]中典型的8個基準函數(shù)測試ALMBO的性能，如表1所示。同時為驗證其性能，選擇飛蛾優(yōu)化算法（MFO）、麻雀搜索算法（SSA）、PSO優(yōu)化算法以及MBO算法進行比較。實驗環(huán)境為Windows10，64位操作系統(tǒng)，CPU為Inter Core i5-6500H，主頻為3.2 GHz，內(nèi)存8 GB，算法是使用MATLAB-2014b，使用M語言編寫。為保證對比的公平性，算法基本參數(shù)設置相同：種群規(guī)模為50，測試函數(shù)維數(shù)30/50，最大迭代次數(shù)為1 000次，各算法獨立運行50次。

表1 基準函數(shù)Table 1 Benchmark function

3.2 算法性能分析

5種優(yōu)化算法的8個基準函數(shù)的測試結(jié)果如表2和表3所示。通過對表2和表3的結(jié)果分析，MFO、SSA、MBO對于單峰函數(shù)問題求解上具有較強的搜索能力，精度較高。在對于多峰函數(shù)優(yōu)化問題求解時，其局限性就體現(xiàn)出來，其求解精度不理想。PSO優(yōu)化算法同樣如此，對于多峰函數(shù)尋優(yōu)效果更差。而本文所提出的ALMBO算法無論在30維或50維，多峰或單峰在求解精度上都比其他四種優(yōu)化算法要高。對于30維的f2、f3與f5函數(shù)可以搜到理論最優(yōu)值0。ALMBO在多次尋優(yōu)的平均值與標準差都優(yōu)于其余四種算法，但在50維f7多峰函數(shù)的尋優(yōu)中，其余四種算法陷入了局部最優(yōu)解，故每次尋優(yōu)結(jié)果相近，標準差小。ALMBO雖標準差大于其余四種函數(shù)，但其可以跳出局部最優(yōu)解，尋優(yōu)精度高于其余四種算法。故認為引入變異反向?qū)W習與自適應策略有助于算法搜尋最優(yōu)值，規(guī)避了局部最優(yōu)解，防止算法在不同程度上早熟。同時，在種群更新中引入柯西變異干擾，保持了其多樣性，獲得了較好的尋優(yōu)能力。

表2 30維結(jié)果分析Table 2 Analysis of 30 dimensional results

表3 50維結(jié)果分析Table 3 Analysis of 50 dimensional results

在尋優(yōu)時間上，PSO算法因其算法結(jié)構簡單，故平均耗時最短。MBO與ALMBO引入了調(diào)整算子與遷移算子，同時ALMBO在算子上進行了處理，故這兩種優(yōu)化算法的平均耗時比PSO、MFO要長。但從表2可以看出，在30維情況下，ALMBO的平均耗時與MBO相比不超過0.3 s。在50維情況下，ALMBO的平均耗時與MBO相比不超過0.4 s，雖稍犧牲了些尋優(yōu)時間，但其時間在可接受的范圍內(nèi)。

3.3 Wilcoxon秩和檢驗

上一節(jié)通過最優(yōu)值、平均值與平均耗時等指標對5種優(yōu)化算法進行了比較，但僅通過50次獨立運行的最優(yōu)值、平均值是不能較信服地說明ALMBO算法的優(yōu)越性，故需要進行統(tǒng)計檢驗來說明本文所提出的算法與其他算法相比有顯著性的差異。采用Wilcoxon秩和檢驗來驗證ALMBO每次運行結(jié)果在p=5%的顯著性水平下與其他算法是否有顯著性差異，當p＞5%時，可以認為接受假定H0，即認為兩種優(yōu)化算法之間不存在顯著性差異，算法尋優(yōu)能力相當；當p＜5%時，則拒絕假設H0，即兩種算法之間存在顯著性差異。表4是ALMBO與MFO、SSA、PSO、MBO在顯著性水平p=5%，維度50維下的比較結(jié)果。由于算法自身無法跟自身性能相比，故用N/A來表示。從表4可以看出，檢驗的p值大部分都遠小于5%，故認為ALMBO與其他四種算法存在顯著性差異，并且ALMBO的算法顯著性更佳。

表4 Wilcoxon秩和檢驗的p值Table 4 Wilcoxon rank and p value

3.4 收斂性分析

圖3給出了在30維的條件下8個基準函數(shù)的平均收斂曲線圖。為方便地觀察收斂的情況，對尋優(yōu)的適應度值（縱坐標）取10為底的對數(shù)。由圖3（a）至（h）中可以看出，對于單峰函數(shù)（圖（a）～（e）），MFO、PSO等可以達到較高的精度，而對于多峰函數(shù)，其收斂精度明顯下降。而無論是單峰函數(shù)還是多峰函數(shù)，對于每一個基準函數(shù)，ALMBO比其他優(yōu)化算法的收斂精度和速度都要好。圖（c）與圖（e）分別為在迭代次數(shù)300次與500次內(nèi)搜索到最優(yōu)值0，故在圖中后部分沒有顯示。由此說明，ALMBO具有較強的搜索能力，能夠快速地跳出局部最優(yōu)解向全局最優(yōu)解靠近。

圖3 f1～f8平均收斂曲線Fig.3 Mean convergence curves of f1～f8 strategies

4 總結(jié)

本文在原始帝王蝶算法的基礎上，引入了變異方向?qū)W習策略、自適應權重以及柯西變異，提出了一種改進的變異反向?qū)W習的自適應帝王蝶優(yōu)化算法。并將ALMBO與MFO、SSA、PSO、MBO算法在30維/50維的8個基準函數(shù)進行對比檢驗，同時，還運用了Wilcoxon秩和檢驗的方法，通過顯著性水平來驗證ALMBO算法的優(yōu)越性。實驗表明，ALMBO可以獲得更好的全局最優(yōu)解與收斂速度。在未來的研究中，考慮將算法應用到系統(tǒng)辨識與滾動優(yōu)化中，以進一步驗證算法的性能。