人工蜂群算法简介

本文翻译自：http://www.scholarpedia.org/article/Artificial_bee_colony_algorithm   根据本人的理解而与原文稍有出入。转载请注明：本文原发自CSDN FashionXu的博客。

前言

人工蜂群算法（Artifical Bee Colony）是一种元启发式智能算法，由Karaboga in 2005在2005年引入，用来求解数值优化问题。它受启发于蜜蜂的觅食行为。这种算法主要基于 Tereshko 和Loengarov (2005) 提出的蜂群觅食行为模型。这个模型包含了三种核心元素：雇佣蜂（employed bees），非雇佣蜂（unemployed bees）和食物源（food sources）。前两者负责搜寻蜂巢附近的富源（rich food sources）。这种模型也定义了两种指引模式：富源会反馈会积极信号，从而引导更多的蜜蜂来采蜜；贫源（poor food sources）会反馈消极信号，会导致放弃这个食物源。这两种行为是自组织的和群智能的。

在ABC中，把待求解的问题的解看做是人工食物，食物越充足（rich），表示解的质量越好，然后一群人工蜜蜂会去搜寻富源，从而找到一个相关问题的比较好的解。为了应用ABC，待求解的问题首先要转化为最优化问题，也就是找到一组参数向量，使得目标函数最小化。人工蜂群就会随机初始化一些解，然后通过迭代，使用邻居搜索的策略来向更好的解靠近，并放弃差的解，逐步提高解的质量。

全局优化问题

一个全局优化问题可以定义为寻找参数向量

，使得目标函数

最小化，如下式所示：

              (1)

这个函数会带有如下的等式和/或不等式约束：

                    (2)

subject to:

for 

                  (3)

for 

                 (4)

定义了一个

上的n维的搜索空间S。变量取值范围被限定在起上下限中，如式(2)所示。这也是一个带约束的优化问题。如果

且

，则变为一个无约束优化问题。

人工蜂群元启发式算法

在ABC中，人工蜂群由三种蜜蜂组成：雇佣蜂(employed bees)同特定的食物源相关联；观察蜂(onlooker bees)观察蜂巢内雇佣蜂的舞蹈以决定选择某个食物源；侦察蜂(scout bees)会随机的搜索食物。侦察蜂和观察蜂又叫做未雇佣蜂。算法初始的时候，所有的食物源会被侦察蜂搜索到，然后，食物源会被雇佣蜂和观察蜂所开发利用。持续性的开发利用会使得食物源很快被消耗尽，于是消耗尽食物源的雇佣蜂会转变成为侦察蜂。在ABC中，食物源的位置代表了问题的一个可行解，食物源处的蜂蜜的数量代表了相关问题解的质量。雇佣蜂的数量等于食物源的数量，因为每只雇佣蜂会关联到一个且仅一个食物源。

通用ABC算法框架如下所示：

初始化时期； Repeat 雇佣蜂时期； 观察蜂时期； 侦察蜂时期； 记录找到的最好解； Util (达到最大循环次数或者达到cpu时间)

初始化时期

利用侦察蜂初始化所有代表食物源的向量

，

，SN是种群的大小，设定控制参数。由于每个食物源

都是待优化问题的解向量，因此每个

都含有n个变量

。这些向量将要被优化，从而使得目标函数最小化。可以利用下式进行初始化：

                       (5)

其中

和

是参数

取值的上下限。

雇佣蜂时期

雇佣蜂会依据其记忆中的食物源的位置进行邻居搜索，找食物源附近的更好的食物源。当雇佣蜂找到一个食物源之后，会评估其适应值。此处，它们可以采用下述公式来确定邻居食物源：

                     (6)

其中

是一个随机选择的食物源，i是随机选择的一个位置索引，

是一个[-a,a]之间的一个随机数。当产生新的食物源之后，会计算出它的适应值，并且在

和

之间应用贪心法做出选择。

解的适应值，可以通过下式转化为最小化问题来求解：

                (7)

其中

是待解问题的目标函数值。

观察蜂时期

非雇佣蜂由两部分群体组成：观察蜂和侦察蜂。雇佣蜂会向在蜂巢中等待的观察蜂来分享它们获得的食物源信息。观察蜂会根据这些信息进行一种随机的选择。为此，需要一种基于适应值的选择方法，比如轮盘赌。

被选中的概率

可以用下述表达式计算：

                           (8)

当食物源

被一只观察蜂选中后，利用(6)式产生邻居食物源

，再计算其适应值。在雇佣蜂时期，在

和

之间用贪心法来做出选择。因此，更多的观察蜂会选择富源并反馈回积极信号。

侦察蜂时期

未雇佣蜂随机搜索食物源，称为侦察蜂。如果雇佣蜂通过实现给定的尝试次数之后，仍然未能提高解的质量，则雇佣蜂就变成为侦察蜂，其拥有的解就会被放弃。（尝试次数是由ABC使用者事先给定的，称为“limit”或者“放弃阈值”（abandonment criteria））转换后的侦察蜂开始随机搜索新的解，比如，如果

被放弃了，那么原来拥有

的雇佣蜂就会利用(5)式来产生新的解。因此那些随机产生的贫源或者近期形成的贫源就会被放弃，产生消极的信号，以来平衡积极的信号。

ABC算法总结起来，有以下几点：

1)      根据蜜蜂的觅食行为而得到；

2)      是全局优化算法；

3)      为了数值优化而设计；

4)      也可以用来求解组合优化问题；

5)      可以用于有约束的和无约束的优化问题；

6)      只使用了三个参数（种群数量，最大循环次数以及阈值），这些参数是用户事先确定的；

7)      非常的简单，具有柔性和鲁棒性。

ABC的应用

一种非约束优化问题：训练神经网络求解XOR问题

(后面内容略)

References

Chong, C. S., Sivakumar, A. I., Malcolm Low, Y. H., Gay, K. L. (2006). A bee colony optimization algorithm to job shop scheduling. In Proceedings of the 38th conference on Winter simulation WSC '06, pages 1954-1961, California.

Deb, K. (2000). An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186(2- 4):311–338, Elsevier, Netherlands.

Domínguez, O. C. (2009), An adaptation of the scout bee behavior in the Artificial Bee Colony algorithm to solve constrained optimization problems, Laboratorio Nacional de Informática Avanzada (LANIA), MsC, Thesis, Supervisor: Efrén Mezura-Montes.

Drias, H. S. S., Yahi, S. (2005). Cooperative bees swarm for solving the maximum weighted satisfiability problem. In Computational Intelligence and Bioinspired Systems, volume 3512/2005 of LNCS: 318 – 325, Springer, Berlin.

Goldberg, D.E. (1989), Genetic algorithms in search, optimization and machine learning, Addison-Wesley Professional, ISBN: 0201157675.

Kang, F., Li, J., Xu, Q. (2009), Structural inverse analysis by hybrid simplex artificial bee colony algorithms, Computers & Structures, 87 (13:14), 861-870, Elsevier, Netherlands.

Karaboga, D, (2005). An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

Karaboga D., Basturk B. (2007), Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems, Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing, , volume 4529/2007 of LNCS: 789-798, Springer, Berlin.

Karaboga, D., Basturk, B., Ozturk, C. (2007), Artificial bee colony (ABC) optimization algorithm for training feed-forward neural networks, Modeling Decisions for Artificial Intelligence, volume 4617/2007 of LNCS: 318-319, Springer, Berlin.

Karaboga, D., Akay,B. (2009), A Comparative Study of Artificial Bee Colony Algorithm, Applied Mathematics and Computation, 214, 108-132, Elsevier, Netherlands.

Karaboga, D., Ozturk, C. (2009),Neural Networks Training by Artificial Bee Colony Algorithm on Pattern Classification, Neural Network World, 19 (3), 279-292, Institute of Computer Science AS CR, v. v. i., Czech Republic.

Karaboga, D., Ozturk, C. (2010), A novel clustering approach: Artificial Bee Colony (ABC) algorithm, Applied Soft Computing, Elsevier, Netherlands, In Press.

Karaboga, N. (2009), A new design method based on artificial bee colony algorithm for digital IIR filters, Journal of Franklin Institute, 346 (4): 328-348, Elsevier, Netherlands.

Kennedy, J., Eberhart, R.C. (1995), Particle Swarm Optimization, In Proceedings of 1995 IEEE International Conference on Neural Networks, 4: 1942–1948, Perth, Western Australia.

Lucic, P. and Teodorovic, D. (2001). Bee system: Modeling combinatorial optimization transportation engineering problems by swarm intelligence. In Preprints of the Tristan IV Triennial Symposium on Transportation Analysis, pages: 441-445, SaoMiguel, Azores Islands, Portugal.

Mezura-Montes, E., Coello Coello, C. (2005), Useful infeasible solutions in engineering optimization with evolutionary algorithms. Advances in Artificial Intelligence, volume 3789/2005 of LNCS: 652–662, Springer, Berlin.

Omkar, S.N., Senthilnath, J. , Khandelwal, R., Narayana Naik, G., Gopalakrishnan, S. (2010), Artificial Bee Colony (ABC) for multi-objective design optimization of composite structures, Applied Soft Computing, Elsevier, Netherlands, In Press.

Pan, Q-K. Tasgetiren, M. F., Suganthan; P. N., T. Chua, J. (2010), A Discrete Artificial Bee Colony Algorithm for the Lot-streaming Flow Shop Scheduling Problem, Information Sciences, Elsevier, Netherlands, In Press.

Pham, D. T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., Zaidi, M. (2005). The bees algorithm. Technical report, Manufacturing Engineering Centre, Cardiff University, UK.

Quijano, N. and Passino, K. (2007). Honey bee social foraging algorithms for resource allocation, part i: Algorithm and theory, In Proceedings of American Control Conference, 2007. ACC '07, pages 3383-3388, New York.

Rao, R. S., Narasimham, S.V.L., Ramalingaraju, M., Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm, International Journal of Electrical Power and Energy Systems Engineering (IJEPESE) , 1 (2) :708-714, World Academy of Science, Engineering and Technology.

Singh, A. (2009), An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem, Applied Soft Computing, 9 (2), 625-631, Elsevier, Netherlands.

Tereshko, V., Loengarov, A. (2005), Collective decision-making in honey bee foraging dynamics, Computing and Information Systems, 9 (3): 1-7, University of the West of Scotland, UK.

Teodorovic, D., Dell, M. O. (2005). Bee colony optimization - a cooperative learning approach to complex transportation problems, In Proceedings of 10th EWGT Meeting and 16th Mini EURO Conference, pages: 51- 60.

Vries, H., Biesmeijer J.C. (1998), Modelling collective foraging by means of individual behaviour rules in honey-bees, Behavioral Ecology and Sociobiology , 44: 109-124, Springer, Berlin.

Wedde, H., Farooq, M. (2005). The wisdom of the hive applied to mobile ad-hoc networks. In Proceedings of the Swarm Intelligence Symposium 2005, pages: 341-348, Pasadena, California.

Xu, C., Duan, H. (2010), Artificial bee colony (ABC) optimized edge potential function (EPF) approach to target recognition for low-altitude aircraft, Pattern Recognition Letters, Elsevier, Netherlands, In Press.

Yang, X. S. (2005). Engineering optimizations via nature-inspired virtual bee algorithms. In Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, volume 3562/2005 of LNCS: 317-323, Springer, Berlin.

Internal references

• Marco Dorigo (2007) Ant colony optimization. Scholarpedia, 2(3):1461.

• Howard Eichenbaum (2008) Memory. Scholarpedia, 3(3):1747.

• Marco Dorigo, Marco A. Montes de Oca, Andries Engelbrecht (2008) Particle swarm optimization. Scholarpedia, 3(11):1486.

• Hermann Haken (2008) Self-organization. Scholarpedia, 3(8):1401.

• Marco Dorigo and Mauro Birattari (2007) Swarm intelligence. Scholarpedia, 2(9):1462.