人工蚁群算法的实现与性能分析

目录 错误！未定义书签。TOC\o"1-5"\h\z扌摘要 iiAbstract \o"CurrentDocument"第一章引言 1\o"CurrentDocument"1.1非对称TSP问题（ATSP）及其求解方法概述 1\o"CurrentDocument"1.2人工蚁群算法的主要思想和特点 11.3主要工作 2第二章ATSP问题分析 3\o"CurrentDocument"ATSP问题的数学模型 3\o"CurrentDocument"ATSP问题与TSP问题的比较 3\o"CurrentDocument"第三章求解ATSP问题的人工蚁群算法 4\o"CurrentDocument"ATSP问题的蚁群算法表示 4\o"CurrentDocument"3.2人工蚁群算法的实现 4\o"CurrentDocument"3.2.1人工蚁群算法的流程图 5\o"CurrentDocument"322蚁群的规模、算法终止条件 6\o"CurrentDocument"3.2.3路径选择方法和信息素的更新方法 7\o"CurrentDocument"第四章实验和分析 10\o"CurrentDocument"测试环境 10\o"CurrentDocument"4.2测试用例 10\o"CurrentDocument"4.3实验结果及参数分析 10\o"CurrentDocument"br17.atsp的测试结果 10\o"CurrentDocument"ft53.atsp的测试结果 12\o"CurrentDocument"ftv33.atsp的测试结果 13\o"CurrentDocument"ftv35.atsp的测试结果 15\o"CurrentDocument"br17.atsp相关参数修改后的测试结果 16\o"CurrentDocument"第五章总结 19\o"CurrentDocument"致谢 20\o"CurrentDocument"参考文献 21旅行商问题（TSP问题）是组合优化的著名难题。它具有广泛的应用背景，如计算机、网络、电气布线、加工排序、通信调度等。已经证明TSP问题是NP难题，鉴于其重要的工程与理论价值,TSP常作为算法性能研究的典型算例。TSP的最简单形象描述是:给定n个城市，有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。TSP分为对称TSP和非对称TSP两大类，若两城市往返距离相同，则为对称TSP，否则为非对称TSP。本文研究的是对称的ATSP。实质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间的往返距离是否相同。例如，有A，B两个城市，在TSP问题中，从A到B的距离是等于从B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离就不一定等于从B到A的距离，所以这是双向选择的联通问题。本文主要阐述了用人工蚁群算法的原理和一些与其相关联的知识结构点。通过对算法原理的理解，及在函数优化问题上的应用，与优化组合问题的研究来了解ATSP问题以及人工蚁群算法解决实际问题上的应用与研究。关键词：ATSP；组合优化；人工蚁群算法；TSPAbstractTravelingsalesmanproblem(TSP)istheFamouscombinationoftheoptimizationproblem.Ithasbroadapplications,suchascomputer,network,electricalwiring,processing,sortandcommunicationscheduling,andetc.HasalreadyprovedTSPisadifficultNPproblem,giveningitsimportantengineeringandtheoreticalvalued,TSPisoftenusedasthetypicalexampleofalgorithmperformancestudy.ThemostsimpleimagedescriptionofTSPis:givenncity,atravelingsalesmanstartfromonecity,Visitothercitiesonceandonlyonceagainreturntothestartcity,askedtoidentifyashortestpathofthetour.TSPcanbeclassificatedsymmetricTSPandasymmetricTSPtwobigkinds.Iftwocitiesfromthesamedistance,thatissymmetricTSP,orfortheasymmetricTSP.ThispaperstudiestheATSPproblem.Inessence,ATSPproblemisbasedontheTSPproblem.Thedifferenceliesintwocitiesroundtripdistancebetweenthesameordifferent.Forexample,therearetwocities,AandB,inTSPproblem,fromAtoBisequaltothedistancefromBtohaveAdistance,itsaone-waychoicetheconnectedproblems.ButinATSPproblem,fromAtoBdoesn'tnecessarilyequaltothedistancefromthedistanceBtoA,sothisisthetwo-waychoiceconnectivityproblem.Thispapermainlyexpoundstheemployingworkersgroupoftheprincipleandsomeassociatedknowledgestructureofthepoints.Throughtheunderstandingoftheprincipleofthealgorithm,andintheapplicationofthefunctionoptimizationproblems,AndtheoptimizedcombinationproblemsresearchtounderstandATSPproblemsandoneworkerantsgroupalgorithmofsolvingpracticalproblemswiththeapplicationofresearch.Keywords:ATSP;Combinatorialoptimization;Peopleantsgroupofalgorithm;TSP第一章引言1.1非对称TSP问题(ATSP)及其求解方法概述非对称旅行商问题是一个NP完全问题，目前求解ATSP问题的主要方法有模拟退火算法、遗传算法、蚁群算法等。ATSP是指给定n个城市和各城市间的距离，要求确定一条经过各个城市当且仅当一次的最短路线，并且这N个城市之间两两城市的往返距离不一定相等。它是一种典型的组合优化问题。基于人工蚁群算法求解ATSP问题，是近年来刚刚兴起的热门课题。然而在科学管理与经济决策的许多应用领域中，现实世界存在着大量的多目标优化问题。对于非对称旅行商问题，实际中经常要同时考虑多个目标，如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。1.2人工蚁群算法的主要思想和特点蚁群算法是受到真实蚁群集体行为的启发而得到的新型优化算法，人工蚂蚁和真实蚂蚁存在异同。人工蚂蚁和真蚂蚁的蚂蚁一样，是一群相互合作的个体并且他们有着共同的任务，他们都是通过使用信息素进行间接通讯，而且人工蚂蚁利用了真实蚂蚁觅食行为中的自催化机制。但人工蚁群也存在真蚂蚁所不具有的一些特性，蚁群这种记忆并非存储于蚂蚁个体，而是分布在路径上。人工蚂蚁实质上是由一个离散状态到另一个离散状态的跃迁。信息素的释放时间是根据不同情况而改变的。为了提高系统总体上的性能。蚁群被赋予了其他的功能，如局部优化、原路返回等。蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群在选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离；每只蚂蚁也可以记录自己走过的节点和路径。1.3主要工作蚁群算法最初是应用在对称的旅行商问题，下面对求解旅行商问题进行简单的说明。旅行商问题就是指给定n个城市，并给出两两城市间的距离。要求确定一条经过各城市最短的路径。蚂蚁根据城市的距离和连接边上信息素浓度为变量的概率函数选择下—城市。为了满足问题的约束条件，在完成一次循环前，不允许蚂蚁选择已经访问过的城市，需要由禁忌表控制。完成循环后，路径上都会留下浓度不同的信息素。我们可以通过对信息素浓度的强度，从而选择出最短路径。第二章ATSP问题分析ATSP问题的数学模型ATSP问题(dijHdji,vi,j=1,2,3,…,n),非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V=｛v1,v2,v3，…,vn｝的一个访问顺序为T=｛t1,t2,t3，…,ti,…,tn｝，其中ti^V(i=1,2,3,…,n)，且记tn+1=t1,则旅行商问题的数学模型为：minL=Eni=1dti,ti+1。ATSP问题表示为一个罗个城市的有向图G=(N,仝，其中”=｛1,2涉,基｝©=,｛俺)叮亘”)城市之间距离为 ijnxn,目标函i数为f(W)=口"「I，其中 「2 'n为城市1,2,…，n的一个排列，n+1ATSP问题与TSP问题的比较实质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间的往返距离是否相同。例如，有A,B两个城市，在TSP问题中，从A到B的距离是等于从B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离就不一定等于从B到A的距离，所以这是双向选择的联通问题OTSP较ATSP问题简单点，在算法实现上也容易点，但实际上可以看作是ATSP问题是TSP问题的发展，在此基础上多了路径往返的问题。旅行商问题(TravelingSalesmanProblem,简称TSP)即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V,A)，其中V为顶点集，A为各顶点相互连接组成的边集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：对称旅行商问题(dij=dji,Pi,j=1,2,3,…，n);非对称旅行商问题(dijHdji,vi,j=1,2,3,…，n)。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V二｛v1 , v2 , v3 ,…，vn｝的一个访问顺序为T二｛ t1 , t2 , t3 ,…，ti,…，tn｝,其中tieV(i=1,2,3,…，n),且记tn+1=t1,则旅行商问题的数学模型为[1]:minL二工ni=1dti,ti+1。ATSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。第三章求解ATSP问题的人工蚁群算法3.1ATSP问题的蚁群算法表示ATSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1、 从一个点到另一个点得信息素值，也称信息素痕迹。2、 相邻节点的可见度，即先验值。信息素的更新方式有2种，使信息素挥发：也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；使信息素增强，给评价值“好”(有蚂蚁走过)的边增加信息素。蚂蚁向相邻节点的运动通过一个随机原则来实现：根据当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找解的过程中，或者找到一个解后，都可以评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。3.2人工蚁群算法的实现基本的蚁群算法是基于图的蚁群算法，graph-basedantsystem,简称为GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，算法步骤如下：TOC\o"1-5"\h\zSTEP0对n个城市的TSP问题,N={l,2,...n}A={(i,j)li,jgN}，城市间的距离矩阵为(d)，给TSP图中的每一条弧(i，j)，赋信息素初值工a(0)=.1「A,ijnxn j假设m只蚂蚁在工作，所有蚂蚁都从同一城市i出发。当前最好解是w=(1,2, ,n)0STEP1(外循环)如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点i0出发，用L(s)表示蚂蚁s行走的城市集合，初始L(s)为空集，1<s<m °oSTEP2(内循环)按蚂蚁1<s<m的顺序分别计算。当蚂蚁在城市i,若是存在L(s)=N或{l1(i,l)gA,l电L(s)}=①完成第s只蚂蚁的计算。否贝若是存在有L(S)丰N且卩={ll(i，l)Gl电L(S)}-{i0}H①，则以概率p=严丄,jet，到达j，0 jZt(k-1)ijL(s)=L(s) {j},i：=；若 L(s)丰N且T={lI(i,l)GTA,l电L(s)}-{i0}=①

则到达i0，L(s)=则到达i0，L(s)=L(sSTEP3对1-s-m，若按L(s)中城市的顺序计算路径长度；若L(s)HN,路径长度置为一个无穷大值(即不到达)。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为to若f(L(t))<f(L(W)),则W二L(t)o用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。( p(i,j)为W上的一条弧工.伙)=(l(i,j)为W上的一条弧j k-1j w(i,j)不是W上的一条弧丿芒(k)=(1(i,j)不是W上的一条弧丿'ij k-1ij得到新的t..(k)，k：=k+1…，…重•复步骤STEP1ok>K,jlnk在STEP3中，挥发因子Pk对于一个固定的K>1，满足PkG-^(k+I)，并且/Pk=-k>K,k=1以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程如下:(1)信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程,由(1—Pk叫(k)表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。(2)信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部分，称为离线更新方式(还有在线更新方式)。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群(m只蚂蚁)中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。在STEP3中，蚁群永远记忆到目前为止的最优解。3.2.1人工蚁群算法的流程图

3.2.2蚁群的规模、算法终止条件蚁群算法的规模有蚁群大小：一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。蚁群算法的终止条件如下：1、 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；2、 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续;3、目标值控制规则，给定优化问题(目标最小化)的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。3.2.3路径选择方法和信息素的更新方法信息素的更新分为离线和在线两种方式。离线方式(同步更新方式)的主要思想是在若干只蚂蚁完成n个城市的访问后，统一对残留信息进行更新处理。信息素的在线更新(异步更新方式)即蚂蚁每行走一步，立即回溯并且更新行走路径上的信息素。离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新。蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问(第k-1次蚁群循环)后，统一对残留信息进行更新处理T少)二\伙一“+At少—1),其中J.(k)为第k-1ij ij j j次循环后的的信息素的痕迹值。单蚂蚁离线更新是在第s只蚂蚁完成对所有n个城市的访问后，进行路径回溯，更新行走路径上的信息素，同时释放分配给它的资源。更新公式为Ty.(s+1)「(s)+ATy-(s)第s+1只蚂蚁根据1.•(S+1)重新计算路由表。j 、TSP问题中，蚁群优化算法根据信息素痕迹更新方式不同可以分为At1)或AT)为不同的算法，采用离线方式，并且At(t)={|W|,(i,j)eWijI〔0(i,j)时，其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走的一条路径。Q为一个常数，该算法名为蚁环算法,特点是行走的路径越短对应保存的信息素的值就越大。GBAS算法是典型的离线信息素更新方式。该算法中，蚁群中蚂蚁的先后出行顺序没有相关性，但是每次循环需要记忆m只蚂蚁的行走路径，以进行比较选择最优路径。相对而言，单蚂蚁离线更新方式记忆信息少，只需要记忆第s只蚂蚁的路径，并通过信息素更新后，释放该蚂蚁的所有记录信息。实际上这种方式等价于蚁群离线方式中只有一只蚂蚁。与单蚂蚁离线更新方式相比，信息量记忆更小的是信息素在线更新方式，即蚂蚁每走一步，马上回溯并且更新刚刚走过的路径上的信息素，其规则为T(k+1)=T(k)+At(k)jijij其中，k为蚂蚁行走的第k步蚁量算法的信息素更新为At..(k)=d~，Q为常量，d..表示ilj d ijij到j的距离，这样信息浓度会随城市距离的减小而加大。蚁密算法的信息素更新方式为Aj.（k）=Q。I]以上三种算法中，蚁环算法效果最好，因为他用的是全局信息，而其余两种算法用的是局部信息。蚁环离线更新方法很好地保证了残留信息不至于无限积累，非最优路径会逐渐随时间推移被忘记。3.2.4蚁群算法的应用1、蚁群算法在优化问题中的应用蚁群算法最初被用经典的组合优化问题，随着研究的深入，应用范围不断扩大，现在应用到静态组合优化问题、动态组合优化问题、连续空间优化问题、以及其他领域。下面分别介绍了在不同领域中的应用：（1）在静态组合优化中的应用蚁群算法最先应用于旅行商问题（TSP）问题，它是组合优化中研究最多的NP问题之一。该问题主要是在n个城市中，必须访问每个城市且每个城市只能访问一次，最后回到起始城市，寻找最短路径。目前，求解TSP问题的方法有很多，穷举搜索法、最近邻算法、插入算法等，也有其他优化算法，例如：模拟退火算法、遗传算法、神经网络算法、禁忌算法等。许多研究表明。应用群算优化算法求解TSP问题要优于其他的方法。二次分配问题（QAP）指的是分配n个设备给n个地点使得分配代价最小。事实上,QAP问题是一般化的TSP问题。车问任务调度问题（JSP）指的是一组M台机器和一组T个任务，任务有一组制定的将在这些机器上执行的操作序列组成。还有许多问题，像车辆路线问题、图着色问题（GCP）、有序排列问题（SOP）、最短的公共父序列问题（SCS）等。2、改进蚁群算法近年来，蚁群优化算法研究主要集中在改善蚁群算法的性能方面。改进的方法主要是在搜索控制的具体方面不同。但这些算法都是基于蚂蚁找出最优解来指导蚂蚁搜索的过程。（1）带精英策略的蚂蚁系统是最早的改进蚂蚁系统。在这个系统中，为了使到目前所找出的最优解在下一循环中对蚂蚁更有吸引力。在每次循环之后给予最优解以额外的信息素量，这样的解被称为全局最优解，找出这个解的蚂蚁被称为精英蚂蚁。但是该系统存在缺点，若在进化过程中，解的总质量提高了，解元素之间的差异减小了，将导致选择概率的差异也随之减小，使得搜索过程不会集中到所找出的最优解附近，阻止了对更优解的进一步搜索。基于优化排序的蚂蚁系统：将遗传算法中排序的概念扩展应用到蚂蚁系统中，当每只蚂蚁都生成一条路径后，蚂蚁按路径长度排序，蚂蚁对激素轨迹量更新的贡献根据该蚂蚁的排名进行加权。只考虑w只最好的蚂蚁，而且要以有效避免上述的某些局部极优路径被很多蚂蚁过分重视的情况发生。最大一最小蚂蚁系统与蚁群系统相似。为了充分利用循环最优解和到目前为止找出的最优解，在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁。而在蚂蚁系统中，对所有蚂蚁走过的路径都进行信息素更新。为了避免搜索的停滞，把每个解的元素上的信息素轨迹量的值域范围限制在［Min.Max］区间内。在蚂蚁系统中的信息素轨迹量不被限制，使得一些路径上的轨迹量远高于其他边，蚂蚁都沿着同条路径移动，组织了进一步搜索更优解的行为。(4)最优一最差蚂蚁系统。该算法在蚁群算法的基础上进一步增强了搜索过程的指导性，使得蚂蚁的搜索更集中于当前所找出的最好路径的领域内。蚁群算法的任务就是引导问题的解向着全局最优的方向不断进化。该算法的思想就是对最优解进行更大限度的增强。而对最差解进行削弱，使得属于最优路径的边与属于最差路径的边之间的信息量差异进一步增大，从而使蚂蚁的搜索行为更集中于最优解的附近。蚁群算法还可以与其他智能优化算法相融合，取长补短，改进和完善算法的性能。目前蚁群算法可以与遗传算法、粒子群算法等进行融合，更有效的解决一些问题。第四章实验和分析4.1测试环境CPUE5300@2.60GHz2.59GHz,1.96GB的内存4.2测试用例NAME:br17TYPE:ATSPCOMMENT:17cityproblem(Repetto)DIMENSION:17EDGE_WEIGHT_TYPE:EXPLICITEDGE_WEIGHT_FORMAT:FULL_MATRIXEDGE_WEIGHT_SECTIONNAME:ft53TYPE:ATSPCOMMENT:AsymmetricTSP(Fischetti)DIMENSION:53EDGE_WEIGHT_TYPE:EXPLICITEDGE_WEIGHT_FORMAT:FULL_MATRIXEDGE_WEIGHT_SECTIONNAME:ftv33TYPE:ATSPCOMMENT:AsymmetricTSP(Fischetti)DIMENSION:34EDGE_WEIGHT_TYPE:EXPLICITEDGE_WEIGHT_FORMAT:FULL_MATRIXEDGE_WEIGHT_SECTIONNAME:ftv35TYPE:ATSPCOMMENT:AsymmetricTSP(Fischetti)DIMENSION:36EDGE_WEIGHT_TYPE:EXPLICITEDGE_WEIGHT_FORMAT:FULL_MATRIXEDGE_WEIGHT_SECTION4.3实验结果及参数分析4.3.1br17・atsp的测试结果istance=87theroadlistis：0113101181546314751612290distance=87thedistancelistis: 33335866668885333timespend=3_640：0921213185715314461611100：0921213185715314461611100theroadlistisdistance=87thedistancelistis: 33333588866668533timespend=3.531theroadlistis：0102111121398631445161570distance=8?thedistancelistis: 33333335866668885timespend=3.625巳呂呂曰nykeytocontinuetheroadlistis：0121312101197541431586160distance=87thEdist曰nee ijj：33333335866668885timespend=3.593distance=87theroadlistis：0101392121181475315461610dis七曰口匚巳胡1?thedistancelistis: 33333358886666853timespend=3・453Ffe呂占any tocontinLiEtheroadlistis：0122111161535814467913100distance=87thedistancelistis: 33335866886685333timespend=3.937*ressanykeytocontinuetheroadlistis：0108516153641471112913120distance=87thedistancelistis: 35888666685333333timespend=3.390Pfessanyk^ytocontinuE. theroadlistis：0911122101318541436715160distance=87thedistancelistis: 33333335866668885timespend=3.640Pfessanyk^ytocontinuE. distance=87theroadlistis：0113101181546314751612290distance=87thedistancelistis: 33335866668885333timespend=3.640theroadlistis：0921213185715314461611100distance=87thedistancelistis: 33333588866668533tinespend=3・531pFEgganykeytocontinue.组数12345678910平均值Distance8787878787878787878787Time3.6403.5313.6253.5933.4533.9373.3983.6403.6403.5313.604・3・2ft53.atsp的测试结果theroadlistis :0363540211110121413171615373938423141474246434544343226252729282024232219188976551484952E03331300distance=7146thedistancelistis：14348109792301141796011179482414115812514”63801158118926842911594861692791Q572141634982078196145317869991115570247316929977119136500timespend=163.562[Pressanykeytocontinuetheroadlistis：0419876551484952503326252729282139361012141311321716232024221918153735403845424643414744343231300distance=7149thedistancelistis：24558137321111115570247316929977232105721416354723198139179601115413498794813636207611453170141401094876948429671894786169166136500timespend=175.62536101214131132171615373540212&242322191889765514849525033300distance=7085thedistancelistis：2455881189268429115948616916613410572141636211252313917960111541349879482414140109791152078196145Bl78699911155702473169299772355QQtimespend=157.125pi*eMManykeytocontinue Itheroadlistis：0363540212320242219181537393841897655148495250332627292825321716111012141345424643414744□43231300distance=7298thedistancelistis：14348109792623620761145317014115812514058746999111557024731692997723215814163365599879487511417960111215948429671894786169166136500timespend=171.812theroadlistis：0418976551484952503326252729282024232219181716153735402139384542464341474434323130361012141311320distance=7171thedistancelistis：245587469991115570247316929977232105721416349820781961453144482414140109792311257694842967189478616916613662813917960111541349860timespend=151.687theroadlistis：0414147424643454434323126252729282039383610121413113217161537354021242322191898765514849525033300distance=7110thedistancelistis：245588118926842911594861691661341Q572141&3498138125231391796Q11154134987948241414010979307819614531128321111115570247316929977235500timespend=153.453：0418976551484952503326252729282139364147443735403845424643245587469991115560111541349879484786169166136500702473169299772321363620761145317010572141414010：0321716111012141345424643384189theroadlistis25272928212320242219181537393635503331300distance=?193thedistancelistis：125987948751141791692791057214163547262362076114531：0418976551484952503326252729282139364147443735403845424643245587469991115560111541349879484786169166136500702473169299772321363620761145317010572141414010：0321716111012141345424643384189theroadlistis25272928212320242219181537393635503331300distance=?193thedistancelistis：125987948751141791692791057214163547262362076114531469991115570247316929977119136500timespend=189.54640607011121594141158984147447655134322648495218947868429674810948140587|组数12345678910平均值Distance72937146714970857298717171107115711171937167.1Time174.163.5175.6157.1171.8151.6153.4152.6171.6189.54166.1867163252512875371566094.3・3ftv33.atsp的测试结果theroadlistiistance=1286thedistancelist601255341207timespend=34.312：013121415161252423262728292220213118194653033230is：132531793257820485350284636197627174554343110132381627theroadlistis:1711810932746distance=1286thedistancelistis：B60125534120754timespend=35.1090131214151612524232728292622202131181953033230132531793257820101502815313619762717343110132381627theroadlistis:1711810932746distance=1286thedistancelistis:60125534120754timespend=39.01501312141516125242327282926222021311819530332301325317932578201015028153136197627174343110132381627theroadlistis :01312141516125262728292224231920213118171181093274653033230distance=1324thedistancelistis：1325317932573753502846472036531976271P60125534120754343110132381627timespend=41.140Pt'rrranu1<rufinnnntimmtheroadlistis :01312141516125242326272829222021311815171181093274653033230distance=1286thedistancelist心132531793257820485350284636197627174E60125534120754343110132381627timespend=35.625[Pressanykeytocontinue.theroadlistis:01252423171131181920212226272829161514121393278104653033230distance=1369thedistancelistis:2657820456011327175319713653502870973L25292074853108343110132381627timespend=37.578r r ・ Thb・・ 亠J-fc ctheroadlistis :01312141516125242326272829222021311819171181093274653033230distance=1286thedistancelistis：132531793257820485350284636197627174560125534120754343110132381627timespend=35.343theroadlistis ：01252423171131181920212226272829161514121393278104653033230distance=1369thedistancelistis：2657820456011327175319713653502870973L25292074853108343110132381627timespend=35.625theroadlistis:01312141516252423179327810113118192021222627282913330465230distance=1339thedistancelistis：132531793482045662074853611132717531971365350285240278434311141627timespend=36.953theroadlistis :01312141516125242326272829222021311819171181093274653033230distance=1286thedistancelistis：132531793257820485350284636197627174560125534120754343110132381627timespend=35.359Pressanukeutocontinue_组数12345678910平均值Distance12861286128612861286128612861286128612861286Time34.3135.1039.0141.1435.6237.5735.3435.6236.9535.3536.60295058353964・3・4ftv35.atsp的测试结果theroadlistis ：013125763489111415161262524171033181920212228293027233135324230distance=1497thedistancelistis:717531967595028132760343112074867317932578thedistancelistis:7175319675950281531110482751631627timespend=42.437theroadlistis：013125763230272325241710331819202122282931352434891114151626130distance=1.485thedistancelistis：1327603431101561531472045601132717531967595Q564838209374867317934163927timespend=44.468・亠r小theroadlistis：013127653489111415162625241710331819*02122232728293135243230130distance=1479thedistancelistis：132794316060748673179348204560113271753196736365350564838205156523927timespend=43.921theroadlistis：0131257634891114151626252417103318192122232728293135243230130distance=1479thedistancelistis：1327603431120748673179348204560113271b53196736365350564838205156523927timespend=41.468theroadlistis：013125763489111415162625241710331819202122232728293135243230130distance=1479thedistancelistis：132760343112074867317934820456011327]53196736365350564838205156523927timespend=42.687Pfgssanykeytocontinue theroadlistis：01261615141113348912576432302723252171033181920212228293135230distance=1495thedistancelistis：265734973125497486760343195515615314'204560113271753196759505648381627timespend=45.906P"aG勺__3JUJ_IfflII_tn__r>n1-~in“a theroadlistis：0133489 11 14 15 16 2613 12 576 432302723254171033181920212228293135 2 0distance=1492thedistancelistis：1349748 67 31 79341639 37 6034 31955156153147204560113271753196759 50 56 48 38 43timespend=41.515theroadlistis：013125763489111415162625241710331819202122232728293135243230130distance=1479thedistancelistis：1327603431120748673179348204560113271753196736365350564838205156523927timespend=46.343theroadlistis：01312576323027232524171033181920212222931352434891114151626130distance=1485thedistancelistis：1327603431101561531472045601132717531975950564838209374867317934163927timespend=42.140TOC\o"1-5"\h\ztheroadlistis：0133489 11 14 15 16 26 1 3 12 5 7 6 4 32 30 27 23 25241710331819202122282931352 0distRnce=1492thedistsincelistis：1349748 67 31 793416 39 37 60 34 31 95 51 56 15 34720456Q113271753196759 50 56 48 38 43timespend=45.156组数12345678910平均值Distance14971485147914791479149514921479148514921486Time42.4344.4643.9241.4642.6845.9041.5146.3442.1445.1543.60781876530644.3.5brl7.atsp相关参数修改后的测试结果(1)将蚂蚁指数改变为50只时，其它参数不变，测试结果为theroadlistis：0714315854616111921013120distance=87thedistancelistis: 58668866853333333timespend=2.500theroadlistis：0102985161446315711121310distance=87thedistancelistis: 33358886666853333timespend=2.437Pressanykeytocontinuetheroadlistis：0101112913121615414853670distance=87thedistancelistis: 33333335866886685timespend=2.500theroadlistis：0913102116158541436711120distance=87thedistancelistis: 33333588866668533timespend=2.500[Pfessany tocontinuE.theroadlistis：0113102121614815354671190distance=8?thedistancelistis: 33333588866668533timespend=2.515theroadlistis：0161576453148111102913120distance=87thedistancelistis: 58886666853333333timespend=2.609Pfe呂呂any tocontinuE.theroadlistis：0971516144536811101312210distance=87thedistancelistis: 35888666685333333timespend=2.453theroadlistis：0863151614457913102121110distance=87thedistancelistis: 58668866853333333timespend=2.546theroadlistis：0753616154148913121112100distance=87thedistancelistis: 58668866853333333timespend=2.578theroadlistis：0921131016153546814711120distance=87thedistancelistis: 33333586666888533timespend=2.421组数12345678910平均值Distance8787878787878787878787Time2.5002.4732.5002.5002.5152.6092.4532.5462.5782.4312.515(2)将挥发因子改变为0.005，其它参数不变时的测试结果为:theroadlistis：0921011161485415367113120distance=87thedistancelistis: 33335888666685333tinespend=0.875theroadlistis：0108154141663571112291310distance=87thedistancelistis: 35866886685333333tinespend=0.843theroadlistis：0122101185367154141611390distance=87thedistancelistis: 33335866886685333timespend=0.890an#kg*tocontinuE.theroadlistis：085315461614?113121192100distance=87thedistancelistis: 58666688853333333timespend=0.859puEssanyk^yto匚ontinuE.theroadlistis：0814453671516121112913100distance=87thedistancelistis: 58666688853333333timespend=0.843theroadlistis：0122913111854147631516100distance=87thedistancelistis: 33333358668866853timespend=0.843theroadlistis：0102913111854671431516120distance=87thedistancelistis: 33333358668866853timespend=0.859theroadlistis：0102913111854671431516120distance=87thedistancelistis: 33333358668866853timespend=0.859[Pfessany tocontinLi巳.theroadlistis：0121213101176315451614890distance=87thedistancelistis: 33333358666688853timespend=0.843theroadlistis：0121116144158635710139210distance=8?thedistancelistis: 33586688668533333timespend=0.843Pressanykeytocontinue组数12345678910平均值Distance8787878787878787878787Time0.8750.8430.8900.8590.8430.8430.8590.8590.8430.8430.856第五章总结蚁群算法问世至今已有十多年的时间，其理论和应用都有了很大的进步，蚁群算法从最初求解旅行商问题开始，已经逐步发展为一个优化工具.并且较为成功地应用到科学和工程中的多个领域。众多研究已经证明.蚁群算法具有很强的发现较好解的能力，因为该算法不仅利用了正反馈原理.而且是一种本质并行的算法，不同个体之间不断进行信息交流和传递，从而能够相互协作。蚁群算法相对于各种比较成熟的计算智能方法来说，它的数学离了基础相对薄弱，缺乏具备普遍意义的理论性分析。算法中涉及的各种参数设置也没有确切的理论依据，通常都是通过经验来确定。因此，蚁群算法还有许多问题需要解决，它的应用也有待进一步的发掘。蚁群算法还有许多要研究的地方，主要是①进一步的研究算法收敛性的分析.得出更强的收敛性证明并得出收敛速度将会加速算法的发展；②蚁群算法的理论性分析和参数的设置；③蚁群算法的应用领域的扩展，应用较多的是静态组合优化问题，改进并将其应用于动态组合优化问题和连续优化问题是值得探索的。对于ATSP,目前还不存在能找到完美解的方法，这个问题是NP难的［20］：目前还没有任何算法能在与城市总数呈多项式关系的时间复杂性下找到完美解。我们只能产生一些近似完美解，在合理的运行时间里使其与完美解尽可能的接近。从目前发表的各种求解ATSP的论文的结论来看，少于100个城市的ATSP例子很适合于用全局优化技术求解，但是要考虑城市规模比这大得多的ATSP实例则需要采用启发式方法。为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提出的改进策略主要有：并行多邻域搜索，平滑优化曲面形状，引进重升温、熵抽样等高级技术等。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度和鲁棒性的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优化策略会是一种趋势。对于TSP的求解，我认为以后在以下几个方面可能会有很好的进展：1）新的方法的提出；2）基于目前各种方法的改进；3）混合优化策略的发展等。我们希望最终人们能找到一种求解TSP的完美方法。致谢在本论文完成之际，首先我要对我的指导老师表示深深的感谢。他学识渊博，治学严谨，不仅是我理论知识学习上的良师，同时是我生活上的楷模。蔡老师在百忙之中，不辞辛苦地给予了许多指导和帮助，使我能顺利地完成这次课程设计。其次我要感谢我的同学们给我的帮助，是他们在我遇到困难时，为我指出错误，耐心的给我讲解，让我在这次课程设计中学到了很多，有了很多收益。参考文献1、 邢文训，谢金星.现代优化计算方法.北京：清华大学出版社，2005.2、 王凌.智能优化算法及其应用.北京：清华大学出版社，2001.3、 阎平凡，张长水.人工神经网络与模拟进化计算.北京：清华大学出版社，2005.4、 王小平，曹立明.遗传算法一一理论、应用与软件实现•西安：西安交通大学出版社，2002.5、 梁家明.基于蚁群算法的TSP问题研究.广东佛山6、 赵天男，王晓红.蚁群算法及其研究.辽宁渤海大学附录程序代码#include〈stdio.h〉#include〈stdlib.h〉#include〈time.h>#include〈string.h〉#defineM100structAntInf //