数执车与离用
算法分析
基于TSP的蚁群算法参数选择问题分析
丁上凌李斌
(商丘职业技术学院河南商丘476000)
摘要：根据日前针对社会性动物群体活动的实验调查，发现其自组织行为广泛存在,例如群体活动较为频繁的妈效,在群体竟食过程中能够找到效穴到食物的最短路径,即效群算法。文章国烧蚁群算法在TSP中的应用，就算法的参数选择进行了深入的研究。最后通过对全文的研究工作进行了总结，并展望了其应用价值及后期还需继续研究的问题。
关键词数群算法TSP最斑路径参数选撑
中图分类号：TP183
文献标识码：A
蚁群算法是一种用来在图中寻找优化路径的机率型算法。它由 MarcoDorigo提出，它主要的依据就是蚂蚁在觅食过程中能够找到蚊穴到食物的最短路径。蚂蚁的视觉系统非常薄弱，儿乎可以说是瞎子，但是它们却能发现食物与蚊穴之间最短的距离。生态学家的研究表明，蚂蚊是借助信息素来实现这一点的，数群算法也越来越多被应用到实际的间题中，并且取得了较好的效果，例如调度间题、着色问题、求解旅行商问题(TSP)，并在大规模集成电路设计，通信路由控制等诸多领域表现出较好的性能。本文在介绍蚁群算法的基本原理的基础上，主要分析了蚊群算法参数的选择策略问题。
1蚊群算法的基本原理
1.1效群算法的原理
蚁群算法是从自然界启发中得到的一种新型的模拟进化算法，应用该算法求解TSP问题取得了较好的结果。科学家发现虽然单个蚂蚊无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线。经过大量研究发现：蚂蚁在运动过程中，能够留下一种称之为信息素的物质，而且蚂数在运动过程中能够感知这种物质，并以此指导自已的运动方向，因此，由大量蚂蚁组成的蚊群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚊越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大。敦群算法具有实现简单、正反馈、分布式的优点。
人工数群和自然界数群的相似之处在于，两者优先选择的都是含"信息素"浓度较大的路径。这在两种情况下，较短的路径上都能聚集比较多的信息素，受到上述情况的启发，科研人员在此基础上提出了蚁群算法，它不仅具有蚁群觅食行为中的信息传递功能，还其有自然界数群所没有的记忆能力，即能够保存已经去过的地方和已经走过的路径，从而能够更加智能的选择下一地点和路径，并且按照一定的规律总结出特有的算法进行最短路径的选择。
1.2基于TSP问题的数群算法数学模型
TSP问题又称为旅行商问愿题，是数学领域中著名问题之一。假设有一个旅行商人要拜访M个城市，他必须选择所要走的路径，路径
文章编号:1007-9416(2016)12-0131-02
的限制是每个城市只能拜访一次，而且最终要回到原来出发的城市。路径的选择目标是要求旅行商人怎样才能得到最短的路径，取得最佳的利益。
根据信息素更新的策略不同，DorigoM曾给出了不同的蚊群算法模型，分别称为ant-cycle模型，antquantity模型和ant-den-sity模型。它们的差别在于循环中路径的信息素的增量△t,(t)的求法不同。
在ant-quantity模型中：
1/d
()=
0
当k只蚂蚁在和+1时刻经过（i，i）时
其它
在ant-cycle模型中：
4r,0)=je/z,
0
当k只蚂蚊在t和t+1时刻经过（i，j）时
其它
在ant-density模型中：
Ar,() =
0
当k只蚂蚁在t和t+1时刻经过（i，j）时
其它
其中，O是信息素强度，它影响算法的收敛速度d。是指两座城市之间的欧氏距离，L，是指第只蚂蚊所走的路径长度。ant-quantity和ant-density是利用局部信息完成求解运算，ant-cycle是利用整体信息完成求解运算。通过实验得到ant-cyde的模型比其他
两种模型效果好。 2参数优化策略
通过对蚁群算法基本原理及其数学模型的学习理解，可以使用 MATLAB进行蚊群算法求解TSP最短路径问题的仿真试验工作，其主要任务是：根据城市的坐标，使用蚊群算法求解TSP最优化间题，并绘制最佳结果的路径图，生成平均距离和最短距离统计图，
算法中的主要参数有：城市的个数，城市的坐标(城市个数+2的矩阵)最大循环次数(即送代的次数)，蚂数个数，表征信息素重要程
表1
蚂蚁数、城市数及蚂蚁数/城市数与最短路径长度关系
蚂蚁数
15（缺省值）
5 15 25 10 30 50 15 45
收稿日期：2016-10-22
城市数
20（缺省值）
10 10 10 20 20 20 30 30
蚂蚊数/城市数
0.75 0.5 1.5 2.5 0.5 1.5 2.5 0.5 1.5
最短路径长度 4148.5973 3272.3217 3272.3217 3272.3217 4147,8282 4132.8314 4143.0698 5231.5418 5029.6058
作者简介：丁上凌(1981一),男,河南永城人,讲师,武汉大学硕士,研究方向：网络技术、计算机应用；李斌(1979一),男河南商丘人,制教投
武汉大学颐士，研究方向：网络技术，多媒体技术
131
万方数据