基于協(xié)同進(jìn)化布谷鳥搜索算法

王慶喜++朱麗華

摘要：在布谷鳥搜索算法的基礎(chǔ)上，通過引入?yún)f(xié)同進(jìn)化策略，提出了一種協(xié)同進(jìn)化布谷鳥搜索算法，該算法對高維函數(shù)優(yōu)化問題采用分而治之的方式把高維問題分解為若干個(gè)低維問題，各低維問題協(xié)同進(jìn)化。改進(jìn)提升了算法的搜索能力，提高了算法的有效性。

關(guān)鍵詞：布谷鳥搜索算法；協(xié)同進(jìn)化策略；維數(shù)災(zāi)難

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）04-0233-02

Cuckoo Search Algorithm Based on Co-evolution

WANG Qing-xi， ZHU Li-hua

（School of Computer Science & Information Engineering， Anyang Institute of Technology， Anyang 455000， China）

Abstract： based on cuckoo search algorithm， we propose a collaborative cuckoo search algorithm by introducing the cooperative strategy， the algorithm solves the algorithm of high dimensional optimization problems using the way that the high dimensional problem is decomposed into several low dimensional problems， and the low dimensional problems co evolution. The improved algorithm improves the searching ability of the algorithm and improves the algorithm's effectiveness.

Key words： Cuckoo search algorithm； co-evolution strategy； Curse of dimensionality

1 背景

智能算法是一種模仿自然界生物機(jī)理的算法，具有自學(xué)習(xí)、自組織和自適應(yīng)性，其有效性被多為學(xué)者證明，并且遺傳算法和粒子群優(yōu)化算法已經(jīng)被應(yīng)用到在高維優(yōu)化問題[1-2]。布谷鳥搜索算法從2009年Xin-She Yang開發(fā)出來以后，已經(jīng)成功應(yīng)用到多個(gè)領(lǐng)域[3-5]，布谷鳥搜索算法在求解低維優(yōu)化問題時(shí)，通常高效可靠，但是在求解高維優(yōu)化問題時(shí)，其優(yōu)化效果大幅下降。因此本文引入?yún)f(xié)同進(jìn)化策略，提出了優(yōu)化高維問題的協(xié)同進(jìn)化布谷鳥搜索算法。

2 布谷鳥搜索算法

2.1 算法原理

布谷鳥的繁殖是具有侵略性的，它們把鳥蛋下到其他鳥類的鳥窩中，并且通過把其他鳥的鳥蛋移出鳥窩的方式提高自己后代的孵化概率[3]。另一方面，宿主鳥也進(jìn)化出識別外來鳥蛋的能力，當(dāng)其識別出外來鳥蛋時(shí)，會將外來鳥蛋推出鳥窩保證自己后代能夠繁衍。因此布谷鳥在選擇鳥窩時(shí)，會對鳥窩進(jìn)行評估，如果感覺可能被宿主鳥發(fā)現(xiàn)的話，就會放棄當(dāng)前鳥窩。

研究顯示[4]許多動(dòng)物和昆蟲的飛行路徑是一種隨機(jī)行走，因?yàn)橄乱徊經(jīng)Q定于兩個(gè)因素：當(dāng)前位置和到下一個(gè)位置的躍進(jìn)概率，并且通過數(shù)學(xué)建模發(fā)現(xiàn)，其飛行行為呈現(xiàn)出萊維飛行的特點(diǎn)。萊維飛行是一種隨機(jī)行走，其步長是根據(jù)重尾分布的概率分布，大量行走之后，從原來的隨機(jī)游走的距離趨向于一個(gè)穩(wěn)定的分布

2.2 算法描述

在布谷鳥搜索算法中，每一個(gè)鳥窩代表一個(gè)解決方案（解），每一個(gè)布谷鳥鳥蛋代表一個(gè)新的解決方案（新解）。布谷鳥搜索算法[5]采用新的比較好的解決方案代替一個(gè)鳥窩中不太好的解決方案，經(jīng)過若干次的迭代后，找到最優(yōu)的解決方案。

在優(yōu)化單目標(biāo)問題時(shí)，每一個(gè)布谷鳥一次選擇一個(gè)鳥窩下一個(gè)蛋；在迭代過程中，最好的鳥窩（解決方案）會被保留到一下代，而不好的鳥窩會被新的鳥蛋（解決方案）替代；宿主鳥窩數(shù)量是固定的，宿主鳥發(fā)現(xiàn)外來鳥的概率也是固定的，為了簡單，該概率取值0.25。

鳥窩位置更新公式：

其中[α]>0表示步長，Levy表示萊維飛行，其值由萊維分布決定：

3 協(xié)同進(jìn)化布谷鳥搜索算法

目前，大多數(shù)優(yōu)化算法都是針對低維問題提出的，但是優(yōu)化問題的規(guī)模和復(fù)雜度越來越大，解決低維優(yōu)化問題的算法已經(jīng)不能滿足大規(guī)模高維度優(yōu)化的需求。

雖然原始布谷鳥搜索算法已經(jīng)被廣泛地應(yīng)用于函數(shù)優(yōu)化，但是對于高維函數(shù)，算法優(yōu)化性能急劇下降。為了使用布谷鳥搜索算法求解高維函數(shù)優(yōu)化，必須對高維函數(shù)問題進(jìn)行降維處理，本文采用協(xié)同進(jìn)化策略實(shí)現(xiàn)降維。

3.1 協(xié)同進(jìn)化策略

協(xié)同進(jìn)化策略[6]是指通過將問題分解的方式解決大規(guī)模問題的一種策略，是一種分而治之的方法。在智能優(yōu)化算法中，協(xié)同進(jìn)化策略將一個(gè)高維搜索空間分解成多個(gè)低維的子空間，每個(gè)子空間作獨(dú)立進(jìn)化，并協(xié)同組成個(gè)體，進(jìn)行適應(yīng)度值計(jì)算。本文把d維向量分割成d個(gè)一維向量，即每一維都分解成一個(gè)子空間。在每一次迭代中，這些子空間的變量獨(dú)立進(jìn)化，在得到子空間的最優(yōu)值后，將其通過當(dāng)前最優(yōu)解傳給其他子空間，從而協(xié)同得出最終的全局最優(yōu)解。

3.2 數(shù)學(xué)符號

假定使用種群規(guī)模為n的布谷鳥搜索算法來優(yōu)化d維函數(shù)。

[xi，j]表示第i個(gè)鳥窩在第j維（第j個(gè)子空間）上分量的值。

[x（t）i（j，xi，j）]表示向量[x（t）i]第j個(gè)元素被[xi，j]替換后的向量。

b表示目前最佳鳥窩，即當(dāng)前最優(yōu)解。

p0表示宿主鳥發(fā)現(xiàn)外來蛋的概率

3.3 適應(yīng)度值計(jì)算與比較

協(xié)同進(jìn)化的鳥窩是分割開的，不再是一個(gè)完整的d維鳥窩向量，因此其鳥窩適應(yīng)度值計(jì)算和原始布谷鳥搜索算法中的鳥窩適應(yīng)度值計(jì)算存在差異。

假設(shè)在t次迭代時(shí)，第j個(gè)子鳥窩的第i個(gè)鳥窩的適應(yīng)度值計(jì)算采用的向量為：第j個(gè)分量取[xi，j]，其余d-1個(gè)分量則取當(dāng)前第i個(gè)鳥窩的其他n-1維的值，記為[x（t）i（j，xi，j）]。

3.4 鳥窩位置比較規(guī)則

令[x（t+1）i=x（t）i（j，xi，j）]，其中[j=1，2，…，d]

當(dāng)[f（x（t+1）i）

從鳥窩比較規(guī)則可知：每個(gè)鳥窩在進(jìn)化過程中始終保持最佳，而變量采用子空間的分量外，其余都采用了對應(yīng)鳥窩的當(dāng)前最佳分量，因此協(xié)同策略對更新后的鳥窩分量都進(jìn)行適應(yīng)度值評估，提高了鳥窩（解）的多樣性，提高了鳥窩之間的相互學(xué)習(xí)性。

3.5 CCS偽代碼

綜上所述，協(xié)同進(jìn)化布谷鳥搜索算法的進(jìn)化過程轉(zhuǎn)變?yōu)槎鄠€(gè)變量的協(xié)同進(jìn)化，最大的改進(jìn)是鳥窩的適應(yīng)度值計(jì)算規(guī)則的修改，算法的偽代碼如下所示：

4 結(jié)束語

通過引入?yún)f(xié)同進(jìn)化策略的方式，對布谷鳥搜索算法進(jìn)行改進(jìn)，提升了算法的高維優(yōu)化能力。系統(tǒng)進(jìn)化策略把優(yōu)化問題的高維搜索空間分解成多個(gè)一維的子搜索空間，子搜索空間協(xié)同進(jìn)化，經(jīng)過若干次迭代后獲得高維優(yōu)化問題的最優(yōu)解。

參考文獻(xiàn)：

[1] Dynamically Exploring Internal Mechanism Of Stock Market By Fuzzy-based Support Vector Machines With High Dimension Inputspace And Genetic Algorithm[J]. Expert Systems with Application， 2009 ，32（2）： 1240-1248.

[2] Kiranyaz S， Ince T， Yildirim A， et al. Fractional Particle Swarm Optimization in Multidimensional Search Space[J]. IEEE transactions on systems， man， and cybernetics， Part B. Cybernetics： A publication of the IEEE Systems， Man， and Cybernetics Society， 2010， 40（2）.

[3] S Walton， O Hasan， K Morgan， et al. Modify cuckoo search： A new gradient free optimisation algorithm[J]. Chaos， Solitons & Fractals， 2011， 44（6）： 710-718.

[4] Ehsan valiant， Saeed Tavakoli， Shahram Mohanna， et al. Improved cuckoo search for reliability optimization problems[J]. Computers & Industrial Engineering， 2013（64）： 459-468.

[5] Xinxin Ouyang， Yongquan Zhou， Qifang Luo，et al. A Novel Discrete Cuckoo Search Algorithm for Spherical Traveling Salesman Problem[J]. Applied Mathematics & Information Sciences， 2013， 7（2）： 777-784.

[6] Valian E， Mohanna S， Tavakoli S. Improved cuckoo search algorithm for feed forward neural network training[J]. Int J Artif Intell， 2011， 2（3）： 36-43.