毕业设计（论文）-蜂群算法在路径优化上的应用.doc

本科毕业设计说明书（论文） 第 25 页 共 25 页1 绪论1.1 研究背景和意义当今社会的经济、科技快速发展，面临着很多复杂的非线性系统和快速反应系统这使得我们传统的优化方法在解决这类问题上渐渐乏力。于是，人们开始寻找更快、更好的方法去解决这些复杂问题。如今，引入自然界的规律来解决建模和解决复杂的优化问题变得越来越流行，这主要是由于经典算法在解决较大规模的组合或高度非线性优化问题的效率十分低下。目前的情况是解决整数或离散决策变量线性优化模型在大多数情况下没有太大的区别。这些的主要原因之一是经典的优化算法在给定问题的解决方案缺乏灵活性。一般情况下，一个给定的问题在这样种方式下是仿照一个经典的算法，如单纯形算法。这通常需要做出几个假设以验证在很多情况下这是不容易实现的。为了克服这些限制，设计更灵活的适应性算法是非常迫切的。由于这种情况，科研人员提出了很多的元启发式算法，如禁忌搜索算法、蚁群算法、遗传算法等。研究表明，这些算法可以比经典算法提供更好的解决方案。自然启发算法的一个分支，被称为群体智能，目的是发展元启发式算法以解决昆虫问题。蜂群算法是一种相对较新的群智能算法。蜂群算法试图模拟自然界蜜蜂的采蜜行为。蜜蜂使用多种方式，如摇摆舞定位最佳食物来源，并寻找新的食物源。这使得它们适合开发新智能搜索算法。移动机器人如果能够在生命探测、自动导航作业中借用成熟的路径优化技术，就能明显减少在运行工作中的造成的机械消耗和减少运作时间。不单单是移动机器人需要路径规划，在实际生活中的其他领域，大多数都需要路径优化技术。所以，各个相关领域都把路径规划作为一个重要的研究方向。经过各国学者对生物群体不懈的研究，提出了许多具备高性能的群智能算法。基于觅食的蜂群算法利用蜜蜂间寻找最优解的正反馈机理具有收敛性强、鲁棒性强等优点，将蜂群算法建立应用模型运用在路径优化问题上，提供了一种新的思路，具有一定的研究意义。1.2 国内外研究现状1.2.1 路径规划的研究现状在面对复杂的环境规划、不确定性和其他因素的领域中，路径规划可以转换成一个多约束，多目标优化问题的模型。依照不同程度的认知信息，对路径规划问题可以分为两类：其中一个的是完全已知的全局路径规划问题，也可以被称为静态规划或离线路径规划；对应于其它的未知环境信息或其他部分未知的局部路径规划，也被称作在线路径规划问题。这几年来，国内和国外的路径规划在各个领域的研究学者也取得了一些成绩，根据对环境因素的认知程度，给出了一些路径规划的方案。人工势场法、自由空间法等都是常见的路径规划方法1。在动态不确定因素下的路径规划是一个典型的NP-Hard问题，在多目标和多约束的苛刻限制下，路径规划问题运用传统优化方法由于自身的具有的局限性，使得算法表现出一系列的缺陷，例如，缺乏自适应性并且计算的复杂度高、规划效果差，所以国内外的学者也在积极地寻找新的解决方案以解决传统优化方法的局限性。值得庆幸的是，伴随着科学研究的不断推进，提出了一些新颖算法，如蜂群算法、遗传算法等在研究中有很强适应性的启发式算法2。1.2.2 蜂群算法的研究现状受到自然界的蜜蜂行为提出的蜂群算法(BCA，Bee Algorithm)是一种较新的元启发式优化算法。根据蜜蜂的机理的不同，蜂群算法可分为以下两大类3：基于蜜蜂繁衍机理的蜂群算法(BCO on propagating)。基于蜜蜂觅食机理的蜂群算法(BCO on gathering)。两种算法各有其独立的发展轨迹和实现原理。对于基于繁衍的蜂群算法。Abbass发展出一种蜜蜂繁衍优化模型(BMO， Bee Mating Optimization)。Bozorg Haddad和A.Afshar成功地将蜜蜂繁衍优化模型运用到离散水库的优化问题上。蜜蜂的采蜜行为是一种典型的群体智慧行为。Yang首先提出了虚拟蜜蜂理论 (VBA，virtual bee algorithm)在数值优化问题上得到了应用。VBA中，开始的时候在解空间中随意散布着一些虚拟的蜜蜂：这群蜜蜂依据自身储存的判定函数适应值来采集蜂巢附近的花蜜源4。1.3 研究内容蜂群算法是一种新型的元启发式优化算法，只是最近几年开发的模型。其研究在国内外还是比较少的。最近几年来，全球的科研人员借助蜂群算法研究了经典的数值优化函数，但是针对旅行商问题（TSP）研究还是比较少。 旅行商问题是一个典型的NP-Hrad问题，不管是理论上还是在实践上都具有重要的研究价值。因此，本文将介绍蜂群算法在TSP问题上的研究。1.4 章节安排本文章节安排如下：第一章 绪论。介绍了本文的研究背景、研究现状、研究意义和主要的研究内容等。第二章 基于采蜜机理的蜂群算法。详细阐述了蜂群算法的仿生机理，算法的原理和介绍路径优化问题的基本问题和研究难点。第三章 基于采蜜机理的蜂群算法在TSP问题上的应用。描述了基本的TSP问题，蜂群算法在TSP上实现的方式。第四章 蜂群算法的matlab测试并进行算法参数分析。第五章 总结。论文所做的主要工作，论文还存在的不足有待进一步研究。2 蜂群算法解决优化问题算法随着时间的推进在不停地发展：从最初的构造性开发方法到局部优化搜索技术进一步发展到现在的元启发式优化算法5。元启发式算法是使用智慧生物仿生学基本方法，加入了许多其他学科的概念和方法（如人工智能，物理，生物等）使其具有高效的优化性能，并且具有应用广泛性和无需问题的特殊信息，能有效的解决NP-Hrad问题。接下来，我们将对启发式算法中的蜂群群算法作一简要介绍。2.1 蜂群算法的模型蜂群算法是一种群智能优化算法，是通过对自然界中蜜蜂出巢采集食物的行为进行模拟的算法。在真实的情况下，蜜蜂能在苛刻和复杂的环境中进行高收益率的采蜜，并且还可以随着环境的改变而变换自己的采蜜方式。2005年Karaboga5通过对蜜蜂采食行为的研究给出了人工蜂算法的模型。这其中包括了雇佣蜂、非雇佣蜂和食物源三个基本组成6：雇佣蜂：也被称为引领蜂，它的数量与食物源的数量相对应，它自身还储存食物源的相关信息。回到蜂巢中时会通过摇摆舞的形式按一定的概率与其它蜜蜂分享自身携带食物源的信息。非雇佣蜂：非雇佣蜂有两种，分别是跟随蜂与侦察蜂，它们的主要目的是开采蜜源和发掘新的新的蜜源。跟随蜂按轮盘赌的选择方法从引领蜂那获取食物源的信息。食物源：蜜蜂的搜索目标，离蜂巢的远近程度、花蜜量的多少等由多方面因素评价其质量。在算法中,蜜源的质量与收益度成正比。2.2 蜂群算法的流程和特点2.2.1 蜂群算法的流程刚开始的时候，侦察蜂根据以往的经验知识决定其搜索方式，也能完全随机的搜索。经过一系列搜索后，如果蜜蜂找到某个食物源，侦察蜂就开始进行采集花蜜利用自身的储存功能标记食物源的位置。同时，侦察蜂蜂将成为被引领蜂。蜜蜂采完食物源后把蜂蜜放在蜂巢接着将有以下几种选择7：(1) 放弃食物源而成为非雇佣蜂。(2) 通过跳摇摆舞招募更多的蜜蜂采集食物源，接着继续去食物源采蜜。(3) 继续在之前侦查食物源采蜜并且不进行招募活动8。非雇佣蜂有如下选择8：(1) 转变成为侦察蜂并探索蜂巢周围的食物源。其搜索方式可以由先前经验知识决定也可以进行随机侦查。(2) 在观察完摇摆舞后接收舞蹈信息转变为跟随蜂，开始在食物源附近进行搜索并采集蜂蜜。为了更进一步理解蜂群算法，算法的程序流程如图2.2所示。2.2.2 蜂群算法的特点综上，蜂群算法具有以下几种特点9：(1) 它是一种模拟自然生物的启发式算法。通过模拟自然界中蜂群高效率寻找蜜源的机理。(2) 具有角色分工、角色转换机制。蜂群中的蜜蜂按照自己角色采用不同的搜索方式，并根据食物源收益率自发的调整自身的角色，以适应下一次搜索过程。(3) 较强协同工作能力。蜜蜂在选择路径时，蜜蜂依据角色转换获取的信息决定是否选用以前蜜蜂搜索到比较丰富的食物源路线，形成正反馈，能以较大概率找到的最优解。(4) 鲁棒性。运用概率规则和随机搜索目标，不用借助先前的经验，有适用性和鲁棒性。(5) 可以和其他启发式算法结合在一起使用。蜂群算法之所以具有很强的发现最优解的能力，这是因为算法利用了引领蜂和跟随蜂寻路的正反馈机制，在一定程度上可以加算法的收敛速度。并且蜜蜂间不持续地进行信息传递和交流，从而可以相互协作，更有利于发现最优解10。开始初始化参数，产生初始位置找到初始蜜源引领蜂搜索新蜜源并确定初始标记蜜源跟随蜂搜索蜜源更改标记蜜源是否出现侦察蜂产生新位置取代相应蜜源确定本代的标记蜜源是否满足终止条件输出最优蜜源结束YNY图2.2 蜂群算法流程图 2.3 蜂群算法的原理初始化的时候，算法随机生成含有个可行解并且进行计算，代表了蜜蜂数量（刚开始的时候所有蜜蜂都设为侦查蜂），同时也是相对应食物源的数量。其中。计算解对应的函数值，按照函数值的优劣进行排序，预定临界值（例如排名前），将排名在前的解作为蜜源位置，即设定前的蜜蜂为引领蜂，后的蜜蜂为跟随蜂。引领蜂招募跟随蜂概率为11：(2.1) 式中，是第个解的函数值，适应度越高的食物源被选择的概率越大。引领蜂和跟随蜂的邻域搜索公式：(2.2)式中，k1，2，N，j1，2，d都是随机选择的，并且kj，R为-1，1范围的随机数。若食物源经过若干次搜索后，没有得要最优解，该食物源将被引领蜂放弃。(2.3)在蜂群算法中，雇佣蜂经过limit次搜索后没有的最优解自己的角色将转化成侦察蜂，使算法能够跳跳出局部最优解，加快算法的收敛速度12。2.4 解的构造过程蜂群算法中构造解的过程与真实蜜蜂寻找食物源的过程相似。每一个蜜蜂不是每次都重复之前的采蜜路径。完成一次寻路后，蜜蜂在蜂巢舞蹈区交流蜜源的方位、质量。本节将解释蜜蜂是如何构造优化解来解决问题。蜜蜂在根据自己所走的路径距离的长短来随机构造解，为转换的角色的蜜蜂提供信息。在蜜蜂寻径的过程中可以根据具体情况获得的蜜源局部信息，每一个节点所对应的边距都包含一个启发值。在很多情况下，表示蜜蜂在加入一个节点的时候是从局部问题一种估测。每个蜜蜂都拥有储存地理位置和蜜源质量的能力，用来记录当前自己所走过的每一个节点。在寻路过程中，第个蜜蜂的存储单元被定义为禁忌表。其主要作用为：提供作为约束条件；解决目标函数优化解的质量。在构造可行解的过程中，定义解的终止标准即满足这个要求，然后，算法添加节点的过程就结束了。在状态时，蜜蜂从点相邻的点中选择，这样就转移到新的状态。在转移的过程中既要考虑到随机状态转移规则，又要考虑到以下条件：得到可行解的约束条件；中存储已经搜索过的节点；启发信息。因为蜜蜂扮演了不同的角色，所以蜜蜂构建路径的方式也有一定不同。引领蜂仅是重走了上一次迭代过程中所走的的路径，即保持可行解的数量不做任何改变。跟随蜂与侦察蜂则是根据概率转移规则来选择下一个路径节点，其计算方法如下：(2.4) 0otherwise表示的是由第k个蜜蜂在的时候由节点移动到节点的概率；=。表示的是第个蜜蜂在节点周围可行的节点，由蜜蜂还没有访问过的节点和在满足一定约束条件下的节点组成。是第只搜寻蜜蜂具备的禁忌表，用来储存蜜蜂所走过的节点信息，以用来确保没有重复经过同一个节点，在某些应用中还可以方便蜜蜂按原路返回蜂巢。，分别表示控制蜂群找到解的信息和搜寻可行解问题的信息。，分别代表其在方程权重参数。蜜蜂在控制信息方面存在一定的区别。侦察蜂： (2.5)其中l为集合的元素数目，即蜜蜂还没有访问过的节点个数；跟随蜂：n 选择引领蜂的道路 (2.6) 不选择引领蜂的道路=其中，表示引领蜂的引导性强弱，同样指蜜蜂未走过的节点个数13。2.5 路径优化问题的研究难点与实质2.5.1 路径规划问题的描述在上个世纪后期，一系列问题引起汽车产业的快速发展，推动智能交通系统的快速发展，路径优化技术是其研究的热点之一6。在这个阶段中，路径优化理论有了较大突破。可以借用物流例子来说明一般路径优化问题，可以描述如下有L个客户，已知每个顾客从配送中心到K汽车到达的需求和位置，并且要在完成配送任务后返回发配中心，要使每辆在运载一定货物质量的条件下使其运送的运送的路线长度最短，尽可能要满足以下3个约束条件11：(1) 在运送过程中物流货车运送线路上客户点所要求货物的总质量不能大于货车的最大装载量。(2) 在运送过程中物流货车运送线路的总距离长度不能超过货车一次行驶的最大行驶距离。(3) 在运送过程中物流货车运送线路上的客户点的要求应由同一辆货车完成任务。这样做得目的是运营的总成本最低。路径规划如图2.5所示 配送线路 1配送线路 2配送线路 3物流中心客户点图2.5 路径规划示例图2.5.2 车辆路径优化问题分类及其约束条件分配路径的合理与否，物流的发货速度，运营成本受到了很多因素的影响，所以采用科学合理的方法来确定配送路线是非常重要的工作。确定配送路线可以采取多种数学方法和运用在数学方法的基础上发展和演变来的经验。怎样处理信息是指快速，准确的进行路径优化14。路径优化是一个典型NP-Hard问题，可选配物流送路径方案的数量随着节点数量增加将以指数增长的速度快速增加，这就是组合爆炸现象。用来解决物流配送车辆路径优化问题的方法有很多，本质上，可以有两大类算法即智能算法和精确算法。精确算法是可以得到最优解的算法，主要有：切削平面法，分支定界法，网络流算法，动态规划法等。因为精准算法的计算量随着问题大小的增加成指数增长，在实践中，它的应用范围是有限的。为此，专家们把精力主要集中在构建一个更全面的启发式算法上。路径优化技术的核心算法是路径优化算法。如果建立一个合理、高效的诱导数据库，那么诱导系统和运行效果取决于所选择的路径优化算法的优缺点。2.5.3 车辆路径优化的基本问题为了方便路径优化问题便于理解，经常利用一些技术把问题或模型转换成一个或多个以往学过的问题，然后再用一些拥有成熟理论去获得可行解和最优解。其中常见的问题有: 中国邮递员问题、运输问题、旅行商问题、最短路问题、背包问题、多个旅行商问题等。2.6 蜂群算法在路径优化中的应用由于科学研究不断的被探索，一系列新兴的科学和算法，例如神经网络、粒子群算法、遗传算法等智能优化方法具有很强的适用性。这些方法也开始被用在各个领域的路径规划13 路径规划是一个典型的NP-hard的组合优化问题。按照车辆调度的实际情况，检查汽车和总行程两个目标函数，赋予了新的算法的问题，蜂群算法。验证算法的有效性是要通过计算benchmark问题，还要把结果与其他启发式算法作比较和分析。蜂群算法的智能优化算法都是刚刚开始，在国内和国外关于蜂群算法的文献很少，所以它不仅是有效尝试扩大蜂群算法，还为路径优化应用的范围提供了新的的解决方案 15。2.7 本章小结在物流系统中的车辆数和车辆路线需要合理安排以减少运营中的费用，还可以提高经济效益，但是多个目标同时实现最优是很困难的，经常会有所得失。车辆数量少了，行驶的路程可能长了；反之车辆数量多了，行驶路程就会短了。此外，实对目标的定位还需要依靠决策者的判断。蜂群算法可以用来作为一种新的可行的手段来解决这样的问题。此外，国内外关于蜂群算法的文献很少，本章是在蜜蜂生物学机制的深入分析的基础上，深入分析路径上的问题，最后给出算法的框架。为下一章蜂群算法在TSP问题上应用奠定了基础。3 旅行商问题3.1 蜂群算法在TSP问题上的应用3.1.1 TSP问题的描述旅行商问题(Traveling Salesman Problem，TSP)是一个受到国内外学者广泛研究的经典组合优化问题，经典的旅行商问题可以被描述为：在贸易交流中，商品销售员开始的时候从出发城市起步，经过若干城市进行商业贸易，接着回到起始的城市。这当中走怎样的路线可以使行走的总距离最短并且花费的时间最少，这属于NP-Hard问题。并且在走的路径中，节点城市的数量越多，可选择的线路数量呈指数量的增长，而且还不能在有限的时间内找到最优解16。TSP问题在许多实际问题的管理领域中都有应用，如旅游景点路径规划问题，描述了怎么规划游客的行走路线，可以使经过的路径总和最小。货车配送的网络优化问题，要缩短交货时间，从而提高客户满意度；巴士路线规划问题，拟规划路径网络，找到最佳的巴士路线设置，以满足群体的需求。在实际生活中，TSP问题有很多，就不在此一一列举，所以深入研究对TSP问题的研究，可以为解决实际管理问题提供理论依据。早期的研究者主要使用精确算法解决TSP问题，常用的方法包括：分支定界算法，线性规划和枚举法。然而，追求精确算法的精确解，却忽略了算法消耗的时间在增长，问题规模在增大，精准算法将变得力不从心，所以，在以后的科学研究中，国内外学者把启发式算法变成研究重点。近几年来，许多解决旅行商的元启发式的算法被提出来，主要有神经网络 (Neural Network)、模拟退火 (Simulated Annealing，SA)、遗传算法 (Genetic Algorithms，GA)、蚁群优化算法 (Ant Colony Optimization，ACO) 、粒子群优化算法 (Particle Swarm Optimization，PSO)等一系列改进算法。总之，算法解决TSP问题主要集中在以下方面：继续提高现有的TSP算法，结合的各种算法的优势改善算法的性能，对混合TSP算法进行研究，利用人工智能来解决TSP算法，应用领域不断拓展的新算法。3.2 蜂群算法求解TSP 问题3.2.1 用蜂群算法求解TSP的步骤对于进行大规模求解TSP问题，考虑到TSP整体求解过程中的复杂性，在设计算法的同时可以对其进行空间分解，借助聚类的方法将整个问题分割成若干子问题，然后是用启发式算法迅速得到子问题的一个近似解，接下来，在规则搜索和蜂群算法的混合方式指导下对其进行优化，当每个子问题求解完成后用临近规则来求解问题的整体解，最后，使用局部改进算法对其作更加全面的加工就能得到最终解。蜂群算法求解TSP问题的流程如图3.1所示。3.2.2 蜜蜂的寻路过程求解TSP的解可以用节点序号形成的一个有向环状排列来表示。所有TSP的解都是由起点节点出发，经过每次运行后就向解集合中增加一个以前没访问过的节点，蜜蜂访问过每个节点后就终结解。TSP问题中没有对的特别约束条件15。定义。作为路径行进矩阵（禁忌表）。依据每个蜜蜂角色的不同而采取不同的构建方式。首先，蜜蜂的角色为侦查蜂时，进行随机搜索路径；单作为跟随蜂时，采用轮盘赌的方式来选择跟随引领蜂的采蜜路径；当作为引领蜂时，就直接重复上一次的搜索路径，中的路径不发生改变。下文将详细介绍下跟随蜂和侦察蜂的采蜜路径的构建过程。当前侦察蜂对应的节点为i，未访问节点的集合为，则由侦察蜂选择节点完全根据节点之间的启发性信息。用来确定，它的转移概率由式(2.4)、式(2.5)确定。其中为节点i到节点j的距离。路径的长度越短，节点被选择到的几率就越大。可用图3.2(a)、图3.2(b)可以描述跟随蜂构建节点的全过程。图中，跟随蜂首先走到了A节点，在路口决定访问哪个节点时，他会先检查它所对应的引领蜂走过的路径。在图3.2(a)中，跟随蜂可以选择中就包含B节点，即跟随蜂可以得路径中包含了AB，而其跟随的引领蜂路径也包含AB，此刻跟随蜂重走AB的概率就比选择其他路径的概率大；在图3.2(b)中，跟随蜂待可以选择的包括了AB、AC、AD，而其跟随的引领蜂路径为AZ，此刻跟随蜂选择这三条路径的概率是相等。N=0求跟随蜂第次选择所有非禁忌城市的概率参数初始化更新禁忌矩阵按概率，跟随蜂完成第次选择更新转移因子矩阵求侦察蜂第次选择所有非禁忌城市的概率按概率，侦察蜂完成第次选择参数初始化精英策略，保留上代最佳计算整个蜂群路径长度路径长度排序更新本代引领因子若出现停滞。则调整参数Q，输出最优解，画最优路径图及收敛曲线NNYYNNNYY图3.1 TSP问题的蜂群算法流程图 B C D较小概率较大概率AE跟随蜂路径等概率选择B、C、D三点B C DAEZ跟随蜂路径AB引领蜂路径ZABCD引领蜂路径 (a) 引领蜂后续路径含跟随蜂可选路 (b) 引领蜂后续路径不含跟随蜂可选路径图3.2 引领蜂后续路径3.2.3 更新策略蜂群算法求解最优的解决方案类比于蜜蜂找到一个高收入的食物来源。蜜蜂在保证食物源的方面具有精英带领作用。食物源的质量的质量很好，就需要更多的跟随蜂，这样做的目的是加强算法的收敛性17。为了增加可行解的多样性需要侦察蜂不按照引领蜂已走过的觅食路径随机的寻找食物源，可以避免算法陷入局部最优解，TSP 问题和可行解优化问题对应的关系如表3.3所示。表3.3 tsp问题与可行解优化问题对应的关系可行解优化问题蜂群采蜜行为TSP问题问题的解解的优化程度解的速度问题的最优解遍历所有城市的路径路径长度TSP解的速度最短路径蜜源位置蜜源的大小收益度寻找及采集蜜源的速度高收益度实物源在蜂群算法中具有两级因子机制，其中一个是引领因子，另一个则是转移因子。引领因子需要分析所对应的引领蜂留下来的觅食路径来确定任意两个节点之间的路径强度，转移因子指的是跟随蜂蜂从节点i 到节点j 转移强度的大小，和蜜蜂采取怎样的更新策略及引领因子有一定的关系，等到转移因子进行归一化计算后，就可以得到相对应的两个节点之间蜜蜂的转移概率，在具体情况下，可以采用如下的策略17。蜜蜂可以在中选择的节点，其中蜜蜂所访问的的节点信息存储中，一直做动态调整以适应蜜蜂不断地选择节点。每增加一次进化代数的值，都要清空所有路径上的转移因子，保证转移因子没有以前的寻径信息。蜜蜂们每进行一次迭代计算，通过式(1) (2) (3)的计算，所有路径中的转移因子都要进行调整一次。接着，对蜜蜂所走的路径进行长度排序，得出引领路径的矩阵。最后就要采用2级更新策略求取解。第1级：引领因子更新策略(1) 引领路径的选择有以下3种的方式：选取路径中最短的一条路径作为引领路径；选取所有路径中长度是前位(还可以是前% 作为引领路径)；把上一代的所有蜜蜂访问过的总路径作为引领路径。选择蜜蜂所走路径中最短的一条作为引领路径 ,i=1(3.1)0 其他=(2) 选取路径长度排序前位( 或者% 作为引领路径)(3.2) 0 其他=(3) 把上代的所有蜜蜂走过的总路径作为引领路径 (3.3)0 其他=在公式中：进化代数的值是；在蜜蜂的第代后，把探寻的路线距离进行排序就是引领路线的矩阵是；所有的蜜蜂的总的数量是；当第只蜜蜂进行第次的迭代计算后引领的因子在路径ij上的值是。这其中蜂群算法可以建立以下三种模型：模型、模型、模型。 模型 模型 模型，0 其他=(3.5)第2级：转移因子动态更新策略重新更新转移因子，已知的节点与上一级的节点形成引领矩阵，可以求出每个节点上的转移因子的信息，以下是转移因子进行更新的公式： =(3.6)式中：是第只侦察蜂从节点到节点的转移因子，是引领蜂还没有走过的路径，可以选择节点的总的数量；作为转移强度；作为可以选择的节点的总数量；当选到以前侦察蜂没有走过的路径的时候，转移因子的值是，其中，当先的路径包括以前侦察蜂走过的路径条件的时候，转移因子的值为，如果选择其它未选的路径时，转移因子的值为18。3.2.4 蜂群算法的状态转移策略假设蜂巢中的所有的蜜蜂数量为，其中侦察蜜蜂的数量为，剩下的跟随蜜蜂的数量，就有了=+的等式，这其中等于总蜜蜂数量的1/c左右，c是常数，当取的数值小于10的时候，能保证算法是具有收敛性的。随着引领蜂从节点移动到节点，引领蜂就要采取与以前一样的寻径过程。需要根据下面的公式算出侦察蜂和跟随蜂在第代的第只蜜蜂在节点转移过程中的概率。状态转移公式为= (3.7) 1 根据转移概率状态转移因子的大小选择转换路径，以确保大多数的蜜蜂蜂的历史信息由上一代蜜蜂传递的，而侦察蜂确保其中一些蜜蜂有随机侦查路径的能力，保证解具有多样性，以帮助算法跳出局部最优解，因为引领蜂相对于其它的蜜蜂具备精英性，可以储存关于上代记录的最佳路径，这样做能让算法的收敛性得到提高，减少算法在计算过程中的的振荡性，正是这几个方面的因素才能让蜂群算法的收敛速度加快并且全局搜索能力得到提升，依据，算出算法的状态动态值确定其值。当解不明显变化时就可以停止对它的计算。3.3 本章小结本章蜂群算法的思想提供了解决TSP问题的一种思路。考虑到蜂群算法容易陷入局部最优解，即单个蜜蜂搜索到的解或许完全一样，继而不能对解的空间进行进一步的搜索，不能发现更优的可行解。所以在原算法的基础上引入了更新策略和状态转移策略，进一步扩展了算法的全局搜索能力。4 蜂群算法的算法框架与实现在第一章介绍了本毕业设计的研究背景与意义、研究现状和主要的研究内容后，第二章主要研究学习了基于采蜜机理的蜂群算法，对蜂群算法的仿生机理，算法的原理进行了归纳总结，并简单介绍了路径优化问题的实质与研究难点。第三章中我们深入研究了基于采蜜机理的蜂群算法在TSP问题上的应用。由于时间关系，蜂群算法在TSP上应用的仿真算法我们未完全实现，在本毕业设计中，我们针对蜂群算法基于采蜜机理的三个关键问题的选择进行了定义，并在Matlab下实验计算优化解，以下是对该算法框架的介绍和算法实现过程中遇到的难点进行解释。4.1 蜂群算法的三个关键步骤：针对蜂群算法，文献中有不同的具体实现方法，但最关键的三个问题就是：(1) 初始解产生；(2) 邻域搜索规则的制定；(3) 跟随蜂选择引领蜂的概率。蜂群算法就是这样一个思路，不同的文章选择的策略不同（在前两章中我们已介绍），公式也不一样，算法就会有不同。接下来，介绍下我们实现该算法时的定义与选择：(1) 初始解产生，也就是ScoutBee的生产；（我们算法程序初始令NP=20，就是假设有20只蜂，10个引领蜂，10个跟随蜂，并假设有10个蜜源，这是开始解）(2) 邻域搜索规则的制定（就是侦察蜂在领域寻找新的蜜源的规则）(3) 跟随蜂选择引领蜂的概率, 就是OnloolerBee选择解的策略（文献中通常遵循轮盘赌的规则）算法流程图如图4.1所示。开始第一步：初始化蜂群数量第二步：设置食物源对应的引领蜂并且进行领域搜索探索到新的食物源，然后保存最好的一个。根据蜜源的数量设置跟随蜂改善limit循环第四步：发送侦察蜂搜索新的食物源并且记录下之前最好的蜜源信息是非满足终止条件输出最优解YesYesNoNo图4.1 算法流程图4.2 算法中几个问题的解释-ABC algorithm 计算程序第一步，先初始化，即参数的选择与设定。NP=20；%/* 引领蜂和跟随蜂的数量*/FoodNumber=NP/2；%/*蜜源的数量是整个引领蜂和跟随蜂总数量的一半，这里也表示引领蜂或跟随蜂的数量*/limit=100；%/*一个蜜源如果在限定次数内没有得到改善将被雇佣蜂放弃*/maxCycle=2500；%/*觅食的周期次数算法结束的终止次数*/-主程序用调用的子函数主要有：(1) 子函数sphere，就是我们要求的优化函数，是计算适应度的，求的适应度，才能求轮盘赌的概率。以下是调用Sphere的子函数，其中ub是自变量的上界，lb是下界，D是每个解的维度。objfun=Sphere； %优化函数D=100； %/*进行函数优化的参数的大小*/ub=ones(1，D)*100；%/*参数的下界 */lb=ones(1，D)*(-100)；%/*参数的上界*/轮盘赌的原理简单来说就是：随机产生一个0-1之间的数rand，然后我们通过第i个解fitness的一个公式计算出一个概率pi，如果randpi，这个解i就被选择（这里我们用下面的(4.2)公式来计算，也可以根据实际问题来变换。(2) 子函数calculatfitness，我们知道，一个蜜源被选择的概率正比于它的质量，如距离的远近，蜜的多少等，因此可以使用不同的方案来计算的概率值。%/*举个例子 prob(i)=fitness(i)/sum(fitness)*/%/*或者以其它的计算方法 prob(i)=a*fitness(i)/max(fitness)+b*/%/*概率值通过计算适用度的值除以最大的适用度*/prob=(0.9*Fitness./max(Fitness)+0.1； （4.2） 这里所求的是函数sphere的最优解，众所周知，该函数的最优解是零。（当然我们可以选取别的测试函数。）sphere （其中x取值-100，100）最后程序运行的结果：maxCycle =2500 ObjVal=1.39063e-006maxCycle=2500就是定义的循环次数，也就是结束条件； ObjVal=0.00000139063 就是求得的最优解（sphere函数的最优解是零）。4.3 算法的主要步骤综上，蜂群算法的主要步骤描述如下第一步：初始化蜂群数量。随机生成NP个可行的解决方案。 NP/2可行的解决方案，作为初始的食物来源。第二步：引领蜜蜂对应他们的食物源S1。在引领蜂发现食物来源后，跟随蜂进行领域搜索了新的食物来源。比较这两种食物来源，并采取更好的。探索新的解决方案S2。第三步：根据蜜源的数量设置跟随蜂。引领蜂会在蜂巢的舞池中带来新的解决方案，跟随蜂会采用轮盘赌的选择法来选择实物的来源S3，然后进行领域搜索找到新的解决方案S4。比较S3和S4方案选择更好的方案。第四步：如果没有明显改善limit循环次数就发送侦察蜂在区域搜索来发现新的蜜源。在同一时间内，储存迄今为止发现的最优的食物源信息。重复第二至第四步，直到得到满意的结果。这里终端的循环次数对应整个算法的最大的循环次数。结 束 语本篇毕业设计论文主要分析了蜂群算法的原理与模型，研究了算法的特点及其在控制领域路径优化中的应用。通过对算法的分析了解，发现蜂群算法利用蜜蜂采食过程中不同角色之间的正反馈机制让其具有很多的特性，诸如能够快速的发现最优解、全局寻优能力强等优点。但是蜂群算法相对于GA、ACO、PSO三者的研究时间相对较