改进的蚁群算法在TSP问题上的应用
摘要：旅行商问题（Traveling Salesman Problem，TSP）是近代组合优化领域的一个典型难题。现实生活中的很多问题都可以转化为TSP问题，如邮路问题、通讯网络设计、大规模集成电路的综合布线设计等。因此，对TSP问题的研究具有重要的理论意义和实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。本文所用到的蚁群算法也在其中。
蚁群算法是受大自然中蚂蚁觅食启发而提出的一种智能仿生算法，具有较强的鲁棒性、分布式计算、易于与其它方法结合等优点。本文提出一种基于模糊集合的改进蚁群算法，该算法根据隶属度对种群进行评价，并依此进行信息素的更新，在求解速度和解的质量上取得一个较好的平衡。通过对改进算法的仿真实验，验证了该算法的可行性及有效性。本文主要的研究工作如下:
1．阐述了论文研究的背景及意义，总结了迄今为止出现的求解TSP问题的各种方法，并对常见的求解方法的优缺点进行了详细的分析，最后，分析了蚁群算法国内外研究现状。
2．给出了蚁群算法的基本原理、算法模型以及特点。
3．提出一种改进的蚁群算法。该算法引入模糊集合的概念，利用隶属度对蚁群寻找到的路径进行模糊评价，并根据模糊评价结果对路径上的信息素进行更新，从而加快了算法收敛速度，提高了算法的性能。 关键词：TSP问题；蚁群算法；组合优化；模糊集合
1
一、绪论
1.1论文选题背景与意义
组合优化问题是运筹学中的一个经典且重要的分支,而在组合优化问题中，旅行商问题（Traveling Salesman Problem，TSP）是近代组合优化领域的一个典型难题。由于TSP问题形式简单、易于描述、且属于典型的NP难问题，因此其作为算法研究与验证的平台而被广泛研究。在TSP问题上取得的理论或者实验成果，可以应用于其他的NP难解问题。事实上，求解NP难问题的许多方法都源自于TSP问题的研究。
TSP问题不但具有很大的理论价值，而且在科学、工程及经济的各方面具有广泛的应用，是诸多领域内出现的多种复杂问题的集中概括和简化形式。如：网络通讯、电路板钻孔、管道铺设、货物配送、交通调度、电网规划等，这些问题或者直接就是TSP问题的原型，或者可以转化为TSP问题。因此，快速、有效地解决TSP问题有着极高的实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法，如遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法等。本文重点研究的是改进的蚁群算法在TSP问题中的应用。
蚁群算法(Ant Colony Optimization,ACO)是一种模仿蚂蚁群体行为的新的智能优化算法。1991年，意大利学者Dorigo M等人首次提出蚁群算法，开始并没受到国际学术界的广泛关注，直到1996年，Dorigo M等人在《IEEE Transactions onSystems,Man,and Cybernetics-Part B》上发表了”Ant system:optimization bya colony of cooperating agents”一文,奠定了蚁群算法的基础。从此之后，蚁群算法逐渐引起了国际学术界的广泛关注。1998年，Dorigo M组织在比利时布鲁塞尔召开了第一届蚂蚁优化国际研讨会，以后每两年召开一次。2000年，GutjahrW J发表了题为“A graph-based ant system and its convergence”的学术论文，对蚁群算法的收敛性进行了证明。同年，Dorigo M和Bonabeau E等在国际顶级学术杂志《Nature》上发表了蚁群算法研究综述，将这一研究推向国际学术界的前沿。
和遗传算法、禁忌搜索算法等智能优化算法相比，蚁群算法具有正反馈性、并发性、易与其它算法相结合等主要特点。这些特点使得蚁群算法的应用非常广泛。如：英国电信公司的电信网络管理试验是基于电子蚂蚁的；英国联合利华公司的生产计划管理软件、美国太平洋西南航空公司的运输管理软件都是基于蚁群算法的。实际上，蚁群算法在诸多的领域都有不俗的表现，如电子系统、控制参数优化、聚类分析、网络路由问题、布局优化等。
总之，蚁群算法已经渗透到多个应用领域，从一维静态优化问题到多维动态优化问题，从离散问题到连续问题。蚁群算法都展现出优异的性能和广阔的发展前景。
1.2 TSP问题简介
TSP问题也称货郎担问题，是一个较古老的问题。最早的记录来自于1759年欧拉研究的骑士周游问题，即对于象棋盘中的64个方格，走访每个方格一次且仅一次。1948年，由于美国兰德公司的推动，TSP问题成为一个知名且流行的问题。它已经被证明属于NP难题。 1.2.1 TSP问题的定义
TSP问题可以简单描述为：给定n个城市(记为：r1，r2，...，rn)和它们
2
两两之间的直达距离(记为：d(ri，rj))，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。即寻找一条巡回路径R?(r1，...，r2，rn)，使得公式(1.1)所示的目标函数最小。
用图论的语言描述为：在一个赋权完全图中，找出一个最小权的哈密顿圈。记G=(V,E)为赋权图，V={1,2,L,n}为顶点集，各顶点间距离
（dij?0，，并设 dij???，i，j?V）dij已知
则TSP的数学模型可写成如下的线性规划形式：
上式中，S为集合S中所含图G的顶点个数。前两个约束意味着对每个顶点而言，仅有一条入边和一条出边，后一约束则保证了没有任何子回路解的产生。满足上述约束的解构成了一条哈密顿回路。
当dij?dji（i,j=1,2,3,L,n)时，称为对称TSP问题。
当dij?dji (i,j=1,2,3,L,n)时，称为非对称TSP问题，或有向TSP问题。 本文探讨的是对称TSP问题的求解。 1.2.2求解TSP问题的智能优化算法
关于求解TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，主要分为三类：精确算法、近似算法以及智能优化算法。常见的精确算法有：整数规划方法、动态规划方法、分支定界算法等。这类算法虽可得到精确解，但计算时间长，实际应用中极少采用。常
3
见的近似算法有：插入算法、r-opt算法和最近邻算法等。这类算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。智能优化方法是近年来发展起来的一个非常活跃的研究领域，主要包括：遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法和粒子群算法等。这类算法虽然不能保证在有限的时间内获得最优解，但选择充分多个解验证后，错误概率可降到可以接受的程度。
1.3蚁群算法研究现状
蚁群算法是一种新型启发式优化算法，在求解节点数为5到100的组合优化问题上，选用合适的参数，其优化结果普遍好于遗传算法和模拟退火算法。因此，目前国内外有许多学者开展了对蚁群算法的研究工作。如：国外学者Stuzle和Hoss提出了最大—最小蚂蚁算法，该算法只对最佳路径增加信息素浓度，并且为信息素设置上下限来避免算法过早出现停滞现象。Cordon O等提出最优—最差蚂蚁算法，该算法对最优解进行更大限度的增强，而对最差解进行削弱，使得最优解与最差解之间的信息素差异增大，从而使蚂蚁的行为更集中于最优解附近。
国内对蚁群算法的研究始于上世纪末，从公开发表的论文看，最先研究蚁群算法的是东北大学的张纪会博士和徐心教授。为了克服蚁群算法计算时间长这一缺点，吴庆洪等于1999年提出了具有变异特征的蚁群算法，该算法采用逆转变异的方式，随机地进行变异，以增大进化时所需的信息量。这种变异机制充分利用了2交换法简洁高效的特点，因此具有较快的收敛速度。吴斌等于2001年提出了一种相遇算法，该算法将相遇算法与采用并行策略的分段算法相结合，用两
只蚂蚁共同完成对一条路径的搜索，以提高搜索速度。徐精明等于2005年提出一种多态蚁群算法，该算法通过引入侦察蚁、搜索蚁和工蚁三种不同种类的蚁群，将局部搜索与全局搜索相结合，使收敛速度大幅提高。针对蚁群算法易限于局部最小点的缺陷，王颖等于2002年提出一种自适应的蚁群算法，该算法通过自适应地改变算法信息素的挥发度系数，在保证收敛速度的条件下提高了解的全局性。刘立东等于2008年提出了一类融入遗传算法的混合蚁群算法，该算法在每代进化中保留最优解和次优解的公共解集后引入遗传操中的交叉算子和变异算子进行运算，加快了算法收敛速度，提高了解的全局性。陈星宇等人于2008年提出一种融入LK算法的混合蚁群算法，该算法将改进的LK算法优化蚂蚁生成解阶段，并在不同阶段灵活运用局部优化算法，此外还将Metropolis概率接受准则融入进来，有效地避免陷入局部最优。
以上改进算法与基本蚁群算法相比，有的算法虽然提高了搜索速度，但不能有效的防止算法陷入局部最优解；有的算法虽然有效的防止算法得到局部最优解，但是在防止陷入局部优化的同时，消耗了大量的计算时间。因此，如何在加快收敛速度和防止陷入局部最优之间取得一个平衡是目前研究的难点之一。
4
二、蚁群算法
蚁群算法不同于其他智能优化算法最为显著的特点是：采用了正反馈机制或称是一种增强学习系统，通过不断更新信息素达到最终收敛于最优解的目的。本章将对蚁群算法的基本原理、算法模型以及优缺点进行详细的分析。 2.1蚁群算法的原理 2.1.1蚁群觅食的特性
觅食行为是蚁群一个重要而有趣的行为。据昆虫学家的观察和研究发现，蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而自主地搜索新的路径，产生新的选择。这是因为在从蚁穴到食物源并返回的过程中，蚂蚁能在其走过的路径上分泌一种化学物质——信息素，通过这种方式形成信息素轨迹。蚂蚁在运动过程中能够感知这种物质的存在及其浓度，并以此指导自己的运动方向，使蚂蚁倾向于朝着该物质浓度高的方向移动。信息素轨迹可以使蚂蚁找到它们返回食物源(或蚁穴)的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。
如图2.1(a)所示，A为蚁巢，D为食物源，蚂蚁总是会选择最短的直线路径AD来搬运食物。如果搬运路线上突然出现障碍物，不管路径长短，蚂蚁按相同的概率选择在图中B点和C点绕过障碍物，如图2.1(b)所示。由于路径ABD的长度小于路径ACD的长度，单位时间内通过路径ABD的蚂蚁数量大于通过路径ACD的蚂蚁数量，则在路径ABD上面遗留的信息素浓度比较高，所以选择路径ABD的蚂蚁随之增多，如图2.1(c)所示。于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流找到寻找食物和蚁穴之间最短路径的目的，如图2.1(d)所示。
图2.1 蚁群寻找食物过程
2.1.2蚁群算法的基本思想
受到自然界中真实蚁群集体行为的启发，意大利学者Dorigo于1991年首次提出了一种基于蚂蚁种群的新型优化算法——蚁群算法。为了和真实的蚂蚁相区别，我们称蚁群算法中的蚂蚁为人工蚂蚁。人工蚂蚁具有双重特性：一方面，它们是真实蚂蚁的抽象，具有真实蚂蚁的一些特性，如个体相互交流的通信机制、
5