吳定會，孔飛，紀志成

?

雞群算法的收斂性分析

吳定會，孔飛，紀志成

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

針對雞群算法建立Markov鏈數(shù)學分析模型，分析此Markov鏈的一些性質，證明雞群狀態(tài)序列是有限齊次Markov鏈。結合隨機算法收斂準則，證明雞群算法能夠滿足隨機算法全局收斂的2個準則，保證算法全局收斂。將算法應用于15個標準測試函數(shù)尋優(yōu)問題，并同標準粒子群算法、蝙蝠算法進行比較。實驗結果表明：該算法具有較好的全局收斂性和計算魯棒性，尤其適合高維、多峰的復雜函數(shù)求解。

雞群算法；Markov鏈；狀態(tài)轉移；全局收斂；標準測試函數(shù)

群體智能優(yōu)化算法(簡稱SIA)是通過模擬自然界生物的群體行為而構造的隨機優(yōu)化算法[1]，如遺傳算法[2?3]、粒子群算法(簡稱PSO)[4?6]、蟻群算法(簡稱ACO)[6?7]、人工蜂群算法(簡稱ABC)[8?12]、人工魚群算法(簡稱AFSA)[13]、狼群算法(簡稱WPA)[14]、蝙蝠算法(簡稱BA)[15]等。這些算法為解決大量存在于計算科學、工程科學、管理科學等科研領域的全局優(yōu)化問題提供了新的求解途徑，因此，成為科研人員長期研究的熱點。但這些算法的理論依據(jù)多來源于對生物群落社會性的模擬，缺乏相關的理論性分析，算法中參數(shù)設置無確切的理論依據(jù)，都是依據(jù)經(jīng)驗確定的，所以，對群體智能優(yōu)化算法的理論性研究顯得尤為重要。雞群算法(簡稱CSO)是由MENG等[16]提出的一種基于雞群搜索行為的群體智能優(yōu)化算法，它模擬了雞群等級制度和雞群行為。整個雞群分為若干子群，每一個子群都由1只公雞、若干只母雞和小雞組成。不同雞遵循不同的移動規(guī)律，在具體的等級制度下，子群之間存在競爭行為，它是一種全局優(yōu)化算法。目前，已經(jīng)有學者提出了改進算法，并將其用于求解約束優(yōu)化問題。但是，雞群算法由于小雞粒子容易陷入局部最優(yōu)而無法取得全局最優(yōu)解[17]，關于雞群算法的收斂性分析，國內(nèi)外幾乎沒有文獻報道，因此，對雞群算法進行收斂性分析具有很重要的理論價值。Markov鏈理論在隨機算法收斂性分析以及收斂概率分析上具有較強的能力，它是一類占有重要地位、具有普遍意義的隨機過程，其應用相當廣泛，目前已經(jīng)應用于模擬退火、粒子群算法、蟻群算法和人工蜂群算法等隨機算法的收斂性分析[18?21]。本文作者采用Markov鏈理論對雞群算法的收斂性進行分析，通過建立雞群算法的Markov鏈模型，研究雞群狀態(tài)的轉移行為，結合隨機算法的收斂準則分析算法的收斂性能。通過仿真實驗驗證雞群算法的尋優(yōu)性能。

1 雞群優(yōu)化算法

雞群算法是由MENG等提出的一種基于雞群搜索行為的隨機優(yōu)化方法，它模擬了雞群等級制度和雞群行為。在描述算法前，先進行如下假設：

1) 設整個雞群中存在著若干子群，1，2，…，A；每個子群A都由1只公雞、若干只母雞和小雞組成，分別用A1，A2，A3表示，其中A1，A2，A3A。

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

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

4)每個子群中的個體都圍繞這個子群中的公雞尋找食物，也可以阻止其他個體搶奪自己的食物；并且假設小雞可以隨機偷食其他個體已經(jīng)發(fā)現(xiàn)的食物，每只小雞跟隨他們的母親一起尋找食物。雞群中具有支配地位的個體具有良好的競爭優(yōu)勢。

在解決優(yōu)化問題時，雞群中的每個個體都對應優(yōu)化問題的1個解。假設R，H，C和M分別為公雞、母雞、小雞和媽媽母雞的個數(shù)。在整個雞群中，所有的個體數(shù)假設為，每個個體的位置x,j()表示第個體的維在第次迭代值。

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

式中：Rand為[0，1]之間均勻分布的隨機數(shù)；1為第只母雞所在子群A中的公雞，即1∈A1；2為整個雞群中公雞和母雞中隨機選取的任意元素，即2∈(11∪21∪…∪A1∪12∪22∪…A2)。小雞的位置更新公式如下：

2 雞群算法的Markov鏈模型

為了證明方便，不考慮粒子的維數(shù)，對雞群中個體位置更新公式進行如下簡化。

公雞的位置更新公式為

式中：1取[0，1]之間的固定值。

母雞的位置更新公式為

式中：2和3取[0，1]之間的隨機數(shù)，但是對于確定的個體，2和3是確定的；2＜1＜1。

小雞的位置更新公式為

為了說明雞群算法的Markov鏈模型，首先給出一些相關定義和數(shù)學描述[22?23]。

定義4(狀態(tài)等價類) 由等價關系“~”在上誘導的雞群狀態(tài)等價類記作=/~，簡稱雞群等價類。

雞群等價類存在以下性質：

2)內(nèi)任意雞群狀態(tài)和外任意雞群狀態(tài)不等價。

定理1 雞群算法中，雞的狀態(tài)x一步轉移到x的轉移概率為

證明：因為雞群中3種雞的位置更新公式不同，所以，3種雞對應的一步轉移概率也不相同。雞的群體為超空間的一組點集，則雞群中個體位置更新過程是在超空間中進行點集之間的變換。由定義5和雞群算法的幾何性質，可得公雞由狀態(tài)x一步轉移到x的轉移概率為

母雞由狀態(tài)x一步轉移到x的轉移概率為

小雞由狀態(tài)x一步轉移到x的轉移概率為

證畢。

式中：為雞群中個體數(shù)。即雞群算法中雞群狀態(tài)s一步轉移到s的概率為雞群內(nèi)所有雞的狀態(tài)同時轉移到雞群s內(nèi)所有雞的狀態(tài)。

表明雞群等價類之間的轉移包括等價類L中的所有雞群轉移到等價類L中的所有雞群。

3 雞群優(yōu)化算法的收斂性分析

定義9(有限Markov鏈) 若狀態(tài)空間是有限的，則稱該Markov鏈是有限Markov鏈。

3.1 收斂準則

雞群優(yōu)化算法屬于隨機搜索算法，因此本文通過隨機算法收斂準則判定雞群算法的收斂行為[24]。

定義搜索的下確界：

式中：()表示在集合上的勒貝格測度，定義最優(yōu)解區(qū)域：

3.2 雞群算法的收斂性

定理4 CSO算法滿足條件H1。

證明：CSO算法每次迭代時都要更新個體當前最優(yōu)位置，即

故CSO算法每次迭代都保存了群體最佳位置，滿足條件H1。證畢。

定理5 雞群算法所產(chǎn)生的Markov鏈是吸收態(tài)Markov鏈。

定理6 雞群算法中，最優(yōu)雞群狀態(tài)集是狀態(tài)空間上的1個閉集。

根據(jù)文獻[25]，本文不加證明的給出定理8。

定理9 當雞群內(nèi)部迭代趨于無窮時，雞群狀態(tài)序列必將進入最優(yōu)狀態(tài)集。

證明：由定理6、定理7和定理8即可得出定理9成立。證畢。

定理10 雞群算法收斂到全局最優(yōu)。

4 實驗與分析

為了充分驗證算法的性能與特點，需要引入較多具有不同特征的標準函數(shù)，本文采用文獻[14]中的15個標準測試函數(shù)作為實驗對象，這15個測試函數(shù)分為4類：單峰不可分函數(shù)、單峰可分函數(shù)、多峰不可分函數(shù)和多峰可分函數(shù)。

文獻[14]中的這15個標準函數(shù)的變量維數(shù)從2維直至200維，都是難度較大的復雜優(yōu)化問題，具有很好的測試性，可較為全面的反應各算法的性能。利用這15個測試函數(shù)對CSO算法、PSO和BA進行比較分析。

實驗環(huán)境為：Windows7 系統(tǒng)，4G內(nèi)存，CPU 3.4 GHz，算法基于Matlab R2011b用M語言實現(xiàn)。

為充分對比各算法的性能，利用CSO，PSO和BA 3種智能算法分別對15個復雜函數(shù)重復進行100次尋優(yōu)計算，從最好值、最差值、平均值、標準差、平均耗時等多方面對算法進行評估。

實驗設置的最大迭代次數(shù)為1 000，初始個體總數(shù)皆為100，3種算法所涉及的其他參數(shù)見表1。

表1 3種算法參數(shù)

表2給出了3種算法對15個復雜函數(shù)尋優(yōu)計算的統(tǒng)計結果。其中，規(guī)定若計算結果小于1×10?20，則視為0。

最好值和平均值可體現(xiàn)算法的收斂精度和尋優(yōu)能力。由表2可知：對于簡單的低維函數(shù)如Easom，Matyas，Booth，Bohachevsky1，Eggcrate，Six Hump Camel Back，Bohachevsky3，PSO算法和CSO算法收斂精度相當高，基本都可以收斂到理論最優(yōu)值。BA算法與PSO算法和CSO算法相比，收斂精度次之，所以，對于簡單的低維函數(shù)，BA算法的尋優(yōu)能力不如PSO算法和CSO算法。但隨著變量維數(shù)的逐漸增加，算法的搜索空間復雜度呈指數(shù)倍增加。對于函數(shù)Trid6，Sumsquares和Sphere(維數(shù)分別為6，10和30)，雖然這3種算法有不同程度的較強尋優(yōu)能力，但是CSO算法對每一個測試函數(shù)都能收斂到理論最優(yōu)值。當維數(shù)增加到60維(Rastrigin函數(shù))、120維(Quadric函數(shù))甚至200維(Ackley函數(shù))時，雖然這3種算法都無法達到理論最優(yōu)值，但是CSO算法收斂精度要明顯高于PSO算法和BA算法收斂精度。特別對于Rastrigin函數(shù)，CSO算法的收斂值要比PSO算法和BA算法的收斂值小得多。由此可見CSO算法在處理多峰、高維復雜函數(shù)中具有很大的優(yōu)勢。

表2 函數(shù)優(yōu)化結果對比

注：黑體表示所獲得的最好值。

最差值和標準差體現(xiàn)了算法的魯棒性和對抗局部極值的能力。由表2可知：除Bridge，Rastrigin，Quadric和Ackley外，PSO算法和BA算法對于其他低維函數(shù)的最差值接近理想值，標準差也較小，可見這2種算法對于低維函數(shù)的尋優(yōu)計算具有一定的魯棒性。但是與PSO算法和BA算法相比，CSO算法所獲得的最差值始終更接近于理想最優(yōu)值，標準差也始終最小，尤其對于測試函數(shù)Easom，Matyas，Booth，Bohachevsky1，Eggcrate，Schaffer，Six Hump Camel Back，Bohachevsky3，Sumsquares和Sphere，CSO算法所獲得的最差值近似等于理論最優(yōu)值，標準差近似為0。可見，CSO算法在函數(shù)尋優(yōu)過程中具有良好的魯棒性。

從平均耗時來看，對于所有的標準測試函數(shù)而言，PSO算法和BA算法的平均消耗時間相當，CSO算法的平均耗時要稍大于PSO算法和BA算法的平均耗時。但是對于計算時間要求不是特別高的優(yōu)化問題，CSO算法因其具有較高的收斂精度和較強的魯棒性而具有很明顯的優(yōu)勢。

雖然CSO是一種全局收斂算法，對于大部分測試函數(shù)在規(guī)定的迭代次數(shù)內(nèi)都能收斂到全局最優(yōu)，但是對于表3中的函數(shù)Quadric和Ackley而言，在一定迭代次數(shù)內(nèi)未能收斂到全局最優(yōu)，這與算法的位置更新公式有關。具體地，算法中小雞的位置更新公式中，小雞只向自己的媽媽學習，并沒有向小雞所在子群中的公雞學習，因而就無法獲取整個子群中公雞的位置信息，算法會陷入局部最優(yōu)。為提高算法的收斂效率，需要對小雞的位置更新公式進行改進。

5 結論

1) 在雞群算法的基礎上，描述了雞的狀態(tài)空間和雞群狀態(tài)空間，通過定義雞群狀態(tài)轉移序列建立了Markov鏈數(shù)學分析模型，分析了該Markov鏈的性質，指出它是有限齊次Markov鏈，分析了雞群狀態(tài)序列最終轉移狀態(tài)，結合隨機搜索算法的收斂準則，驗證了雞群算法的全局收斂性。

2) 通過雞群算法與2種經(jīng)典的智能算法在解決15個復雜函數(shù)尋優(yōu)問題中的比較，實驗結果顯示雞群算法對不同特征的復雜函數(shù)都具有較好的魯棒性和全局收斂性能，可有效避免早熟收斂問題，可為大量非線性多峰值的工程問題求解提供新的思路和解決方法。下一步將對雞群算法進行更深入的理論研究，如利用鞅序列理論對算法的收斂性進行進一步研究，設計改進雞群算法并將其用于求解復雜的工程應用問 題等。

[1] BEHESHTI Z, SHAMSUDDIN S M H. A review of population-based meta-heuristic algorithms[J]. International Journal of Advances in Soft Computing & Its Applications, 2013, 5(1): 1?35.

[2] PETEGHEM V V, VANHOUCKEAB M. A genetic algorithm for the preemptive and non-preemptive multi-mode resource- constrained project scheduling problem[J]. European Journal of Operational Research, 2010, 201(2): 409?418.

[3] 鄭金華, 呂卉, 伍軍, 等. 基于空間交配遺傳算法的收斂性分析[J]. 模式識別與人工智能, 2010, 23(2): 639?645. ZHENG Jinhua, LV Hui, WU Jun, et al. Convergence analysis of genetic algorithm based on spaceMating[J]. PR&AI, 2010, 23(2): 639?645.

[4] KENNEDY J, EBERHART R. Particle swarm optimization[C]// Proceedings of IEEE International Conference on Neural Networks. Piscataway: IEEE Press, 1995: 1942?1948.

[5] TAVAKKOLI MOGHADDAM R, AZARKISH M, SADEGHNEJAD BARKOUSARAIE A. A new hybrid multi-objective Pareto archive PSO algorithm for a bi-objective job shop scheduling problem[J]. Expert Systems with Applications, 2010, 38(9): 10812?10821.

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

[7] SUN Bo, WANG Hui, FANG Yadong. Application of ant colony algorithm in discrete job shop scheduling[C]//Proceedings of the 2nd International Symposium on Knowledge Acquisition and Modeling (KAM). Wuhan, 2009: 29?31.

[8] XU Chunfan, DUAN Haibin. Artificial bee colony (ABC) optimized edge potential function (EPF) approach to target1558 recognition for low-altitude aircraft[J]. Pattern Recognition Letters, 2010, 31(13): 1759?1772.

[9] ZHU Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166?3173.

[10] OMKAR S N, SENTHILNATH J, KHANDELWAL R, et al. Artificial bee colony (ABC) for multi-objective design optimization of composite structures[J]. Applied Soft Computing, 2011, 11(1): 489?499.

[11] KARABOGA D, OZTURK C. A novel clustering approach:artificial bee colony(ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1): 652?657.

[12] HORNG M H. Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation[J]. Expert Systems with Applications, 2011, 38(11): 13785?13791.

[13] LI Xiaolei, SHAO Zhijiang, QIAN Jixin. An optimizing method based on autonomous animats: Fish-swarm algorithm[J]. Systems Engineering Theory & Practice, 2002, 22(11): 32?38.

[14] 吳虎勝, 張鳳鳴, 吳廬山. 一種新的群體智能算法—狼群算法[J]. 系統(tǒng)工程與電子技術, 2013, 35(11): 2430?2438. WU Husheng, ZHANG Fengming, WU Lushan. New swarm intelligence algorithm-wolf pack algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430?2438.

[15] YANG Xinshe. Bat algorithm: literature review and applications[J]. International Journal of Bio-Inspired Computation, 2013, 5(3): 141?149.

[16] MENG Xianbing, LIU Yu, GAO Xianzhi, et al. A new bio-inspired algorithm: chicken swarm optimization[C]//5th International Conference on Swarm Intelligence. Hefei: Springer International Publishing, 2014: 74?85.

[17] 孔飛, 吳定會. 一種改進的雞群算法[J]. 江南大學學報(自然科學版), 2015, 14(6): 681?688. KONG Fei, WU Dinghui. An improved chicken swarm optimization algrorithm[J]. Journal of Jiangnan University (Natural Science Edition), 2015, 14(6): 681?688.

[18] GIDAS B. Nonstationary Markov chains and convergence of the annealing algorithm[J]. Journal of Statistical Physics, 1985, 39(1/2): 73?131.

[19] 任子暉, 王堅, 高岳林. 馬爾科夫鏈的粒子群優(yōu)化算法全局收斂性分析[J]. 控制理論與應用, 2011, 28(4): 462?466. REN Zihui, WANG Jian, GAO Yuelin. The global convergence analysis of particle swarm optimization algorithm based on Markov chain[J]. Control Theory & Applications, 2011, 28(4): 462?466.

[20] 蘇兆品, 蔣建國, 梁昌勇, 等. 蟻群算法的幾乎處處強收斂性分析[J]. 電子學報, 2009, 37(8): 1646?1650. SU Zhaoping, JIANG Jianguo, LIANG Changyong, et al. An almost everywhere strong convergence proof for a class of ant colony algorithm[J]. Acta Electronica Sinica, 2009, 37(8): 1646?1650.

[21] 寧愛平, 張雪英. 人工蜂群算法的收斂性分析[J]. 控制與決策, 2013, 28(10): 1554?1558. NING Aiping, ZHANG Xueying. Convergence analysis of artificial bee colony algorithm[J]. Control and Decision, 2013, 28(10): 1554?1558.

[22] 李寧. 粒子群優(yōu)化算法的理論分析與應用研究[D]. 武漢: 華中科技大學控制科學與工程系, 2006: 42?70. LI Ning. Analysis and application of particle swarm optimization[D]. Wuhan: Huazhong University of Science and Technology. Department of Automatic Control, 2006: 42?70.

[23] 錢偉民, 梁漢營, 楊國慶. 應用隨機過程[M]. 北京: 高等教育出版社, 2014: 60?70. QIAN Weimin, LIANG Hanying, YANG Guoqing. Applied stochastic processes[M]. Beijing: Higher Education Press, 2014: 60?70.

[24] SOLIS F J, WETS J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19?30.

[25] 張文修, 梁怡. 遺傳算法的數(shù)學基礎[M]. 西安: 西安交通大學出版社, 2003: 67?87.ZHANG Wenxiu, LIANG Yi. Mathematical foundation of genetic algorithm[M]. Xi’an: Xi’an Jiaotong University Press, 2003: 67?87.

(編輯 陳愛華)

Convergence analysis of chicken swarm optimization algorithm

WU Dinghui, KONG Fei, JI Zhicheng

(Key Laboratory of Advanced Process Control for Light Industry,Ministry of Education, Jiangnan University, Wuxi 214122, China)

The Markov chain model for chicken swarm optimization (CSO) was established, and the properties of the model were analyzed, which proved that chicken swarm state sequence was a finite homogeneous Markov chain. According to the convergence criteria of stochastic search algorithm, chicken swarm optimization was demonstrated to meet the two convergence criteria, so that the global convergence was ensured. Finally, 15 benchmark functions were used to test the CSO algorithm, and the comparison with particle swarm optimization (PSO) and bat algorithm (BA) was also performed. The simulation results show that CSO outperforms other algorithms in terms of global convergence and computational robustness, and it is particularly suitable for solving high-dimension and multimodal function optimization problems.

chicken swarm optimization; Markov chain; state transition; global convergence; benchmark functions

10.11817/j.issn.1672?7207.2017.08.018

TP301.6

A

1672?7207(2017)08?2105?08

2016?11?25；

2017?03?04

國家自然科學基金資助項目(61572237，61573167)；江蘇省“六大人才高峰”項目(WLW-008)(Projects(61572237, 61573167) supported by the National Natural Science Foundation of China; Project (WLW-008) supported by Jiangsu Six Talents Peak-Funded Projects)

吳定會，博士，副教授，從事風力發(fā)電、智能調度技術研究；E-mail：wdh123@jiangnan.edu.cn