《改进的混合型蚁群算法及其应用硕士学位论文.doc》由会员分享，可在线阅读，更多相关《改进的混合型蚁群算法及其应用硕士学位论文.doc（47页珍藏版）》请在三一办公上搜索。
1、分类号： O157 单位代码：10110 学 号：s20110075中 北 大 学硕 士 学 位 论 文 改进的混合型蚁群算法及其应用 xxx华北改进的混合型蚁群算法及其应用 硕士研究生 孙晶 指导教师 xxx 教授 学科专业 应用数学 年 月 日图书分类号 O157 密级 非密 UDC 510 硕 士 学 位 论 文改进的混合型蚁群算法及其应用 孙 晶 指导教师（姓名、职称） xxx 教授 申请学位级别 理学硕士 专业名称 应用数学 论文提交日期 年 月 日 论文答辩日期 年 月 日 学位授予日期 年 月 日 论文评阅人 答辩委员会主席 年 月 日摘 要 旅行商问题（TSP）与车辆路径问题（
2、VRP）自提出以来，许多学者进行了大量的理论研究和实验分析，取得了非常显著的进展，已经成为了运筹学和组合优化问题领域的热点研究问题。求解他们的算法主要有精确型算法、近似算法和启发式算法。在众多求解TSP算法中，蚁群算法具有较好的性能，该仿生智能算法和传统的算法截然不同，具有鲁棒性、正反馈、并行性和易与其他方法相结合等特点。自创立以来，无论理论研究还是在应用方面都取得了突破性的进展，不但在求解以上两种问题上得到了最优解，而且在工件的排序问题、图着色问题、多目标函数等许多领域也取得了相当不错的效果，具有相当广阔的发展前景。本文首先介绍了一种求解TSP问题的算法改进的混合型蚁群算法，该算法在近邻法构
3、造初始解的基础上，使用2-opt局部搜索法对当前解进行改进，在更新全局信息素时采用基于排序的蚂蚁系统对排在前2名的蚂蚁更新全局信息素，且为全局信息素设置最大值和最小值，并使用MATLAB仿真求解了kroa200等13个经典TSP问题。通过仿真实验可以看出本文改进的算法在求解TSP问题时具有很好的效果，在求解很多问题时已经非常接近最优解或者优于最优解，和最优解相差的百分比基本都在1%以下，并和两种最新改进的蚁群算法以及两种自组织算法进行比较，比较结果充分证明了该改进算法的有效性。其次，本文利用文献提出的统计边数的方法对TSP问题的种群多样性进行了分析，通过实验仿真与基本蚁群算法从平均的边数和、最
4、大的边数以及最小边数和进行了比较分析，从数据上说明了改进的算法具有种群多样性。 最后又把改进的混合型蚁群算法应用到VRP问题，使用MATLAB仿真工具对N44K6等10个经典VRP问题进行了求解，得到的结果和已知最优解的误差很小，都在6%以下，并且N33K6问题得到了和已知最优解相同的解。并且与基本蚁群算法做了比较，比较结果充分证明了该改进算法的有效性。关键词：混合型蚁群算法，TSP问题，种群多样性，VRP问题 AbstractMany scholars have been a lot of theoretical research and experimental analysis sinc
5、e Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) are proposed and notable progress is made. TSP and VRP have become the central issue in operational research and combinatorial optimization. Precise algorithm, approximate algorithm and heuristic algorithm are used to solve the pro
6、blems. Among all the algorithms, ant colony algorithm has better performance. This bionic intelligence algorithm is quite different from the traditional ones, its more robust, positive feedback, concurrency and easy to combine with other algorithms. Since ant colony algorithm is proposed, breakthrou
7、gh progress has been made both in theoretical research and realistic application. Not only optimal results are achieved but also proven to be effective in scheduling jobs, graph coloring, multi-objective function and other scopes. It has a very broad prospect.In this paper, a mixed ant colony algori
8、thm is introduced firstly. The algorithm is based on the traditional ant colony system algorithm, construct an initial result using the nearest neighbor method and then improve the results using 2-opt partial search strategy, and update the global pheromone for the best two colonies with a maximum a
9、nd minimum constraint. The simulation using MATLAB for the classic kroa200 and other twelve TSP problems showed us very good results. All the results have deviations less than 1 percent compared to the best-known results and some problems even achieved better results. In this paper, I also compared
10、the results to two updated ant colony algorithms and two self-organization algorithms, the better results indicated us our mixed ant colony algorithm is a better one. Afterwards we used a method of counting the sum of the route edges to measure the population diversity of our algorithm. Then we comp
11、ared the population diversity of our improved mixed algorithm and the base ACO algorithm. The result shows our algorithm has higher population diversity which gives us a theory support why our algorithm can achieve best result than ever known.Then we applied the algorithm to VRP. We simulated the cl
12、assic N34K6 and other nine VRP problems using the MATLAB tool, the results of which have small deviations compared to the best-known results. All the deviations are all smaller than 6 percent. And we got the result same as the best-known result for N33K6. In this paper, I also compared the results t
13、o the results of the base ant colony optimization algorithm; the better results indicated us our mixed ant colony algorithm is a better one to solve the VRP.Key words: Mixed Ant Colony Algorithm, TSP, population diversity, VRP目 录摘 要 Abstract 第一章 绪论11.1 引言11.2 TSP问题11.2.1 TSP问题的提出11.2.2 TSP问题研究现状21.3
14、 VRP问题31.3.1 VRP问题的提出31.3.2 VRP问题的研究现状51.4 本文主要研究的问题61.5 本文的结构安排7第二章 蚁群算法82.1 蚁群算法综述82.2 蚁群算法的基本思想92.2.1 蚁群系统解决TSP的基本步骤102.2.2 蚁群算法参数的控制选择112.3 基于排序的蚂蚁系统122.4 MAXMIN蚂蚁系统132.5 小结14第三章 改进的混合型蚁群算法及其在TSP中的应用153.1 改进策略153.1.1 局部搜索法153.1.2 2-opt算法153.1.3 改进的混合型蚁群算法163.2 改进的蚁群算法求解TSP问题173.2.1模拟结果及比较173.2.2
15、 结论233.3 改进的蚁群算法求解中国旅行商问题233.3.1 中国旅行商问题描述233.3.2 模拟结果及比较243.3.3 结论273.4 改进的蚁群算法的多样性分析273.5 小结29第四章 改进的混合型蚁群算法在VRP中的应用304.1 求解VRP问题的算法流程304.1.1 求解VRP与求解TSP的不同点304.1.2 求解VRP的程序流程图304.2模拟实验结果及比较334.3小结37第五章 总结与展望375.1本文的研究内容总结375.2本文的不足与展望385.2.1 改进算法的不足385.2.2 展望38参考文献40攻读硕士期间所取得的研究成果45致 谢 第一章 绪论1.1
16、引言随着现在信息技术和网络技术突飞猛进的发展人们不断探索新知的欲望越来越强烈，而大自然是进行人类探索发现的钥匙。科学家们通过观察社会动物像蚁群、鱼群以及鸟群等的自组织行为，利用数学建模及计算机仿真对这些种群进行了研究和实验，从而产生了现在大家所知道的“群体智能”（Swarm-Intelligence，简称SI）1。其中，人工蚁群算法2就是受到大自然真实蚂蚁的启发，通过观察蚂蚁在从巢穴到食物源觅食行为过程而发展起来的。蚂蚁是一种群居性生活的动物，社会结构和分工明确，他们通过释放信息素来搜索最短路径，蚂蚁在运动过程中能够感知这种物质的存在及强度，并借此来引导自己的行动方向，浓度越高吸引的蚂蚁就越多
17、，经过一段时间的搜索，个体间通过这种信息的交流最终达到搜索食物的目的。蚁群算法正是模拟了这样的优化机制，即通过个体之间的信息交流与相互协作最终找到最优解3。蚁群算法是来自生物界的随机优化搜索方法，目前已经在很多领域表现出相当好的性能，他的正反馈机制和协同效应可用于分布式计算，其并行性也具有超强的发展潜能。在求解著名复杂的优化问题旅行商问题（Traveling Salesman Problem）上取得成效以后，其应用已经逐渐渗透到各个领域，比如车辆路径问题(Vehicle Routing Problem)4,5、工件的排序问题6、图着色问题7,8等。不仅如此，它的求解问题的领域也在不断地扩大，对
18、一些约束性问题和多目标问题产生了深远的影响。无论从理论研究还是应用价值方面来看，它都是一种很有途的优化算法。前本文主要是介绍改进的混合型蚁群算法在TSP问题和VRP问题的应用。1.2 TSP问题1.2.1 TSP问题的提出TSP问题是组合优化问题中最典型的问题，最早在1759年由欧拉提出9。欧拉是在研究的骑士周游问题时进行描述的，国际象棋棋盘有64个方格，每一个方格只允许走一次，且所有方格都走一次后返回到起始的方格。TSP在图论意义下常常被称为最小Hamilton圈问题，它可以描述为：给定M个城市及他们相互间的距离，某一旅行商从一个城市出发按照一定的先后顺序访问每个城市，这里要求每个城市必须且
19、只需被访问一次，最后回到出发城市，安排路线的过程中要考虑如何使所行走的路程距离最短。下面我们用数学的语言进行描述10：记G=(V,E)为赋权图，V=(1,2.,n)为顶点集，E为边集，各顶点间的距离dij已知(dij 0，dii=，i，jV)。设 则TSP问题可用如下的数学模型来表示： 这里|S|是集合S中所含图G的顶点数。第一个约束条件和第二个约束条件表示对每个点来说，仅有一条边进和一条边出；第三个约束条件是为了确保没有任何子回路解的产生。因此，满足前三个约束条件的解就构成了一条Hamilton回路。当dij=dji（i,jV）时，被称作是对称TSP问题。当对所有，有不等式成立时，被称为是满
20、足三角不等式的，简记为TSP。1.2.2 TSP问题研究现状由于TSP问题是NP-完全难问题，要想找到一个非常有效的的求解方法还是众多学者需要探索的问题。当然目前求解TSP问题的算法也很多，比如研究者曾试图使用精确型算法求解，但由于该算法属于指数级算法，所以随着规模的不断增大，所需的时间太长，使精确法变得不可能。后来研究者提出使用近似算法或启发式算法进行研究，并且融合多种方法成为研究主流。求解TSP问题的方法可以总结为以下几种11：(1)使用线性规划、动态规划、分支定界等精确算法。(2)使用最近邻、插入式、最小树、r-opt等启发式算法和迭代算法。(3)使用蚁群算法、模拟退火算法、遗传算法、神
21、经网络算法和粒子群算法等仿生自然算法。鉴于蚁群算法等智能优化算法经常停止于局部最优解而得不到最优解，因此研究者将蚁群算法和局部搜索算法结合起来得到混合型算法，混合型算法是一种有效求解TSP问题的方法和方向。TSP问题是众多领域中出现的优化问题的集中概括和简化形式，是各种启发式算法的间接比较标准12，也就是说假如提出的一个算法在求解TSP问题是有效的，那么在其他类型的组合优化问题上稍加修改也将会取得良好的性能，因此，该算法已经成为了测试新的算法或算法间进行比较的标准问题，具有重大的理论研究意义。又由于很多领域的NP难题问题都可以归结为TSP问题，所以它也具有一定的实际应用价值，比如在车辆路径规划
22、问题、邮路问题、装配线路的螺母问题等等都得到了研究者的广泛关注。所以说，TSP问题的有效求解问题仍将具有重要的意义。1.3 VRP问题1.3.1 VRP问题的提出近几年来，随着电子商务的崛起，互联网在国民经济中发挥着越来越广泛的作用，并不断地影响和改变着人们的生活方式，网上购物现已经成为了一种趋势，与此同时，现代化的物流业也受到了广泛的重视，VRP是物流配送优化中关键的一环，是提高物流经济效益，实现物流科学必不可少的，也是管理科学的一个重要研究课题 13，车辆路径的合理选择,可以提高对客户的服务质量，增强客户满意度，降低服务运营成本。自该问题的提出以来，不仅引起了应用数学、运筹学、计算机等各领
23、域的学者关注，也得到了许多管理者和运输策划制定者的极大重视。所以在新的环境下，为了更好的把握好现代物流的发展趋势，对VRP问题的研究是非常有必要的。1.3.1.1 VRP问题的概述VRP问题可以描述为：在满足一定限制条件（如长度、时间和容量等）下，根据客户的不同需求，由配送中心设计从一个或多个起始点出发，计划适当的行车路线，使运送车辆有序的通过，到达多个不同的城市或客户的最优路径分配，以达到诸如路径最短、成本最低、耗时最小等目的，图1.1是VRP问题的形象示意图。配送中心 图1.1 VRP示意图1.3.1.2 常见的约束条件1) 容量限制。虽然每一个城市都有一定的需求量，但是任何车辆所承载的总
24、重量都不能超过该车辆的能力负荷。这种VRP问题被称为容量约束的车辆路径问题（简称 CVRP）。2) 总长限制。每一个路径长度（或时间）不允许超过给定的常数，此长度有城市之间的旅行时间与在城市的逗留时间。我们把这种带有路长或时间限制的VRP称为DVRP。3) 时间窗限制，它包括硬时间窗和软时间窗的限制，主要是指某一城市必须在所规定允许的时间段内被访问、逗留，这种VRP问题被称为时窗限制的车辆路线问题（简称VRPTW）。4) 两城市间的优先关系：城市i必须在城市j之前被访问。CVRP问题是实际应用中最为广泛和最为基本的一类问题，研究CVRP问题对优化物流配送具有十分重要的意义。本文研究的对象就是C
25、VRP问题，对于这种经典的VRP问题，在本文中将简称为VRP14。1.3.1.3 VRP问题的数学模型在VRP问题中，客户对货物的需求数量、每个客户位置的地理坐标都是已知的，每辆车的承载能力是固定的。假设每一个客户只能被访问一次，每辆车所访问的城市的需求总和不能超过车辆的负载能力，并且所使用的车辆数量是固定的。现要使所有的客户都被满足且总运送成本最小。设： 则VRP问题的数学模型可以描述为15,16: 其中约束（a）为车辆负载限制，约束（b）保证每辆车对每个客户只访问一次，约束c -e保证形成回路。参数为距离，为个客户需求量，D为单车载重量。 1.3.2 VRP问题的研究现状国外是从上世纪60
26、年代就开始研究VRP问题的，我国国内对VRP问题的研究起步比较晚，1994年才有第一篇关于VRP问题的研究论文在正式期刊上发表17。随着电子商务的崛起和物流越来越受到人们的重视，国内研究VRP问题的人也越来越多。从论文的研究内容来看，大部分论文都是讨论如何能够有效的求解VRP问题。从目前求解VRP问题的算法来看，主要有精确算法、近似算法以及智能优化算法18,19。1.精确算法。精确算法是在严格的数学理论和方法的基础上，可以求出最优解的算法，它的解通常要优于智能优化算法。它包括分枝定界法、割平面法、网络流算法、动态规划算法等。虽然该算法求解比较精确，但因为采用了严格的数学手段，一般情况下，随着问
27、题规模的逐渐增大计算量通常呈指数型增长，所以无法避免指数爆炸的难题，从而使得该算法在求解中小规模的确定性VRP问题是有效的，且通常这些算法都是针对某一特定问题设计的,适用能力相对较差,因此在实际应用中受到限制。2.近似算法。由于精确法的局限性，所以在求解大规模VRP问题上寻找到求解比较理想的可行解的近似算法是必要和现实的。近似算法主要是通过搜索解空间中部分有限的子空间，以达到在有限的时间内找到质量较好的解，因此，在实际应用要更加广泛。近似算法主要包括两类算法：一类是OBraysy and MGendrean提出的路径构造算法20，另一类是Thangiah提出的两阶段法21,尽管近似算法能够在有
28、限的时间里求出比较满意的解，但由于其搜索解空间能力的有限性，也经常很难达到预期的目的。 3.智能优化算法。智能优化算法是用启发式原理代替精确算法里的决策准则，从而缩小搜索解空间的范围。它的思想是从某一初始解开始，通过对当前解进行不断地局部调整来达到预期的效果。目前，最常见的智能化启发式算法包括蚁群算法、禁忌搜索算法22、遗传算法23、神经网络24及模拟退火算法25等。总体上来说，蚁群优化算法能够较好的求解VRP问题，但是当问题的规模变大时，蚁群优化算法的运行时间较长且易陷入局部最优解。因此，利用蚁群优化算法易于和其他算法结合的特点，本文将蚁群优化算法和局部搜索策略相结合来求解VRP问题。1.4
29、 本文主要研究的问题本文首先针对ASC易陷入局部最优等缺点对蚁群系统提出了改进，并用TSP问题进行了模拟实验，且与几种自组织算法进行了比较，得到了比较好的解，证明了算法的有效性。其次，把改进的算法应用到了中国旅行商问题，对实验结果进行了详细地分析，并且对改进算法通过统计边数的方法对TSP问题的种群多样性进行了分析，通过实验仿真与基本蚁群算法从平均的边数和、最大的边数以及最小的边数和进行了比较分析，从数据上说明了改进的算法具有种群多样性。最后，为了进一步验证算法的有效性，把改进的算法应用到了VRP问题，对十个典型的VRP问题进行了模拟实验，并与基本蚁群算法进行了比较，得到理想的结论。1.5 本文
30、的结构安排本文论文共分为六章，各章节的主要内容结构安排如下：第一章：概述了TSP问题和VRP问题产生的背景、数学模型、解决问题的模型和研究现状，并指出了本文的主要研究问题和论文结构安排。第二章：在介绍基本蚁群算法原理及数学模型的基础上，给出了以TSP问题为例的蚁群系统的算法流程，分析了蚁群算法的重要参数对蚁群算法性能的选择控制，并对国内外蚁群算法的研究现状进行了总结与概括，还重点介绍了两种典型、有效的改进的蚁群算法：最大最小蚂蚁系统和基于排序的蚂蚁系统。这些基本理论与思想为第三章提出的改进策略奠定了基础。第三章：详细地介绍了一种改进的混合型蚁群算法，在ASC的基础上主要提出了三处改进：加入了2
31、 -opt算法；基于排序的思想：对排在第一和第二的蚂蚁进行信息素的更新；为了防止程序陷入停滞，给全局信息素设置最大值和最小值。并且以典型的TSP问题和中国旅行商问题进行了模拟实验，证明了算法的有效性，除此之外，还对改进算法的多样性进行了详细的分析。第四章：介绍了改进的混合型蚁群算法在10个典型的VRP问题中的应用，并详细地介绍了算法的流程。第五章：对本文的主要内容做了总结，并对蚁群算法的研究做了展望。第二章 蚁群算法2.1 蚁群算法综述蚁群算法（AS）是由意大利学者Dorigo.M等人26,27 首次在1991年的首届欧洲人工生命会议上提出的，随后又提出了一些改进的蚁群算法，如M.Dorigo
32、等人第一次提出的改进的蚂蚁系统精英蚂蚁系统（EAS），它主要是在开始到当前为止时，对算法所搜索的最优路线释放附加的信息素。1995年，L.M.Gambradella、M.Dorigo提出了用伪随机比例状态转移规则替换AS算法中的随机比例选择规则的Ant-Q算法，引入了局部信息素更新机制和全局信息，避免了过早停滞28。1996年，M.Dorigo等人又发表了“Ant System：Optimization by a Colony of Cooperating Agents”一文29，提出了蚁群系统(ACS)，详细的论述了蚁群算法的原理及其应用。1997年，B.Bullnheimer等人提出了基于
33、排序的蚂蚁系统（RANKBASED AS）30，在所有蚂蚁都走完一遍后，对蚂蚁的路径长度进行排序，只允许排列在最前面的m只蚂蚁和生成最优路径的蚂蚁释放信息素。1999年，T.Stutzle等人提出了最大一最小蚂蚁系统(Max-Min Ant System，简称MMAS)31-33，该算法的主要特点是为信息素设置最大值和最小值，以免某条路径上信息素过多而出现停滞现象。虽然国内对蚁群算法的引入研究开始的比较晚，但是已在几年之间发展成为热点领域。最早在国内介绍蚁群算法的是张纪会博士，发表蚁群算法研究成果的是彭斯俊等；李生红和马良首次在博士学位论文中研究蚁群算法；马良等人在正规学术媒体上发表蚁群算法文
34、献。1999年，吴庆红和张纪会等人34引入2-opt变异机制，提出了具有变异特征的蚁群算法。吴斌和史忠植首先提出了一种基于蚁群算法的TSP问题分段求解算法35，它的思想是把相遇算法与并行策略的分段算法相结合，提高了蚂蚁寻找最优解的质量。为了克服算法易于陷入局部最优解的劣势，王颖和谢剑英提出了一种自适应的蚁群算法36，覃刚力等人通过调整路径上的信息素的变化，提出了自适应调整信息素的蚁群算法37。蚁群算法不仅在理论方面引起国际学术界许多研究学者的重视，在应用方面也得到了广泛关注，使蚁群算法除了应用于TSP问题以外，在其他领域也得到了迅速的扩大。1994年,A coloni等人将蚂蚁系统应用于车间作
35、业调度问题38。1997年，Costa和Herz研究了增强的AS算法，并将该算法运用在求解图的着色问题上39。1999年，V Maniozzo成功地将蚂蚁系统应用于指派问题40，而后Gambardellab又发表了用蚁群系统来解决指派问题的相关论文41。Bullnheimer等人把基于排序的蚂蚁系统应用到求解车辆路径问题上，并得到了和最优解非常接近的结果42。Gambardella对车辆路径问题进行了更深入的研究，得到了比以往更优的解43。2002年，Rafael S.Parpinelli把蚁群算法应用到数据挖掘中44。2003年汪镭、吴启迪45把蚁群算法用于解决系统识别。所以，对蚁群算法理论
36、及其应用的探索定将成为一个长期的研究热点问题，具有更加广阔的科研价值和发展前景。2.2 蚁群算法的基本思想生物学家研究发现，自然界中的蚂蚁觅食是一种群体行为，并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物的过程中，会在其经过的路径上释放一种被称为信息素（pheromone）的化学物质，信息素能够沉积在路径上，并随着时间的推移逐渐挥发。在蚂蚁觅食的过程中能够感知这种物质的存在及其浓度，并根据信息素浓度的高低来选择自己的行动方向，蚂蚁总会倾向于浓度高的方向前进，这样经过蚂蚁越多的地方信息素浓度就会越强，从而后续的蚂蚁选择该路径的可能性就会越大，这样就会形成一种正催化作用。经过一段时间的搜索后，蚂蚁最终
37、可以找到一条从巢穴到食物源的最短路径。Jean Louis Deneubourg及其同事为了验证蚂蚁觅食的特性，在阿根廷进行了实验。实验中Jean Louis Deneubourg及其同事建造了一座有两个分支的桥，其中一个分支的长度是另一个分支的二倍，同时把蚁巢和食物源分隔开来，实验发现，蚂蚁通常在几分钟内就选择了较短的那条分支46。Jean Louis Deneubourg 所建立的模型可以由图2.1模拟。现假设路径“巢穴-ACD-食物”和路径“巢穴-ABD-食物”的长度分别是6和4。蚂蚁的移动速度为1，即在单位时间内可以移动一个单位长度。在开始前所有路径上的信息素都为0。在t=1时，8只蚂
38、蚁从巢穴出发已经移动到了A点。这8只蚂蚁会有一半的蚂蚁选择走AB，另外一半的蚂蚁选择走AC。在t=4时，最先到达食物源的4只蚂蚁将会原路返回。在t=5时，原路返回的4只蚂蚁走到了D点。这时路径BD、CD上的信息素的数量相同。因此2只蚂蚁选择走DB，2只蚂蚁选择走DC。在t=8时，有2只蚂蚁会走回到巢穴中，此时CA、DC、DB上却各有2只蚂蚁。在t=9时，最先回到巢穴的2只蚂蚁再次出发走到A点，这2只蚂蚁将会再次选择是走AB还是走AC。图2.1 蚂蚁从巢穴至食物源的模拟图在t=9时，路径AB上的信息素数量是8而路径AC上的信息素量是6，因此有超过50%的蚂蚁会选择路径A，从而使路径AB上的信息素
39、比AC上的信息素量进一步加大。当蚂蚁觅食的次数不断增多，路径AB上的信息素的量和路径AC上的信息素的量的差距也会越来越大，当觅食的次数无限增大时，所有的蚂蚁都会选择路径“巢穴-ABD-食物”。2.2.1 蚁群系统解决TSP的基本步骤下面以TSP问题为例说明蚁群算法流程47： 1. nc=0(nc为迭代步数或搜索次数)；将各ij和错误！未找到引用源。ij初始化；将m只蚂蚁置于n个顶点上；2将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁k，按伪随机比例规则（2.1）移至下一顶点j；将顶点j置于当前解集； (2.1)其中，J是根据概率公式（2.2）给出的概率分布产生出来的一个随机变量。 (2.2)a
40、llowedk表示蚂蚁k下一步允许选择的城市集合，ij=1/dij。3. 计算各蚂蚁的目标函数值；记录当前的最好解；4. 按更新方程（2.3）修改轨迹强度； (2.3) (2.4)5. 对各边弧（i , j），置nc=nc+1；6. 如果nc预定的迭代次数且无退化行为（即找到的都是相同解），则转步骤2；7. 输出目前最好解。2.2.2 蚁群算法参数的控制选择 算法中参数的选择至关重要，如果选择不当，对算法的适用性影响很大，严重可能导致算法的整体性能变差。以下介绍本文对各参数的选择。1.信息素的重要程度a参数a反映了在搜索过程中，蚂蚁所积累的信息素在指导蚂蚁搜索路径的相对重要性48。如果a的值很
41、大，就表示信息素量越重要，那么蚂蚁选择之前蚂蚁所经过的边就越大，这样搜索的随机性、搜索范围就会减小，从而使搜索易于陷入局部最优解。如果a的值很小，就表示信息素的重要性较低，这说明蚂蚁主要依靠启发式因子来引导搜索。所以a的值不同，算法求解的结果也不同，a值的恰当选择，会使算法取得良好的效果。在文献10中通过实验认为a的取值范围1，2是比较合理的，本文a的取值为a=1。2.信息素挥发系数随着时间的推移，在蚁群算法中，以前蚂蚁所留下的信息素将不断地挥发，参数表示信息素轨迹挥发的重要性，直接影响着算法的收敛速度和全局搜索能力。为了确保残留信息的适应度，的值选取应在0 q0时，算法采用的是随机搜索，当q
42、 q0时算法采用的是确定搜索。显然，当q0较小时，更多的采用随机搜索能够增大搜索空间，提高找到最优解的概率；当q0较大时，更少地采用随机搜索能够快速收敛。因此q0需要选择一个大小适中的值，让算法能够尽可能快的收敛并且能够尽可能的找到全局最优解。通过实验发现，当q0取值在0.7，0.9时，算法具有比较好的性能。本文q0 取值为q0 = 0.9。4.种群的大小m 在搜寻的过程中，蚂蚁表现出的复杂而有序的行为，与群体间的交流协作是分不开的。种群大小直接影响着算法的执行效率和收敛速度，所以种群大小的选取也至关重要，如果m太小，尤其是所选问题规模较大时，会使搜索的随机性减弱，收敛速度加快，易于过早出现停
43、滞现象，不能保证找到最优解；若m太大时，尽管提高了算法的随机搜索能力，增加了找到最优解的概率，但也增加了算法的复杂性，收敛速度减慢。本文中种群数量取m=20。2.3 基于排序的蚂蚁系统基于排序的蚂蚁系统是在蚂蚁系统或精英蚂蚁系统中针对蚂蚁释放信息素的缺点进行改进的。在精英蚂蚁系统和蚂蚁系统中，更新信息素时会对系统中所有的蚂蚁进行信息素的更新，这样，所有的蚂蚁所经过的路径上的信息素浓度差异会越来越小，使得蚂蚁选择出最优路径的可能性变小。为了解决这个问题，基于排序的蚂蚁系统改进如下49：1. 在所有蚂蚁都构建路径以后，把蚂蚁所走的路径按长度大小进行排序，只允许构建至今最优路径的蚂蚁和排在最前面的(
44、m-1)只蚂蚁释放信息素。2. 信息素更新规则如下： 其中，。表示排在前面的第t只蚂蚁所建立的路径的长度，为至今最优路径的长度。 2.4 MAXMIN蚂蚁系统MAXMIN蚂蚁系统是由TStuetzle和HHHoos提出的，由于在蚁群系统中，只允许最优蚂蚁释放信息素，这样一些边上信息素就会过快增加，很容易出现过早的停滞现象。所以最大最小蚂蚁系统提出如下改进思想50：1将信息素浓度值设置在一个区间内。2将信息素的初值设为一个最大值。以便蚂蚁在开始阶段有更大的搜索空间。3在每次迭代过程中，只允许一只蚂蚁进行信息素更新。更新如下：其中，被允许释放信息素的蚂蚁是当前具有最优路径的蚂蚁。当被选择的边由于正反馈机制使得边上的信息素明显高于其他边时，就会出现停滞现象。
