The Bees Algorithm – A Novel Tool for Complex Optimisation Problems

D.T. Pham, A. Ghanbarzadeh, E. Koccedil;, S. Otri , S. Rahim , M. Zaidi

Manufacturing Engineering Centre, Cardiff University, Cardiff CF24 3AA, UK

Abstract

A new population-based search algorithm called the Bees Algorithm (BA) is resented. The algorithm mimics the food foraging behaviour of swarms of honey bees. In its basic version, the algorithm performs a kind of neighbourhood search combined with random search and can be used for both combinatorial optimisation and functional optimisation. This paper focuses on the latter. Following a description of the algorithm, the paper gives the results obtained for a number of benchmark problems demonstrating the efficiency and robustness of the new algorithm.

Keywords: Bees Algorithm, Function Optimisation, Swarm Intelligence

1. Introduction

Many complex multi-variable optimisation problems cannot be solved exactly within polynomially bounded computation times. This generates much interest in search algorithms that find near-optimal solutions in reasonable running times. The swarm-based algorithm described in this paper is a search algorithm capable of locating good solutions efficiently. The algorithm is inspired by the food foraging behaviour of honey bees and could be regarded as belonging to the category of “intelligent” optimisation tools [1].

Section 2 reviews related work in the area of intelligent optimisation. Section 3 describes the foraging behaviour of natural bees and the core ideas of the proposed Bees Algorithm. Section 4 details the benchmarking problems used to test the efficiency and robustness of the algorithm and presents the results obtained. These show that the algorithm can reliably handle complex multi-model optimisation problems without being trapped at local solutions.

1. Intelligent swarm-based optimisation

Swarm-based optimisation algorithms (SOAs) mimic naturersquo;s methods to drive a search towards the optimal solution. A key difference between SOAs and direct search algorithms such as hill climbing and random walk is that SOAs use a population of solutions for every iteration instead of a single solution. As a population of solutions is processed in an iteration, the outcome of each iteration is also a population of solutions. If an optimisation problem has a single optimum, SOA population members can be expected to converge to that optimum solution. However, if an optimisation problem has multiple optimal solutions, an SOA can be used to capture them in its final population. SOAs include the Ant Colony Optimisation (ACO) algorithm [2], the Genetic Algorithm (GA) [3] and the Particle Swarm Optimisation (PSO) algorithm [4].

Common to all population-based search methods is a strategy that generates variations of the solution being sought. Some search methods use a greedy criterion to decide which generated solution to retain. Such a criterion would mean accepting a new solution if and only if it increases the value of the objective function (assuming the given optimisation problem is one of optimisation). A very successful non-greedy population-based algorithm is the ACO algorithm which emulates the behaviour of real ants. Ants are capable of finding the shortest path from the food source to their nest using a chemical substance called pheromone to guide their search. The pheromone is deposited on the ground as the ants move and the probability that a passing stray ant will follow this trail depends on the quantity of pheromone laid. ACO was first used for functional optimisation by Bilchev [5] and further attempts were reported in [5, 6].

The Genetic Algorithm is based on natural selection and genetic recombination. The algorithm works by choosing solutions from the current population and then applying genetic operators – such as mutation and crossover – to create a new population. The algorithm efficiently exploits historical information to speculate on new search areas with improved performance [3]. When applied to optimisation problems, the GA has the advantage of performing global search. The GA may be hybridised with domain-dependent heuristics for improved results. For example, Mathur et al [6] describe a hybrid of the ACO algorithm and the GA for continuous function optimisation.

Particle Swarm Optimisation (PSO) is an optimisation procedure based on the social behaviour of groups of organisations, for example the flocking of birds or the schooling of fish [4]. Individual solutions in a population are viewed as “particles” that evolve or change their positions with time. Each particle modifies its position in search space according to its own experience and also that of a neighbouring particle by remembering the best position visited by itself and its neighbours, thus combining local and global search methods [4].

There are other SOAs with names suggestive of possibly bee-inspired operations [7-10]. However, as far as the authors are aware, those algorithms do not closely follow the behaviour of bees. In particular, they do not seem to implement the techniques that bees employ when foraging for food.

1. The Bees Algorithm
   1. Bees in nature

A colony of honey bees can extend itself over long distances (more than 10 km) and in multiple directions simultaneously to exploit a large number of food sources [7,8]. A colony prospers by deploying its foragers to good fields. In principle, flower patches with plentiful amounts of nectar or pollen that can be collected with less effort should be visited by more bees, whereas patches with less nectar or pollen should receive fewer bees [9,10].

The foraging process begins in a colony by scout bees being sent to search for promising flower patches. Scout bees move rand

全文共27372字，剩余内容已隐藏，支付完成后下载完整资料

---

蜜蜂算法 - 复杂优化问题的新工具

D.T. Pham, A. Ghanbarzadeh, E. Koccedil;, S. Otri , S. Rahim , M. Zaidi

卡迪夫大学大学制造工程中心，英国卡迪夫市CF24 3AA，

摘要：

一种新的基于人群的搜索算法叫做蜜蜂算法（BA）。该算法模拟了蜜蜂群的食物觅食行为。 在其最初版本中，算法执行一种与随机搜索相结合的邻域搜索，可用于组合优化和功能优化。本文重点介绍后者，在对算法进行了描述之后，本文给出了一些基准问题的结果，证明了新算法的效率和鲁棒性。

关键词：蜜蜂算法，功能优化，群智能

1介绍

许多复杂的多变量优化问题无法在多边形有限计算时间内精确地求解。在合理的运行时间内找到近似最优解，是搜索算法中比较重要的研究课题。本文中描述的基于群体的算法是一种能够有效地定位好解决方案的搜索算法。该算法灵感来源于蜜蜂的食物觅食行为，可以被认为属于“智能”优化工具类。

第2节审查了智能优化领域的相关工作。第3节描述了自然蜂的觅食行为和所提出的蜜蜂算法的核心思想。第4节详细说明了用于测试算法的效率和鲁棒性的基准测试问题，并提供了所获得的结果。这表明该算法可以可靠地处理复杂的多模型优化问题，而不会被困在本地解决方案中。

2智能群优化

基于群优化算法（SOA）模拟自然的方法来推动搜索到最优解。SOA和直接搜索算法（如爬坡和随机游走）之间的关键区别在于，SOA针对每一次迭代使用大量解决方案，而不是单个解决方案。 随着一系列解决方案的处理，每次迭代的结果也是一个解决方案。 如果一个优化问题具有单一的优化，则可以预期SOA人口成员可以收敛到最优解。 然而，如果优化问题具有多个最优解，则SOA可用于在最终人群中捕获它们。SOA包括蚁群优化（ACO）算法[2]，遗传算法（GA）[3]和粒子群优化（PSO）算法。

所有基于人群的搜索方法的共同之处在于产生寻求解决方案的变体的策略。 一些搜索方法使用贪婪标准来决定要保留哪个生成的解决方案。当且仅当增加目标函数的值（假定给定的优化问题是优化之一）时，这样的标准将意味着接受新的解决方案。 非常成功的非贪心人群算法是模拟真实蚂蚁行为的ACO算法。 蚂蚁能够使用称为信息素的化学物质找到从食物来源到巢穴的最短路径，以引导他们的搜索。信息素随着蚂蚁的移动而沉积在地面上，并且通过的流浪蚂蚁跟随这条路线的可能性取决于铺设的信息素的数量。蚁群算法首先用于Bilchev在[5]中提出的功能优化，并在[5,6]中报道了进一步的尝试。

遗传算法基于自然选择和遗传重组。该算法通过从当前人口中选择解决方案，然后应用遗传算子（如突变和交叉）来创建新的群体。该算法有效地利用历史信息推测新的搜索区域，具有改进的性能[3]。当应用于优化问题时，遗传算法具有执行全局搜索的优点。 遗传算法可能与其他群优化算法进行相关启发式杂交，以获得改进的结果。例如，Mathur等人在[6]中描述了ACO算法和GA的连续函数优化的混合。

粒子群优化（PSO）算法是基于组织群体的社会行为的优化过程，例如[4]中提到的鸟类群集或鱼类学习方式。人口中的个人解决方案被视为随着时间演变或改变其位置的“粒子”，每个粒子根据自己的经验和相邻粒子的位置，通过记住自身及其邻居访问的最佳位置修改其在搜索空间中的位置，从而结合局部和全局进行搜索的方法[4]。

还有其他的群优化算法的名称暗示可能是蜜蜂启发的操作，比如[7-10]中提到的。然而，就作者所知，这些算法并没有密切关注蜜蜂的行为，特别是，它们似乎没有采用蜜蜂在觅食时所采用的技术。

3 蜜蜂算法

3.1 自然界的蜜蜂

蜜蜂的采蜜范围可以在长距离（超过10公里）和多个方向上同时延伸，以获取大量的食物来源[7,8]。蜂群通过将采蜜蜂部署到良好的花田来繁荣蜜场。原则上，花蜜或花粉较多的花田会更容易吸引大量的蜜蜂来收集花蜜或花粉，而花蜜较少或花粉少的花田则很少有蜜蜂造访[9,10]。

觅食过程开始于一个蜂群，被派出的侦察蜂寻找有希望的花地位置。侦察蜂从一个花地随机移动到另一个。在收获季节，一个蜂群会继续探索，保持一部分蜜蜂作为侦察蜂[8]。

当它们返回蜂巢时，那些发现花地的侦察蜂被评定为高于某一质量阈值（以某些成分的组合（如依据糖含量来测定））存放其花蜜或花粉，并进入“舞池”开始跳称为“摇摆舞”的舞蹈[7]。

这个神秘的舞蹈对于蜂群交流至关重要，并且舞蹈中包含有关花地的三条信息：花地将被发现的方向，花地与蜂巢的距离及其质量评价（或适应度）[7,10]。 这些信息有助于蜂群将蜜蜂精确地送达花地，而无需使用指南或地图。每个人对外部环境的了解仅仅是从摇摆舞中获取的。这种舞蹈使蜂群根据其提供的食物的质量和收获所需能量的量来评估不同花地的相对优点[10]。舞池跳舞后，舞者（即侦察蜂）带着蜂巢内的跟随蜂回到发现花地的位置。更多的跟随蜂被送到更有前途的花地。这样可以让蜂群快速有效地收集食物。

蜜蜂从花地中收获时，会监测其食物的水平。这对他们返回蜂巢时决定下一次跳动的舞蹈是必要的。如果花地仍然足够好，可以用来作为食物来源，那么它会在摇摆舞中被宣传，更多的蜜蜂将被招募到该来源。

3.2 拟蜜蜂算法

如上所述，蜜蜂算法是一种优化算法，灵感来源于蜜蜂的自然觅食行为，用来寻找最优解[4]。图1以最简单的形式显示了算法的伪代码。该算法需要设置多个参数，即：侦察蜂数（n），n个访问站点中选择的站点数（m），选择站点中的最佳站点数（e），招募最佳e站点的蜜蜂数（nep），为另一个（m-e）选定站点招募的蜜蜂数量（nsp），包括站点及其邻域和停止标准的花地初始大小（ngh）。 该算法首先将n个侦察蜜蜂随机放置在搜索空间中。在第2步中会对由侦察蜂访问过的站点的适应度进行评估。

1.初始化人口随机解。

2.评估人群的适合度。

3.循环（停止不符合标准）形成新的种群

4.选择邻域搜索的站点。

5.为选定的地点（更多的蜜蜂获取最佳e站点）

招募蜜蜂并评估适合度。

6.从每个花地中选择适合的蜜蜂。

7.分配剩余的蜜蜂来随机搜索并评估其适合度。

8.结束。

图1 基本蜜蜂算法的伪代码

在步骤4中，将具有最高适合度的蜜蜂选为“选中的蜜蜂”，并且选择由它们访问的站点进行邻域搜索。然后，在步骤5和6中，算法在所选择的站点附近进行搜索，分配更多的蜜蜂以在最佳e站点附近进行搜索。蜜蜂可以根据与他们正在访问的站点相关的适合度直接选择。或者，使用适合度值来确定蜜蜂被选择的概率。通过招募更多的蜜蜂来比较其他选择的蜜蜂，通过招募更多的蜜蜂来更详细地描绘代表更有希望的解决方案的最佳e站点附近的搜索。与侦察一样，这种差异招聘是蜜蜂算法的关键操作。

然而，在步骤6中，对于每个花地，仅选择具有最高适应度的蜜蜂以形成下一个蜜蜂群体。实际上，没有这样的限制。这里介绍了这个限制，是用来减少要探索的点数。在步骤7中，群体中剩余的蜜蜂随机搜索搜索空间，以搜索新的潜在解决方案。重复这些步骤，直到达到停止标准。在每次迭代结束时，蜜蜂将拥有两个新的群体 – 从每个选定的花地和其他侦察蜂的代表中分配进行随机搜索。

4 实验

显然，如上所述的蜜蜂算法适用于组合和功能优化问题。在本文中，将演示用于功能优化。组合优化问题的解决方案仅在于变换界定邻域的方法。

使用两个标准的功能优化问题来测试蜜蜂算法，并建立其参数的正确值，另外8个用于对该算法进行基准测试。当蜜蜂算法搜索最大值时，在应用算法之前将要最小化的功能反转。

Shekel的Foxholes（图2），De Jong的测试套件中的一个2D功能被选为测试算法的第一个功能。

为此测试设置以下参数值：种群n = 45，所选择的位点数m = 3，精英位点数e = 1，初始花地大小ngh = 3，最佳站点周围的蜜蜂数nep = 7，围绕其他选定点的蜜蜂数nsp = 2。注意，ngh定义了邻居的初始大小，其中放置了跟随蜂。例如，如果x是第i个维度中精英蜜蜂的位置，则在优化过程开始时，随机蜜蜂将被随机地放置在该维度的区间xie plusmn; ngh中。随着优化的进行，搜索邻域的大小逐渐减小，以便于解决方案的微调。

Inverted Shekel#39;s Foxholes

125

115

105

95

85

75

65

55

45

35

25

0

500

1000

1500

2000

Visited Points ( Mean number of function evaluations )

图3 适合度的进化和被访问次数(基于Shekelrsquo;s Foxholes)

图3展示了作为所访问点数的函数获得的适合度值。结果来自100次独立运行的平均值。可以看出，在大约1200次访问之后，蜜蜂算法能够找到接近最优的解决方案。

为了测试该算法的可靠性，采用了具有六维的倒数Schwefel函数（方程式2）。 图4展示了突出其多模态的功能的二维视图。

图5显示了适合度值随着访问点数的变化而变化。结果来自100次独立运行的平均值。可以看出，在大约3,000,000次访问之后，蜜蜂算法能够找到接近最优的解决方案。

蜜蜂算法应用于八个基准函数[6]，结果与使用其他优化算法获得的结果进行了比较。测试功能及其最优性如表1所示。有关蜜蜂算法的其他结果和更详细的分析，请参见[1]。

表2给出了蜜蜂算法和确定性单纯形法（SIMPSA）[6]，随机模拟退火优化算法（NE SIMPSA）[6]，遗传算法（GA）[6]和蚁群系统（ANTS）[6]。

再次强调，所访问的点数是100次独立运行的平均值。表3显示了与不同测试功能一起使用的经验派生的蜜蜂算法参数值。

当获得的最大适合度与全局最优值之间的差值小于最佳值的0.1％时，或小于0.001时，优化停止，以较小者为准。在最佳值为0的情况下，如果最优值小于0.001，则解决方案被接受。

第一个测试功能是De Jong的，其中蜜蜂算法可以找到比蚁群系统快120倍的速度，比遗传算法快207倍，成功率为100％。 第二个功能是Goldstein和Price的，其中蜜蜂算法达到最佳速度比蚁群算法和遗传算法快5倍，再次获得100％的成功。 布兰林的功能与蚁群系统相比有15％的改善，与遗传算法相比有77％的改善，同时也取得了100％的成功。

功能5和6分别是Rosenbrock的两个和四个功能。在二维函数中，蜜蜂算法比其他方法提供了100％的成功和良好的改进（至少比其他方法少两倍的评估）。在四维情况下，蜜蜂算法需要更多的功能评估才能达到最佳效果，成功率100％。 NE SIMPSA可以找到最佳的功能评估减少10倍，但成功率仅为94％，ANTS发现最佳成功率为100％，比蜜蜂算法快3.5倍。测试功能7是六维的超球体模型。蜜蜂算法只需要与GA相比的功能评估数量的一半，ANTS所需的三分之一。第八个测试功能是十维功能。蜜蜂算法可以比GA快10倍，比ANTS快25倍，成功率100％。

5 总结

本文提出了一种新的优化算法。n维多模态函数的实验结果表明，该算法具有显着的鲁棒性，在所有情况下都能达到100％的成功率。该算法收敛到最大或最小，而不会被困在局部最优。该算法通常优于其他与优化速度和获得的结果精度相比较的技术。算法的一个缺点是使用的可调参数的数量。然而，可以通过进行少量试验来设置参数值。

其他优化算法通常采用梯度信息。然而，所提出的算法很少使用这种类型的信息，因此可以容易地从本地最优解决。进一步的工作应该是减少参数，并加入更好的学习机制。

致谢

本文描述的研究是作为目标1 SUPERMAN项目，EPSRC创新制造研究中心项目和EC FP6创新生产机器和系统（I * PROMS）卓越网络的一部分进行的。

使用人工蜂群算法和蜜蜂算法设计PID控制器

1. 人工蜂群算法

在人工蜂群算法中，有三群蜜蜂：旁观蜂，雇佣蜂和侦察蜂。一个蜂群由旁观蜂和雇佣蜂组成。 如果受雇的蜜蜂放弃食物来源，它将成为一名侦察蜂。问题的解决方案（人口）的数量等于围观蜜蜂或受孕蜜蜂的数量。通过食物来源的位置提出优化问题的可能解决方案，质量（适合度）用相关食物来源的花蜜量测量。食物来源的数量等于被雇佣的蜜蜂数量。

在算法的第一步，人工蜂群算法解决方案（食物来源位置）的初始种群P（G = 0）由ABC随机生成。 SN表示人口的大小。通过使用D维向量来呈现每个解xi（i = 1,2，...，SN）。这里，D表示优化参数的数量。在初始化之后，雇佣蜂、旁观蜂和侦察蜂反复搜索所有食物来源，直到达到预定次数的迭代（Cycle = 1,2，...，MCN）。受雇的蜜蜂首先根据本地信息（视觉信息）开始邻域搜索，并测试新来源（新解决方案）的花蜜量（适应度值），新源的适应度值如果比以前的适应度值更好，则替换前一个源，否则保持前一源。所有雇佣蜂的搜索过程完成

全文共7815字，剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[145813]，资料为PDF文档或Word文档，PDF文档可免费转换为Word