改進的動物遷徙算法求解全局優化問題

劉金承，費佳慧

(1.長春金融高等專科學校，長春130028;2.東北師范大學計算機科學與信息技術學院，長春130117)

自20世紀80年代開始，一些看似不起眼的群居低智能的生物所表現出來的生活能力相當驚人，如:鳥群、魚群、蜜蜂等。雖然他們的結構都很簡單，但是他們之間具有相互合作的能力，是相當復雜的。這些群居低智能生物通過合作所表現出較高的“智能”，即群集智能。這種現象得到了許多學者的廣泛關注，通過對這些群居低智能的生物進行模擬，提出了許多算法，如BP神經網絡(Back Propagation Neural Network，BPNN)、人工免疫系統(Artificial Immune Systems，AIS)、模擬退火算法(Simulated Annealing Algorithm，SAA)、粒子群優化算法(Particle Swarm Optimization，PSO)、蟻群算法(Ant Colony Optimization，ACO)、禁忌搜索(Tabu Search，TS)、差分進化算法(Differential Evolution，DE)等如雨后春筍般不斷出現。進入21世紀至今:來自于大自然的神奇靈感使得啟發式算法迅速發展，各種算法百家爭鳴。在世紀之初的十年間，出現了大量的改進算法，改進的思想和方法各式各樣。為了提高全局優化問題的求解性能，本文提出了一種改進的動物遷徙算法來求解全局優化問題，增加尋優能力和收斂速率。我們知道帶慣性權重的標準粒子群優化算法全局搜索能力很強，并且通過慣性權重W值的變化，還可以控制收斂速率的快慢。動物遷徙算法本身就具有很強尋優能力，為了進一步提高動物遷徙算法的性能，將動物遷徙算法和帶權重的粒子群優化算法相結合，提出了一種改進的動物遷徙算法。

1 動物遷徙算法

1.1 靈感的來源

動物遷徙算法［1］是一種新的全局優化算法。算法的主要思想來自于無處不在的動物遷徙行為，基本上可以在所有主要的動物群體中發現。像哺乳類，魚群，昆蟲類，爬行動物類，鳥群，甲克類等。

圖1 環型拓撲結構

1.2 兩個流程中的主要原則

在第一個流程中，動物遷徙算法模仿了動物種群從當前位置遷徙到新的位置。在這個過程中，每一個動物個體都將遵循著三個主要的規則:1)和它的鄰居避免沖撞;2)和它的鄰居在相同的方向上進行移動;3)和它的鄰居保持緊密。對于第一個規則來說，需要每一個種群中的個體位置都是不同的。對于后面兩個規則，需要動物個體通過當前位置的鄰居來移動到一個新的位置上。為了定義每個個體鄰居的概念，我們使用一個環型拓撲結構，如圖1所示。

為了簡單起見，我們設置了鄰居的長度為5對于每個維度的動物個體。在動物遷徙算法中鄰居拓撲是靜態的，而且是定義了在一整套指數的向量。如果標志動物是i，那么鄰居的組成是由i－2，i－1，i，i+1，i+2我們可以在圖1中看到。如果標志動物是1，那么鄰居的組成是由NP－1，NP，1，2和3。如果標志動物是2，鄰居組成是由 NP，1，2，3 和 4。如果標志動物是 NP，那么動物鄰居的組成是由 NP－2，NP－1，NP，1，2。如果標志動物是NP－1，那么鄰居的組成是由NP－3，NP－2，NP－1和1。如果鄰居的拓撲被構造，我們將隨機選擇一個鄰居然后根據它的鄰居更新個體的位置。我們通過下面的公式發現:Xi，G+1=Xi，G+δ(Xneighborhod，G－Xi，G)，Xneighborhod，G為鄰居的當前位置，δ是由高斯分布的隨機數生成器產生的，Xi，G+1是第i個個體的新位置。

在第二個流程中，算法模仿了動物種群在移動中是如何行動的。在種群更新過程中，一些動物可能要離開種群，而另一些動物要加入到新的種群中。動物遷徙算法假定種群總數是固定不變的。種群中的動物將要被新的個體所代替的概率為Pa。概率Pa是根據適應度fitness的好壞來決定的。對于最好的適應度fitness，被代替的概率Pa是1/NP。對于最壞的適應度fitness，被代替的概率Pa是1。每當算法產生一個新的解，算法會與 Xi，G進行評估和比較。如果 Xi，G+1的適應度 fitness比 Xi，G的適應度 fitness小，那么 Xi，G+1作為一個新的基本解;相反的，如果 Xi，G+1的適應度 fitness比 Xi，G+1的適應度 fitness大，那么 Xi，G+1將繼續作為一個基本解。

1.3 動物遷徙算法的偽代碼:begin

設定后代計數器的G=0;隨機初始化種群Xi，人口數NP，通過適應度函數評價Xi中的每一個個體。

1.4 基于對立基學習的動物遷徙算法

曹毅和李向濤等人在2013年提出了基于對立基學習的動物遷徙算法［2］。當同時地考慮候選解在當前搜索空間和它的對立空間，通過在兩個搜索空間中選擇更好的個體，算法能夠提供更多的機會來找到全局最優解，并且提高了算法的收斂速度。動物遷移算法自提出后在不斷改進中。

2 粒子群優化算法

2.1 粒子群優化算法概述

粒子群優化算法［3］(PSO)是一種模仿我們所觀察到的動物或昆蟲的社會性行為(如魚群、鳥群)的基于群體的隨機優化算法。它首先是由詹姆士·肯尼迪和羅素·阿伯哈特于1995年提出。自那時起，PSO作為一種可以解決許多不同優化問題的魯棒高效的算法，獲得了越來越多的研究者所關注。在PSO中，群體中的單個粒子表示了一個潛在的解，此粒子在問題的求解空間中移動用來找到最優或者說是足夠好的解。粒子將其目前所在的位置廣播給它所相鄰粒子。粒子的位置根據其變化的速率(速度)和與其現在所在的位置的差異(分別是其鄰居找到的最佳的位置與其目前所找到的最佳的位置)而調整。由于算法是迭代的，種群越來越集中于具有高質量解的區域。

2.2 標準粒子群優化算法

Shi等在原始粒子群優化算法基礎上，引入到慣性權重，提出帶有慣性權重的粒子群優化算法［］，它的速度更新公式如下:

目前來說，采用較多的動態慣性權重值是Shi所提出的線性遞減值(Linearly Decreasing Weight，LDW)的策略，表達式如下:

其中Tmax表示最大進化代數;Wmin表示最小慣性權重;Wmax表示最大慣性權重;t表示當前迭代次數。在大多數的應用中Wmax=0.9，Wmin=0.4。標準粒子群優化算法具有全局搜索能力強，收斂速率快等優點。

3 改進的動物遷徙算法

3.1 改進目標:尋優能力和收斂速率

動物遷徙算法全局搜索部分的公式如下:

我們可以通過對公式(1)和公式(3)的對比發現，粒子群優化算法具有W*vi(q)這個重要部分，它體現了算法有較強全局搜索能力。在粒子群優化算法中，當W的值比較大時，粒子群優化算法全局搜索能力強，可以有較大的搜索的空間，可以更好地找到最優解所在的區域;當W的值比較小時，粒子群優化算法具有了較強的局部搜索能力，收斂速率高，尋優能力強，優化結果明顯、精確。通過公式(1)和公式(3)，用粒子群算法替代動物遷徙算法的全局搜索部分，從而提高了動物遷徙算法的尋優能力和收斂速率。

對于怎么設置慣性權重W才能將混合動物遷徙算法的尋優能力和收斂速率發揮出來，進行了以下三次嘗試。

首先將粒子群優化算法的慣性權重W設置為0.4，通過算法在23個benchmark基準測試函數上進行仿真實驗的結果得出，當W=0.4時，混合動物遷徙算法具有了較快的收斂速率。但是其穩定性很差，當對適應度函數進行多次仿真實驗后發現，W=0.4時的混合動物遷徙算法很不穩定，容易陷入到局部極值點。

其次考慮將粒子群優化算法的慣性權重W設置為0.9，通過算法在23個benchmark基準測試函數上進行仿真實驗的結果得出，當W=0.9時，混合動物遷徙算法具有了穩定的解，但是其尋優效果很差，收斂速率緩慢。

最終，選擇了線性遞減的慣性權重W作為混合動物遷徙算法的W值。

通過觀察公式(4)發現，當W的值比較大時，算法的全局搜索能力強，可以有較大的搜索空間，更好的找到最優解所在區域;當W的值比較小時，算法具有了較強的局部搜索能力，收斂速率高，尋優能力強，優化結果明顯、精確。所以本文決定使用線性遞減的慣性權重W來調節，使得混合動物遷徙算法在算法初期，具有較高的全局搜索能力，可以搜索到最優解所在的區域;算法后期又具有較高的局部搜索能力，較快的收斂速率，可以更精確的找到最優解。其中的相關參數分別有:r1，r2為［0，1］的隨機數;W，c1、c2是控制速度更新公式三部分內容的權值，W稱為慣性權重，c1、c2為加速因子。

3.2 改進的動物遷徙算法的流程圖

改進的動行遷徒算法流程圖如圖2所示。

圖2 改進的動物遷徙算法流程圖

3.3 偽代碼:begin

設定后代計數器G=0;隨機初始化種群Xi，人口數NP;通過適應度函數評價Xi中的每一個個體。

3.4 函數仿真測試

為了進一步驗證算法的有效性選擇的23個標準測試函數在Matlab中進行實驗。在這些函數中，函數f01－f13是多維問題。函數f01－f05是單峰函數，f05是在D＞3的情況下是多維函數。f06是階梯函數有一個最小值和不連續。函數f07是一個嘈雜的二次函數當隨機在［0，1］中是一個均勻分布隨機數在［0，1］中。接下來的7個函數是多峰測試函數。對于這些函數來說，根據問題的規模局部最小值增大。對于許多優化問題來說，他們顯然屬于一類最困難的問題。函數f14－f23是低維問題，只有幾個局部的最小值。對于單峰函數來說，研究者關注更多的是在收斂率方面而不是優化的最終結果;對于多峰函數來說，最終結果要比不同算法的收斂率更重要，因為他們反映了一個算法對于避免壞的最優條件的能力和去定位一個好的全局最優解。到目前為止，這些基準測試函數被廣泛應用于許多研究者的不同算法中。

4 實驗結果及分析

在實驗分析中，將改進的動物遷徙算法(PSAMO)與傳統的算法比如差分進化算法(DE)、粒子群優化算法(PSO)、生物地理學優化算法(RCBBO)、螢火蟲算法(FA)［4］、動物遷徙算法(AMO)、人工蜂群算法(ABC)、布谷鳥搜索算法(CS)［5］、引力搜索算法(GSA)的數值優化問題的平均值進行比較。

4.1 單峰函數

為了體現本文所提出的改進動物遷徙算法的有效性，將改進的動物遷徙算法與差分進化算法(DE)、粒子群優化算法(PSO)、生物地理學優化算法(RCBBO)、螢火蟲算法(FA)、動物遷徙算法(AMO)、人工蜂群算法(ABC)、布谷鳥搜索算法(CS)、引力搜索算法(GSA)進行比較，在解的平均值表中，f01－f05是單峰函數。對于單峰函數來說，搜索算法的收斂速率比最終結果更為重要，因為這些函數是專門為了優化單峰函數的，從算法的排名我們可以看出，雖然混合算法在單一某個測試函數中表現并不是最好的，但是在f01－f07的平均排名下，混動動物遷徙算法的排名是最好的。

圖3 對于f01函數PSAMO和其他算法性能的比較

圖4 對于f02函數PSAMO和其他算法性能的比較

通過從圖3和圖4觀察混合算法的收斂速率，我們發現，在算法運行的初期，算法具有較強的全局搜索能力，可以找到最優解所在區域;在算法運行的后期，算法具有較強的局部搜索能力，可以更精確的找到最優解，從而總結出改進的動物遷徙算法具有較快的收斂速率。

圖5 對于f03函數PSAMO和其他算法性能的比較

圖6 對于f04函數PSAMO和其他算法性能的比較

圖7 對于f05函數PSAMO和其他算法性能的比較

圖8 對于f06函數PSAMO和其他算法性能的比較

通過對圖8可以看出，PSAMO有較強的尋優能力，在算法初期便直接收斂到了全局最優解。

圖9 對于f07函數PSAMO和其他算法性能的比較

圖10 對于f08函數PSAMO和其他算法性能的比較

4.2 多峰高維函數

對于函數f08到f13，最終解是非常重要的，因為函數能反應出來算法跳出局部極小和獲得全局最優的能力。我們測試了f08－f13，局部極小的數量以指數方式增長像函數增長的維度。通過表中可以看出最終解的平均值的排名，動物遷徙算法在最終解的排名上表現的十分優秀，我們也能發現在f8－f13的7個函數的平均排名里也是最好的。

圖11 對于f09函數PSAMO和其他算法性能的比較

圖12 對于f10函數PSAMO和其他算法性能的比較

通過對圖10，圖11，圖12的研究可以看出，在多峰高維函數優化中，取得最優解的值是非常重要的。其中PSAMO在求解高峰多維函數時，表現良好。

圖13 對于f11函數PSAMO和其他算法性能的比較

圖14 對于f12函數PSAMO和其他算法性能的比較

圖15 對于f13函數PSAMO和其他算法性能的比較

通過觀察圖13，圖14，圖15可以發現，在求解多峰高維函數時，傳統算法所得到的最優解不如混合動物遷徙算法所得到的最優解好。

4.3 多峰低維函數

對于函數f14－f23，f14－f23是比f08－f13更簡單的多峰低維函數。對于f14－f23這10個函數來說，混合算法都表現十分良好，不僅單個函數排名是最好的，而且平均排名也是最好的。

5 結語

本文提出了一種改進的動物遷徙算法，將動物遷徙算法中全局搜索部分改為使用標準粒子群優化算法，用以提高動物遷徙算法的全局搜索能力還有其收斂速率。實驗結果表明，改進后的動物遷徙算法在求解23個benchmark基準測試函數時，性能有了明顯提高，體現了算法的有效性。

這一改進的動物遷徙算法目前只應用于求解連續的全局優化問題上，目前也有不少學者正在進行離散空間求解的研究。如何將混合動物遷徙算法應用在全新的領域，如多目標優化問題、約束優化問題、動態優化問題等，需要進一步的分析研究。

［1］Li X，Zhang J，Yin M.Animal migration optimization:an optimization algorithm inspired by animal migration behavior［J］.Neural Computing and Applications，2014，24(7):1867－1877.

［2］Cao Y，Li X，Wang J.Opposition－based Animal Migration Optimization［J］.Mathematical Problem.

［3］J.Kennedy，and R.C.Eberhart .Particle swarm optimization［C］//.In Proceedings of the 1995 IEEE International Conference on Neural Networks，volume 4 pages 1942－1948 IEEE Press ，Piscataway ，NJ ，1995 in Engineering 2013，2013(1):1－7.

［4］Yang XS.Nature－inspired Metaheuristic Algorithms［M］.Frome:Luniver Press，2008.

［5］Yang XS，Deb S.Cuckoo search via Levy flights［C］.Nature＆ Biologically inspired computing.World Congress on IEEE，2009:210－214.