改進的動物遷徙算法求解全局優(yōu)化問題

劉金承，費佳慧

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

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

1 動物遷徙算法

1.1 靈感的來源

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

圖1 環(huán)型拓撲結(jié)構(gòu)

1.2 兩個流程中的主要原則

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

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

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

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

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

1.4 基于對立基學(xué)習(xí)的動物遷徙算法

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

2 粒子群優(yōu)化算法

2.1 粒子群優(yōu)化算法概述

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

2.2 標(biāo)準(zhǔn)粒子群優(yōu)化算法

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

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

其中Tmax表示最大進化代數(shù);Wmin表示最小慣性權(quán)重;Wmax表示最大慣性權(quán)重;t表示當(dāng)前迭代次數(shù)。在大多數(shù)的應(yīng)用中Wmax=0.9，Wmin=0.4。標(biāo)準(zhǔn)粒子群優(yōu)化算法具有全局搜索能力強，收斂速率快等優(yōu)點。

3 改進的動物遷徙算法

3.1 改進目標(biāo):尋優(yōu)能力和收斂速率

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

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

對于怎么設(shè)置慣性權(quán)重W才能將混合動物遷徙算法的尋優(yōu)能力和收斂速率發(fā)揮出來，進行了以下三次嘗試。

首先將粒子群優(yōu)化算法的慣性權(quán)重W設(shè)置為0.4，通過算法在23個benchmark基準(zhǔn)測試函數(shù)上進行仿真實驗的結(jié)果得出，當(dāng)W=0.4時，混合動物遷徙算法具有了較快的收斂速率。但是其穩(wěn)定性很差，當(dāng)對適應(yīng)度函數(shù)進行多次仿真實驗后發(fā)現(xiàn)，W=0.4時的混合動物遷徙算法很不穩(wěn)定，容易陷入到局部極值點。

其次考慮將粒子群優(yōu)化算法的慣性權(quán)重W設(shè)置為0.9，通過算法在23個benchmark基準(zhǔn)測試函數(shù)上進行仿真實驗的結(jié)果得出，當(dāng)W=0.9時，混合動物遷徙算法具有了穩(wěn)定的解，但是其尋優(yōu)效果很差，收斂速率緩慢。

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

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

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

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

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

3.3 偽代碼:begin

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

3.4 函數(shù)仿真測試

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

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

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

4.1 單峰函數(shù)

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

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

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

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

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

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

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

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

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

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

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

4.2 多峰高維函數(shù)

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

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

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

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

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

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

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

通過觀察圖13，圖14，圖15可以發(fā)現(xiàn)，在求解多峰高維函數(shù)時，傳統(tǒng)算法所得到的最優(yōu)解不如混合動物遷徙算法所得到的最優(yōu)解好。

4.3 多峰低維函數(shù)

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

5 結(jié)語

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

這一改進的動物遷徙算法目前只應(yīng)用于求解連續(xù)的全局優(yōu)化問題上，目前也有不少學(xué)者正在進行離散空間求解的研究。如何將混合動物遷徙算法應(yīng)用在全新的領(lǐng)域，如多目標(biāo)優(yōu)化問題、約束優(yōu)化問題、動態(tài)優(yōu)化問題等，需要進一步的分析研究。

［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.