劉金承，費(fèi)佳慧

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

自20世紀(jì)80年代開(kāi)始，一些看似不起眼的群居低智能的生物所表現(xiàn)出來(lái)的生活能力相當(dāng)驚人，如:鳥(niǎo)群、魚(yú)群、蜜蜂等。雖然他們的結(jié)構(gòu)都很簡(jiǎn)單，但是他們之間具有相互合作的能力，是相當(dāng)復(fù)雜的。這些群居低智能生物通過(guò)合作所表現(xiàn)出較高的“智能”，即群集智能。這種現(xiàn)象得到了許多學(xué)者的廣泛關(guān)注，通過(guò)對(duì)這些群居低智能的生物進(jì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)、差分進(jìn)化算法(Differential Evolution，DE)等如雨后春筍般不斷出現(xiàn)。進(jìn)入21世紀(jì)至今:來(lái)自于大自然的神奇靈感使得啟發(fā)式算法迅速發(fā)展，各種算法百家爭(zhēng)鳴。在世紀(jì)之初的十年間，出現(xiàn)了大量的改進(jìn)算法，改進(jìn)的思想和方法各式各樣。為了提高全局優(yōu)化問(wèn)題的求解性能，本文提出了一種改進(jìn)的動(dòng)物遷徙算法來(lái)求解全局優(yōu)化問(wèn)題，增加尋優(yōu)能力和收斂速率。我們知道帶慣性權(quán)重的標(biāo)準(zhǔn)粒子群優(yōu)化算法全局搜索能力很強(qiáng)，并且通過(guò)慣性權(quán)重W值的變化，還可以控制收斂速率的快慢。動(dòng)物遷徙算法本身就具有很強(qiáng)尋優(yōu)能力，為了進(jìn)一步提高動(dòng)物遷徙算法的性能，將動(dòng)物遷徙算法和帶權(quán)重的粒子群優(yōu)化算法相結(jié)合，提出了一種改進(jìn)的動(dòng)物遷徙算法。

1 動(dòng)物遷徙算法

1.1 靈感的來(lái)源

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

圖1 環(huán)型拓?fù)浣Y(jié)構(gòu)

1.2 兩個(gè)流程中的主要原則

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

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

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

1.3 動(dòng)物遷徙算法的偽代碼:begin

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

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

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

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

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

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

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

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

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

其中Tmax表示最大進(jìn)化代數(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)化算法具有全局搜索能力強(qiáng)，收斂速率快等優(yōu)點(diǎn)。

3 改進(jìn)的動(dòng)物遷徙算法

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

動(dòng)物遷徙算法全局搜索部分的公式如下:

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

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

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

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

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

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

3.2 改進(jìn)的動(dòng)物遷徙算法的流程圖

改進(jìn)的動(dòng)行遷徒算法流程圖如圖2所示。

圖2 改進(jìn)的動(dòng)物遷徙算法流程圖

3.3 偽代碼:begin

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

3.4 函數(shù)仿真測(cè)試

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

4 實(shí)驗(yàn)結(jié)果及分析

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

4.1 單峰函數(shù)

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

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

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

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

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

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

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

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

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

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

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

4.2 多峰高維函數(shù)

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

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

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

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

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

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

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

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

4.3 多峰低維函數(shù)

對(duì)于函數(shù)f14－f23，f14－f23是比f(wàn)08－f13更簡(jiǎn)單的多峰低維函數(shù)。對(duì)于f14－f23這10個(gè)函數(shù)來(lái)說(shuō)，混合算法都表現(xiàn)十分良好，不僅單個(gè)函數(shù)排名是最好的，而且平均排名也是最好的。

5 結(jié)語(yǔ)

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

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

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