基于種群信息的布谷鳥算法

高淑芝,高 越

(1.沈陽化工大學 裝備可靠性研究所， 遼寧 沈陽 110142； 2.沈陽化工大學 信息工程學院， 遼寧 沈陽 110142)

元啟發(fā)式算法是復雜函數(shù)最優(yōu)值問題的一個重要解決方法.它們的靈感來自自然界中某種生物的某種行為,如啟發(fā)自鳥群覓食行為的粒子群算法(PSO)[1]、啟發(fā)自螢火蟲閃光行為的螢火蟲算法(FA)[2]、啟發(fā)自蜂群群體行為的人工蜂群算法(ABC)[3]等，這些算法已經(jīng)在實際問題中被證明了具有良好的性能[4-6].最近，出現(xiàn)了一種布谷鳥算法[7-8]，該算法模擬自然界中布谷鳥的產(chǎn)卵行為進行尋優(yōu)，并使用模擬果蠅飛行過程的Levy飛行策略進行搜索.該策略采用一系列具有突變序列特征的隨機游走，以較高概率在小范圍內(nèi)搜索的同時以較小概率作大步長的隨機游動.其優(yōu)勢在于，只要經(jīng)過迭代的次數(shù)足夠多，Levy飛行總能找到搜索域內(nèi)每一個點，即總能找到最優(yōu)解.布谷鳥算法的優(yōu)勢在于，其控制參數(shù)只有2個，即搜索步長α和個體被發(fā)現(xiàn)的概率Pa.只要控制其中一個保持不變，就可以很容易觀察到另一個參數(shù)的值對結(jié)果的影響.但是，CS算法在處理多模態(tài)函數(shù)時的效果還略有不足，雖然已經(jīng)有許多布谷鳥算法的變種被提出[9-11]，但是仍然存在很多問題.在某個個體陷入局部最優(yōu)時，它可能無法根據(jù)它的近鄰跳出局部極值，因為這些個體很可能也具有相似的屬性.但是，如果依靠群體中最優(yōu)個體的位置以及整個種群位置的均值，就可以跳出該極值區(qū)域，并進一步找到全局最優(yōu).為了證明所提出方法具備以上特點，使用幾個常見的目標函數(shù)用于測試，通過與其他算法的比較來證明這一方法的有效性.

1 布谷鳥算法

在自然界中，布谷鳥尋找適合自己產(chǎn)卵巢穴的方式是一種隨機的方式，為了模擬其產(chǎn)卵的過程，引入以下3條理想化的規(guī)則：

(1) 每個布谷鳥的蛋代表一個解，布谷鳥每次只產(chǎn)一個蛋，并隨機選擇某個鳥巢將蛋放入其中.

(2) 布谷鳥們每一代都會尋找到許多鳥巢產(chǎn)卵，其中一部分鳥巢中放著優(yōu)質(zhì)的蛋，這些蛋代表位置較好的解，這些鳥巢將被保存到下一代.

(3) 寄主巢的數(shù)量不變，且寄主有一定的概率pa∈(0,1)發(fā)現(xiàn)布谷鳥放的蛋.被發(fā)現(xiàn)的蛋將被宿主舍棄.

在布谷鳥算法中，鳥巢中的每個蛋都代表一個解，布谷鳥所產(chǎn)的蛋代表新解,采用更好的解或者新解來取代鳥巢中的劣解.該算法可以拓展得更加復雜，一個巢可以有多個卵的情況，即一群解.但是，本文僅考慮最簡單的情況，即一個巢中僅包含一個解.這樣，不論是蛋、巢還是布谷鳥，都表示為算法中的解.根據(jù)以上假設(shè)的布谷鳥產(chǎn)卵行為，得出以下布谷鳥算法的解的更新公式：

(1)

(2)

其中:u～N(0,1);v～N(0,1);

φ=[Γ(1+β)·sin(π·β/2)/

(3)

β是一個常數(shù)，它的值在區(qū)間[1,2]上，一般取1.5;Γ(?)是Gamma函數(shù).

2 基于種群信息的布谷鳥算法

布谷鳥算法單一地使用Levy飛行策略導致整個搜索過程過于依賴隨機游走，搜索效率不佳，難以在期望的時間內(nèi)尋找到最優(yōu)值，浪費了大量的計算成本，在處理一些有許多局部極小值的多模態(tài)函數(shù)時，需要很多次迭代才能收斂.Levy飛行策略步長的選擇也極為重要，選擇的步長較大會導致個體徘徊在最優(yōu)值附近，難以找到其精確的位置，達到預想的精度就會變得較為困難；選擇的步長較小可能會導致難以找到最優(yōu)解，收斂于局部極小值.這就意味著需要大量的先驗性試驗確定步長的大小.

整個種群信息的引入給布谷鳥算法提供了跳出局部最優(yōu)的能力以及局部搜索的能力.引入整個種群個體的平均位置幫助個體跳出局部極值，該搜索策略的個體位置更新公式為

(4)

(5)

其中p代表種群大小.

種群中的個體將根據(jù)整個種群和自身的位置生成新個體，從自身與平均位置連線上的另一端跳出局部極值，保證算法的全局探索能力.擁有足夠的全局探索能力能夠保證算法成功找到全局最優(yōu)值所在的區(qū)域，但是找到的解并不一定能夠找到具有足夠精度的值，這可能會導致最終的解不滿足需要的精度要求.所以還應該有一種搜索策略保證算法的局部搜索能力.一種依靠種群最優(yōu)位置的搜索策略如等式(6)所示.

(6)

在迭代過程中，這兩種策略和Levy飛行策略將具有相同的概率被選擇，個體選擇搜索策略的方式為

(7)

其中θ是一個[0,1]上服從均勻分布的隨機數(shù).每個個體在每一代都將隨機選擇一種搜索策略，生成新的個體.算法的過程如下：

步驟1：算法初始化，設(shè)置種群大小popsize、迭代總次數(shù)Gmax、Levy飛行的步長以及布谷鳥被發(fā)現(xiàn)的概率.

步驟2：初始化種群，計算每個個體的適應度值，并比較出最優(yōu)個體.

步驟3：每個個體根據(jù)式(7)隨機選擇策略并生成新一代個體.

步驟4：計算每個個體的適應度值.

步驟5：根據(jù)布谷鳥被發(fā)現(xiàn)的概率隨機舍棄部分個體.

步驟6：計算每個個體的適應度值，并更新最優(yōu)個體.

步驟7：判斷迭代終止條件是否滿足，若終止條件未滿足，則轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟8.

步驟8：終止循環(huán)，輸出最優(yōu)值.

3 實驗與分析

3.1 實驗函數(shù)與參數(shù)設(shè)置

為了證明基于種群信息的布谷鳥算法具有更強的全局探索能力和局部搜索能力，將其與基本布谷鳥算法和粒子群算法在6種常見的基準函數(shù)上進行仿真，這6種函數(shù)以及他們的參數(shù)和搜索域如下：

Ackley函數(shù)：

Bohachevsky 函數(shù)：

0.4cos(4πx2)+0.7,-100≤x≤100；

Schewefel 函數(shù)：

Griewank 函數(shù)：

|xi|≤600;

Rastrigin 函數(shù)：

xi∈[-5.12,5.12]；

Weierstrass 函數(shù)：

a=0.5,b=3,kmax=20,x∈[-0.5,0.5]D.

在這些函數(shù)中，Bohachevsky函數(shù)是二維的，其他函數(shù)都在十維上進行仿真，所有函數(shù)的真實最小值都是0.布谷鳥被發(fā)現(xiàn)的概率被設(shè)置為0.25，粒子群算法的權(quán)重設(shè)置為0.7，學習因子c1和c2的值都是1.4.這些參數(shù)來源于原始布谷鳥算法和粒子群算法作者們的仿真實驗，仿真過程見文獻[1-2].在每個函數(shù)上的仿真都將進行30次，結(jié)果取平均值.

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

基于種群信息的布谷鳥算法和CS算法及PSO算法的比較結(jié)果如圖1所示.

圖1 基于種群信息的布谷鳥算法與其他兩種算法在6種基準函數(shù)上的比較

從圖1中可以看出:PBCS在6種測試函數(shù)中都體現(xiàn)出了絕對優(yōu)勢.橫坐標迭代次數(shù)反映了算法的運行時間.他們具有相同的迭代次數(shù)，每一次迭代中各個函數(shù)的評估次數(shù)決定3種算法的總評估次數(shù).雖然每個算法的個體更新公式不同，但是每一代的每一個個體在使用復雜的適應度函數(shù)進行評估所占用的計算量遠遠超過個體更新時的計算量，所以，因算法個體更新公式不同而產(chǎn)生的時間差可以忽略不計.縱坐標代表適應度值，對數(shù)坐標軸可以很清晰地比較算法的性能.

Ackley函數(shù)在全局最優(yōu)值附近有許多局部極小值，這使得算法不容易尋找到真正的全局最小值.從圖1中可以看出：PSO和CS算法在搜索時困于1附近，難以找到真正的全局最小值所在的位置，而PBCS則成功地找到了全局最小值；此外，在Weierstrass函數(shù)上，它們也面臨著相似的情況，而PBCS成功地找到了全局最優(yōu)解.在這種情況下，即使增加迭代次數(shù)也不能使PSO和CS找到理想的值，因為它們并沒有發(fā)現(xiàn)全局最優(yōu)值所在的區(qū)域.

在Schwefel函數(shù)上，3種算法都成功地找到了全局最優(yōu)值所在區(qū)域，但在相同的時間內(nèi)，PBCS找到的解更加精確.Rastrigin函數(shù)在整個搜索域內(nèi)都具有許多局部極小值，是一個非?！捌閸纭钡暮瘮?shù)，非常考驗算法的全局搜索能力.PSO和CS算法的搜索陷于局部極小值中，PBCS雖然可以找到最優(yōu)值所在區(qū)域，但是精確度并不高，這種情況可以用增加迭代次數(shù)的方式解決.

在Bohachevsky函數(shù)、Griewank 函數(shù)上，PSO和PBCS算法的曲線在迭代到一定次數(shù)時“消失”了.這是因為圖像的縱坐標軸是對數(shù)坐標軸，它們在算法迭代結(jié)束前找到了真正的最小值0，而對數(shù)坐標軸不能顯示出0.雖然它們都能找到真正的最小值，但是PBCS的速度顯然更快一些.

通過以上6個測試函數(shù)的對比，PBCS算法的全局探索能力和局部尋優(yōu)能力都明顯強于其他兩種算法.

4 結(jié) 論

基于種群信息的布谷鳥算法中，每個個體參考整個種群的均值和最優(yōu)值生成下一代個體，能成功地跳出局部極值，也可以尋找到具有足夠精度的值，性能超越了未改進前的布谷鳥算法和粒子群算法.在6種常見的基準函數(shù)上，實驗證明了PBCS算法的全局探索性能和局部搜索性能.實驗結(jié)果表明：PBCS的性能明顯優(yōu)于CS算法和PSO算法.本文提出的種群信息策略以及依賴全局最優(yōu)位置的局部搜索策略在一定程度上彌補了原有Levy飛行策略收斂速度慢和容易陷入局部極值的不足.