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
- 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.
- 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.
-
The Bees Algorithm
- 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，英国
摘要
一种新的基于人群的搜索算法叫做Bees算法（BA）。该算法模拟了蜜蜂群的食物觅食行为。在其基本版本中，算法执行一种与随机搜索相结合的邻域搜索，可用于组合优化和功能优化。本文重点介绍后者。在对算法进行了描述之后，本文给出了许多基准问题的结果，证明了新算法的效率和鲁棒性。
关键词：蜜蜂算法，功能优化，群体智能
1.简介
许多复杂的多变量优化问题无法在有界多边形计算时间内精确地求解。这个搜索算法中产生了很大的兴趣，在合理的运行时间内找到近似最优解。本文中描述的基于群体的算法是一种能够有效地定位好解决方案的搜索算法。该算法受蜂蜜食物觅食行为的启发，可以被认为属于“智能”优化工具[1]。
第2节介绍了智能优化领域的相关工作。第3节描述了自然蜂的觅食行为并所提出的蜂算法的核心思想。第4节详细说明了用于测试算法的效率和鲁棒性的基准测试问题，并提供了所获得的结果。这表明该算法可以可靠地处理复杂的多模型优化问题，而不会被困在本地解决方案中。
2.智能群优化
基于群优化算法（SOA）模拟自然的方法来推动搜索到最优解。 SOA和直接搜索算法（如爬坡和随机游走）之间的关键区别在于，SOA针对每一次迭代使用大量解决方案，而不是单个解决方案。随着一系列解决方案的处理，每次迭代的结果也是一个解决方案。如果一个优化问题具有单一的优化，则可以预期SOA人口成员可以收敛到最佳解决方案。然而，如果优化问题具有多个最优解，则SOA可用于在最终人群中捕获它们。 SOA包括蚁群优化（ACO）算法[2]，遗传算法（GA）[3]和粒子群优化（PSO）算法[4]。
所有基于人群的搜索方法的共同之处在于产生寻求解决方案的变体的策略。一些搜索方法使用贪婪标准来决定要保留哪个生成的解决方案。当且仅当增加目标函数的值（假定给定的优化问题是优化之一）时，这样的标准将意味着接受新的解决方案。非常成功的非贪心人群算法是模拟真实蚂蚁行为的ACO算法。蚂蚁能够使用称为信息素的化学物质找到从食物来源到巢穴的最短路径，以引导他们的搜索。信息素随着蚂蚁的移动而沉积在地面上，并且通过的流浪蚂蚁跟随这条路线的可能性取决于铺设的信息素的数量。 ACO首先用于Bilchev的功能优化[5]，并在[5,6]中报道了进一步的尝试。
遗传算法基于自然选择和遗传重组。该算法通过从当前人口中选择解决方案，然后应用遗传算子（如突变和交叉）来创建新的群体。该算法有效地利用历史信息推测新的搜索区域，具有改进的性能[3]。当应用于优化问题时，GA具有执行全局搜索的优点。 GA可能与域相关启发式杂交，以获得改进的结果。例如，Mathur等人描述了ACO算法和GA的连续函数优化的混合。
粒子群优化（PSO）是基于组织群体的社会行为的优化过程，例如鸟类群集或鱼类学习方式。人口中的个人解决方案被视为随着时间演变或改变其位置的“粒子”。每个粒子根据自己的经验和相邻粒子的位置，通过记住自身及其邻居访问的最佳位置修改其在搜索空间中的位置，从而结合局部和全局搜索方法[4]。
还有其他的SOA名称暗示可能是蜜蜂启发的操作[7-10]。然而，就作者所知，这些算法并没有密切关注蜜蜂的行为。特别是，他们似乎没有实施蜜蜂在觅食时所采用的技术。
3.蜜蜂算法
3.1蜜蜂在自然界
蜜蜂的殖民地可以在长距离（超过10公里）和多个方向上同时延伸，以利用大量的食物来源[7,8]。殖民地通过将牧师部署到良好的田地来繁荣。原则上，多花蜜可以用更少的蜜蜂来收集花蜜或花粉，花蜜要花更多的蜜蜂，而花蜜较少或花粉少的花粉则要少吃蜜蜂[9,10]。
觅食过程开始于一个殖民地，被派对的蜜蜂发送以寻找有希望的花卉补丁。 Scout蜜蜂从一个补丁随机移动到另一个补丁。在收获季节，一个殖民地继续探索，保持一部分人口作为侦察蜂[8]。
当他们返回蜂巢时，那些发现补丁的侦察蜜蜂被评定为高于某一质量阈值（以某些成分的组合（如糖含量测定））存放其花蜜或花粉，并进入“舞池”进行称为“摇摆舞”的舞蹈[7]。
这个神秘的舞蹈对于殖民地交流至关重要，并且包含有关花卉补丁的三条信息：它将被发现的方向，与蜂巢的距离及其质量评价（或适应度）[7,10]。这些信息有助于殖民地将蜜蜂精确地发送给花朵，而无需使用指南或地图。每个人对外部环境的了解仅仅是从摇摆舞中收集出来的。这种舞蹈使殖民地根据其提供的食物的质量和收获所需的能量量来评估不同补丁的相对优点[10]。舞池跳舞后，舞者（即侦察蜂）回到带有跟随蜂蜜在蜂巢内等待的花朵。更多的跟着蜜蜂被送到更有前途的补丁。这样可以让殖民地快速有效地收集食物。
蜜蜂从补丁中收获时，会监测其食物的水平。当他们返回蜂巢时，这是必要的。如果补丁仍然足够好，作为食物来源，那么它会在摇摆舞中被宣传，更多的蜜蜂将被招募到该来源。
3.2 拟蜜蜂算法
如上所述，蜜蜂算法是一种优化算法，灵感来源于蜜蜂的自然觅食行为，找到最优解[4]。图1以最简单的形式显示了算法的伪代码。该算法需要设置多个参数，即：侦察蜂数（n），n个访问站点中选择的站点数（m），选择站点中的最佳站点数（e），蜜蜂数招募最佳e站点（nep），为另一个（我）选定站点（nsp）招募的蜜蜂数量，包括站点及其邻域和停止标准的补丁初始大小（ngh）。该算法首先将n个侦察蜜蜂随机放置在搜索空间中。在第2步中评估由球探拜访的场地的适应度。
- 初始化人口随机解。
- 评估人群的适应度。
- 形成新的人口。
- 选择邻域搜索的网站。
- 为选定的地点（更多的蜜蜂获取最佳e站点）招募蜜蜂并评估健康。
- 从每个补丁中选择适合的蜜蜂。
- 分配剩余的蜜蜂来随机搜索并评估其适合度。
在步骤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个维度中精英蜜蜂的位置，则在优化过程开始时，随机蜜蜂将随机地放置在该维度的区间xiengh中。随着优化的进行，搜索邻域的大小逐渐减小，以便于解决方案的微调。
图3示出了作为所访问点数的函数获得的适合度值。结果是100次独立运行的平均值。可以看出，在大约1200次访问之后，蜜蜂算法能够找到接近最优的解决方案。
为了测试该算法的可靠性，采用了具有六维的倒数Schwefel函数（方程式2）。图4示出了突出其多模态的功能的二维视图。
为此测试设置以下参数值：种群n = 500，所选择的位点数m = 15，精英位点数e = 5，初始斑块大小ngh = 20，精英点周围的蜜蜂数nep = 50，数目蜜蜂周围其他选择的点nsp = 30
图5显示了适应度值随着访问点数的变化而变化。结果是100次独立运行的平均值。可以看出，在大约3,000,000次访问之后，蜜蜂算法能够找到接近最优的解决方案。
蜜蜂算法应用于八个基准函数[6]，结果与使用其他优化算法获得的结果进行了比较。测试功能及其最佳值如表1所示。有关蜂类算法的其他结果和更详细的分析，请参见。
表2给出了蜜蜂算法和确定性单纯形法（SIMPSA）[6]，随机模拟退火优化程序（NE SIMPSA），遗传算法（GA）[6]和Ant殖民地制度（ANTS）。
再次，所访问的点数是100次独立运行的平均值。表3显示了与不同测试功能一起使用的经验派生的蜜蜂算法参数值
当获得的最大适应度和全局最优值之间的差值小于最佳值的0.1％时，优化停止，或小于0.001，以较小者为准。在最佳值为0的情况下，如果最佳值小于0.001，则解决方案被接受。
第一个测试功能是De Jong，其中蜜蜂算法可以找到比ANTS快120倍的速度，比GA快207倍，成功率为100％。第二个功能是Goldstein和Price，其中蜜蜂算法达到最佳速度比ANTS和GA快5倍，再次获得100％的成功。布兰林的功能与ANTS相比有15％的改善，与GA相比有77％的改善，同时也取得了100％的成功。
功能5和6分别是Rosenbrock的两个和四个功能。在二维函数中，蜜蜂算法比其他方法提供了100％的成功和良好的改进（至少比其他方法少两倍的评估）。在四维情况下，蜜蜂算法需要更多的功能评估才能达到最佳效果，成功率100％。 NE SIMPSA可以找到最佳的功能评估减少10倍，但成功率仅为94％，ANTS发现最佳成功率为100％，比Bees算法快3.5倍。测试功能7是六维的超球体模型。蜜蜂算法需要与GA相比的功能评估数量的一半，ANTS所需的三分之一。第八个测试功能是十维功能。蜜蜂算法可以比GA快10倍，比ANTS快25倍，成功率100％。
5 结论
本文提出了一种新的优化算法。 n维多模态函数的实验结果表明，该算法具有显着的鲁棒性，在所有情况下都能达到100％的成功率。该算法收敛到最大或最小，而不会被困在局部最优。该算法通常优于其他与优化速度和获得的结果精度相比较的技术。算法的一个缺点是使用的可调参数的数量。然而，可以通过进行少量试验来设置参数值。
其他优化算法通常采用梯度信息。然而，所提出的算法很少使用这种类型的信息，因此可以容易地从本地最优解决。进一步的工作应该是减少参数，并加入更好的学习机制。
致谢
本文描述的研究是作为目标1 SUPERMAN项目，EPSRC创新制造研究中心项目和EC FP6创新生产机器和系统（I * PROMS）卓越网络的一部分进行的。
使用ABC和BA的PID控制器的设计
A.人造蜂群算法
在ABC算法中，有三群蜜蜂：旁观者，就业和侦察员。一个殖民地由旁观者蜜蜂和受雇的蜜蜂组成。如果受雇的蜜蜂放弃食物来源，它将成为一名侦察蜂。问题的解决方案（人口）的数量等于围观蜜蜂或受孕蜜蜂的数量。通过食物来源的位置提出优化问题的可能解决方案，质量（适合度）用相关食物来源的花蜜量测量。食物来源的数量等于就业的蜜蜂数量。
在算法的第一步，ABC解决方案（食物来源位置）的初始种群P（G = 0）由ABC随机生成。 SN表示人口的大小。通过使用D维向量来呈现每个解xi（i = 1,2，...，SN）。这里，D表示优化参数的数量。在初始化之后，采用蜜蜂，旁观者蜜蜂和侦察蜜蜂反复搜索所有食物来源，直到预定次数的迭代（Cycle = 1,2，...，MCN）。受雇的蜜蜂首先根据本地信息（视觉信息）开始邻域搜索，并测试新来源（新解决方案）的花蜜量（适应度值），新源的位置如果比以前的位置更好，则替换前一个位置，否则保持前一位置。所有受养蜜蜂完成搜索过程后，食物来源的花蜜信息及其位置信息与舞蹈区旁边的蜜蜂共享。围观蜜蜂评估从所有养蜂中获取的花蜜信息，然后通过使用与其花蜜量相关的选择概率来选择食物来源。
人工旁观蜂根据与该食物源相关联的选择概率值选择食物来源，pi由以下表达式[3]计算：
其中fiti是第i个解决方案的适应度值，其与位置i处的食物来源的花蜜量成比例。 SN是等于所用蜜蜂数（BN）的解的数量。
为了从记忆中产生候选食物的位置，ABC使用以下表达式[3]：
其中kЄ{1,2，...，SN}和jЄ{1,2，...，D}是随机选择的索引。索引k随机确定，但必须与i不同。 Фij是一个随机数，在[-1,1]之间选择。蜜蜂通过使用此参数可视地比较两个食物位置。只要xij和xkj的位置之间的变化减小，位置xij的扰动就会减小。因此，搜索接近搜索空间中的最佳解决方案。
侦察蜜蜂取代了动态范围内随机生产的新食物来源，被雇用的蜜蜂放弃了。在ABC中，如果某个位置不能进一步改善，则在预定数量的周期内，则认为该食物来源被放弃。在这里，由于在每个周期中唯一的一个来源被遗弃，所以一个被使用的蜜蜂变成了一个童子军。所谓“限制”
全文共7680字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144627]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
