蚁群算法求解tsp问题

《蚁群算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、HUNANUNIVERSITY课程作业课程题目智能优化算法学生姓名李小燕学生学号S131020016专业班级计算机科学与技术学院名称信息科学与工程学院指导老师杨圣洪2014年6月8日蚁群算法求解TSP问题摘要：蚁群算法是一种分布式内在并行算法。单个蚂蚁的搜索过程是彼此独立的，易于局部最优，通过个体间不断的信息交流和传递有利于发现较好解；并且该算法是一种正反馈算法。路径上的信息素浓度较高，将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的进化过程。本文通过求解TSP问题，通过在特定情况下对路径进行逐

2、步遍历比较来降低陷入局部最优解的可能性,找出最优解。关键词：蚁群算法；TSP；信息素；遍历1.引言TSP问题又称最短路径问题，还称为旅行商问题，是一种比较经典的NP难题，问题描述较简单，而获得最优解却十分困难。求解TSP问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得TSP问题的解集来验证。旅行商问题的经典描述为：已知N个城市及相互间的距离，旅行商从某城市出发遍历这N个城市后再回到原点，在旅行商每个城市都只访问一次的前提下确定一条最短路径。蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模

3、拟自然界的蚂蚁觅食过程对目标进行搜索，而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质—信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。蚁群算法实现TSP过程为：将m只蚂蚁放入到n个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者

4、一个循环（完成对所有n个城市的访问）后，更新所有路径上的信息素浓度。2.蚁群算法的数学模型（1）、基本参数、信息素浓度公式、择路概率设蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为dij，t时刻城市i与城市j之间的信息素浓度为tij(t)，初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为tij(0)=t0。蚂蚁k(k=1,2,..,m)根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市，设Pijk(t)表示t时刻，蚂蚁k从城市i到城市j的概率，其计算公式为如下：其中：hij(t)为启

5、发式函数，hij(t)=1/dij，表示蚂蚁从城市i转移到城市j的期望程序；allowk(k=1,2,…,m)表示蚂蚁k待访问的城市的集合，开始时allowk为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市。a为信息素的重要程度因子，其值越大，转移中起的作用越大b为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁以较大的概率转移到距离短的城市。蚂蚁释放的信息素会随时间的推进而减少，设参数r(0

6、环后，各个城市间连接路径上的信息素浓度，需要实时更新。tij(t+1)=(1-r)tij(t)+Dtij，Dtij=其中：Dtijk表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度Dtij表示所有蚂蚁在城市i与城市j的连接路径上，释放的信息素浓度。（2）、Dtijk的计算方法Dtijk=其中：Q为常数，表示蚂蚁循环一次释放的信息素的总量；dij为第k只蚂蚁经过路径的长度，Length；3.算法实现步骤1、初始化参数蚂蚁数量m，信息素重要程度a，启发函数重要程度b，信息素挥发因子r，信息素释放总量Q，最大迭

7、代次数iter_max。获取各城市之间的距离dij，为了保证启发式函数hij=1/dij能顺利进行，对于i=j即自己到自己的距离不能给为0，而是给成一个很小的距离，如10-4或10-5。2、构建解空间将各个蚂蚁随机地置于不同出发点，对每个蚂蚁按归照下式，确定下一城市。3、更新信息素计算各个蚂蚁经过的路径长度Lk，记录当前迭代次数中的最优解(即最短路径)，根据如下公式更新信息素：tij(t+1)=(1-r)tij(t)+Dtij，Dtij=Dtijk=4、判断是否终止若没有到最大次数，则清空蚂蚁经过路径的记录表，返

8、回步骤2。4.相关实验4.1实验内容1、访问我国每个省会城市一次也仅一次的最短路径，共有31个2、如果采用枚举法，巡回路径可能1.326´1032种。3、城市的坐标citys，这是直角坐标，根据二个城市的坐标值，可以用D=可计算出任意二个城市间的距离。citys=1304231236391315417722443712139934881535332615563238122