變異反向學習的自適應帝王蝶優化算法

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

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

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

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

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

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

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

1 帝王蝶優化算法

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

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

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

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

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

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

1.1 遷移算子

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

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

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

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

1.2 調整算子

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

2 變異反向學習的自適應的MBO算法

2.1 變異反向學習遷移算子

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

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

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

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

故本文將變異反向學習融入MBO算法中，其數學表達式為：

2.2 自適應調整算子

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

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

2.3 柯西變異擾動

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

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

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

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

2.4 算法流程圖與步驟

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

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

2.5 時間復雜度的分析

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

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

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

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

（4）在遷移算子中的引入變異反向學習策略，有2個內循環，時間復雜度為O(DN1)。

（5）在調整算子中引入自適應策略，存在2個內循環，時間復雜度為O(D(N-N1))。優化算法ALMBO總時間復雜度為：

上述分析可知，ALMBO算法在時間復雜度上與原始MBO時間復雜度是相當的。

2.6 收斂性分析

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

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

證明ALMBO算法在狀態轉移過程中都是在有限空間中進行的，算法中的變異反向學習遷移，自適應調整，柯西變異干擾等操作都是滿足獨立隨機的過程，并且整個迭代進化過程都是采取的保留最優個體的機制，第t+1代的種群Qt+1只是受第t代種群Q t的影響，與種群之前的信息無關。因此{X t,t≥0}是有限狀態空間的齊次馬爾科夫鏈。

引理2在ALMBO算法的狀態空間中，存在常數μ∈(0,1)，使條件p ij＜μ成立，p ij表示從狀態空間A i轉移到狀態空間A j的概率[19]。

定理2ALMBO優化算法以概率1收斂到全局最優解。

3 實驗及結果分析

3.1 參數設定

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

表1 基準函數Table 1 Benchmark function

3.2 算法性能分析

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

表2 30維結果分析Table 2 Analysis of 30 dimensional results

表3 50維結果分析Table 3 Analysis of 50 dimensional results

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

3.3 Wilcoxon秩和檢驗

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

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

3.4 收斂性分析

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

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

4 總結

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