蚁群算法求解TSP问题.doc

HUＮAＮ 　UNIVERSＩTＹ
课 程 作 业
课程题目
　 智能优化算法 　 　 　 　 　 　
学生姓名
　 李小燕
学生学号
　　 　 Ｓ13１02０01６
专业班级
　 　计算机科学与技术
学院名称
　 　信息科学与工程学院
指导老师
　 杨圣洪
2014 年6月 8日
蚁群算法求解ＴSＰ问题
摘要：蚁群算法是一种分布式内在并行算法。单个蚂蚁的搜索过程是彼此独立的，易于局部最优,通过个体间不断的信息交流和传递有利于发现较好解;并且该算法是一种正反馈算法。路径上的信息素浓度较高,将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的进化过程。本文通过求解TSP问题，通过在特定情况下对路径进行逐步遍历比较来降低陷入局部最优解的可能性， 找出最优解。
关键词：蚁群算法;TＳP；信息素;遍历
1.　引言
TSＰ问题又称最短路径问题，还称为旅行商问题,是一种比较经典的　NＰ 难题，问题描述较简单，而获得最优解却十分困难。求解 TSP 问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得　ＴＳP 问题的解集来验证。旅行商问题的经典描述为：已知N 个城市及相互间的距离，旅行商从某城市出发遍历这 N　个城市后再回到原点,在旅行商每个城市都只访问一次的前提下确定一条最短路径。
蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行搜索,而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质-信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时,留下的信息素也会越来越多,以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度,逐渐形成了一条它们自己事先并未意识到的最短路线.
　 蚁群算法实现TSP 过程为：将 m 只蚂蚁放入到 ｎ 个随机选择的城市中，那么每个蚂蚁每步的行动是:根据一定的依据选择下一个它还没有访问的城市;同时在完成一步（从一个城市到达另一个城市)或者一个循环(完成对所有 n 个城市的访问)后，更新所有路径上的信息素浓度.
2。 蚁群算法的数学模型
(1）、基本参数、信息素浓度公式、择路概率
设蚂蚁的数量为m,城市的数量为n，城市i与城市ｊ之间的距离为dij，ｔ时刻城市i与城市j之间的信息素浓度为ｔij（t),初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为ｔｉｊ（0）=t０.
蚂蚁k(k=1，２,．.,ｍ）根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市,设Pijk(t）表示ｔ时刻，蚂蚁ｋ从城市i到城市ｊ的概率,其计算公式为如下：
其中：
hiｊ(t)为启发式函数,hij（t）=1/dｉj,表示蚂蚁从城市i转移到城市j的期望程序；
ａlｌowｋ（ｋ=1，２,…，m)表示蚂蚁k待访问的城市的集合，开始时allowk为其他ｎ-１城市,随着时间推进,其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市.
a为信息素的重要程度因子,其值越大，转移中起的作用越大
b为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁以较大的概率转移到距离短的城市。
蚂蚁释放的信息素会随时间的推进而减少，设参数r(0<r<1）表示信息素的挥发度,当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度，需要实时更新。
tｉj(t+1）=(1－r)tiｊ(t）＋Dtij，Dｔｉｊ＝
其中：
Dｔijk表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度
Dｔij表示所有蚂蚁在城市i与城市j的连接路径上,释放的信息素浓度。
（2）、Dtiｊk的计算方法
Dtｉｊk=
其中：
Ｑ为常数,表示蚂蚁循环一次释放的信息素的总量；
ｄｉｊ为第ｋ只蚂蚁经过路径的长度,Lengｔh；
3。 算法实现步骤
１、初始化参数
蚂蚁数量m，信息素重要程度a,启发函数重要程度b，信息素挥发因子r，信息素释放总量Q，最大迭代次数iteｒ_ｍａx。获取各城市之间的距离ｄij,为了保证启发式函数hｉj=1／dｉｊ能顺利进行，对于i=ｊ即自己到自己的距离不能给为0,而是给成一个很小的距离,如1０—４或10—5。
2、构建解空间
将各个蚂蚁随机地置于不同出发点,对每个蚂蚁按归照下式，确定下一城市。
３、更新信息素
计算各个蚂蚁经过的路径长度Lk，记录当前迭代次数中的最优解（即最短路径）,根据如下公式更新信息素：
tij（t+1）=（１-r）ｔij(t）+Dtij，Dtij=
Dtiｊk=