文章快速检索 高级检索

Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation
CHEN Jie, SHEN Yanxia , LU Xin
Research Center of Engineering Applications for IOT, Jiangnan University, Wuxi 214122, China
Abstract: The artificial bee colony (ABC) algorithm converges slowly and easily gets stuck on local solutions; hence, an ABC algorithm based on information feedback and an improved fitness value evaluation is proposed. The algorithm first introduces a memory mechanism for individual components to feedback information to enhance its capacity for population exploitation and to accelerate the convergence speed. Then, it adopts a new fitness function to increase the difference between individuals and to avoid premature convergence from failing to identify the best individual. Finally, the algorithm integrates an optimal nectar-source guidance mechanism into the knockout function to prevent the production of unexpected individuals. Experiments were conducted on standard functions and were compared with those with several typical improved ABCs. The results show that the improved algorithm accelerates the convergence rate and improves the solution accuracy.
Key words: artificial bee colony algorithm     swarm intelligence     evolutionary algorithm     function optimization     information feedback

1 人工蜂群算法

ABC算法是通过种群协作工作来完成寻优过程的优化算法，在ABC算法中，蜂群被分为引领蜂、跟随蜂和侦查蜂3类以协同工作。假设对于一个优化问题，其最优解在D维空间，采用ABC算法对其寻优，主要过程如下：

1)初始化种群。设置种群数量为N,其中引领蜂和跟随蜂各占一半,即N/2；设置最大迭代次数和最大不更新淘汰次数；随机产生N/2个D维的初始解{x1,x2,…,xN/2}，其中xi={xi1,xi2,…,xiD}，i=1,2,…,N/2，并对初始解(蜜源)进行适应度评价。随机产生初始解的公式为

 xij=L+rand(0,1)×(U-L) (1)

2)种群更新。引领蜂随机选择相邻蜜源并与其产生一个新的蜜源，比较二者蜜源质量，择优保留；跟随蜂根据由引领蜂蜜源质量信息转化的概率来选择是否对该蜜源进行邻域搜索并更新。引领蜂和跟随蜂的蜜源更新公式为

 vnj=xij+R×(xij-xkj) (2)

3)概率选择。跟随蜂根据一定概率决定是否选择对引领蜂蜜源进行邻域搜索，概率信息计算公式为

 ${P_i} = \frac{{{F_i}}}{{\sum\limits_{i = 1}^{N/2} {{F_i}} }}$ (3)

 ${F_i} = \left\{ \begin{array}{l} \frac{1}{{1 + {\rm{fi}}{{\rm{t}}_i}}},{\rm{fi}}{{\rm{t}}_i} \ge 0\\ 1 + \left| {{\rm{fi}}{{\rm{t}}_i}} \right|,{\rm{fi}}{{\rm{t}}_i} < 0 \end{array} \right.$ (4)

4)种群淘汰。如果某个解经过一定次数的更新后，其解的质量仍未得到改善，一般认为该解陷入局部最优，此时，引领蜂将转化为侦查蜂，由式(1)重新产生一个新的解。

2 改进的人工蜂群算法 2.1 基于信息反馈的种群更新

 xpq=xkq+φ×(xqbest-xkq) (5)

2.2 基于对数的适应度函数

 $\left\{ \matrix{ {\rm{fi}}{{\rm{t}}_1} = 1 \times {10^{ - 20}}\buildrel {{f_4}} \over \longrightarrow {F_1} \approx 1\buildrel {{f_3}} \over \longrightarrow {P_1} = 0.33 \hfill \cr {\rm{fi}}{{\rm{t}}_2} = 1 \times {10^{ - 50}}\buildrel {{f_4}} \over \longrightarrow {F_2} \approx 1\buildrel {{f_3}} \over \longrightarrow {P_2} = 0.33 \hfill \cr {\rm{fi}}{{\rm{t}}_3} = 1 \times {10^{ - 100}}\buildrel {{f_4}} \over \longrightarrow {F_3} \approx 1\buildrel {{f_3}} \over \longrightarrow {P_3} = 0.33 \hfill \cr} \right.$ (6)

 ${F_i} = \frac{{0.1}}{{0.1 + \frac{1}{{\left| {{\rm{lgfi}}{{\rm{t}}_i}} \right|}}}},0 \le {\rm{fi}}{{\rm{t}}_i} \le {10^{ - \alpha }}$ (7)

 $\left\{ \matrix{ {\rm{fi}}{{\rm{t}}_1} = 1 \times {10^{ - 20}}\buildrel {{f_7}} \over \longrightarrow {F_1} \approx 0.67\buildrel {{f_3}} \over \longrightarrow {P_1} = 0.27 \hfill \cr {\rm{fi}}{{\rm{t}}_2} = 1 \times {10^{ - 50}}\buildrel {{f_7}} \over \longrightarrow {F_2} \approx 0.83\buildrel {{f_3}} \over \longrightarrow {P_2} = 0.35 \hfill \cr {\rm{fi}}{{\rm{t}}_3} = 1 \times {10^{ - 100}}\buildrel {{f_7}} \over \longrightarrow {F_3} \approx 0.91\buildrel {{f_3}} \over \longrightarrow {P_3} = 0.38 \hfill \cr} \right.$ (8)

2.3 基于最优引导的淘汰更新函数

 xnm=xmbest+φ×(xmbest-xlm) (9)

 图 1 改进后算法流程图Fig. 1 The flow diagram of improved algorithm
3 仿真结果与分析

 Function 函数 公式 搜索范围 最优值 f1 Sphere f(x)=$\sum\limits_{i = 1}^n {X_i^2}$ [-100,100] 0 f2 Schwefel2.22 f(x)=$\sum\limits_{i = 1}^n {\left| {{x_i}} \right| + \prod\limits_{i = 1}^n {\left| {{x_i}} \right|} }$ [-10,100] 0 f3 Schwefel2.21 f(x)=maxi=1n|xi| [-100,100] 0 f4 Rosenbrock f(x)=$\sum\limits_{i = 1}^{n - 1} {\left[ {100{{\left( {{x_{i + 1}} - x_i^2} \right)}^2} + {{\left( {1 - {x_i}} \right)}^2}} \right]}$ [-30,30] 0 f5 Step f(x)=$\sum\limits_{i = 1}^n {{{\left( {\left\lfloor {{x_i} + 0.5} \right\rfloor } \right)}^2}}$ [-100,100] 0 f6 Quartic f(x)=$\sum\limits_{i = 1}^n {ix_i^4 + {\rm{random}}\left[ {0,1} \right)}$ ［-1.28,1.28] 0 f7 Schwefel2.26 f(x)=$- \sum\limits_{i = 1}^n {\left( {{x_i}\sin \sqrt {\left| {{x_i}} \right|} } \right)}$ [-500,500] -418.98n f8 Rastrigin f(x)=$\sum\limits_{i = 1}^n {\left[ {x_i^2 - 10\cos \left( {2\pi {x_i}} \right) + 10} \right]}$ [-5.12,5.12] 0 f9 Ackley f(x)=$- 20\exp \left( { - 0.2\sqrt {\sum\limits_{i = 1}^n {x_i^2/n} } } \right) - \exp \left( {\sum\limits_{i = 1}^n {\cos \left( {2\pi {x_i}} \right)/n} } \right) + 20 + e$ [-32,32] 0 f10 Griewank f(x)=${1 \over {4000}}\sum\limits_{i = 1}^n {x_i^2} - \prod\limits_{i = 1}^n {\cos \left( {{{{x_i}} \over {\sqrt i }}} \right) + 1}$ [-600,600] 0

 图 2 MMABC和ABC对部分测试函数收敛曲线Fig. 2 Some convergence curves of testing functions between MMABC and ABC

 Function Dimensions Algorithm Best Worst Mean Std f1 50 100 ABC MMABC ABC MMABC 8.91×10-16 0 2.09×10-15 0 1.13×10-15 0 2.55×10-15 0 9.62×10-16 0 2.33×10-15 0 8.52×10-17 0 1.68×10-16 0 f2 50 100 ABC MMABC ABC MMABC 2.28×10-15 7.95×10-255 4.99×10-15 8.59×10-254 2.52×10-15 9.85×10-253 5.42×10-15 6.57×10-252 2.42×10-15 2.12×10-253 5.19×10-15 1.64×10-252 1.01×10-17 7.95×10-255 1.37×10-16 2.51×10-253 f3 50 100 ABC MMABC ABC MMABC 2.85×10-2 1.35×10-16 1.14×101 1.46×10-7 1.39×10-1 2.22×10-15 1.33×101 5.42×10-7 6.58×10-2 8.89×10-16 1.21×101 2.46×10-7 4.12×10-2 7.32×10-16 6.64×10-1 1.49×10-7 f4 50 100 ABC MMABC ABC MMABC 1.71×10-3 3.01×10-4 7.82×10-2 9.28×10-3 9.23×10-2 1.88×10-2 2.77×10-1 1.16×10-2 6.31×10-3 2.57×10-3 9.94×10-2 1.13×10-2 3.48×10-2 7.84×10-3 1.02×10-1 3.23×10-3 f5 50 100 ABC MMABC ABC MMABC 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 f6 50 100 ABC MMABC ABC MMABC 7.61×10-2 2.91×10-2 2.61×10-1 1.12×10-1 9.22×10-2 3.93×10-2 3.67×10-1 1.43×10-1 9.89×10-2 3.56×10-2 3.26×10-1 1.31×10-1 8.5×10-3 3.72×10-3 3.61×10-2 1.05×10-2 f7 50 100 ABC MMABC ABC MMABC -2.094 75×104 -2.094 91×104 -4.189 79×104 -4.189 83×104 -2.071 16×104 -2.094 91×104 -4.166 14×104 -4.189 83×104 -2.081 97×104 -2.094 91×104 -4.179 95×104 -4.189 83×104 7.57×101 3.98×10-12 8.46×101 2.64×10-3 f8 50 100 ABC MMABC ABC MMABC 0 0 1.14×10-13 0 5.68×10-14 0 2.27×10-13 0 4.55×10-14 0 1.18×10-13 0 2.27×10-14 0 5.57×10-14 0 f9 50 100 ABC MMABC ABC MMABC 1.04×10-13 1.63×10-16 1.46×10-13 2.33×10-16 1.47×10-13 4.44×10-16 1.61×10-13 8.87×10-16 1.35×10-13 3.25×10-16 1.55×10-13 5.78×10-16 1.59×10-14 2.35×10-17 5.32×10-15 1.42×10-17 f10 50 100 ABC MMABC ABC MMABC 1.11×10-16 0 1.44×10-15 0 5.54×10-16 0 1.56×10-13 0 1.99×10-16 0 3.27×10-14 0 1.78×10-16 0 6.14×10-14 0

 Function Iter ABC MABC IABC LRABC MMABC f1 1×105 Mean Std 4.73×10-16 4.38×10-17 0 0 0 0 0 0 0 0 f2 1×105 Mean Std 1.17×10-15 2.53×10-17 0 0 0 0 0 0 0 0 f3 1×104 Mean Std 6.71×10-3 8.37×10-4 1.43×10-2 5.48×10-3 3.08×10-5 3.16×10-5 3.07×10-4 3.11×10-4 5.16×10-6 2.65×10-6 f4 1×105 Mean Std 3.11×10-1 3.23×10-1 1.18×10-1 1.26×10-2 1.76×10-2 2.16×10-2 1.71×10-2 1.65×10-2 2.89×10-3 5.73×10-3 f5 1×103 Mean Std 0 0 0 0 0 0 0 0 0 0 f6 1×104 Mean Std 2.51×10-2 3.87×10-2 3.36×10-2 8.08×10-3 1.05×10-2 2.59×10-3 5.98×10-4 2.88×10-4 4.41×10-3 1.23×10-3 f7 3×103 Mean Std -12 569.5 1.03×10-4 -12 569.5 1.63×10-12 -12 569.5 1.15×10-12 -12 569.5 8.13×10-13 -12 569.5 3.68×10-13 f8 3×103 Mean Std 3.41×10-14 2.78×10-14 0 0 0 0 0 0 0 0 f9 3×103 Mean Std 9.45×10-14 8.26×10-15 3.92×10-14 5.22×10-15 3.14×10-14 2.84×10-15 2.31×10-15 1.74×10-15 1.45×10-14 1.02×10-15 f10 3×103 Mean Std 4.44×10-17 5.43×10-17 0 0 0 0 0 0 0 0

 图 3 5种算法对部分函数测试对比曲线Fig. 3 Some comparison curves of testing functions between five algorithms

4 结束语

 [1] KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied soft computing, 2008, 8(1): 687-697. [2] 秦全德, 程适, 李丽, 等. 人工蜂群算法研究综述[J]. 智能系统学报, 2014, 9(2): 127-135. QIN Quande, CHENG Shi, LI Li, et al. Artificial bee colony algorithm: a survey[J]. CAAI transactions on intelligent systems, 2014, 9(2): 127-135. [3] 温长吉, 王生生, 于合龙, 等. 基于改进蜂群算法优化神经网络的玉米病害图像分割[J]. 农业工程学报, 2013, 29(13): 142-149. WEN Changji, WANG Shengsheng, YU Helong, et al. Image segmentation method for maize diseases based on pulse coupled neural network with modified artificial bee algorithm[J]. Transactions of the Chinese society of agricultural engineering, 2013, 29(13): 142-149. [4] OZTURK C, KARABOGA D. Hybrid artificial bee colony algorithm for neural network training[C]//Proceedings of IEEE Congress on Evolutionary Computation. New Orleans, LA: IEEE, 2011: 84-88. [5] ZHANG Rui, SONG Shiji, WU Cheng. A hybrid artificial bee colony algorithm for the job shop scheduling problem[J]. International journal of production economics, 2013, 141(1): 167-178. [6] ZHANG Shuzhu, LEE C K M, CHOY K L, et al. Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem[J]. Transportation research part D, 2014, 31: 85-89. [7] ADARYANI M R, KARAMI A. Artificial bee colony algorithm for solving multi-objective optimal power flow problem[J]. International journal of electrical power & energy systems, 2013, 53: 219-230. [8] 匡芳君, 徐蔚鸿, 金忠. 自适应Tent混沌搜索的人工蜂群算法[J]. 控制理论与应用, 2014, 31(11): 1502-1509. KUANG Fangjun, XU Weihong, JIN Zhong. Artificial bee colony algorithm based on self-adaptive Tent chaos search[J]. Control theory & applications, 2014, 31(11): 1502-1509. [9] ALIZADEGAN A, ASADY B, AHMADPOUR M. Two modified versions of artificial bee colony algorithm[J]. Applied mathematics and computation, 2013, 225: 601-609. [10] LIAO Xiang, ZHOU Jianzhong, OUYANG Shuo, et al. An adaptive chaotic artificial bee colony algorithm for short-term hydrothermal generation scheduling[J]. International journal of electrical power & energy systems, 2013, 53: 34-42. [11] GAO Weifeng, LIU Sanyang, HUANG Lingling. Enhancing artificial bee colony algorithm using more information-based search equations[J]. Information sciences, 2014, 270: 112-133. [12] 李国亮, 魏振华, 徐蕾. 分阶段搜索的改进人工蜂群算法[J]. 计算机应用, 2015, 35(4): 1057-1061. LI Guoliang, WEI Zhenhua, XU Lei. Improved artificial bee colony algorithm using phased search[J]. Journal of computer applications, 2015, 35(4): 1057-1061. [13] BABAYIGIT B, OZDEMIR R. A modified artificial bee colony algorithm for numerical function optimization[C]//Proceedings of IEEE Symposium on Computers and Communications. Cappadocia: IEEE, 2012: 245-249. [14] GAO Weifeng, LIU Sanyang. A modified artificial bee colony algorithm[J]. Computers & operations research, 2012, 39(3): 687-697. [15] 高卫峰, 刘三阳, 黄玲玲. 受启发的人工蜂群算法在全局优化问题中的应用[J]. 电子学报, 2012, 40(12): 2396-2403. GAO Weifeng, LIU Sanyang, HUANG Lingling. Inspired artificial bee colony algorithm for global optimization problem[J]. Acta electronica sinica, 2012, 40(12): 2396-2403. [16] 刘三阳, 张平, 朱明敏. 基于局部搜索的人工蜂群算法[J]. 控制与决策, 2014, 29(1): 123-128. LIU Sanyang, ZHANG Ping, ZHU Mingmin. Artificial bee colony algorithm based on local search[J]. Control and decision, 2014, 29(1): 123-128.
DOI: 10.11992/tis.201506024

0

#### 文章信息

CHEN Jie, SHEN Yanxia, LU Xin

Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation

CAAI Transactions on Intelligent Systems, 2016, 11(02): 172-179.
DOI: 10.11992/tis.201506024