自適應(yīng)混合文化蜂群算法求解連續(xù)空間優(yōu)化問題

張 強，李盼池，王 梅

?

自適應(yīng)混合文化蜂群算法求解連續(xù)空間優(yōu)化問題

張 強，李盼池，王 梅

(東北石油大學(xué)計算機與信息技術(shù)學(xué)院 黑龍江大慶 163318

提出一種自適應(yīng)混合文化蜂群算法求解連續(xù)空間優(yōu)化問題。算法中群體空間采用最優(yōu)覓食理論改進群體更新方式；信念空間通過云模型算法和最優(yōu)排序差分變異策略對知識進行更新；利用混沌算法和反向?qū)W習算法進化外部空間；3種空間通過自適應(yīng)的影響操作來實現(xiàn)知識的交換。典型復(fù)雜函數(shù)測試表明，該算法具有很好的收斂精度和計算速度，特別適宜于多峰值函數(shù)尋優(yōu)。

蜂群算法; 文化算法; 云模型; 連續(xù)空間優(yōu)化

人工蜂群算法(ABC)是文獻[1]為解決函數(shù)優(yōu)化問題而提出的。其原理是模擬蜜蜂的采蜜機制，通過不同分工的蜂群間相互協(xié)作完成進化搜索工作，具有操作簡單、設(shè)置參數(shù)少、收斂速度更快、收斂精度更高的優(yōu)點，已逐步應(yīng)用到智能優(yōu)化、模式識別、工業(yè)控制、圖像識別、神經(jīng)網(wǎng)絡(luò)優(yōu)化和聚類分析等[2-8]領(lǐng)域。

文化作為存儲知識的載體在生物群體中不斷的傳遞和繼承，對種群進化的加速作用比單純依靠基因遺傳快，可以很好地指導(dǎo)生物個體行為[9]。多數(shù)學(xué)者研究進化算法主要集中在生物進化選擇機理方面，本文將文化算法思想[10]嵌入到ABC中，提出一種自適應(yīng)混合文化蜂群算法(AMC-ABC)。首先，整個蜜蜂種群個體采用佳點集理論產(chǎn)生；其次，將蜜蜂種群分為群體空間、信念空間和外部空間，并引入云模型理論、差分變異策略和反向混沌理論改進3個空間內(nèi)個體的進化方式；最后，通過影響函數(shù)完成整個群體知識的存儲和傳播。

1 人工蜂群算法基本原理

ABC算法將蜂群分為3類：引領(lǐng)蜂、跟隨蜂和偵察蜂，本文以求解最小化問題為例簡要闡述其具體尋優(yōu)過程。

1.1 種群初始化

1.2 引領(lǐng)蜂進化方式

(3)

1.3 跟隨蜂進化方式

1.4 偵察蜂進化方式

為了避免在迭代進化后期喪失種群的多樣性，ABC將經(jīng)過連續(xù)代進化適應(yīng)度不變的個體轉(zhuǎn)換成偵察蜂，并按式(1)重新產(chǎn)生新個體。通過引領(lǐng)蜂種群、跟隨蜂種群及偵察蜂的進化搜索，經(jīng)過反復(fù)循環(huán)尋優(yōu)直到算法迭代到最大迭代次數(shù)或種群的最優(yōu)解達到預(yù)定誤差精度時算法結(jié)束。

2 自適應(yīng)混合文化蜂群算法原理

從計算模型的角度出發(fā)，符合文化算法要求的進化算法都可以嵌入文化算法框架。本文將引領(lǐng)蜂、跟隨蜂和偵察蜂劃分為信念空間、群體空間和外部空間，3個空間通過自有的改進進化方式完成空間內(nèi)個體的進化，利用影響函數(shù)實現(xiàn)空間之間各類知識的傳播和繼承，進而加速算法尋優(yōu)速率，提升算法尋優(yōu)性能及解決問題的適應(yīng)性。

2.1 基于佳點集理論的個體初始化

進化算法中種群初始化大多采用隨機方式生成，若生成的個體分布在最優(yōu)解周圍，則算法快速收斂到最優(yōu)解的概率將加大。在未知最優(yōu)解所在位置的情況下，若要加速算法收斂、改善尋優(yōu)性能，就需要讓初始化的種群盡可能均勻分布在整個解空間。佳點集理論[11]表明：近似計算函數(shù)在維歐氏空間單位立方體上的積分時，采用個佳點得到的加權(quán)和比任何其他個點獲得的誤差都小。文獻[12-13]將其應(yīng)用到種群的初始化，取得了很好的尋優(yōu)效果，定義如下：

2.2 信念空間的進化方式

蜂群算法中的引領(lǐng)蜂是群體空間中最優(yōu)子集，因此將其作為信念空間中的個體。經(jīng)典ABC中引領(lǐng)蜂進化方式是任意選擇一個個體與某個體進行交叉操作，這種方式可能存在兩個個體互為選擇進化的情況，也可能會出現(xiàn)同一個個體與多個個體交叉進化的情況。雖然存在一個隨機因子會保證新生個體的多樣性，但是這些個體的進化方向卻相對穩(wěn)定，對收斂速度會造成影響。同時每次迭代過程中最優(yōu)個體都會找一個不如它的個體進行交叉，雖然存在能找到比其更優(yōu)個體的可能性，但其操作的本質(zhì)是進行局部尋優(yōu)。所以有必要對引領(lǐng)蜂的進化方式進行兩種改進。

2.2.1 信念空間內(nèi)最優(yōu)個體的進化方式

社會學(xué)原理指出在優(yōu)秀個體周圍較易發(fā)現(xiàn)更優(yōu)個體，即局部最優(yōu)值周圍往往存在更優(yōu)值。云模型在知識表達時具有不確定中帶有確定性、穩(wěn)定之中又有變化的特點, 體現(xiàn)了自然界物種進化的基本原理[14-16]。本文采用正態(tài)云模型算法完成最優(yōu)個體的進化行為。將最優(yōu)個體作為期望()表示搜索中心；用當代適應(yīng)度方差作為熵()來動態(tài)改變尋優(yōu)搜索范圍；用超熵()控制云滴的離散度，初期加大算法的隨機性，后期加強算法的穩(wěn)定性，設(shè)置，產(chǎn)生與空間內(nèi)個體數(shù)量相同的一組云滴，如果新個體較優(yōu)則替換。

2.2.2 信念空間內(nèi)非最優(yōu)個體的進化方式

差分進化算法是文獻[17]為求解切比雪夫多項式擬合問題而提出的一種采用浮點矢量編碼在連續(xù)空間中進行隨機搜索的優(yōu)化算法，具有原理簡單、受控參數(shù)少的優(yōu)勢，采用最優(yōu)排序差分變異策略[18-19]作為非最優(yōu)個體的進化規(guī)則為：

式中，隨機選擇互不相同且不同于該更新個體的兩個個體，然后對適應(yīng)度進行排序，選擇3個個體最優(yōu)的個體作為，較優(yōu)個體作為，最差個體作為；為比例縮放因子。如果適應(yīng)度相差很小，說明兩個個體在空間中相隔很近，應(yīng)取較大值，以防止擾動量過??；如果適應(yīng)度相差很大，說明兩個個體在空間相隔很遠，應(yīng)取較小值，以限制擾動量過大。下面給出一種確定方式：

(6)

2.3 群體空間的進化方式

用跟隨蜂組成群體空間，ABC的進化機理使其在求解高維連續(xù)優(yōu)化問題時效果不夠理想。主要是因為跟隨蜂種群的搜索方式是擇優(yōu)選擇個體進行貪婪搜索，雖然有利于加速收斂速度，卻也增加了在解決高維優(yōu)化問題時易陷入局部最優(yōu)的概率。自然界中蜜蜂在采蜜過程中多數(shù)是以較少的移動來獲取更多的蜜源，這也符合最優(yōu)覓食理論：為獲得較優(yōu)的覓食效果，生物更趨向在覓食過程中以更低的能效耗費來獲得更多的食物[20-21]。蜜蜂間的能效吸引力為：

(8)

2.4 外部空間的進化方式

外部空間由偵察蜂構(gòu)成，反向?qū)W習理論可以使算法獲取較好的收斂速率和優(yōu)化性能[22]?；煦缬成涫股傻膫€體呈現(xiàn)遍歷性、隨機性和多樣性，可有效地在收斂區(qū)域以外空間搜索全局最優(yōu)位置[23-24]。采取階Chebyshev混沌映射完成個體變異，按式(9)計算適應(yīng)度，取最優(yōu)個體更新偵察蜂：

2.5 影響函數(shù)的設(shè)計

2.6 算法流程

1) 初始化算法的相關(guān)參數(shù)，并采用佳點集理論產(chǎn)生種群個體；2) 計算種群個體的適應(yīng)度，將種群分為信念空間、群體空間和外部空間；3) 按照2.2節(jié)的進化方式進化信念空間中的個體，按照2.3節(jié)進化群體空間中的個體，按照2.4節(jié)進化外部空間中的個體；4) 計算個體適應(yīng)度，滿足結(jié)束條件則退出，否則執(zhí)行流程5)；5) 利用影響函數(shù)完成3種空間知識的傳遞；6) 轉(zhuǎn)到流程3)，直到滿足終止條件。

3 實驗仿真

為驗證本文算法性能，以8個函數(shù)極值優(yōu)化為例，與標準粒子群算法(PSO)、經(jīng)典遺傳算法(GA)、蛙跳算法(SFLA)和經(jīng)典蜂群算法(ABC)的尋優(yōu)性能進行對比。5種算法的種群個體均設(shè)置為100，最大進化次數(shù)均設(shè)置為4 000，尋優(yōu)精度均設(shè)置為1010-10，各測試函數(shù)獨立運行20次；PSO運行參數(shù)：慣性因子0.729 8，自身因子1.496 18，全局因子1.496 18；GA運行參數(shù)：交叉概率，變異概率；SFLA運行參數(shù)：分為10個子群，每個子群10個青蛙，子群內(nèi)部迭代次數(shù)為20次；ABC算法的，比較5種算法的最優(yōu)結(jié)果、最差結(jié)果、平均結(jié)果、平均運行時間和方差。其中，最優(yōu)結(jié)果、最差結(jié)果反映解的質(zhì)量，平均結(jié)果顯示算法所能達到的精度，平均時間反映算法的收斂速度，方差反映算法的穩(wěn)定性和魯棒性。

該函數(shù)是二維的復(fù)雜函數(shù)，具有無數(shù)個極小值點，最小值0。

該函數(shù)存在許多局部極小點，全局最小值0。

該函數(shù)全局最小值0。

該函數(shù)有一個全局最小值0。

該函數(shù)存在許多局部極小點，全局最小值0。

該函數(shù)有一個全局最小值0。

該函數(shù)存在許多局部極小點，數(shù)目與問題的維數(shù)有關(guān)，全局最小值0。

該函數(shù)是個多峰值的函數(shù)，全局最小值0。

表1 f1運行仿真結(jié)果對比

表2 f2運行仿真結(jié)果對比

表3 f3運行仿真結(jié)果對比

表4 f4運行仿真結(jié)果對比

表5 f5運行仿真結(jié)果對比

表6 f6運行仿真結(jié)果對比

表7 f7運行仿真結(jié)果對比

表8 f8運行仿真結(jié)果對比

從表1～表8的運行結(jié)果可知，AMC-ABC的求解精度和速度都要優(yōu)于其他4種算法。從以下兩方面進行分析：

1) 對比最優(yōu)結(jié)果、最差結(jié)果、平均結(jié)果可知，AMC-ABC的求解性能最好。①因為蜜蜂種群采用佳點集理論進行初始化，增加了蜜蜂個體快速定位到最優(yōu)解的概率；②信念空間采用的云模型算法有益于最優(yōu)個體向其附近更優(yōu)值進行自適應(yīng)定位，同時云模型的隨機性又保持了蜜蜂個體的多樣性，進而起到提高尋優(yōu)性能和速率的作用；③由反向理論和混沌理論產(chǎn)生的個體變異，有利于算法在尋優(yōu)后期增加個體多樣性，可有效地在收斂區(qū)域以外空間搜索全局最優(yōu)位置，進而改善算法在求解一些高維優(yōu)化函數(shù)收斂速率慢、易早熟等問題。2) 對比運行時間和方差可知，AMC-ABC的性能要優(yōu)于其他進化算法，分析其原因是：SFLA和ABC的進化方式較PSO和GA的簡單，且調(diào)整參數(shù)少，同時它們利用小生鏡的方式進行尋優(yōu)，速度相對快一些。SFLA在分組內(nèi)迭代一定次數(shù)后再重新分組，在一定程度上與ABC的經(jīng)過次迭代后變成偵查蜂相似，所以二者的性能較相似。而AMC-ABC在進化過程中采用云模型和最優(yōu)排序差分變異策略使得個體更新時既保持了隨機性，又使得個體變化帶有確定性，與經(jīng)典算法的隨機方式相比更易向最優(yōu)解方向靠近。而基于最優(yōu)覓食理論的群體空間更新機制有利于避免算法參數(shù)試算，雖然在每次迭代進化過程中增加了計算量，但通過迭代次數(shù)可以看出，其收斂的速度確實得到很大提高，使得運行時間較短。同時仿真結(jié)果表明AMC-ABC對高維多峰函數(shù)的求解具有很好的適應(yīng)性。

4 結(jié)束語

本文將文化算法思想嵌入到人工蜂群算法中，將引領(lǐng)蜂、跟隨蜂和偵察蜂劃分為信念空間、群體 空間和外部空間，利用佳點集、云模型和混沌算法等理論改進3種空間中個體的進化行為，既發(fā)揮了蜂群算法原有進化算子的優(yōu)勢，又改進了算法的不足。3個子群空間通過影響函數(shù)來完成個體間知識的交換，仿真實例結(jié)果表明所提算法具有很好的尋優(yōu)速率和效率，同時對其他進化算法的改進具有一定的借鑒意義。

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Erciyes: Erciyes Univ Press, 2005.

[2] KARABOGA D, OZTURK C. Neural networks training by artificialbee colony algorithm on pattern classification[J]. Neural Network World, 2009, 19(3): 279-292.

[3] KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute-Engineering and Applied Mathematics, 2009, 346(4): 328-348.

[4] COBANLI S, OZTURK A, GUVENC U, et al. Active power loss minimization in electric power systems through artificial bee colony algorithm[J]. International Review of Electrical Engineering-Free, 2010, 5(5): 2217-2223.

[5] MA M, LIANG J H, GUO M, et al. SAR image segmentation based on artificial bee colony algorithm[J]. Applied Soft Computing, 2011, 11(8): 5205-5214.

[6] JI J Z, WEI H K, LIU C N. An artificial bee colony algorithm for learning Bayesian networks[J]. Soft Computing, 2013, 17(6): 983-994.

[7] YAN X H, ZHU Y L, ZOU W P, et al. A new approach for data clustering using hybrid artificial bee colony algorithm[J]. Neuro Computing, 2012, 97: 241-250.

[8] GARG H. Solving structural engineering design optimization problems using artificial bee colony algorithm[J]. Journal of Industrial and Management Optimization, 2014, 10(3): 777-794.

[9] REYNOLDS R G. An introduction to culturalalgorithms[C]// Proc of the 3rd Annual Conference on Evolutionary Programming. San Diego, River Edge, NJ, USA: World Scientific Publishing Co Inc, 1994: 131-139.

[10] 郭一楠, 陳美蓉, 王春. 文化算法的收斂性分析[J]. 控制與決策, 2013, 28(9): 1361-1364.

GUO Yi-nan, CHEN Mei-rong, WANG Chun. Analysis on the convergence of cultural algorithm[J]. Control and Decision, 2013, 28(9): 1361-1364.

[11] 華羅庚, 王元. 數(shù)論在近代分析中的應(yīng)用[M]. 北京: 科學(xué)出版社, 1978: 1-99.

HUA Luo-geng, WANG Yuan. The application of number theory in modern analysis. [M]. Beijing: Science Press, 1978: 1-99.

[12] 劉香品, 宣士斌, 劉峰. 引入佳點集和猴群翻過程的人工蜂群算法[J]. 模式識別與人工智能, 2015, 28(1): 80-89.

LIU Xiang-pin, XUAN Shi-bin, LIU Feng. Artificial bee colony algorithm with good point set and turn process of monkey algorithm[J]. Pattern Recognition and Artificial Intelligence, 2015, 28(1): 80-89.

[13] 畢曉君, 張磊. 基于混合策略的雙種群約束優(yōu)化算法[J].控制與決策, 2015, 30(4): 715-720.

BI Xiao-jun, ZHANG Lei. Dual population constrained optimization algorithm with hybird strategy[J]. Control and Decision, 2015, 30(4): 715-720.

[14] 付斌, 李道國, 王慕快. 云模型研究的回顧與展望[J]. 計算機應(yīng)用研究, 2011, 28(2): 420-426.

FU Bin, LI Dao-guo, WANG Mu-kuai. Review and prospect on research of cloud model[J]. Application Research of Computers, 2011, 28(2): 420-426.

[15] 張光衛(wèi), 何銳, 劉禹, 等. 基于云模型的進化算法[J]. 計算機學(xué)報, 2008, 31(7): 1082-1090.

ZHANG Guang-wei, HE Rui, LIU Yu, et al. An evolutionary algorithm based on cloud model[J]. Chinese Journal of Computers, 2008, 31(7): 1082-1090.

[16] 張英杰, 邵歲鋒, NIYONGABO J. 一種基于云模型的云變異粒子群算法[J]. 模式識別與人工智能, 2011, 24(1): 90-94.

ZHANG Ying-jie, SHAO Sui-feng, NIYONGABO J. Cloud hypermutation particle swarm optim ization algorithm based on cloudmodel[J]. Pattern Recognition and Artificial Intelligence, 2011, 24(1): 90-94.

[17] RAINER S, PRICE K. Differential evolution- a simple and efficient heuristic for global optimization over continuous spaces[J]. J of Global Optimization, 1997, 11(4): 341-359.

[18] KAELO P, ALI M M. A numerical study of some modified differential evolution algorithms[J]. European Journal of Operational Research, 2006, 169(3): 1176-1184.

[19] WU L H, WANG Y N, ZHOU S W. Self-adapting control parameters modified differential evolution for trajectory planning manipulator[J]. J of Control Theory and Applications, 2007, 5(4): 365-374.

[20] 孫儒泳. 動物生態(tài)學(xué)原理[M]. 3版. 北京: 北京師范大學(xué)出版社, 2001.

Sun Ru-yong. Principles of 3nimal ecology[M]. 3rd ed. Beijing: Beijing Normal University Press, 2001.

[21] 崔志華, 曾建潮. 微粒群優(yōu)化算法[M]. 北京: 科學(xué)出版社, 2011.

CUI Zhi-hua, ZENG Jian-chao. Particle swarm optimization[M]. Beijing: Science Press, 2011.

[22] 王燕. 反向粒子群算法理論及及其應(yīng)用研究[D]. 西安: 西安工程大學(xué), 2011.

WANG Yan. The research of opposition-based particle swarm optimization and its application[D]. Xi'an: Xian Polytechnic University, 2011.

[23] 胥小波, 鄭康鋒, 李丹. 新的混沌粒子群優(yōu)化算法[J]. 通信學(xué)報, 2012, 33(1): 24-37.

XU Xiao-bo, ZHENG Kang-feng, LI Dan. New chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012, 33(1): 24-37.

[24] 劉金梅, 屈強. 幾類混沌序列的隨機性測試[J]. 計算機工程與應(yīng)用, 2011, 47(5): 46-49.

LIU Jin-mei, QU Qiang. Randomness tests of several chaotic sequences[J]. Computer Engineering and Applications, 2011, 47(5): 46-49.

編 輯 漆 蓉

Adaptive Mixed Culture Artificial Bee Colony Algorithm for Continuous Space Optimization Problems

ZHANG Qiang, LI Pan-chi, and WANG Mei

(School of Computer and Information Technology，Northeast Petroleum University Daqing Heilongjiang 163318)

An adaptive mixed culture artificial bee colony algorithm (AMC-ABC) is proposed to solve continuous space optimization problem. In the algorithm, community space is evolved by the improved group update way with optimal foraging theory; the knowledge of belief space is updated by the cloud model algorithm and optimal sorting differential mutation strategy; the outer space is evolved by chaos algorithm and opposition-based learning algorithm; and the knowledge exchange of three kinds of spatial is realized by adaptive acceptance operation and effect of operation. Simulation results of the typical complex functions show that the algorithm has fine the convergence precision and computing speed, particularly suitable for optimization the multimodal function.

artificial bee colony algorithm (ABC)；cultural algorithm；cloud model；continuous space optimization

TP312

A

10.3969/j.issn.1001-0548.2017.02.017

2015-12-30；

2016-03-04

國家自然科學(xué)基金(61170132)；黑龍江省自然科學(xué)基金(F2015020)；黑龍江省教育廳項目(12541086)

張強(1982-)，男，博士，副教授，主要從事智能進化算法、神經(jīng)網(wǎng)絡(luò)方面的研究.