一種改進的雞群算法

孔飛，吳定會

(江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫 214122)

一種改進的雞群算法

孔飛，吳定會*

(江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫 214122)

針對雞群算法在求解高維優化問題時易陷入局部最優和出現早熟收斂的情況，提出一種改進的雞群算法。算法中對小雞的位置更新公式中加入向小雞自身所在群中的公雞學習部分，并引入慣性權值和學習因子，然后用改進的雞群算法對8個基本測試函數進行求解。仿真實驗時與粒子群算法、蝙蝠算法和雞群算法進行對比。結果表明，該算法在求解優化問題時易于跳出局部最優，避免早熟收斂，尤其對于高維問題，該算法相比其他進化算法，更容易找到全局最優值。

群體智能;等級秩序;雞群算法;測試函數;復雜度分析

群體智能優化算法(Swarm Intelligence Algorithm，SIA)是通過模擬自然界生物的群體行為而構造的隨機優化算法［1］，如粒子群算法［2］(Particle Swarm Optimization，PSO)、蟻群算法［3］(Ant Colony Optimization，ACO)、人工蜂群算法［4］(Artificial Bee Colony，ABC)、人工魚群算法［5］(Artificial Fish Swarm Algorithm，AFSA)、蝙蝠算法［6］(Bat Algorithm，BA)等。這些算法為解決大量存在于計算科學、工程科學、管理科學等領域的全局優化問題提供了新的求解途徑，因此成為科研人員長期研究的熱點。全浩軍等［7］將改進的人工魚群算法用于軟硬件劃分;王澤兵等［8］將粒子群算法用于動態熱釋電目標跟蹤;羅慧等［9］將動態蟻群算法用于模擬電路最優測點選擇。新的智能算法仍在不斷出現，如磷蝦群優化算法［10］、混沌果蠅算法［11］、蜘蛛算法［12］等。所有的這些算法都是從自然界中各種生物種群生活規律中抽象出來的。

雞群算法(Chicken Swarm Optimization，CSO)是由MENG Xianbing等［13］于2014年提出的一種基于雞群搜索行為的隨機優化方法，它模擬了雞群等級制度和雞群行為。整個雞群分為若干子群，每一個子群都由一個公雞、若干母雞和小雞組成。不同的雞遵循不同的移動規律，在具體的等級制度下，不同的雞群之間存在競爭，它是一種全局優化算法。相比粒子群算法、蝙蝠算法和差分進行算法［14］，該算法具有收斂速度快和收斂精度高的優點。但是文獻［13］只是對標準測試函數在低維情況下加以求解，并沒有對高維問題進行求解和相關的分析。文中分析了文獻［13］提出的算法在對高維優化問題求解時，收斂精度變低，算法容易陷入局部最優，出現早熟收斂情況。文中提出了一種改進的雞群算法(Improved Chicken Swarm Optimization，ICSO)，算法中對小雞的位置更新公式中加入向小雞自身所在群中的公雞學習部分，并引入慣性權值和學習因子，在保證算法收斂速度的同時盡可能提高算法的收斂精度，防止算法出現早熟收斂情況。通過對基本測試函數的求解驗證了所提算法的可行性和先進性。

1 雞群優化算法

在描述算法前，先進行如下假設:

1)整個雞群中存在著若干子群，每個子群都由一個公雞、若干母雞和一些小雞組成。

2)如何把雞群分成若干子群以及如何確定雞的種類取決于雞自身的適應度值。雞群中，適應度值最好的若干個體作為公雞，并且每只公雞都是一個子群的頭目;具有最差適應度值的若干個體作為小雞;剩余的個體就作為母雞。母雞隨便選擇屬于哪個子群，母雞和小雞的母子關系也是隨機建立的。

3)雞群中的等級制度、支配關系和母子關系一旦建立就保持不變，直至數代以后才開始更新。

4)每個子群中的個體都圍繞這個子群中的公雞尋找食物，也可以阻止其他個體搶奪自己的食物;并且假設小雞可以隨機偷食其他個體已經發現的食物，每只小雞跟隨它們的母親一起尋找食物。雞群中具有支配地位的個體具有良好的競爭優勢，它們先于其他個體找到食物。

在解決優化問題時，雞群中的每個個體都對應優化問題的一個解。假設NR，NH，NC和NM分別為公雞、母雞、小雞和媽媽母雞的個數。在整個雞群中，所有的個體數假設為N，每個個體的位置xij(t)表示第i個體的j維在第t次迭代的值。

整個雞群有3種類型的雞，雞群中個體位置更新公式隨著雞種類的不同而不同。公雞對應雞群中適應度值最好的個體，它們可以在更廣泛的空間尋找食物，公雞對應的位置更新公式如下:

式中:Randn(0，σ2)為均值為0，標準差為σ2的一個高斯分布;ε為一個很小的常數;k為所有公雞中除去i后的任一個體。

母雞的位置更新公式如下:

式中:Rand為［0，1］之間均勻分布的隨機數;r1為第i只母雞自身所在群中的公雞;r2為整個雞群中公雞和母雞中隨機選取的任意個體，且r1≠r2。小雞的位置更新公式如下:

式中:m為第i只小雞對應的母雞;F(F∈［0，2］)為跟隨系數，表示小雞跟隨母雞尋找食物。

2 改進的雞群算法

2.1 雞群算法分析

文中采用文獻［13］中算法對4個標準測試函數在高維條件下進行了求解，并對比了其他兩種算法，求解結果見表1。

由表1可以看出，當D=100時，雞群算法的求解結果雖然好于粒子群算法和蝙蝠算法的求解結果，但是已明顯偏離了全局最優值，尤其是對于Rosenbrock函數算法明顯陷入局部最優，出現早熟收斂現象。

表1 CSO和其他算法對于4個標準測試函數在D=100求解結果比較Tab.1 Com parison betw een the results of CSO and other algorithm s for D=100

2.2 改進的雞群算法

對于式(6)中的小雞位置更新公式，小雞只向自己的媽媽學習，而并沒有向小雞自身所在群中的公雞學習。小雞在更新自己的位置時只能獲取自己媽媽的位置信息，而無法獲取整個子群中公雞的位置信息。當媽媽母雞陷入局部最優時，小雞因為只向自己的媽媽學習，也會陷入局部最優。因此，雞群算法會陷入局部最優。文中對小雞的位置更新公式進行了改進，更新公式中加入了向小雞自身所在群中的公雞學習部分。改進后的位置更新公式如下:式中:m為小雞對應的媽媽母雞;r為媽媽母雞自身所在群中的公雞;C為學習因子，表示小雞向自身所在群中公雞學習的程度;w為小雞的自我學習系數，這與粒子群算法中的慣性權重很相似。

算法的詳細流程如下:

1)初始化雞群x，并定義相關參數NR，NH，NC，NM等;

2)計算雞群的適應度值fitness，初始化個體當前最好位置Pbest和雞群全局最好位置gbest，t=1;

3)如果t%G=1，排序fitness，建立雞群的等級制度，將雞群分成數個子群并確定母雞和小雞的對應關系;

4)使用式(1)、式(3)和式(7)分別更新公雞、母雞和小雞的位置并分別計算每個個體的適應度值;

5)更新雞群的個體當前最好位置和雞群全局最好位置;

6)t=t+1，如果滿足迭代停止條件，則停止迭代，輸出最優值，否則轉到3)。

2.3 參數分析

G的取值對文中算法的收斂精度和收斂速度能產生重要影響。G取值太大，算法不能快速收斂到全局最優值，影響算法的收斂速度;G取值太小，算法容易陷入局部最優值。文中通過對測試函數的測試，得出以下結論:當G=10時，算法在保證收斂精度的同時，收斂速度明顯提高。此外，在綜合考慮算法的收斂精度、收斂速度和魯棒性的情況下，F?。?.4，1］之間的隨機數，C=0.4，w隨迭代次數的增加從0.9到0.4指數遞減。w的計算公式

如公式(7)所示［15］。

3 仿真實驗分析

3.1 參數設置

使用表2列出的8個基本測試函數對文中算法的有效性進行驗證［16-17］，仿真中對比了標準PSO，CSO和BA算法。為了得到客觀評價，4種算法對每一個測試函數獨立運行30次，種群規模都為100，每次運行的最大迭代次數均為1 000，分別在D=10和D=100的情況下對所有的測試函數進行求解。4種算法其他相關參數見表3。

表2 8個標準測試函數Tab.2 Eight benchm ark prob lem s

表3 算法的相關參數設置Tab.3 Related parameter values

3.2 仿真分析

4種算法對每一個測試函數獨立運行30次，求出30次運行結果的最好值、最差值、平均值和標準差，結果列于表4、表5中。

表4 文中算法和其他算法對標準測試函數在D=10的求解結果比較Tab.4 Com parison between the resu lts of ICSO and other algorithms for D=10

表5 文中算法和其他算法對標準測試函數在D=100的求解結果比較Tab.5 Com parison betw een the results of ICSO and other algorithm s for D=100

由表4可以看出，在D=10時，對于大部分測試函數而言，ICSO的求解結果要好于CSO的求解結果，且ICSO和CSO的求解結果要遠遠好于PSO和BA的求解結果。

由表5可以看出，在D=100時，對于這8個測試函數而言，ICSO的求解結果均好于CSO的求解結果，且遠遠好于PSO和BA的求解結果;尤其對于測試函數F2，F5，F6，F7和F8而言，ICSO的求解結果要遠遠好于CSO的求解結果。

4種算法分別對于測試函數代號F1～F8(以下簡稱Fx函數)，在D=100時，獨立運行30次，獲得的平均值收斂曲線如圖1～圖8所示。

圖1 4種算法在D=100對F1函數平均收斂曲線Fig.1 Average convergence curves for F1at D=100

圖2 4種算法在D=100對F2函數平均收斂曲線Fig.2 Average convergence curves for F2at D=100

圖3 4種算法在D=100對F3函數平均收斂曲線Fig.3 Average convergence cu rves for F3at D=100

圖4 4種算法在D=100對F4函數平均收斂曲線Fig.4 Average convergence cu rves for F4at D=100

圖5 4種算法在D=100對F5函數平均收斂曲線Fig.5 Average convergence curves for F5at D=100

圖6 4種算法在D=100對F6函數平均收斂曲線Fig.6 Average convergence curves for F6at D=100

圖7 4種算法在D=100對F7函數平均收斂曲線Fig.7 Average convergence curves for F7at D=100

圖8 4種算法在D=100對F8函數平均收斂曲線Fig.8 Average convergence curves for F8at D=100

由圖1～圖8可以看出，在D=100時，就F1～F8函數而言，ICSO的收斂精度均高于CSO算法，且遠遠高于PSO和BA。在收斂速度方面，對于F2，F4，F5，F6，F7和F8函數而言，ICSO要優于CSO，PSO和BA;對于F1和F3函數而言，ICSO和CSO收斂速度相當，且優于PSO和BA。

3.3 算法復雜度分析

算法的復雜度評價主要包括兩個方面:時間復雜度評價和空間復雜度評價。時間復雜度指算法迭代一次所需要最多步驟的時間復雜度之和，通常用數量級符號階次o表示，如常數階o(1)。空間復雜度指算法在計算機內執行時所需最大存儲空間的度量。由于ICSO與其他3種算法的空間復雜度相當，所有這里只討論一下算法的時間復雜度。

對于群體智能優化算法而言，算法的時間復雜度正比于問題的優化規模D和群體中個體的數目N。由于ICSO與CSO的時間復雜度相同，這里只列出了3種算法在一次迭代中所需要的主要步驟以及對應的時間復雜度，統計結果見表6。

表6 3種算法的時間復雜度分析Tab.6 Time com plexity analysis of three algorithm s

由表6中可以看出，PSO，BA和ICSO的算法運行時間分別為2N+4ND，2N+6ND和N+4ND?？梢钥闯鲞@3種算法的時間復雜度是相同的，但是ICSO比PSO和BA算法語句執行次數少，因而消耗的時間少。

4 結語

為了克服雞群算法在求解高維問題時發生早熟收斂，文中提出一種改進的雞群算法，算法在小雞的位置更新公式中加入向小雞自身所在群中的公雞學習部分，并引入學習因子和慣性權重。對于8個基本測試函數的仿真結果表明，文中算法在求解優化問題時易于跳出局部最優，避免了早熟收斂問題，尤其對于高維問題而言，文中算法相比其他進化算法，更容易找到全局最優值。此外，在算法的執行時間上，文中算法明顯少于粒子群算法和蝙蝠算法。所以文中提出的算法具有可行性和先進性。

［1］Beheshti Z，Shamsudding SM H.A review of population-based meta-heuristic algorithms［J］.Int JAdv Soft Comput Appl，2013，5(1):1-35.

［2］Kennedy J，Eberhart R.Particle swarm optimization［C］//Proceedings of IEEE International Conference on Neural Networks.Perth Australsa:IEEE Press，1995:1942-1948.

［3］Dorigo M，Maniezzo V，Colorni A.Ant system:optimization by a colony of cooperating agents［J］.IEEE Transactions on Systems Man and Cybernetics，Part B:Cybernetics，1996，26(1):29-41.

［4］Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Kayseri:Erciyes University，2005.

［5］LI X L，SHAO Z J，QIAN J X.An optimizing method based on autonomous animats:fish-swarm algorithm［J］.Systems Engineering Theory and Practice，2002，22(11):32-38.

［6］YANG X S.A new metaheuristic bat-inspired algorithm［C］//Nature Inspired Cooperative Strategies for Optimization(NICSO 2010).Berlin Heidelberg:Springer，2010.

［7］全浩軍，張濤，郭繼昌.基于改進人工魚群算法的軟硬件劃分方法［J］.天津大學學報:自然科學與工程技術版，2013，46 (10):923-928.

QUAN Haojun，ZHANG Tao，GUO Jichang.Hardware/software partitioning method based on improved artificial fish swarm algorithm［J］.Journal of Tianjin University:Science and Technology，2013，46(10):923-928.(in Chinese)

［8］王澤兵，楊衛，秦麗.基于粒子群算法的動態熱釋電目標跟蹤［J］.光學學報，2014，34(10):35-41.

WANG Zebing，YANG Wei，QIN Li.Target tracking based on particle swarm optim ization using dynamic pyroelectric infrared sensor［J］.Acta Optica Sinica，2014，34(10):35-41.(in Chinese)

［9］羅慧，蹇興亮，盧偉.基于動態蟻群算法的模擬電路最優測點選擇［J］.儀器儀表學報，2014，35(10):2231-2237.

LUO Hui，JIAN Xingliang，LUWei.Optimal test node selection based on dynamic ant colony algorithm for analog circuit［J］.Chinese Journal of Scientific Instrument，2014，35(10):2231-2237.(in Chinese)

［10］Gandomi A H，Alavi A H.Krill herd:a new bio-inspired optim ization algorithm［J］.Communications in Nonlinear Science and Numerical Simulation，2012，17(12):4831-4845.

［11］LEIX，DU M，XU J，et al.Chaotic fruit fly optimization algorithm［C］//5th International Conference on Swarm Intelligence.Hefei:Springer International Publishing，2014:74-85.

［12］Cuevas E，Cienfuegos M，Zaldívar D，et al.A swarm optimization algorithm inspired in the behavior of the social-spider［J］.Expert Systems with Applications，2013，40(16):6374-6384.

［13］MENG X B，LIU Y，GAO X Z，et al.A new bio-inspired algorithm:chicken swarm optimization［C］//5th International Conference on Swarm Intelligence.Hefei:Springer International Publishing，2014:86-94.

［14］Das S，Suganthan PN.Differential evolution:a survey of the state-of-the-art［J］.IEEE Transactions on Evolutionary Computation，2011，15(1):4-31.

［15］陳貴敏，賈建援，韓琪.粒子群優化算法的慣性權值遞減策略研究［J］.西安交通大學學報，2006，40(1):53-56，61.

CHEN Guimin，JIA Jianyuan，HAN Qi.Study on the strategy of decreasing inertia weight in particle swarm optimization algorithm［J］.Journal of Xi’an Jiaotong University，2006，40(1):53-56，61.(in Chinese)

［16］LIANG JJ，QU B Y，Suganthan PN.Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization［R］.Zhengzhou:Zhengzhou University，2013.

［17］Ho S Y，SHU L S，CHEN J H.Intelligent evolutionary algorithms for large parameter optimization problems［J］.IEEE Transactions on Evolutionary Computation，2004，8(6):522-541.

(責任編輯:邢寶妹)

An Im p roved Chicken Swarm Optim ization A lgorithm

KONG Fei，WU Dinghui*
(Key Laboratory of Advanced Process Control for Light Industry，Ministry of Education，Jiangnan University，Wuxi 214122，China)

Considering the problem that the original chicken swarm optimization algorithm easily falls into local optimum because of the premature convergence for high-dimensional comp lex problems，an improved chicken swarm optimization is proposed.In the algorithm，the part of chicks learning from the rooster in their subgroup is added to chick＇s position update equation，and the inertia weight and learning factor are introduced.Then eight benchmark functions are used to test the proposed algorithm and the comparison with the particle swarm optimization，the bat algorithm，and the original chicken swarm optimization is also performed.The simulation experimental results show that the proposed algorithm is able to avoid premature convergence and can escape from local optimum.Especially，the proposed method outperforms other evolutionary algorithms in finding the global optimum for highdimensional problems.

swarm intelligence，hierarchal order，chicken swarm optim ization，benchmark function，complexity analysis

TP 301.6

A

1671－7147(2015)06－0681－08

2015－06－03;

2015－07－21。

國家自然科學基金項目(61572237，61573167);江蘇省“六大人才高峰”項目(WLW－008)。

孔飛(1986—)，男，安徽合肥人，控制工程專業碩士研究生。

*通信作者:吳定會(1970—)，男，安徽合肥人，副教授，碩士生導師，工學博士。主要從事智能調度技術等研究。Email:wh033098@163.com