蚁群算法实现TSP

1蚁群算法求解TSP问题2目录蚁群算法求解TSP问题...........................................................................................................3摘要：...............................................................................................................................3关键词：...............................................................................................................................3一、引言.............................................................................................................................3二、蚁群算法原理...............................................................................................................4三、蚁群算法解决ＴＳＰ问题...........................................................................................6四、解决ｎ个城市的TSP问题的算法步骤.......................................................................8五、仿真结果.......................................................................................................................9参考文献:............................................................................................................................10附录.....................................................................................................................................103蚁群算法求解TSP问题摘要：蚁群算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试通过matlab仿真解决一个实例问题。关键词：蚁群算法；TSP问题；matlab。一、引言TSP（TravellingSalesmanProblem）又称货郎担或巡回售货员问题。TSP问题可以描述为：有N个城市，一售货员从起始城市出发，访问所有的城市一次，最后回到起始城市，求最短路径。TSP问题除了具有明显的实际意义外，有许多问题都可以归结为TSP问题。目前针对这一问题已有许多解法，如穷举搜索法（ExhaustiveSearchMethod）,贪心法（GreedyMethod）,动态规划法（DynamicProgrammingMethod）分支界定法（Branch-And-Bound），遗传算法（GeneticAgorithm）模拟退火法(simulatedannealing),禁忌搜索。本文介绍了一种求解TSP问题的算法—蚁群算法，并通过matlab仿真求解31个省会城市之间的最短距离，经过仿真试验，证明是一种解决TSP问题有效的方法。20世纪90年代，意大利学者M.Dorigo等人在新型算法研究的过程中，通过模拟自然界蚂蚁的觅食过程：即通过信息素（pheromone）的相互交流从而找到由蚁巢至食物的最短路径，提出了一种基于信息正反馈原理的新型模拟进化算法——蚁群算法（AntColonyalgorithm）。蚁群算法是继遗传算法、人工神经网络等算法之后的又一种启发式算法，它4的基本原理借鉴了这样一个客观事实：蚂蚁由自组织的合作能力所产生的群体智能来寻找路径，它被认为是用于解决组合优化问题的又一种新方法。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。二、蚁群算法原理蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。蚂蚁是如何做到这一点的呢？原来，单个的蚂蚁为了避免自己迷路，它在爬行时，同时也会释放一种特殊的分泌物——信息素（Pheromone），而且它也能觉察到一定范围内的其它蚂蚁所分泌的信息素，并由此影响它自己的行为。当一条路上的信息素越来越多（当然，随着时间的推移会逐渐减弱），后来的蚂蚁选择这条路径的概率也就越来越大，从而进一步增加了该路径的信息素浓度，这种选择过程称为蚂蚁的自催化过程，其原理是一种正反馈机制。这里我们可以用一个图来说明蚂蚁觅食的最短路径选择原理，如图2-1所示。5图2-1蚁群觅食原理如图2-1（a）所示，我们假设A点是食物，而E点是蚂蚁的巢穴，当A、E两点间没有任何障碍物阻挡时，蚂蚁不存在路径选择的问题，这种情况最简单：由于两点间直线距离最短，蚂蚁们搬运食物时，会以直线的形式往返爬行。但在图2-1（b）中的情形有所变化，若某时刻忽然有一个障碍物出现在蚂蚁经过的路径中，原有的路径被切断，那么从A点到E点的蚂蚁就必须在B点决定应该往左还是往右走，而从E点到A点的蚂蚁也必须在D点决定选择走哪条路径；这种决定会受到各条路径上以往蚂蚁留下的信息素浓度（即残留信息素浓度）的影响。如果往右走的路径上的信息素浓度比较大，那么右边的路径被蚂蚁选中的可能性也就大一些；但是对障碍出现后第一个到达B点或D点的蚂蚁而言，因为没有信息素的影响，所以它们选择向左或者向右的可能性是一样的，（b）图所表示的正是此时的情况。若以从A点到E点的蚂蚁为例进行说明（对于从E点到A点的蚂蚁而言，过程也基本是一样的），由于路径BCD比路径BHD要短，因此选择BCD路径6的第一只蚂蚁要比选择BHD的第一只蚂蚁早到达D点；此时，从D点向B点看，路径DCB上的信息素浓度要比路径DHB上的信息素浓度大。因此从下一时刻开始，从E点经D点到A点的蚂蚁，它们选择DCB路径的可能性要比选择DHB路径的可能性大得多，从而使路径BCD（或DCB）上信息素浓度与路径BHD（或DHB）上信息素浓度的差变大；而信息素浓度差变大的结果是选择路径BCD（或DCB）的蚂蚁进一步增加，这又导致信息素浓度差进一步加大。如图2-1（c）所示，随着时间的推移，几乎所有的蚂蚁都会选择路径BCD搬运食物，而我们同时也会发现：BCD路径也正是事实上的最短路径。这种蚁群寻径的原理可简单理解为：对于单个的蚂蚁来说，它并没有要寻找到最短路径的主观上的故意；但对于整个蚁群系统来说，它们又确实达到了寻找到最短路径的客观上的效果。在自然界中，蚁群的这种寻找路径的过程表现为一种正反馈的过程，与蚁群算法中人工蚁群的寻优算法极为一致。例如，我们把只具备了简单功能的工作单元视为“蚂蚁”，那么上述寻找路径的过程可以用于解释蚁群算法中人工蚁群的寻优过程。三、蚁群算法解决ＴＳＰ问题我们来介绍一下如何用蚁群算法求解ｎ个城市的TSP设dij为城市ｉ，ｊ之间的几何距离，dij＝22yyxxjiji2/1。设tbi表示ｔ时刻位于城市ｉ的蚂蚁的个数，蚂蚁总数ｍ＝niitb1，ijt表示ｔ时刻在ｉｊ连线上残留的信息量，初始时刻各条路径上的信息量为ij0＝Ｃ（Ｃ为常数）。用参7数表示信息量的保留度，则经过ｎ个时刻后，路径ｉｊ上的信息量根据下式作调整：ijijijtnt)()(⑴mkkijij1⑵kij表示第ｋ只蚂蚁在本次循环中留在路径ｉｊ上的信息量，ij表示本次循环所有经过的蚂蚁留在ｉｊ上的信息量。kij＝当不经过时０时当第ｋ只蚂蚁经过ｉｊLkQ⑶定义ij＝１／dij。蚂蚁ｋ（ｋ＝１，２，…，ｍ）在运动过程中，kijp表示在ｔ时刻蚂蚁ｋ由位置ｉ转移到位置ｊ的概率：kijp＝其他0kallowdsisisijijallowedjttk⑷我们用),,2,1(mktabuk记录蚂蚁ｋ目前已经走过的城市集合，allowkd表示蚂蚁ｋ下一步允许选择的城市集合，它等于全部的城市集合除去第ｋ只蚂蚁已走过的集合ktabu。定义Lk为第ｋ只蚂蚁在本次循环中走过的路径和。用蚁群算法解决ＴＳＰ问题是一个递推过程，当ｔ＝０时，将蚂蚁放在各城市，设定每条路径上的信息量初值0ij＝Ｃ，每只蚂蚁根据公式⑷决定的概率从城市ｉ到城市ｊ。tij表示曾经有多少蚂蚁经过路径（ｉ，ｊ）；ij说明较近的城市有更大的可能性被选中。α，β用来控制两者对蚂蚁选择的影响力程8度。经过一个循环后，根据公式⑴⑵⑶计算更新每条路径的信息量tij。将所有的),,2,1(mktabuk复原，最后求出本次循环的最短路径minLk。这个过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数NCmax。四、解决ｎ个城市的TSP问题的算法步骤1.初始化：设定t=0，循环计数器nc=0，对每条路径设定初始信息量0ij＝C,ij＝０将ｍ只蚂蚁放在ｎ个城市上（为了使问题简化，设定ｍ＝ｎ）。2.设定taub集合的索引ｓ＝１，对ｋ从１到ｍ，把第ｋ只蚂蚁放在起始位置，对应的设定集合stabuk3.重复下面的步骤，直到集合tabu满为止（这一步将重复ｎ－１次）：设定ｓ＝ｓ＋１；对ｋ从１到ｍ，根据公式⑷确定的概率，选择下一步移动的目标城市ｊ｛在时间ｔ时，第ｋ只蚂蚁所在的城市是ｉ＝1stabuk｝；将第ｋ只蚂蚁移到城市ｊ；把ｊ加入到集合stabuk中。4.对ｋ从１到ｍ：将第ｋ只蚂蚁从ntabuk移动到1tabuk；计算第ｋ只蚂蚁所走过的路程和Lk，并更新最小路径minLk；对每条路径（ｉ,ｊ）：kij＝当不经过时０时当第ｋ只蚂蚁经过ｉｊLkQkijijij5.对每条路径（ｉ,ｊ）根据ijijijtnt)()(计算ntij；设定ｔ＝ｔ＋ｎ；设定ＮＣ＝ＮＣ＋１；对每条路径（ｉ,ｊ），设定ij＝０。6.如果ＮＣ＜NCmax，则清空所有的集合tabu,转到第二步；否则,得出最短的路径。9算法的流程如下图:五、仿真结果10参考文献:[1]黄丽韶,朱喜基.基于MATLAB的蚁群算法求解旅行商问题[J].计算机世界.[2]李志伟.基于群集智能的蚁群优化算法研究[J].计算机工程与设计，2003，08.[3]王源.蚂蚁算法求解TSP问题.[4]杨殿生.TSP问题的蚁群算法求解.鄂州大学报.[5]尹晓峰,刘春煌.基于MATLAB的混合型蚁群算法求解旅行商问题[J].