第四组蚁群算法应用及改进研究

1、第四组 蚁群算法应用及改进研究蚁群算法应用及改进研究（组长）戴家玮家指导：教授【摘要】 组合最优化问题（COP）即给定的约束条件下，求出使目标函数极小（或极大）的变量组合问题，是运筹学中的一个经典且重要的分支，其经典难题为旅行商问题（TSP）。本研究以旅行商问题为出发点，对蚁群算法及其改进方式进行研究，将模拟退火算法与蚁群算法相结合，并结合最大最小蚂蚁系统思想，最终提出模拟退火蚁群算法，对基本蚁群算法进行改进，提高解的质量并蚁群算法收敛速度。且经测试该改进算法的确优于原始蚁群算法。【】蚁群算法旅行商问题公共自行车调度模拟退火算法最大最小蚂蚁系统1第四组 蚁群算法应用及改进研究目录一、绪论5（一

2、） 研究背景5（二） 研究意义5（三） 技术路线6二、文献综述8蚁群算法8（一）1.蚁群算法相关应用82.国外蚁群算法改进研究83.国内蚁群算法改进研究9（二）模拟退火算法101.国外模拟退火算法研究102.国内模拟退火算法研究10小结11（三）三、蚁群算法12（一）蚁群算法产生与发展121.双桥实验122.人工蚂蚁153.人工蚂蚁系统特点17（二）蚁群算法基本模型191.蚂蚁系统数学模型192.蚁群系统算法的实现21（三）后续系统221.22蚁2.蚁量系统223.蚁密系统22蚁群算法改进算法23（四）1.精英蚂蚁系统232第四组 蚁群算法应用及改进研究2.优化排列蚂蚁系统233.最大最小蚂蚁

3、系统244.最优蚂蚁系统255.蚁群系统25（五）双（多）蚁群算法261.双（多）蚁群算法介绍262.多种群蚁群算法以旅行商问题（TSP）为例27四、案例分析公共自行车调度问题30问题提出30（一）（二）方法选择30数学模型描述30（三）（四）算法设计32（五）算例分析33五、模拟退火蚁群算法36（一）模拟退火算法361.模拟退火算法概述362.模拟退火算法结构363.模拟退火算法数学模型374.模拟退火算法（SA）特点385.模拟退火算法流程396.模拟退火算法解决TSP 问题40（二）模拟退火蚁群算法401.算法结合思路402.邻域搜索策略413.改进方式414.改进算法步骤42（三）算法

4、性能测试431.参数设置432.对比结果443第四组 蚁群算法应用及改进研究3.算法优化性能分析44六、总结与展望46（一） 本文工作总结46（二） 存在问题46（三） 研究展望47参考文献484第四组 蚁群算法应用及改进研究一、绪论（一） 研究背景组合最优化问题1（Combinatorial Optimization Problem），简称为 COP，即给定的约束条件下，求出使目标函数极小（或极大）的变量组合问题。是通过对数学方法的研究去寻找离散的最优编排、分组、次序或筛选等，是运筹学中的一个经典且重要的分支，所研究的问题涉及管理、信息科学、工程技术、交通、通信网络等诸多领域。在组合优化问题

5、中最有代表性经典难题就是 TSP 问题（Traveling Salesman Problem，TSP），即旅行商问题。旅行商问题是目前研究最的组合优化问题之一。目前世界上研究旅行商问题最主要遇到的瓶颈问题就是如何避免陷入局部最优以及计算效率的问题。为了解决这些难题，20 世纪 90 年代起，一些更新的思想和算法逐渐形成。由群居性昆虫行为特性获得灵感的蚂蚁算法（又称蚁群算法）是目前研究的热点，蚁群算法就是利用群集智能解决组合优化问题的典型例子2；又如由混沌现象受启发的一系列新尝试，将混沌机制和启发式搜索方法、人工神经网络、模拟退火等相交叉结合，建立优质高效的算法，来提高算法的计算效率和对全局最优

6、点的获取能力。蚁群算法这一研究热点，目前对其基本算法的改进大多数集中于信息素更新机制及参数选择。因此，本文以 TSP 问题为出发点，将模拟退火算法与蚁群算法相结合，对基本蚁群算法进行改进，并结合已有的先进改进思想，在提高量的同时蚁群算法收敛速度。（二） 研究意义在组合最优化问题中，以 TSP 问题为例，最早也最自然的想法就是采用穷举法。然而，所谓最优解的必然存在性和必能找到的特点是建立在问题的规模较小的情的。当可行解集合中的点个数较少时，通过最直观的穷举法很容易得到最优解；但倘若可行合中的有限点数目逐渐增多，此时如果仍采用完全枚举、判别、比较、选择的步骤，则无疑是十分困难和不可取的，所需要的时

7、间和空间是庞大得惊人的。因此，对于 TSP 问题的研究重点应在可以接受的时间及空间复杂度的限制下去寻求最优解，从实际效果来看，以算法、模拟退火算法、遗传算法、人工神经网络算法为代表的现代智能优化算法发展至今，成果斐然3。蚁群算法基于正反馈机制反复迭代获取最优解，为保证其解的精确性在寻优过由于信息素挥发机制的存在，且初期信息素匮乏，收敛速度较慢；而模拟退火算法具有大范围全5第四组 蚁群算法应用及改进研究局搜索能力，由于对系统中反馈信息利用不够，当求解到一定范围时往往做大量无为的冗余迭代。将模拟退火算法与蚁群算法相结合，可使两者优势互补，利用模拟退火算法初期生成信息素分布，利用蚁群算法获得较精确解

8、，另外采用模拟退火的邻域搜索策略在寻优可蚁群算法解的质量，且寻优过程结合最大最小蚂蚁系统思想进一步提高了解的质量且尽可能保障其收敛速度。（三） 技术路线本文共六章，具体安排如下：第一章：绪论，提出本文研究背景及意义，对全文框架进行梳理。第二章：文献综述，对蚁群算法及模拟退火算法国内外相关研究进行综述，为后续两者结合做铺垫。第三章：蚁群算法，从蚁群算法产生及发展切入，研究蚁群算法基本模型，并应用旅行商问题（TSP）对其算法模型及实现流程描述，进而对其目前认可程度较高的几种改进方式进行介绍，其中最大最小蚂蚁系统将在后续改进中进一步进行融合。第四章：蚁群算法案例，以“公共自行车系统调度问题”为实际案

9、例，建立目标函数及其约束条件，利用蚁群算法进行迭代计算，以具体展示蚁群算法如何解决实际问题。第五章：模拟退火蚁群算法，由模拟退火算法入手对对蚁群算法进行改进，即将模拟退火算法与蚁群算法相结合，并对改进的蚁群算法进试，得出最有效的改进模型。第六章：结论与展望，总结本文所做工作及成果，并指出本文不足之处及后续研究方向。本文技术路线如图 1.1 所示：6第四组 蚁群算法应用及改进研究蚁群算法 及其改进算法模拟退火算法图 1.1技术路线图7结论及展望算法性能测试模拟退火蚁群算法 (融合最大最小蚂蚁系统改进)改进算法介绍蚁群算法案例分析蚁群算法国内外相关研究模拟退火算法国内外相关研究文献综述第四组 蚁群

10、算法应用及改进研究二、文献综述（一） 蚁群算法1.蚁群算法相关应用受蚂蚁行为的启发，Colomi 和 Dori 即等人于 1992 年提出 Ant System（AS）的概念，研究成果经应用于传统的旅行商问题（TSP）上，取得了很好的效果。2002 年，Daniel Merkle等人基于串行进度生成机制、最晚开始时间优先规则、正向逆向调度，首次用 ACO 算法解决约束项目排序问题（RCPSP）。国内学者（2005）也将蚁群算法应用于和RCPSP，采用串行进度生成机制和最晚结束时间优先规则，结果证明该算法解决 RCPSP 有效可行。自从蚁群算法诞生之后，它被陆续应用于路由问题、分配问题、调度问题

11、、子集问题等许多领域的问题。在调度问题领域，除了经典受限项目调度问题，它还被应用于车间调度等多个问题，对这些问题的相关研究列于表 2.14中。表 2.1蚁群算法应用于调度问题列表2.国外蚁群算法改进研究在蚁群算法产生之后，许多学者对其进行了改进研究，其中大部分改进研究集中于信息素更新机制的改进。精英策略的蚂蚁系统（Ant System with elitist strategy）5是最早的改进蚂蚁系统。类似于遗传算法中精英策略保留住一代中最适应的，蚁群算法中的精英策略在每次循环后给最优解以额外的信息素量以保持最优解的吸引力，从而得到全局最优解。Stutzle 等人（1997）提出最大最小蚂蚁系

12、统（Max-Min Ant System， MMAS）6，只对找8问题名英文名作者工序车间Job shopColomi，开放车间Open shopPfahringer工作流车间Flow shopStutzle总延迟Total tardinessBauer，总权重延迟Total weighted tardinessden Besten，Merkle&MiddendorfGagne，项目调度Project schedulingMerkle，组车间Group schedulingBlum第四组 蚁群算法应用及改进研究出当前循环中最优解的蚂蚁或者找出全局最优解的蚂蚁走过的路径进行更新，从而防止早熟收敛

13、现象的发生。Merkle 等人（2002）7提出了精英遗忘策略，使精英蚂蚁忘记一部分已找到的局部最优解，从而防止过早收敛，扩大搜索空间，有助于找到全局最优解。对蚁群系统改进的另一个方向是多种群蚁群算法研究，而其中大部分研究都基于计算机并行工程，对系统的多种群蚁群算法研究非常少。KAWAMURA 等（2000）8提出的双蚁群系统，通过蚁群间的互动信息素，在充分利用优秀解的同时夸大搜索的解空间，比单蚁群系统取得更好的效果。其中，种群间的效用分为正效用和负效用，通过参数可以有效和调试效用的。为了充分利用学习机制，强化最优信息的反馈，1995 年 Gambardella 和 Dorigo 提出了Ant

14、-Q 算法9，该算法建立了蚂蚁系统与 Q-learning 的，仅让每一次循环中最短路径上的信息素浓度作更新。学者 Akihide Hiura 提出了一种比较复杂的主体的模型以模拟真实的蚁群。其中建立了两种不同类型的蚂蚁模型，并加入了蚁穴模型，堆模型和天地模型。蚁群的通信方式采用信息素，同时也考虑了噪声。在此模型的基础上，智能体在动态环境中的相互协作行为。这种完全依赖于模型的研究方式有助于启发人们看到很多有趣的现象，但是要解释这种现象就要对蚁群工作的内在机理进行更进一步的了解，根据实际问题应用人工蚁群系统，人工蚁群系统各参数设置及算法结构对求解过程的影响。3.国内蚁群算法改进研究等人（2004

15、）10提出了最优从信息素更新机制的改进角度出发，蚂蚁系统，对最优解进行更大限度的增强，而对解进行削弱，使得属于最优路径的边与属于最差路径的边之间的信息素量差异进一步增大，从而使蚂蚁的搜索行为更集中于最优解的附近。（2002）11提出一种自适应的蚁群算法，该算法通过自适应的改变挥发度等系数使解避免陷入局部最优，同时还收敛速度。和（2002）12提出一种基于蚁群算法的旅行商问题分段求解方法，将提出的相遇算法与分段算法相结合，提高了蚂蚁觅食的质量和解的质量。由于遗传算法具有蚁群算法不具备的一些有点，如前期快速的全局搜索能力等。力等人（2002）13提出了一种动态自适应调整信息素的蚁群算法，将普通蚁群

16、系统中常数的改为可变函数代替，在扩大搜索空间和充分用信息素反馈信息之间取得了较好的平衡。为了充分利用遗传算法的有点，许多学者尝试将遗传算法和蚁群算法结合起来，如Tseng9第四组 蚁群算法应用及改进研究等人（2005）直接将两者结合形成混合算法；Shou（2006）通过采纳遗传算法的部分算子（交叉、变异等）实现两者的结合。此外，等（2004）14将蚁群算法与模拟退火算法结合，利用蚁群算法生成初始解，然后在每个退火温度上进行抽样准则检验产生新更新信息素后再进行蚁群搜索，如此让蚁群算法和模拟退火算法交替进行。这些杂合算法共同点都是利用了蚁群算法获得初始量较好的这一特点，同时也了蚁群算法在搜索后期质

17、量不高、容易陷入过早局部收敛的弱点。在双（多）种群蚁群算法方面，国内的和滕少华（2006）15也提出一种双种群改进蚁群算法，将两个蚂蚁群体分别进化，并定期交换信息素，缓解了信息素的局部收敛现象。张长春等将粒子群算法与蚁群算法游记地结合，提出了 PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达到优势互补。（二） 模拟退火算法1.国外模拟退火算法研究SA 算法由于具有局部最优陷阱的能力，因此被 D.H.Ackley 等人用作 Boltzmann 机的学习算法，从而使Boltzmann 机克服了Hopfield 神经网

18、模型的缺点（即经常收敛到局部最优质）。在 Boltzmann 机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，使系统最终将往全局最优质的方向收敛。SA 算法可用来进行图像恢复等工作16，即把一副被“污染”的图像重新恢复的原图，滤掉其中被畸变的部分。S.Geman 等人的实验结果表明，SA 算法不但可以很好地完成图像恢复工作，而且它还具有很大的并行性。因此它在图像处理方面的应用前景是广阔的。2.国内模拟退火算法研究从模拟退火算法自身要素改进的角度出发，2006 年，等提出基于 ingber根、提出的非常快速的模拟退火算法（简称 VFSA）改进的 MVFSA 算法，该算法VFS

19、A 算法的两个基本特点，主要作两点改动：1，在高温下，一模型的全局扰动方式代替目前的扰动方式；2，在低温下，对模型扰动进行某种约束，边扰动边逐步减小模型扰动空间，以提高新模型被接受的机率。从模拟退火算法与其他搜索算法相结合的角度出发，1997 年、和提出模拟10第四组 蚁群算法应用及改进研究退火算法与遗传算法相结合，主要思想是在传统GA 的生存策略中引入Bloztman 生存机制，将模拟退火算法融入遗传算法的新产生中，以求得最优解作为遗传的父本。2003 年提出模拟退火与遗传算法相结合，此混合算法是以遗传算法为主题流程，侧重全局搜索，将模拟退货机制融入其中，侧重局部搜索，是在对每个实施一定演变

20、而产生解的设计了遗传算法中的变异和倒位的思想。此算法策略是从全局最优解的搜索角度和算法的进化速度上来提高模拟退火遗传算法的性能。此混合算法比基本遗传算法在进化速度上有很大提高，且在局部搜索能力方面也有非常明显的改进，此算法还在从当前局部最优状态向其他未被搜索空间转移的能力上有了较大的实质性。2004 年17提出将模拟退火与免疫算法混合。该混合算法是从一组随机，初始解开始，先通过选择、交叉、变异等免疫操作来产生一组的新抗体，然后再对各新抗体进行模拟退火求最优解。免疫算法的全局搜索能力好，可以快速在解空间的全体解搜索出来，陷入局部最优级解，其局部搜索能力较差。模拟退火算法的 Metropolis

21、准则可以有限度地接受解，并可以使其接受概率趋向于零，使得算法局部搜索能力强。两种算法合理融合，使算法的在全局和局部搜索能力均有提高。2007 年等18提出适应的模拟遗传算法，提出自适应变异概率的概念与理论遗传算法的收敛速度，以解决遗传算法中变异概率取值较小且在整个搜固定不变，易陷入局部最小值的不足，杂交母体选择是以整体退火选择的方式，可克服种群早熟化，避免过早收敛。（三） 小结模拟退火算法是目前来说最的启发式邻域搜索算法，虽然具有较大分为快速全局搜索能力，但是由于对系统中的反馈信息利用不够，当求解到一定范围时往往做大量无为的冗余迭代，使解的质量不高。蚁群算法基于信息素正反馈机制，为求得质量较高

22、的解，由于初期信息素匮乏，导致收敛速度较慢。为了解决蚁群算法存在的不可避免的缺陷，本文将模拟退火算法的邻域搜索思想应用于蚁群算法的寻优中，完美解决了各自算法的问题和缺陷。另外融合了目前解决 TSP 问题最好的改进思想最大最小蚂蚁系统，在寻优过进一步提高解的质量并尽可能保障其收敛速度。11第四组 蚁群算法应用及改进研究三、蚁群算法（一） 蚁群算法产生与发展1.双桥实验昆虫学家发现，在觅食过，蚂蚁在它所经过的路径上留下浓度与源质量成比例的信息素，并能够感知信息素的存在及其浓度，以此指导朝着信息素浓度高的地方移动。于是，蚁群的集体行动便表现出一种信息正反馈现象。蚂蚁群体就是通过这种间接交流机制达到在

23、觅食过沿着最短路径前进的目的。为了研究蚂蚁群体觅食行为的特征，Deneubourg 及他的同事们设计了一种双桥实验19。双桥的首尾分别连接了蚁穴和源。他们在试验中测试了不同长度的双桥（分别称为双桥实验（1）和双桥实验（2），得到了十分重要的结论。在 Deneubourg 等人的实验中，两个桥的长度是一样的，如图 3.1（a）所示。实验的结果显示（如果 3.1（b）所示），蚂蚁群体只有很小的概率会均匀选择两桥，大多数情，蚂蚁群体会渐渐只选择其中某一桥，而两桥被选择的概率几乎是相等的。造成这种现象的是：在觅食的最初期，蚂蚁们对任何一桥都没有偏好，于是随意选择一座桥，并在经过的路径上留下信息素。在初

24、期，两桥上的信息素浓度大致相等，然而由于随机波动，双桥中的一个也许会拥有的信息素，于是蚂蚁群体更加倾向于走这一路径，并留下的信息素。于是，这种正反馈效应随着时间慢慢放大。如果时间足够长，这种现象会导致所有蚂蚁最终都选择某一条路径。这种自身催化或者正反馈的过程，实际就是蚂蚁群体实现自组织行为的一个例子，这种宏观模式（蚂蚁群体倾向于选择某一条路径）的出现来自于微观层面的过程与交互作用。在这个实验中，蚂蚁的微观行为可以解释蚂蚁群体集中于一条路径的宏观现象。蚂蚁在觅食过，感知周围环境的变化并进行信息传递，从而调整自身的群体行为。12第四组 蚁群算法应用及改进研究图 3.1 双桥实验（1）及其实验结果在

25、 Gross 等人（1989）的实验中20，两桥的长度不一样，较长的一条为较短的一条长度的两倍，也就是说两桥的长度比设定为 2:1（如图 3.2（a）所示）。这个实验的结果显示，经过一定的时间以后，大部分的蚂蚁会选择较短的一桥进行觅食，小部分的蚂蚁会选择较长的一桥进行觅食。其可以解释为：在觅食的最初期，蚂蚁随机选择觅食途径，因此较长一桥和较短一桥选择概率相等，然而当蚂蚁发现两桥的长度差别后，便更倾向于走更短的路径，从而迅速的在较短路径上留下浓度很高的信息素，强化了蚁群的正反馈行为。由于较短路径上信息素浓度积累得比较长路径要快得多，因此大多数蚂蚁在选择路径会选择较短路径，形成了如图 3.2（b）

26、所表现的现象。与双桥实验（1）相比，双桥实验（2）觅食初期随意波动的影响大大减小，起作用的主要是媒介质、自身催化和差异路径长度等机制。值得注意的是，虽然较长路径远长于较短路径，但仍有一部分蚂蚁会选择较长路径，蚂蚁这种不依据信息素浓度进行路径选择的行为称为路径探索，对蚁群优化模型的建立有着不容忽视的作用。图 3.2 双桥实验（2）及其实验结果在几年后，Dorigo 和Stutzle（2004）21考虑到另一种情况：如果在蚂蚁集中于某一条13第四组 蚁群算法应用及改进研究觅食路径后在添加一条新的路径，那么蚁群的行为会发生怎样的变化？他们在双桥的基础上，进行了附加实验。他们在实验初期只提供一条较长的

27、觅食路径，在 30 分钟以后再添加一条较短路径（如图 3.3（a）所示。有趣的是，在出现新的较短路径后，蚂蚁群体并没有选择较短路径，而是仍然选择原来的较长路径，如图 3.3（b）所示。实验者对此的解释为：由于长路径上信息素浓度过高，而信息素蒸发又太慢，即使有蚂蚁进行路径探索，但较短路径的信息素浓度仍远远低于较长路径，从而使大部分蚂蚁个人仍然选择较长分支而不选择较短分支。图 3.3 双桥实验的附加实验及其结果在双桥实验后，Deneuborug 和他同事尝试用数学方法解释在实验中观察到的蚁群现象，提出了一个简单的随机模型，形成了蚂蚁系统和蚁群系统的雏形。假设信息素挥发（实验进行的时间很短，故可不考

28、虑信息素挥发的情况）。设和是第只蚂蚁经过某一桥后在A 桥和 B 桥上已经经过的蚂蚁数，那么第 + 1只蚂蚁选择分支A 的概率为( + ) = ( + ) + ( + )( 1.1)同时，这只蚂蚁选择分支B 的概率为：( + ) = ( + ) + ( + )( 1.2)显然，有 + = 1，也就是说这只蚂蚁必然需要在两个分支中选择一个。这两个公式要表达的现象很简单：以往走分支 A 的蚂蚁越多，正在选择路径的这种蚂蚁选择分支 A的概率就越大。而蚂蚁数量对蚂蚁路径选择的影响，是通过信息素浓度来实现的。在模型中，信息素的浓度的影响又是通过参数和来的。表示公式的非线性程度，值越大，信息素浓度差别的影响

29、就越大。当值很大时，两分支上信息素浓度些微的差距就会导致选择高信息素浓度路径的蚂蚁数量远大于低浓度路径。表示进行随机选择程度，值越大，蚂蚁越忽略信息素对选择的作用。当值相对于蚂蚁数量达到无限大时，所有蚂蚁都以 1/214第四组 蚁群算法应用及改进研究的概率选择两条分支。Liu 采用蒙特卡罗方法对此系统进行了模拟，证实了模型对实验描述的有效性。值得注意的是，在这个模型中，蚂蚁在前往觅食和返回巢穴的过都会信息素。Deneubourg进行的实验也证明了，这是蚁群集中到较短路径的必须方式，如果蚂蚁仅仅在前往觅食或返回巢穴的过信息素，那蚁群是无法找到巢穴与的最短路径的。2.人工蚂蚁双桥实验向人们展示了蚂

30、蚁群内在的搜寻最短路径的能力，于是人们尝试去设计一种人工蚂蚁，使之在类似双桥系统的图上移动并寻找最短路径。例如，考虑一个静态连接图 = (，)，如图 3.4 所示，其中表示节点集合，它的绝对值为节点数量，表示连接中节点的边的集合。引入蚁群使之在这个连接图中进行路径搜索，寻找从源节点（蚁巢）到目的节点（源）目的的最短距离。在这个例子中，粗线表示的路径即为蚂蚁找到的最短路径。图 3.4 蚂蚁在静态连接图中找到的最短路径解在蚂蚁路径搜索能力的基础上，人们开始试图开发人工蚂蚁。然而人们发现，仅仅对自然界中的蚂蚁进行模仿存在很大的缺陷：由于蚂蚁在进行路径选择时依据的是信息素，蚂蚁本身对路径的长短并没有直

31、观预见。因此，如果在搜索初期的随机选择中蚂蚁选择了较差的路径解（如形成环路）而这个被强化，那么由于正反馈作用，这个较差解的路径上会积累越来越多的信息素从而使得蚂蚁群体集中于这个较差路径解。究其根本，这个问题是由蚂蚁群体信息素的正反馈作用即信息素的正向更新引起的。然而，如果只是去掉信息素的正向更新而只保留信息素的逆向更新（信息素的挥发），蚂蚁群体将15第四组 蚁群算法应用及改进研究只遵循随机搜索而无法获得最短路径。因此，解决这个问题的关键是赋予人工蚂蚁一些不同于自然蚂蚁的能力，建立一个有效的信息素更新机制。人工蚂蚁的这种智能首先表现为一种记忆力，它们可以把所有已经被搜的路径的长度都记住，然后使人

32、工蚂蚁具备对路径的评估比较能力，从而排除较差的解（如距离较长的路径或包含了较好路径的环路路径），而在较好的信息素。此外，由于人工蚂蚁具备了评估比较能力，因为可以根据解的质量决定在路径上的信息素的量。另一个问题是如何利用蚂蚁的路径探索能力，使蚂蚁在一定程度上搜索“较差”的路径，避免过分重复搜索已有的路径和解的过早收敛。为此，可以引入现实中自然蚁群也具有的信息素挥发现象，使得所有路径上的信息素以一定的速度挥发，降低被搜多的路径上的信息素，从而让其他路径有更大的概率被蚂蚁选择。在解决了这两个问题后，便可以根据以下几个关键模块建立人工蚂蚁系统：蚂蚁的路径搜索行为：在静态连接图中，蚂蚁在节点以一定的概率

33、选择下一个节点，建立一个局部解。选择概率的大小取决于可选择的节点间信息素浓度的大小。蚂蚁完成多次节点选择后一个完整搜索和行进的过，蚂蚁不信息素，即没有直接的信息素正向更新。在搜索的初期，每条边都被赋予一定数量的信息素，蚂蚁开始搜索路径。此时第只蚂蚁处于第个节点选择作为下一个节点的概率为： = (3.3) 0其中，为蚂蚁在节点上可以选择的相邻节点的集合。蚂蚁依据这个概率在每一个节点做出路径选择，直至形成从蚁穴到源的完整路径。然后，蚂蚁会凭借人工赋予的智能对解的性能进行评估，如果当前经过的路径的解较好，则在回蚁穴的途中信息素，这也使蚁群表现为信息素反向更新。信息素更新机制：蚂蚁在到达源后，会沿原路

34、返回蚁穴，并根据路径解的性能一定量的信息素。设更新的信息素的量为，则信息素的更新机制可以简单描述为： + (3.4)从式（3.4）可以看出，一旦有蚂蚁经过某条路径，那么该路径上必然会增加一定量的信息素。的选择通常设定为所经过路径长度的函数，所经过的路径越短，更新的信息素越多。信息素挥发机制：自然蚁群系统也有信息素挥发现象，但是对于蚁群路径探索行为的促16第四组 蚁群算法应用及改进研究进作用并不明显。与此不同，人工蚁群的信息素挥发强度可以进行人工，因此信息素挥发强度可以进行人工，因此信息素的挥发机制在人工蚁群系统中有着重要的作用。人工蚁群系统中，信息素的挥发和信息素的是交互进行的。与信息素的不同

35、，在所有路径山信息素的挥发量是一样的。信息素的这个挥发机制可以描述为： (1 ) (，) (3.5)其中 (0，1，表示挥发系数。每个周期（例如一只蚂蚁完成一次搜索）每条边都会挥发相同量的信息素。3.人工蚂蚁系统特点人工蚂蚁系统的建立，一方面参照并借鉴了真实蚂蚁系统的特性，是在观察和实验的基础上对真实蚂蚁觅食行为的一种抽象。人工蚂蚁和真实蚂蚁有以下的一些共同点：（1） 人工蚂蚁和真是蚂蚁一样，通过互相合作完成任务人工蚂蚁和真实蚂蚁的能力都很不出色，但是却能够通过群体的相互合作完成无法完成的工作，如觅食等。它们的行为受群体内其他行为的影响，同时影响着其他的行为，而它们这种相互影响、相互合作的行为

36、的目的，是完成群体的共同的任务，如觅食。（2） 人工蚂蚁和真实蚂蚁一样，以信息素作为媒介人工蚂蚁和真实蚂蚁一样，在选择路径的时候可以感知别的蚂蚁遗留在道路上的信息素浓度，同经过的道路上一定量的信息素，新的信息素起到了道路上信息素更新的作用。这种信息素更新的机制是蚂蚁系统的关键，形成了信息素的正反馈效应，使蚂蚁渐渐集中于某些路径，也使蚁群算法具有收敛性。（3） 人工蚂蚁系统和真实蚂蚁系统一样，都存在信息素挥发现象真实蚂蚁系统中，信息素会随着时间自然挥发，这种现象造成了蚂蚁的路径探索行为。由于这种行为有利于搜索不同路径，防止过早收敛，因此在人工蚂蚁系统中人为建立了信息素挥发机制，定期在所有路径上挥

37、发相同量的信息素。（4） 人工蚂蚁和真实蚂蚁一样，都通过基于概率决策的局部行为完成任务人工蚂蚁和真实蚂蚁一样，在进行路径选择是根据路径上的信息素浓度进行概率型决策，某一段路径上的信息素浓度越大，被蚂蚁选中的概率就越大。所有分支路径又组成了蚂蚁的整个路径，即通过局部路径搜索完成整个路径的搜索。（5） 人工蚂蚁系统和真实蚂蚁系统一样，都具有自组织特性17第四组 蚁群算法应用及改进研究人工蚂蚁群体和真实蚂蚁群体都没有者，每个蚂蚁单独行动就能够使群体完成复杂的任务，并且保证群体有序运转。蚂蚁系统的这种自组织性使蚁群算法具有易于等特点。另一方面，为了便于算法模型的建立、增加算法的柔性、增强算法的性能，人

38、工蚂蚁又被赋予了一些特殊的智能使以完成一些真实蚂蚁难以做到的行为：（1） 搜索行为的差别真实蚂蚁是在现实的三维世界中进行连续的爬行；人工蚂蚁是在抽象画的二维地图中进行搜索，而人工蚂蚁的行为是在节点间的离散的跃迁。（2） 信息素更新机制的差别真实蚂蚁在行进的同时不断着信息素，并且在前进和返回的途中都在信息素；人工蚂蚁在前进过程不信息素，只在返回的途中信息素，并且信息素的是在瞬间完成的。此外，人工蚂蚁得到了可以解的质量的人工智能，所以信息素的大小与解的质量有关；真实蚂蚁无法解的质量，对所有路径都信息素。在人工蚂蚁系统的基础上，Dorigo 提出了蚁群算法。概括起来，蚁群算法具有以下特点：（1） 全

39、局搜索能力强使用相互作用的蚂蚁群体进行搜索，使获得最优解的概率增加。蚂蚁搜索时基于概率决策而不是确定型决策，使得解空间较大，所有路径都有可能被找到。（2） 算法适应性强蚁群算法对搜索空间没有特殊要求，可以应用于非常多种类型的问题。此外，由于任务是由群体完成的，所以单个蚂蚁不工作对群体行为造成影响。（3） 易与其他算法相结合蚁群算法的搜索时逐步完成的，因此可以方便的在每一步或每完成一次搜索后与其他算法或其他优化策略组合，如与正向逆向调度结合。此外，由于存在启发式信息，蚁群算法获得初始解的能力较随机生成初始解的算法更强，与其他算法结合可以获得较好的结果，例如使用蚁群算法迭代若干次后作为遗传算法的初

40、始解进行交叉，变异等操作。（4） 容易出现过早收敛现象蚁群系统中信息素的正反馈现象有着正反两面性，一方面使蚂蚁可以集中于某路径即保证算法的收敛性，另一方面，容易使蚁群过早陷入某些较差解或次优解。信息素挥发可以在18第四组 蚁群算法应用及改进研究一定程度上弥补这个缺点，此外也可以在算法中引入改进措施进行弥补。而在引入改进措施后，蚁群算法往往得到了较高质量的解，但牺牲了其收敛速度，最终另一，即收敛速度过慢。（二） 蚁群算法基本模型在人工蚂蚁系统的基础上，Dorigo 提出了最早的蚁群算法蚂蚁系统，大部分蚁群算法都是以蚂蚁系统为原型的。蚁群系统可以应用于许多问题，对应不同的问题，蚁群算法的数学模型的

41、表现形式并非完全相同。旅行商问题作为一个组合优化难题是蚂蚁系统最早应用的问题，而且他是一个最短路径问题，与蚁群的觅食行为非常相似，因此，为了解释蚁群首先借由旅行商问题（TSP）给出蚂蚁系统的数学模型。然后介绍算法的基本模型，蚂蚁系统解决旅行商问题的实现方法。1.蚂蚁系统数学模型旅行商问题可以描述为：在 = (，)的途中，为节点即城市的集合，为连接节点的无向连接弧即连接两两城市的道路，已知 = 个城市两两之间的距离，求一条路径使得旅行商依次经过每个城市一次且总路程最短。首先定义符号：表 3.1 TSP 蚁群算法符号表值得注意的是，启发信息是人工蚂蚁智能的又一体现。自然蚂蚁在搜索初期对途径没有任何

42、偏好，只是纯粹的依靠概率进行搜索。为了提高人工蚂蚁的效率，蚂蚁系统引入了启发信息即从城市移动到城市的启发程度，事实证明这对算法效率的提高特别是初始量的提高有非常重要的作用，nij通常依据问题性质而认为决定，不随着蚁群的移动而改变。例如，在TSP 问题中，一般设定 = 1 ，路径的长度越短，初期拥有的信息越多。蚂蚁系统的数学模型的建立与最初的人工蚂蚁相似，也是通过蚂蚁的路径搜索行为、信19符号说明m蚁群中蚂蚁的总数()时刻位于城市的蚂蚁的个数城市和城市之间的距离路径(，)的能见度，即为启发信息路径(，)上的信息素强度，即信息素信息蚂蚁在路径(，)上的信息素量蚂蚁从城市移动到城市的概率第四组 蚁群

43、算法应用及改进研究息素更新机制和信息素挥发机制等几个关键模板构建。蚂蚁的路径搜索行为：在网络图 = (，)中，蚂蚁在节点以一定的概率选择下一个节点，建立一个局部解，多个局部解一个完整解。选择概率的大小取决于可选择的节点间信息素浓度的大小。当第( = 1，2， ，)只蚂蚁处于节点时，它选择节点作为下一个目的节点的概率为： () () () ()() =(3.6)0其他情况其中，为蚂蚁在节点上可以选择的相邻节点的集合。从式（3.6）可以看出，蚂蚁选择下一个节点的概率同时受启发信息和信息素信息影响，而这个影响的大小则受参数和。和分别反映了启发信息和信息素信息在蚂蚁选择中的相对重要性。此外，为了达到旅

44、行商问题的每个城市只能经过一次的要求，蚂蚁们还会建立一个已经达到过的城市的集合，这个类似表的集合使得蚂蚁选择到达过的城市，它在选择中的作用通过来体现，即表中的城市会自动从中排除。信息素更新机制：与真实蚂蚁在行进的同时信息素不同，人工蚂蚁只在完成完整的路径搜索后，根据这个路径的质量决定的信息素的量，并在返回途中沿原路。在算法模型中，信息素的是瞬间完成的。蚂蚁系统信息素的更新机制可以通过下式表现：( + ) = () + (， + )(3.7)=1其中， (， + )表示第只蚂蚁在完成从到的路径后在路径(，)上的信息素，它的大小根据完整路径的质量而定，路径越短，的信息素越多，可以表示为： 0如果(

45、，)在路径上否则(3.8) (， + ) = 其中，为一正常数，表示第 k 只蚂蚁完成的完整路径的长度，即中所有边的长度之和。显然，蚂蚁在路径(，)上的长度。的信息素大小取决于(，)所在的完整路径信息素挥发机制：在信息素更新的同时，人工蚁群同样有类似自然蚁群信息素挥发现象，他的作用是平衡信息素的累计，扩大蚂蚁的搜索范围，避免蚂蚁过早的集中于某些路径，有助于获得最优解。蚂蚁系统的信息素挥发机制可以通过下式表现：20第四组 蚁群算法应用及改进研究( + 1) = (1 )()(3.9)其中，为信息素的挥发率，与信息素更新需要在完成整个路径的搜索之后进行不同，信息素的挥发与蚂蚁的行为无关，仅仅根据挥

46、发率随时间挥发。2.蚁群系统算法的实现以旅行商问题，顺序构建为例，即只有在一只蚂蚁获得一条完整路径并完成信息素更新后，下一只蚂蚁才开始搜索，蚂蚁系统算法的实现步骤可以表示为：（1）初始化相关参数，如蚂蚁数目、算法终止条件及和的值等；（2）将蚂蚁随机或均匀分布到各个城市；（3）蚂蚁通过概率选择进行路径搜索，并将每一步的城市列入列表中；（4）当某只蚂蚁完成了一次完整的路径搜索后，更新信息素；（5）当所有蚂蚁完成了搜索，是否满足算法终止条件；（6）重复 2-5 的过程直至满足算法终止条件，终止算法。根据以上步骤，TSP 问题的 AS 算法流程图可以表示为：是图 3.5 蚂蚁系统算法流程图21终止算法

47、满足算法终止条件？否是所有蚂蚁完成了搜索？否更新信息素第k只蚂蚁完成搜索分配蚂蚁初始化参数第四组 蚁群算法应用及改进研究（三） 后续系统在蚂蚁系统（AS）算法出现之后，Dorigo22根据的不同，发展出了三种不同的模型，分别称为蚁（antcycle system）、蚁量系统（ant-quantity system）和蚁密系统（ant-density system）。这三种算法是蚂蚁系统的直接后续算法，可以说是基本蚂蚁系统的不同表现形式，但也存在一些差别。1. 蚁蚁基于顺序构建的方法构建解，即一只蚂蚁完成一次完整的路径搜索后才根据该解的质量对该路径进行信息素更新。蚁的信息素更新机制如下所示：/，

48、如果(，)在路径上0，否则 (， + ) = (5.1)其中，为一正常数，表示第只蚂蚁完成的完整路径的长度，即是中所有边的长度之和。显然，蚂蚁在路径(，)上的信息素大小取决于(，)所在的完整路径的长度。2. 蚁量系统蚁量系统与蚁的差别在于信息素更新的方式，它的更新方式如下所示：/，如果蚂蚁经过(，) (， + 1) = (5.2)0，否则其中，为一正常数，为路径(，)的长度。从该式可以看出，蚁量系统的信息素更新方式是随着蚂蚁的行进不断逐步进行的。蚂蚁每完成一次节点的选择，即蚂蚁完成一段的行进，就根据这段路径的质量（路径的长度）息素就越多。信息素，路径的长度越短，获得的信3. 蚁密系统蚁密系统与

49、蚁周和蚁量系统的差别也在于信息素的更新方式，它的更新方式如下所示：，如果蚂蚁经过(，) (， + 1) = (5.3)0，否则其中，为一正常数。从式中可以看出，蚁密系统信息素的与蚂蚁经过的路程长度无关，也就是说，蚂蚁在它经过的每段路径都相同量的信息素。三种蚂蚁系统算法的最主要区别在于信息素的更新方式。后两种系统中，蚂蚁每完成一中，蚂蚁只有在走完个城市22段路径都会更新信息素浓度，利用的是局部信息；而蚁第四组 蚁群算法应用及改进研究后信息素浓度，利用的是整体信息。1996 年，Dorigo5等对这三种算法进行了比较，结果是蚁比其他两种算法有更好的性能。此后的研究主要基于蚁而进行，而蚁也通常被直接叫做蚂蚁系统，其他两种算法基本已被遗弃。（四） 蚁群算法改进算法蚂蚁系统在解决一些小规模的 TSP 问题时的表现尚可令人满意。但随着问题规模的扩大，蚂蚁系统很难在可接受的循环次