王慶喜++朱麗華

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

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

中圖分類號：TP18 文獻標識碼：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 背景

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

2 布谷鳥搜索算法

2.1 算法原理

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

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

2.2 算法描述

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

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

鳥窩位置更新公式：

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

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

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

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

3.1 協(xié)同進化策略

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

3.2 數(shù)學符號

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

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

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

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

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

3.3 適應度值計算與比較

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

假設在t次迭代時，第j個子鳥窩的第i個鳥窩的適應度值計算采用的向量為：第j個分量取[xi，j]，其余d-1個分量則取當前第i個鳥窩的其他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]

當[f（x（t+1）i）

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

3.5 CCS偽代碼

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

4 結束語

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

參考文獻：

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