硕士论文：基于TSP问题的蚁群算法优化及并行策略研究

《硕士论文：基于TSP问题的蚁群算法优化及并行策略研究》由会员分享，可在线阅读，更多相关《硕士论文：基于TSP问题的蚁群算法优化及并行策略研究（103页珍藏版）》请在装配图网上搜索。

1、学校代码：10491 研究生学号：12003566中国地质大学硕士学位论文基于TSP问题的蚁群算法优化及并行策略研究硕 士 生：张 礼学科专业：计算机应用技术指导教师：罗忠文 副教授二六年五月A Dissertation Submitted to China Universityof Geosciences for the Degree of Master of EngineeringThe Research on Optimization andParallelization Strategies of Ant Colony Algorithmfor Solving Traveling Sa

2、lesman ProblemMaster Candidate：Zhang LiMajor：Computer Application TechnologySupervisor：Associate Prof. Luo ZhongwenChina University of GeosciencesWuhan 430074 P. R. China研究生学位论文原创性声明我以诚信声明：本人所呈交的硕士学位论文是在罗忠文副教授的指导下，开展研究工作所取得的研究成果。文中关于TSP问题的蚁群算法新的优化策略是在罗忠文老师的指导下独立完成；算法运行数据结果、为确定各个关键参数的分析及其设定数据系本人研究和测试

3、所得；文中蚁群算法的并行策略及算法的展望系本人独立完成，不包含他人研究成果。所引用他人之思路、方法、观点、认识均已在参考文献中明确标注，所引用他人之数据、图件、资料均已征得所有者同意，并且也有明确标注，对论文的完成提供过帮助的有关人员也已在文中说明并致以谢意。学位论文作者签字：签字日期： 年 月 日作者简介张礼，男，1979年9月出生，2000年7月本科毕业于上海交通大学热能工程及其自动化专业，2003年9月进入中国地质大学武汉攻读计算机应用技术专业硕士学位。在读研期间，主要学习了算法设计与分析、高级计算机体系结构、组合数学、Visual C+、科学社会主义、自然辩证法、英语含专业英语等十几门

4、课程，总学分34.5分，平均分为84.7分。在攻读硕士学位期间，曾在武汉中地数码科技股份教育部GIS工程中心进行实习，参与了多个软件工程的开发，主要从事国土资源部门基于MAPGIS平台的应用软件的研发，参与开发的工程有：湖南省衡阳市国土资源局国土资源电子政务系统、基于MAPGIS并内嵌RedOffice的公文流转开发等。2005年5月份，开始进入蚁群算法领域，并研究算法的优化及并行策略。在校期间，已发表论文十余篇，其中核心期刊一篇；以第一作者身份发表的论文主要有：一局部公开期刊从略1、基于MAPGIS工作流及RedOffice的公文流转开发. 商场现代化核心期刊. 2005年9月号，第20期总

5、第443期.2、电子政务开展现状及策略分析. 中国学术论坛. 2005年第1期.3、蚁群算法的一种优化策略. 知识与创新. 2005年第11期.4、Oracle应用系统性能优化. 学位理论版. 2005年第2期.5、用SVG技术实现基于Web的GIS. 知识与创新. 2005年第11期.6、GML、VML和SVG的比拟. 经营与管理增刊. 2005年增刊第082号.7、下一代网络NGN标准概述. 知识与创新. 2006年第2期.基于TSP问题的蚁群算法优化及并行策略研究硕士生：张礼 导师：罗忠文 副教授摘 要许多实际工程问题可以抽象为相应的组合优化问题，TSP问题是作为所有组合优化问题的范例而

6、存在的，它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法可以求解出TSP问题的最优解；但是对现有的计算机来说，让它在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的算法应运而生了，本文所描述的蚁群算法AC也在其中。目前已出现了很多的启发式算法，而蚁群算法作为一种新型的启发式算法，已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度，同时按照路径上的信息素浓度来选择下一步的路径：好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径；最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反响原理正是

7、整个算法的关键所在。首先，本文简要介绍了几种启发式算法并引出蚁群算法，并对蚁群算法根本原理、几种算法模型和相应的数学公式作了详细阐述，同时对前人的研究结果进行了引用；此外针对蚁群算法的缺陷，还描述了前人对算法所作的一些典型的优化：如蚁群系统算法ACS也称蚁群优化算法ACO、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。然后，文章对蚁群算法中的关键参数的设置进行了深入的研究。对参数、m的作用作了理论上的研究，对它们的最优化配置进行了分析；同时针对以往参数设定的不便，提出了一种全新的、比拟适当的参数设置方案：通过将蚁群算法的参数设置问题描述成均匀设计中多因素多水平的试验设计，它能用较少的

8、试验很快设置出参数值，并可使蚁群算法获得较优的运行性能。接着，本文提出了建立在蚁群系统算法ACS根底上的一种新的优化策略：采用新方案进行关键参数设置，以克服以往的参数设置困难、不准确的缺点；通过引入遗传算法中用到的杂交算子，使前面蚂蚁所留信息素尽量少对后面的蚂蚁产生误导，增强算法的搜索能力；通过全局最小信息素浓度的设置，来扩宽算法的搜索空间；采用更高效的信息素更新和路径选择机制，以加快算法的收敛速度，使其更容易收敛到全局最优解。并对该优化策略进行了初步实验，证明了其有效性和可行性，也为蚁群算法的优化提供了一个新途径。在此之后，文章对蚁群算法的并行策略进行了初步的探讨，深入分析了两种不同的并行策

9、略：同步策略和局部异步策略；另外，还提出了一种新的模式学习并行蚁群算法，并对它进行了具体的介绍。最后，本文对改进后的蚁群算法、以及蚁群算法的并行策略进行了总结性的阐述；同时对蚁群算法的进一步优化提出了自己的设想：引入种群入侵算子也叫外变异算子、权函数等；并对蚁群算法的研究前景进行了展望。关键词：TSP问题；蚁群算法；关键参数设置；优化策略；并行策略The Research on Optimization andParallelization Strategies of Ant Colony Algorithmfor Solving Traveling Salesman ProblemMaste

10、r Candidate：Zhang Li Supervisor：Prof. Luo ZhongwenAbstractMany actual engineering problems can be regarded as combination optimization problems，and TSPTraveling Salesman Problem is a typical combination optimization problem，it has become and will continue to become a standard problem to test a new a

11、lgorithm of combination optimization. Theoretically speaking，the enumeration can get the best answer of TSP；but to all computers nowadays，it is hardly to obtain the best answer in such huge researching space by using common enumeration. So all kinds of algorithms emerged because of demand，the ant co

12、lony algorithmAC described in this paper is one of them.Presently many heuristic algorithms appeared，and AC algorithm is a class of heuristic algorithms that have been successfully applied to solving TSP. Ants reinforce pheromone intensities of better paths by excreting chemical substancenamely pher

13、omone，synchronously they select next paths according to pheromone intensities：more ants will select better paths，and more pheromones will be laid over better paths；at last all ants will focus on the best path. This is a form of behavior called autocatalytic behavior，it is the key to the success of A

14、C algorithm.Firstly，this paper introduces briefly several heuristic algorithms and educes AC algorithm，expounds fundamental、several models、corresponding mathematic formula，synchronously refers to other investigation conclusion；also describes some typical optimizations aiming at shortcomings of AC al

15、gorithm：for example，ant colony system algorithmACS，namely ACO、max-min ant system algorithmMMAS、ant colony system algorithm with mutation features etc.Then，the paper investigates the settings of important parameters about AC algorithm. Study theoretically the functions of parametersviz. 、m，analyses t

16、heir optimum settings；at the same time，it presents a kind of scheme：uniform design method is used to convert the problem of parameter establishment into experimental design of multi-factor and multi-level，it can obtain conveniently all parameters，and shows good performance effectiveness.Afterwards，a

17、 new optimization strategy based on ACS algorithm is provided：a new method is used to set important parameters for overcoming former defects；a crossover operator used in genetic algorithm is contained in the optimization strategy for increasing researching ability of algorithm；setting the minimal ph

18、eromone intensity for expanding researching space；adopting new pheromone updating and path selecting methods for quickening constringency speed of algorithm. In addition，we demonstrate the feasibility and efficiency of new optimization strategy by means of experimental study，and also provide a new a

19、pproach of optimization about AC algorithm.Whereafter，the parallelization strategies of AC algorithm are discussed，and analyze two kinds of parallelization strategies：synchronous parallel algorithm and asynchronous parallel algorithm；moreover，recommend concretely a new algorithm：parallel model-learn

20、ing AC algorithm.Finally，this paper summarizes the improvements and parallelization strategies of AC algorithm；and provides synchronously my own imagination about the farther optimization of AC algorithm：introducing reproduction in-break operatornamely external mutation operator；furthermore，indicate

21、s the investigation future of AC algorithm.Key Words：Traveling Salesman Problem；Ant Colony algorithm；Settings of important parameters；Optimization strategies；Parallelization strategies目 录第一章 绪 论11.1 引 言11.2 本文的研究内容11.2.1 蚁群算法的根底性理论研究21.2.2 蚁群算法的优化策略研究21.2.3 蚁群算法的并行策略研究21.3 本文的创新之处21.4 本文的组织3第二章 蚁群算法

22、根底理论42.1 TSP问题简介及其解法42.1.1 TSP问题的定义及传统解法42.1.2 现代启发式算法42.2 蚁群算法概述52.2.1 群体智能简介52.2.2 蚁群算法的定义52.2.3 蚁群算法的根本原理62.2.4 算法的数学模型表述72.2.5 蚁群算法的伪码表述92.2.6 蚁群算法的实验结果102.3 蚁群算法的特征及优缺点112.3.1 算法特征112.3.2 算法的优点112.3.3 算法的缺陷112.4 蚁群算法已有的改进及优化策略122.4.1 蚁群系统算法ACS122.4.2 最大最小蚁群系统算法MMAS132.4.3 具有变异特征的蚁群算法13第三章 蚁群算法中

23、关键参数的设置153.1 各个关键参数的介绍及设置153.1.1 启发式因子153.1.2 信息素残留度173.1.3 蚂蚁总个数m183.2 基于均匀设计的关键参数设置193.2.1 传统的参数设置方法的缺陷193.2.2 基于均匀设计的关键参数设置19第四章 蚁群算法优化的一种新策略234.1 蚁群算法优化的理论根底234.1.1 路径选择机制234.1.2 信息素更新机制234.2 蚁群算法优化的新策略244.2.1 算法优化的初步设想244.2.2 优化的途径在已有改进型算法ACS的根底上244.2.3 优化后的算法描述27实验及结果分析29第五章 蚁群算法的并行策略315.1 蚁群算

24、法的两种并行策略315.1.1 同步的并行策略315.1.2 局部异步的并行策略325.1.3 两种并行策略的比拟335.2 蚁群算法并行的新策略355.2.1 算法的根本思想355.2.2 模式的获取365.2.3 模式学习并行蚁群算法描述36第六章 结论与展望386.1 结 论386.1.1 蚁群算法优化策略386.1.2 蚁群算法并行策略386.2 展 望396.2.1 对优化策略的展望396.2.2 对并行策略的展望39致 谢40参考文献41第一章 绪 论1.1 引 言优化问题是人们在改造世界时经常会遇到的一类普遍问题，人们日常生活中对自己行为的指导实际上就是对某些利益的最大化过程：当

25、我们考虑一个优化问题时，目标就是要得到最好的可能的解，即最优解。组合优化问题是最常见的优化问题之一，许多实际工程问题可以抽象为相应的组合优化问题，如：集成电路的综合布线、电信网络路由、网络导航、交通网络中的最正确路径选择等问题。TSP问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。传统解法对小搜索空间的TSP问题适用，而且有的算法获得精确解的性质也正是人们所期望的。一般说来，这些方法有：迪杰斯特拉dijkstra算法、弗诺伊德Floyd算法、其它的算法如局部搜索的梯度法等。但传统算法仅能运用于小问题集，因为随着问题集增大，算法时间复杂度也会呈现指数级

26、的增加，使我们不能在有效的时间内完成任务，所以它们并不具推广性。于是许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法AC是由意大利学者Macro Dorigo等人在20世纪90年代提出来的1，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS也称蚁群优化算法ACO、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，

27、但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。1.2 本文的研究内容本文的研究内容可以概括为三局部，即：蚁群算法的根底性理论、蚁群算法的优化策略、蚁群算法的并行策略。而蚁群算法的优化策略研究这局部内容，又可以划分为两个子块，即：蚁群算法关键参数的设置和在ACS算法

28、根底上所作的改进。1.2.1 蚁群算法的根底性理论研究这局部内容主要是讨论几种启发式算法并深入蚁群算法领域，对它的根本原理、几种算法模型和相应的数学公式作具体了解，同时对前人的研究成果进行引用；此外针对蚁群算法的缺陷，还会研究前人对算法所作的一些典型的优化：如蚁群系统算法ACS也称蚁群优化算法ACO、最大最小蚁群系统算法MMAS、具有变异特征的蚁群算法等。1.2.2 蚁群算法的优化策略研究这是研究的第二局部内容，它又可以划分为两个子块，即：蚁群算法关键参数的设置和在ACS算法根底上所作的改进。1.2.2.1 关键参数的设置这一块内容属于优化策略研究的一局部，它对关键参数、m的作用作理论上的探讨

29、，对它们的最优化配置进行分析；同时针对以往参数设定的不便，尝试提出一种全新的、比拟适当的参数设置方案，使蚁群算法获得较优的运行性能。1.2.2.2 在ACS算法根底上所作的改进这一子块属于优化策略研究的另一局部内容，也是优化策略研究的最核心、最重要的局部。它将提出建立在蚁群系统算法ACS根底上的一种新的优化策略，并通过对该优化策略进行初步实验来证明其有效性和可行性。1.2.3 蚁群算法的并行策略研究这局部内容将对蚁群算法的并行策略进行初步的探讨，深入分析两种不同的并行策略：同步策略和局部异步的策略；另外，还会提出一种新的并行策略模式学习并行蚁群算法，并会对它进行具体的介绍。1.3 本文的创新之

30、处本文的创新之处主要在蚁群算法的优化策略研究这一局部。具体的说，可以分为两点：一是提出了一种对关键参数、等进行合理设置的方案；二是设计了一套基于ACS算法根底上的优化策略，它对原ACS算法的诸多方面进行了改进。这些创新也为蚁群算法的优化提供了一个新的途径。另外，创新之处在蚁群算法的并行策略研究这局部也有表达，主要是在蚁群算法中引入了一种模式学习并行策略。1.4 本文的组织本文共分为六章，其章节组织如下：第一章为绪论，引出TSP问题和蚁群算法，并简要介绍本文的研究内容、创新之处及全文的组织；第二章详细介绍蚁群算法的根底性理论及其相关的概念、术语，包括算法已有的、典型的优化策略分析；第三章对算法参

31、数、m的作用及其设置进行了理论研究，并提出了相关的参数设置方案，以克服以往参数设置困难、不准确的缺点。第四章对算法的优化策略进行了研究，描述了算法的一种新优化策略，它在ACS算法的根底上作了许多的改进，并对其实现过程中遇到的相关难点和重点进行了讨论，同时对该优化策略进行了实验来证明其有效性和可行性。第五章主要讨论了蚁群算法两种不同的并行策略，并具体介绍了一种新的模式学习并行蚁群算法。第六章对全文的研究内容及成果进行了总结，并提出了对进一步研究工作的设想与展望。第二章 蚁群算法根底理论2.1 TSP问题简介及其解法2.1.1 TSP问题的定义及传统解法TSP问题的英文名为traveling sa

32、lesman problem，中文译为货郎担问题，或旅行商问题。它的定义很简单：即一个货郎要走访n个城市，每个城市必须经过一次且只能经过一次，最后回到出发的城市就算完成了一次旅行，问如何能找到一条最短的路径。TSP问题是作为所有组合优化问题的范例而存在的，它已成为测试新算法的标准问题。TSP问题又可分为对称的TSP问题和非对称的TSP问题ATSP两种，从A点到B点的距离与从B点到A点的距离相比拟，假设距离总相等那么为对称的TSP问题，否那么为非对称的TSP问题。如果它俩的数据结构用图来表示，那么前者是一个无向图，后者是一个有向图；假设用邻接矩阵来表示的话，那么前者是一个对称阵，而后者是一个非对

33、称阵。TSP问题的传统解法可分为两类：一类为全局搜索法，另一类为局部搜索法。全局搜索法可以方便地运用于小搜索空间的TSP问题，而且它所获得的是精确解，此类方法如：迪杰斯特拉dijkstra算法：求从某个节点到其余各节点的最短路径；弗诺伊德Floyd算法：求每对节点间的最短路径。而局部搜索法，它在局部搜索中，由当前的解求得下一个的可能解下一代解，并比拟下一代解和当前解的关系，选取较好者取代当前解，从而反复迭代，它所获得的是局部最优解，此类方法如：梯度法和不动点法。梯度法计算函数的梯度或近似值，然后朝梯度方向进行搜索；不动点法先构造辅助函数，然后再进行迭代，从而发现不动点来获得最终的解。由于算法时

34、间复杂度的原因，全局搜索法不适于大搜索空间的TSP问题；而局部搜索法，它为防止陷入局部最优，扩大邻域的大小是必然的，但随着邻域增大，对于NP难度问题，算法的复杂性也会呈现出指数次方的增加。综上所述，传统方法虽然有其可供学习借鉴的地方，但它不适用于大搜索空间的TSP问题，推广性较差，我们需要另外的新方法来克服传统方法的缺陷。2.1.2 现代启发式算法针对传统解法的缺点，具有较强鲁棒性的现代启发式算法出现了，它不仅适用于TSP问题，而且还可适用于许多其它的问题，这样的性质显然更适合实际问题处理，其推广性很强。NP难度问题的时间复杂度是不能改变的，因此现代启发式方法把重点放在了防止局部优化上，比拟典

35、型的启发式算法有：模拟退火算法、禁忌算法、基于群体的算法等。模拟退火算法Simulated annealing是一个典型的启发式算法，算法中有当前点Vc，根据该点评价其邻域中的某一点Vn，如果Vn较好，那么用其代替Vc；否那么会按照概率p来替换Vc。其中：p = e-f(Vn)-f(Vc)/T公式2-1；该概率公式由晶体结晶的物理过程得到，其与初始值无关，算法求得的解与初始解状态S算法迭代的起点无关。模拟退火算法具有渐近收敛性，已在理论上被证明是一种收敛于全局最优解的全局优化算法，而且具有并行性。而禁忌算法，它在每次迭代中，也是由某当代点的邻域来得到下一代最优可能点；不同的是，该算法保存有一个

36、禁忌表，在禁忌表中出现的点不允许出现在下一代点中，这样就可以避兔算法陷入局部最优。基于群体population的算法是又一种很重要的启发式算法，该类算法属于概率算法，候选解作为群体中的个体被保存下来。例如：演化算法、粒子群算法以及下文即将介绍的蚁群算法都属于这类算法。2.2 蚁群算法概述2.2.1 群体智能简介在某群体中假设存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为群体智能Swarm Intelligence。群体中的简单个体是指具有简单能力如搬运、通信等的个体，这种能力可以用某一简单的功能函数来表示；简单合作是指个体只能与其邻近的个体进行某种简单的协同动作如几

37、只蚂蚁共同搬动一个物体，或通过改变环境间接的与其它个体之间进行简单通信如一只蚂蚁将信息素留在环境中，为其它蚂蚁提供了一种可选择路径的信息。群体智能是近年来人工智能研究的一个热点课题，它对于没有集中控制并且不提供全局模型的问题，提供了一种复杂的分布式解决方案。科学家们受社会性昆虫群体智能的启发，通过对其行为的模拟，已得出了一系列用于解决传统复杂问题的新方法，蚁群算法便是其中很具有代表性的一种。2.2.2 蚁群算法的定义20世纪90年代，意大利学者M.Dorigo等人在新型算法研究的过程中，通过模拟自然界蚂蚁的觅食过程：即通过信息素pheromone的相互交流从而找到由蚁巢至食物的最短路径，提出了

38、一种基于信息正反响原理的新型模拟进化算法蚁群算法Ant Colony algorithm。蚁群算法是继遗传算法、人工神经网络等算法之后的又一种启发式算法，它的根本原理借鉴了这样一个客观事实：蚂蚁由自组织的合作能力所产生的群体智能来寻找路径，它被认为是用于解决组合优化问题的又一种新方法。2.2.3 蚁群算法的根本原理蚁群算法的根本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不兴旺，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化如原有路径上有了障碍物后，自适应地搜索新的最正确路径。蚂蚁是如何做到这一点的呢？原来，单个的蚂蚁为

39、了防止自己迷路，它在爬行时，同时也会释放一种特殊的分泌物信息素Pheromone，而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多当然，随着时间的推移会逐渐减弱，后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程，其原理是一种正反响机制。这里我们可以用一个图来说明蚂蚁觅食的最短路径选择原理，如图2-1所示。图2-1 蚁群觅食原理如图2-1a所示，我们假设A点是食物，而E点是蚂蚁的巢穴，当A、E两点间没有任何障碍物阻挡时，蚂蚁不存在路径选择的问题，这种情况最简单：由于两点间直线距离最

40、短，蚂蚁们搬运食物时，会以直线的形式往返爬行。但在图2-1b中的情形有所变化，假设某时刻突然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，那么从A点到E点的蚂蚁就必须在B点决定应该往左还是往右走，而从E点到A点的蚂蚁也必须在D点决定选择走哪条路径；这种决定会受到各条路径上以往蚂蚁留下的信息素浓度即残留信息素浓度的影响。如果往右走的路径上的信息素浓度比拟大，那么右边的路径被蚂蚁选中的可能性也就大一些；但是对障碍出现后第一个到达B点或D点的蚂蚁而言，因为没有信息素的影响，所以它们选择向左或者向右的可能性是一样的，b图所表示的正是此时的情况。假设以从A点到E点的蚂蚁为例进行说明对于从E点到A

41、点的蚂蚁而言，过程也根本是一样的，由于路径BCD比路径BHD要短，因此选择BCD路径的第一只蚂蚁要比选择BHD的第一只蚂蚁早到达D点；此时，从D点向B点看，路径DCB上的信息素浓度要比路径DHB上的信息素浓度大。因此从下一时刻开始，从E点经D点到A点的蚂蚁，它们选择DCB路径的可能性要比选择DHB路径的可能性大得多，从而使路径BCD或DCB上信息素浓度与路径BHD或DHB上信息素浓度的差变大；而信息素浓度差变大的结果是选择路径BCD或DCB的蚂蚁进一步增加，这又导致信息素浓度差进一步加大。如图2-1c所示，随着时间的推移，几乎所有的蚂蚁都会选择路径BCD搬运食物，而我们同时也会发现：BCD路径

42、也正是事实上的最短路径。这种蚁群寻径的原理可简单理解为：对于单个的蚂蚁来说，它并没有要寻找到最短路径的主观上的成心；但对于整个蚁群系统来说，它们又确实到达了寻找到最短路径的客观上的效果。在自然界中，蚁群的这种寻找路径的过程表现为一种正反响的过程，与蚁群算法中人工蚁群的寻优算法极为一致。例如，我们把只具备了简单功能的工作单元视为“蚂蚁，那么上述寻找路径的过程可以用于解释蚁群算法中人工蚁群的寻优过程。2.2.4 算法的数学模型表述蚁群算法又可分为三种不同的类型，分别称之为：ant-cycle system、ant-quantity system、ant-density system，它们代表着三种

43、不同的数学模型，它们三者的差异主要在于蚂蚁对信息素更新的方式不同下文我们会讨论到它们具体的差异。在求解TSP问题时，为了充分利用整体信息，一般采用ant-cycle system，本文所采用的也是ant-cycle system模型。2.2.4.1 人工蚁群与自然界蚁群的异同在蚁群算法中的人工蚁群和自然界蚁群的相似之处在于，两者优先选择路径的机制相似，都是优先选择“信息素浓度较大的路径，都会造成较短的路径上聚集比拟多的信息素的结果；另外，两者信息传递的方式相同，它们的工作单元蚂蚁都是通过在其所经过的路径上留下一定信息的方法来进行间接的信息传递。而人工蚁群和自然界蚁群的区别在于，人工蚁群具有一定

44、的记忆能力，它能够记忆已经访问过的节点；另外，人工蚁群具有一定的算法规律，它在选择下一条路径的时候，并不像自然界蚁群那样是完全盲目的，而是按照相应的数学公式有意识地寻找最短路径如在TSP问题中，可以预先知道下一个目标的距离。2.2.4.2 两个重要的数学公式：路径选择机制与信息素更新机制下面我们以蚁群算法的ant-cycle system模型为例，来详细阐述算法中蚂蚁的路径选择机制和信息素更新机制。在给出数学公式之前，先引入如下的符号：设n为TSP问题的城市节点的个数，m为蚂蚁群体的总数目；diji，j=1、2、n表示由节点i到节点j的有向距离；ijt表示t时刻ij路径上残留的信息素，在初始时

45、刻各条路径上的信息素相等，可设ij0=cc为一初始值常量。蚂蚁kk=1、2、m在运动过程中，会根据各条路径上的信息素浓度大小来决定它自己下一步要转移的城市节点，S表示在t时刻蚂蚁k由节点i转移到城市节点j的概率即人工蚁群路径选择的数学公式：S = ij(t)ij / jallowedij(t)ij 假设jallowed或 = 0假设jallowed公式2-2；其中，ij表示由城市节点i转移到节点j的期望程度，称之为期望值，它可以根据某种启发式算法及问题的情况来确定，这里我们认为ij=1/dij；、分别表示蚂蚁在运动过程中选择城市节点i、j间的这条路径时，城市i、j间所积累的信息素和距离的相对重

46、要性权重，分别称之为信息启发式因子即和期望值启发式因子即，也叫能见度；而allowed表示蚂蚁k下一步允许选择的城市节点集合，由于与自然界蚁群不同，人工蚁群是具有记忆功能的，我们可设集合tabuk用以记录蚂蚁k当前已经走过的节点tabuk将随着蚂蚁的搜索进程而作动态的调整，那么allowed=1、2、n-tabuk。随着时间的推移，以前留在路径上的信息素会逐渐消逝挥发掉，假设用参数表示信息素的残留程度那么1-表示信息素的消逝程度，经过n个时刻蚂蚁完成一次循环，各条路径上的信息素要根据下面公式作全局调整即人工蚁群信息素更新的数学公式：ijt+n = ijt+ijt，t+n公式2-3；其中，ijt

47、+n表示在t+n时刻ij路径上所积累的信息素；ijt，t+n表示在t至t+n时刻内所有蚂蚁完成一次循环后所有经历ij路径的蚂蚁留在ij路径上的信息素增量；由ijt，t+n的定义出发，我们很容易得到它的计算公式：ijt，t+n = ijkt，t+n公式2-3-1；公式2-3-1是公式2-3的子公式，它其中的ijkt，t+n表示在t至t+n时刻内所有蚂蚁完成一次循环后第k只蚂蚁留在ij路径上的信息素增量。而对于ijkt，t+n的计算，不同的蚁群算法模型有不同的数学公式，由于本文采用的是ant-cycle system模型，这里先介绍ant-cycle system模型下的ijkt，t+n的计算公式

48、：ijkt，t+n = Q / Lk(t，t+n)假设蚂蚁k在本次循环中经过ij路径或 = 0假设蚂蚁k在本次循环中未经过ij路径公式2-3-1-1；前面说过，公式2-3-1是公式2-3的子公式；而这里的公式2-3-1-1又是公式2-3-1的子公式，也可以说，它算得上是公式2-3的孙公式了。公式2-3-1-1中，Q表示单个蚂蚁循环一周所释放信息素的总量，其值为一常量；而Lk(t，t+n)表示第k只蚂蚁在本次循环中所走路径的总长度，其值为它所走各路段的距离之和。2.2.4.3 蚁群算法三种数学模型的区别蚁群算法有三种数学模型：ant-cycle system、ant-quantity syste

49、m、ant-density system，它们的路径选择与信息素更新的机制根本相同，其差异主要在于信息素更新的局部的规那么有所不同；具体地说，就是ijkt，t+n的数学计算公式有所不同。在ant-cycle system模型中，ijkt，t+n的计算公式见公式2-3-1-1。在ant-quantity system模型中，ijkt，t+n的计算公式为：ijkt，t+n = Q / dij假设蚂蚁k在t至t+1时刻间经过ij路径或 = 0假设蚂蚁k在t至t+1时刻间未经过ij路径公式2-3-1-2而在ant-density system模型中，ijkt，t+n的计算公式为：ijkt，t+n =

50、Q假设蚂蚁k在t至t+1时刻间经过ij路径或 = 0假设蚂蚁k在t至t+1时刻间未经过ij路径公式2-3-1-3这里我们可以看出，后两种模型中利用的是局部信息，而ant-cycle system模型利用的是整体信息，在求解TSP问题时性能也较好，因而人们一般采用它作为根本模型。2.2.5 蚁群算法的伪码表述根据上述讨论，我们可以编写出根本蚁群算法的程序，其伪码表述如下：Begin初始化：用邻接距阵初始化图，设置各边上初始信息素之值；t0；/t被设为时刻值。iteration0；/设iteration为迭代步数。将m只蚂蚁随机置于m个节点上；/说明：由于是随机放置，此m个节点允许重复，即多只蚂蚁

51、可置于同一节点。Loop： 将所有蚂蚁的初始出发点置于各自的当前解集中；/当前解集为各蚂蚁的tabu list表，用数组表示。for i0 to n-1 dofor k0 to m-1 do按路径选择机制公式2-2所算得的概率来选择下一个节点j；移动蚂蚁k至节点j；将节点j置于蚂蚁k的当前解集中；end fort+；end for计算各蚂蚁的多个目标函数值；/这里是指用全局更新规那么公式2-3来更新各边上的信息素值。更新当前的理想解，得到迄今为止最好的周游路径，并将其记录到一数组MIN中；t+；重置所有当前解集-1；/就是将tabu list表数组表示全都置为-1，好为下一次迭代作准备。ite

52、ration+；假设iterationq0公式2-4；其中，q为一个在区间0，1内的随机数，服从均匀分布；q0是一个参数常量0q01，例如可取q0=0.8；而S是根据公式2-2来确定的。由上述公式确定蚂蚁转移到哪个城市的方法就是伪随机概率选择规那么pseudo-random proportional rule。在这种规那么下，每当蚂蚁要选择向哪个城市转移时，就产生一个在0，1范围内的随机数，根据这个随机数按公式2-4来确定用哪种方法产生蚂蚁转移的方向，然后用对应的方法产生转移方向。2.4.1.2 ACS的全局更新规那么在ACS中，全局更新不再用于所有蚂蚁，而是只对每一次循环中最优的蚂蚁使用，它

53、在所有蚂蚁完成一次循环后执行；更新规那么可用如下公式表示：ijt1-ijt+ijt公式2-5；其中，为区间，上的参数；而ijt那么用如下的公式计算：ijt= Q/L假设ij路径是算法已求出的最优路径的一局部或 = 0假设ij路径不是已求出的最优路径的一局部公式2-5-1；这里的公式2-5-1是公式2-5的子公式，其中的Q表示单个蚂蚁循环一周所释放信息素的总量，其值为一常量；而L为算法运算到当前为止，已求出的最优路径的长度。2.4.1.3 ACS的局部更新规那么局部更新规那么在所有蚂蚁完成每一次转移后执行，其更新公式为：ijt+1=1-ijt+ijt，t+1公式2-6；其中，为区间，上的参数；而

54、ijt，t+1的计算那么有三种选择：ijt，t+1=0公式2-6-1；ijt，t+1= cc为初始时刻信息素浓度值，为一常量公式2-6-2；ijt，t+1=maxjallowedijt公式2-6-3；这里的公式2-6-1、2-6-2、2-6-3均为公式2-6的子公式，其中，局部更新规那么的子公式采用公式2-6-3的ACS算法也被称为Ant-Q System算法，由前述的介绍可知，它其实与强化学习算法很相似。2.4.2 最大最小蚁群系统算法MMAS德国学者Thomas Stuzle和Holger Hoos提出的一种改进的算法最大最小蚁群系统算法Max-Min Ant System，MMAS，它是

55、一个比拟好的算法，在解决TSP、QAP等问题时结果要优于一般的蚁群算法3。MMAS与ACS两者的共同点是在算法的每次迭代中只允许表现最好的蚂蚁更新路径上的信息素；其不同之处主要在于如何防止过早的停滞现象Stagnation。MMAS限定了信息素浓度允许值的上下限，并且采用了平滑机制，MMAS在算法启动时将所有支路上的信息素浓度初始化为最大值max，每次迭代后，按信息素残留度降低信息素素浓度，只有最正确路径上的支路才允许增加其浓度，并保持在高水平上。但是，仅仅采用最大最小信息素浓度的限制还缺乏以在较长的运行时间里消除停滞现象，因此采用了平滑机制：信息素浓度的增加正比于max和当前浓度ijt之差。

56、2.4.3 具有变异特征的蚁群算法具有变异特征的蚁群算法是由吴庆洪等人提出来的4。其核心思想是为了克服蚁群算法收敛较慢的问题，采用逆转变异方式，随机地进行变异，以增大进化时所需的信息量；这种变异机制充分利用了2-OPT交换法简洁高效的特点，因此具有较快的收敛速度。我们设某蚂蚁个体所走路径为：i0i1i2in-1,i0、i1、in-10，1，2，n-1，如果满足dis1is2+dis1+1% nis2+1% n dis1is1+1% n+dis2is2+1% n，其中：s1、s20，1，n-1，符号%表示整除符号；那么进行操作：inversions1，s2，solutioni，函数inversion的功能是把个体solutioni的s1+1和s2这一段颠倒过来，如：