基于蚁群算法在TSP问题中的仿真分析

1、基于蚁群算法在TSP问题中的仿真分析【摘要】在移动机器人路径规划TSP问题中选取蚁群算法和遗传算法的 matlab 仿真作为研究重点， 根据算法的特 点分析了蚁群算法的主要参数例如启发信息影响程度的表 达因子；信息素挥发系数，蚁群中的蚂蚁数量等对TSP问题规划最优解和效率的影响，同时对比遗传算法对TSP问题的仿真分析，得出蚁群算法的效率优势和遗传算法的稳定性优 势，为进一步的两种算法优势互补融合研究做铺垫。【关键词】TSP问题；蚁群算法；遗传算法；仿真分析目前，关于蚁群算法在 TSP问题中的应用及改进已经相 对成熟， 文献1 通过引入模糊集合的概念提出改进路径更新 效果的蚁群算法（FACO，该

2、方法通过模糊评价充分合理利 用信息素，能有效提高求得最优解的几率，是一种有效的改 进算法。文献 2 通过在最大最小蚁群算法基础上，通过遗传 算法特点对蚁群算法参数设置进行优化，有效提高算法求解 信息素的速度。 文献 3通过提出相遇策略以及分组并列运行 方式改进蚁群算法以及在二维和三维环境进行建模仿真，验 证了蚁群改进算法的可靠和有效性。 文献 4通过提出扩大局 部搜索空间策略和信息素更新机制提出蚁群自适应优化算 法求解TSP问题的方法，提高算法收敛速度和精度。同时探 讨了将混沌扰动引入信息素更新的求解过程，可以用更优解 取代当前最优值。1、基本蚁群算法TSP仿真分析及改进基本蚁群算法求解 TS

3、P问题的实质在于引入蚂蚁行走的思想求解最优路径问题，蚂蚁随机挑选路径并产生信息素， 信息素越大代表路径长度越短从而反馈引导蚂蚁选择路径 最短的路线，蚁群算法有比较好的自组织性，通过整体反馈 寻优可以应用于很多实际组合优化问题。对于蚁群算法的流程，首先应该明确蚁群算法公式及符号定义在蚁群算法描述之前，引入如下变量记号：m:蚁群中的蚂蚁数量；B :启发信息影响程度的表达因子，相当于能见度；p :信息素挥发系数，p <1;dij :边（i, j）代表城市距离；n ij :边（i, j）的启发因子，取n ij=I/dij，这个值固定，一般不随蚂蚁系统而改变；t ij :边（i, j）的信息素值表

4、示；Pkij （t）:在t时刻蚂蚁k从城市i转移到城市j的概率，i 为当前蚂蚁所在的城市， j 为蚂蚁尚未访问过的城市； 其中，蚂蚁系统使用随机比例规则进行状态转移，用公式（1-1）表示:（1-1）allowedK ：在本次循环中蚂蚁 k 未曾访问的城市集合； tabuK:蚂蚁k的禁忌表，记录蚂蚁己经访问的城市而禁 止再走这些城市。城市 i 和城市 j 之间路径的信息素量，经过 n 个时刻， 信息素调整如公式（ 1-2）所示:（1-2） 其中信息素调整原则我们采用蚁周（ant-cycle system）模型，利用的是蚂蚁的全局信息素调整方式， 效果最为优越， 蚁周模型中:其中Q:表示蚂蚁释放在

5、所经过路径上（一个过程或一 次迭代）的信息素总量，为正常数；Lk:表示第k只蚂蚁在当前迭代中所经过的路径长度； t ijk:表示蚂蚁k释放在路径（i, j）上的信息素； t ij :表示所有蚂蚁释放在路径（i, j）上的信息素总和。本文进行如下蚁群算法 TSP仿真实现，选取参数信息素 启发因子a=1，路径启发因子B =2，局部信息素挥发系数 p 仁0.2,全局信息素挥发系数 p 2=0.1，蚂蚁数量为 m=100, 最大迭代次数 NCmax=500 实际仿真结果如下:同时我们输出蚁群个体适应度最优随着迭代次数的变 化曲线,在迭代 50 次以后适应度值达到相对稳定状态,表 示路径选择基本稳定在小

6、范围波动,从而达到输出路径的效果5。验证了蚁群算法的有效性。 同时可以对基本蚁群算法作出改进，即采用最大最小蚂 蚁系统对将信息素在每条路径上的值限定于t min , t max范围内，如若超出范围则被强制置为上限或下限。这样可以 有效控制路径上的信息素差值多大导致的算法过早收敛，同 时有利于蚁群的集中搜索 6。仿真结果如图 3：2、结论利用蚁群算法对TSP问题的求解，验证了蚁群算法在路径规划问题中的有效性，同时对蚁群算法的参数设置对仿真 结果的影响进行探讨，蚁群算法的参数较多，如何设置需要 根据对算法具体要求合理配置。综上分析，蚁群算法在求解 TSP问题时具有比较强的速度优势，而遗传算法具有比较高 的可靠性和独立性，因此我们通过以上仿真分析的结论，可 以为进一步的融合算法深入研究打好基础。参考文献1 江迎春改进的蚁群算法在 TSP问题上的应用D中南 民族大学， 2009.2 冯月华.基于遗传算法的蚁群算法参数优化研究J.贵阳学院学报：自然科学版，2014，（1）.3 马金财 .基于蚁群算法的机器人路