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

高淑芝,高 越

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

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

1 布谷鳥算法

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

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

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

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

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

(1)

(2)

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

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

(3)

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

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

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

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

(4)

(5)

其中p代表種群大小.

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

(6)

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

(7)

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

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

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

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

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

步驟5：根據布谷鳥被發現的概率隨機舍棄部分個體.

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

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

步驟8：終止循環，輸出最優值.

3 實驗與分析

3.1 實驗函數與參數設置

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

Ackley函數：

Bohachevsky 函數：

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

Schewefel 函數：

Griewank 函數：

|xi|≤600;

Rastrigin 函數：

xi∈[-5.12,5.12]；

Weierstrass 函數：

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

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

3.2 實驗結果與分析

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

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

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

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

在Schwefel函數上，3種算法都成功地找到了全局最優值所在區域，但在相同的時間內，PBCS找到的解更加精確.Rastrigin函數在整個搜索域內都具有許多局部極小值，是一個非常“崎嶇”的函數，非常考驗算法的全局搜索能力.PSO和CS算法的搜索陷于局部極小值中，PBCS雖然可以找到最優值所在區域，但是精確度并不高，這種情況可以用增加迭代次數的方式解決.

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

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

4 結 論

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