一種元啟發(fā)式算法: 海島算法

馬吉明， 張 嵩， 蘇日建， 張國良， 陳浩洋， 山石姣

(鄭州輕工業(yè)大學(xué) 計算機與通信工程學(xué)院，河南 鄭州 450001)

0 引言

經(jīng)過漫長的時間演化，大自然造就了很多奇妙的現(xiàn)象，令人嘆為觀止的同時也給人們?yōu)榻鉀Q問題帶來了無限的啟發(fā).人們從各種現(xiàn)象中汲取智慧.例如，根據(jù)自然界的生物進化按“適者生存，優(yōu)勝劣汰”這一規(guī)律提出了遺傳算法(GA)[1]；受生物免疫系統(tǒng)啟發(fā)而設(shè)計的人工免疫算法(AIS)[2]；受到即興創(chuàng)作音樂作品的啟發(fā)而提出的和聲搜索算法(HS)[3]；根據(jù)金屬的退火過程提出模擬退火算法(SA)[4].根據(jù)動物的覓食行為，眾多學(xué)者提出了很多智能算法，包括粒子群算法(PSO)[5]、蟻群算法(ACO)[6]、螢火蟲算法(FA)[7]、蝙蝠算法(BA)[8]、狼群算法(WPA)[9]、細菌覓食優(yōu)化算法(BFA)[10]、布谷鳥算法(CS)[11]、人工魚算法(AFSA)[12]、蛙跳算法(SFLA)[13]、人工蜂群算法(ABC)[14]、雞群算法(CSO)[15]、天牛須算法(BAS)[16]等.這樣的元啟發(fā)式算法成為解決許多棘手優(yōu)化問題的有效方法.由于這些算法都具有某些優(yōu)點和缺點，很多學(xué)者針對其缺點不斷進行改進，并應(yīng)用于合適的領(lǐng)域中[17].因此，從自然界中獲取新啟發(fā)，為解決優(yōu)化問題等提供新思路仍然具有意義.

筆者根據(jù)海島上植物的生長位置隨著海平面的上升及海島面積的縮小，越來越集中于最高點的現(xiàn)象，提出一種新的元啟發(fā)式算法，即海島算法(IA).海島算法通過不斷升高海平面的同時，維持植物總數(shù)不變，從而來尋找最佳點位置.通過實驗，與已經(jīng)廣泛應(yīng)用的粒子群算法進行對比.實驗表明，相比于粒子群算法，海島算法在CEC2013函數(shù)集上，總體上保持優(yōu)勢.

1 海島算法

海島算法是一種新的元啟發(fā)式算法.海島算法分為3個階段：淘汰階段、海平面上升階段、平衡階段.

1.1 淘汰階段

該階段是為迭代的海平面上升階段做準備，主要的任務(wù)是根據(jù)范圍的變化量來產(chǎn)生本次迭代需要淘汰植物的個數(shù).因為至少需要2個植物才能定義海島的范圍，所以淘汰后，未被淘汰的植物個數(shù)至少為2，即最大的淘汰個數(shù)要小于總量數(shù)減2.該階段的任務(wù)由淘汰函數(shù)完成.淘汰函數(shù)的自變量為范圍的變化量，函數(shù)值為淘汰個數(shù).當(dāng)范圍變化量比較大時，為了避免陷入局部解，應(yīng)減少淘汰個數(shù)來減小下一次的范圍變化量；當(dāng)范圍變化量比較小時，為了加快算法收斂，應(yīng)增加淘汰個數(shù)來增大下一次的范圍變化量.故函數(shù)滿足以下兩點要求：

(1)范圍變化量為零時，淘汰個數(shù)為最大淘汰個數(shù).

(2)淘汰函數(shù)為一個遞減函數(shù)，隨著范圍變化量的增大，淘汰個數(shù)將減小.

采用既滿足以上兩點要求又較為簡單的負指數(shù)函數(shù)：

fout(h)=[(Am-Al)·e-h]+Al,

(1)

式中：h為范圍變化量，由上次迭代中海平面上升階段產(chǎn)生；Am為最大淘汰個數(shù)；Al為最小淘汰個數(shù).

1.2 海平面上升階段

海平面上升階段將根據(jù)淘汰階段產(chǎn)生的淘汰個數(shù)來提升海平面.海平面的提升表現(xiàn)為海島范圍的縮小.該階段的主要任務(wù)是產(chǎn)生新的海島范圍以及海島范圍變化量.其中，新的海島范圍為接下來的平衡階段做準備，范圍變化量為下次迭代中淘汰階段做準備.

海島的新范圍由未被淘汰的植物所生長的范圍所決定.新范圍由每一維度的最大值Xmax和最小值Xmin表示.為了避免由于收斂過快，易陷入局部最優(yōu)位置，將范圍通過公式2和3進行擴展.

(2)

(3)

海島范圍變化量由公式4表示：

(4)

1.3 平衡階段

平衡階段的主要任務(wù)是在海平面上升的同時，維持植物的總量不變，并根據(jù)位置高度進行排序.具體的實現(xiàn)是在海平面上升階段產(chǎn)生的新范圍內(nèi)，產(chǎn)生A個新植物，替換種群中最差的植物，從而使植物總量不變.

為了加快搜索速度，提高搜索精度，將每一個新植物通過式(5)朝著全局最優(yōu)植物處移動，然后評估該植物，若優(yōu)于全局最優(yōu)植物，則將兩者的位置和適應(yīng)度值進行交換.

x(j,:)=x(j,:)+2·rand(1,D)·

(x(1,:)-x(j,:)),

(5)

式中：x(j,:)為在新范圍內(nèi)產(chǎn)生的第j個新植物位置；x(1,:)為全局最優(yōu)位置；D為維度；2為參數(shù)，使移動后的位置在當(dāng)前位置向最優(yōu)位置方向上以2倍的距離均勻分布.

移動和評估完所有新植物后，所有植物根據(jù)適應(yīng)度值進行排序.在程序中，測試函數(shù)的適應(yīng)度值即為植物的位置高度，當(dāng)按照從大到小排序時，即求解測試函數(shù)最大值；當(dāng)按照從小到大排序時，即求解測試函數(shù)最小值.3個階段相互依存，關(guān)系如圖1所示.每一次的迭代包含該3個階段.

圖1 3個階段關(guān)系圖Fig.1 Three-stage relationship

1.4 算法流程

基本海島算法的步驟如下.

步驟1 參數(shù)初始化：設(shè)最大評估次數(shù)E，海島的維度D，淘汰個數(shù)的最大最小值分別為Am，Al，范圍變化量h，植物總量N，植物的生長位置為xi(i=1,2,…,N)，海島范圍Xmax,Xmin.

步驟2 進入淘汰階段，根據(jù)式(1)生成淘汰個數(shù).

步驟3 進入海平面上升階段，記錄上次迭代的海島范圍，產(chǎn)生新的海島范圍，根據(jù)式(2)和(3)，對新范圍進行擴展，根據(jù)式(4)產(chǎn)生海島范圍變化量h.

步驟4 進入平衡階段，在新的海島范圍內(nèi)根據(jù)淘汰個數(shù)產(chǎn)生新植物，并對植物種群中最差的植物進行淘汰.

步驟5 每一個新植物向最優(yōu)植物處移動，求解新植物的適應(yīng)度值，若優(yōu)于最優(yōu)植物，則進行交換，最后對所有植物進行排序.

步驟6 若達到終止條件，輸出結(jié)果，終止算法.否則，轉(zhuǎn)入步驟2，進入下一次的迭代.

算法偽代碼如下所示.

輸入：初始化N、Al、Am、h、D、E，

Xmax=100·ones(1,D)，Xmin=-100·ones(1,D),

x=ones(N,1)·Xmin+ones(N,1)·(Xmax-Xmin)·rand(N,D);

獲取每一個植物對應(yīng)的適應(yīng)度值，并排序

輸出：最優(yōu)值位置x(1,:)，最優(yōu)值適應(yīng)度值fit(1)

1：while(結(jié)束條件)

2： 淘汰階段

3： 根據(jù)式(1)生成淘汰個數(shù)；

4： 海平面上升階段

6：Xmax=max(x(1:N-taotai,:));

7：Xmin=min(x(1:N-taotai,:));

8： 對新的海島范圍使用式(2)和式(3)進行擴展；

9： 根據(jù)式(4)產(chǎn)生范圍變化量；

10： 平衡階段

11： 在新范圍內(nèi)產(chǎn)生A個新植物，替換最差的A個植物；

12： forj=N-A+1:N；

13： 根據(jù)式(5)進行移動；

14： if(達到最大評估次數(shù))

15： 輸出結(jié)果，算法結(jié)束

16： else

17：fit(j)=Fun(x(j,:)); 評估次數(shù)加一;

18： 判斷是否優(yōu)于最優(yōu)植物，是則進行交換

19： end

20： end

21： [fit,index]=sort(fit);x=x(index,:);

22：end

2 算法分析及對比

2.1 算法分析

相比于粒子群算法、蝙蝠算法、蜂群算法等，海島算法在每次的迭代中，并未對每一個植物進行位置的更新和評估，而是只更新最差的植物，個數(shù)為淘汰階段產(chǎn)生的淘汰個數(shù).這樣不僅可以在每一次迭代中減少計算量，而且也保留了相對較好的位置信息，其信息將在接下來多次的迭代中被利用，直到該位置被淘汰.因此，算法對每一個位置信息都有著充分的利用.這也是海島算法能體現(xiàn)優(yōu)越性的關(guān)鍵原因.

當(dāng)求解的函數(shù)存在連續(xù)梯度很小或很大區(qū)域，即存在連續(xù)平坦或有尖銳峰或谷的區(qū)域，如圖2所示，將不適合算法的求解.

圖2 不利情況Fig.2 Unfavorable situation

由于搜索范圍內(nèi)存在很大的平坦區(qū)域，新增的植物位于平坦區(qū)域的概率很高，因此，海平面上升階段，海島的范圍變化不大，甚至為0，不利于算法的收斂.但通過淘汰階段產(chǎn)生更多的淘汰個數(shù)，最終使其跳出局部解.最極端的情況下，只保留2個植物，其余全部淘汰.據(jù)此，也可以預(yù)測出，該算法不適合求解具有眾多尖銳的峰，且峰周圍區(qū)域較為平坦的函數(shù).典型函數(shù)如f8函數(shù).

在求解函數(shù)的整個求解區(qū)域內(nèi)，梯度相對適中，即沒有連續(xù)平坦和尖銳峰或谷的區(qū)域，如圖3所示，將適合算法的求解.

圖3 有利情況Fig.3 Favorable situation

在該搜索區(qū)域范圍內(nèi)，新增的植物更易處于不同的高度，這將有利于算法往最優(yōu)位置處收斂.典型函數(shù)如f1函數(shù).

由于植物隨機分布在搜索范圍內(nèi)，在算法初期，搜索范圍較大，僅通過范圍的縮小來使算法收斂，相較于單個粒子根據(jù)其他信息尋找最優(yōu)位置的算法如粒子群優(yōu)化算法，收斂速度慢，但將新植物向最優(yōu)植物處移動，大大提高了算法的收斂速度，而通過對新范圍的擴展，使算法又盡可能避免因收斂過快而陷入局部最優(yōu)位置；在算法后期，隨著搜索范圍逐漸縮小，整個種群在一個小范圍內(nèi)尋找最優(yōu)位置，加速了收斂速度，從而達到更好的精度.海島算法是整個種群通過淘汰方式逐漸縮小搜索范圍來尋找最優(yōu)區(qū)域，相較于單個粒子尋找最優(yōu)位置的算法，具有更強的魯棒性.

若取每次迭代的平均評估次數(shù)為(Am+Al)/2，則公式及排序操作的次數(shù)為2E/(Am+Al)，與最大評估次數(shù)成線性關(guān)系，故算法的計算復(fù)雜度為O(n).

2.2 算法對比

有些元啟發(fā)式算法在新粒子生成方式上，基于粒子的當(dāng)前位置，根據(jù)其他信息調(diào)整步長及方向進行移動來生成新粒子，一般都具有慣性權(quán)重系數(shù).如粒子群算法利用個體認知和社會認知信息，蝙蝠算法利用回聲定位信息.在收斂方式上，這些信息調(diào)整的步長和方向?qū)龑?dǎo)種群收斂于最優(yōu)值.

有些元啟發(fā)式算法在新粒子生成方式上，是在整個搜索區(qū)域內(nèi)，通過應(yīng)用某種策略來產(chǎn)生新粒子.如遺傳算法通過選擇、交叉和變異3種算子來產(chǎn)生新粒子，人工蜂群算法通過偵察蜂隨機搜索、采蜜蜂采蜜、觀察蜂跟隨3種方式來產(chǎn)生新粒子.在收斂方式上，遺傳算法采用適者生存的原則，人工蜂群算法采用貪婪準則來更新差粒子，通過不斷更新差粒子來實現(xiàn)種群朝著最優(yōu)值收斂.很多元啟發(fā)式算法從某種程度上講，都是通過迭代，不斷地生成新粒子和更新差粒子，使種群朝著最優(yōu)值收斂.

IA算法在新粒子生成和收斂方式上與上述兩種不同.新粒子采用最簡單的隨機搜索策略生成于不斷縮小的搜索范圍內(nèi)，通過更新最差個體使搜索范圍縮小，再通過不斷縮小搜索范圍來使算法收斂.

3 實驗仿真分析

3.1 實驗設(shè)計

為了驗證本文海島算法的性能，通過解決CEC2013測試集中測試函數(shù)來分析所提算法的性能.CEC2013測試集中包含28個函數(shù)，其中f1～f5為單峰函數(shù)，f6～f20為多模態(tài)函數(shù)，f21～f28為組合函數(shù)，搜索范圍均為[-100,100].如表1所示.

實驗環(huán)境是在Windows 10系統(tǒng)Matlab R2014a軟件，CPU為i5-3470 3.20 GHz，RAM為4 GB.

海島算法的參數(shù)設(shè)置如表2所示.

為了體現(xiàn)算法的優(yōu)越性，在相同的條件下，與已經(jīng)被廣泛使用的粒子群算法進行對比.兩個算法的種群大小一致.粒子群算法的社會認知系數(shù)為1.5，個體認知系數(shù)為1.5，慣性權(quán)重系數(shù)為0.8.

表1 測試函數(shù)Tab.1 Test function

表2 參數(shù)設(shè)置Tab.2 Parameter settings

針對每一個函數(shù)，兩個算法分別在搜索維度為10、30和50上獨立運行51次，并將計算結(jié)果進行對比分析.由于海島算法每次迭代中，對測試函數(shù)的評估次數(shù)無法確定，故通過比較相同的評估次數(shù)下計算結(jié)果的精度，來比較算法的性能.

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

兩個算法分別在搜索維度為10、30和50上，分別對測試函數(shù)評估100 000、300 000、500 000次.將51次中所得最優(yōu)誤差值、最差誤差值、中間誤差值、平均誤差值和其標(biāo)準差作為算法精度和魯棒性的衡量指標(biāo)，如果小于10-8，則認為0.10維運行結(jié)果如表3～4所示，20維和30維運行結(jié)果如圖4～5所示.

表3 10維f1～f7Tab. 3 10 dimensional f1～f7

圖4 30維運行結(jié)果Fig.4 Operation results of 30 dimensional

圖5 50維運行結(jié)果Fig.5 Operation results of 50 dimensional

f8函數(shù)是指數(shù)函數(shù)疊加上適度放大的余弦而得到的連續(xù)性測試函數(shù)，其特征是一個幾乎平坦的區(qū)域由余弦波調(diào)制形成一個個孔或峰，從而使曲面起伏不平，有著較為平坦的區(qū)域和陡峭的峰，同樣有此特點的函數(shù)還有f2、f3、f4函數(shù).f14、f15、f16、f22和f23有非常密集的陡峭的峰和谷形成的眾多局部最優(yōu)位置，從對算法的分析中可知，海島算法并不適用于求解具有此類特點的函數(shù).

在51次獨立運行的結(jié)果中，28個函數(shù)中有5個函數(shù)f2、f3、f8、f15、f16，在10、30、50維度上均差于PSO算法，f4、f14、f22和f23在30、50維度上均差于PSO算法.其余函數(shù)在3個維度中均優(yōu)于PSO算法，驗證了算法的分析及算法的有效性.從總體上看，海島算法在CEC2013函數(shù)集中的大部分函數(shù)中表現(xiàn)優(yōu)異，相同條件下海島算法的精度和魯棒性普遍優(yōu)于已被廣泛應(yīng)用的粒子群算法.

表4 10維f8～f28Tab. 4 10 dimensional f8-f28

4 結(jié)論

筆者提出一種新的元啟發(fā)式算法即海島算法.通過對海島算法分析，找出該算法優(yōu)缺點，并對算法的收斂特點、魯棒性及計算復(fù)雜度進行探討.最后在CEC2013函數(shù)集上進行實驗分析，結(jié)果表明，總體上，海島算法的尋優(yōu)能力強于粒子群算法.下一步將研究不同的淘汰函數(shù)及海島范圍變化量的表達方式對算法的影響.