自适应蚁群算法在求解TSP问题中的应用

卢宇凡，张 莉

（西安工程大学 电子信息学院，陕西 西安 710048）

旅行商问题[1]（TSP）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径。限制条件是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是所有路程之中的最小值。TSP问题是一个组合优化问题，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

蚁群算法[2]是源于生物世界仿生类随机搜索算法，它应用于组合优化中具有很强的发现解的能力，且具有分布式计算、易于与其他方法相结合及鲁棒性强的优点。在仿真中表现出高度的灵活性、健壮性。但是还存在较多的问题，例如搜索速度慢，局部寻优能力差等。针对这些问题，将算法进行改进，调节信息素Q与信息素挥发系数ρ，使其变为动态的自适应信息素与动态的信息素挥发系数，进行仿真测试改进的优化算法，从而达到更优的结果。

1 基本蚁群算法及其改进

1.1 基本蚁群算法

蚂蚁在寻找食物过程中总能找到一条食物所在地和蚁穴地之间的最短路程，经研究发现蚂蚁会在其走过的路径上留下称之为信息素的物质，其他蚂蚁可以感知这种物质并以此指引其运动的方向。这种信息素允许叠加，走过同一条路径的蚂蚁数量越多，这条路径上的信息素浓度越大。由此可以吸引其他蚂蚁以更大的概率走此路径。反之，走过的蚂蚁越少，信息素的浓度就越低，行走该路径的概率就越小，同时，这种信息素还会随着时间的推移而挥发[3]。

设 m 表示蚂蚁总数量，dij（i，j=0，1，…n-1）表示节点 i和节点 j之间的距离，τij（t）表示 t时刻 i、j在连线上的信息素。在算法的初始时刻，将m只蚂蚁随机地放到n个节点上，此时各路径上的信息素相等，设τij（0）为常数，每只蚂蚁根据路径上保留的信息素独立地选择下一个节点。在时刻t，蚂蚁k从节点i转移到节点j的概率为：

其中，allowedk={0，1，…n-1}表示蚂蚁k下一步允许选择的所有节点；α表示路径上的信息量对蚂蚁选择路径所起的影响程度；ηij是启发函数，表示由节点i转移到节点j的期望程度；β表示ηij对蚂蚁选择路径的影响程度，一般可取ηij=1/dij。每只蚂蚁将根据式（1）进行搜索前进。N个时刻遍历所有节点后，将依据式（2）对各条路径上的信息素进行更新。

Y=[40 90；36 85；53 68；26 61；7 64；2 99；68 58；71 44；54 62；84 68；63 61；19 53；23 61；85 45；92 38；25 38；24 42；58 69；71 71；74 78；87 76；18 40；13 40；82 7；62 33；58 36；45 21；42 26；43 35；4 52]；

所测试项目均符合预期目标，并且APP在运行过程中并未出现任何异常，测试顺利结束。游戏运行界面如图3所示。

其中，ρmin为ρ的最小值，可以防止ρ太小降低算法的收敛速度。

最后可以根据适当条件来终止迭代运算，求得解。

1.2 更新策略

在基本的算法中信息素挥发系数ρ为常数，当处理的问题规模比较大时，由于ρ的存在会使那些从未被搜索到的路径信息素减小到几乎为0，因而降低了算法的全局搜索能力。而当ρ过大时，以前搜索过的路径被再次选择的可能性过大，也会影响算法的随机性和全局搜索能力；反之，通过减小ρ虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低[1]。因此本文采取自适应改变ρ的值，初始值ρ=1，当最优解在一段时间内无明显改进时，ρ会按式 （7）进行自适应调节以加快收敛速度，提高搜索质量。

蚁群算法中“信息素”更新机制的选择直接影响算法性能[4]。本文蚁群算法采用自适应的信息素调节机制，每次搜索迭代过程中，局部地更新信息素。同时，在完成一次循环后，选出全局最优解，进行信息素的全局更新。这样，采取全局最优蚂蚁的信息素不断地进行全局更新，可使信息素尽可能地均匀分布，增强了正反馈机制，提高蚁群算法的收敛速度。本文用函数Q（t）代替基本算法中常数Q，在蚂蚁搜索过程中信息素改变的情况下，能自适应[5-6]地调节以使在后续的随机搜索过程中，避免由于某条路径上信息素过多或过少使算法陷入局部最优解中，有效地保证了算法的求解精度，加快了收敛速度。

在学校安全管理中，学校往往均建立了以校长为核心的领导机构，还制定了相关的若干安全管理制度和事故应急处置预案等等。并做到落实了责任，签订了责任书。可本人却认为安全管理固然重要，可安全教育更需要落实。诸如对学生进行安全教育的内容有无明确的细则？安全活动开展要达到什么样的程度？孩子们的收获怎样等等这些具体的教育措施更是需要静心思考和处理。在具体的安全教育实践中，我们首先要从思想高度上重视安全防范工作，切实做好学生的安全教育落实和督查。定期对校园内外各种安全隐患进行相机排查，并及时解决处理尤为重要。

式中，Δτij表示第 k只蚂蚁在路径 （i，j）上留下的信息量。根据不同的蚁群算法其取值不同，在ant system模型中其取值如式（4）所示。Lk表示第k只蚂蚁本次遍历所走路程总长度；Q为常数，表示信息素强度，在一定程度上影响算法的收敛速度。

其中，常数 ρ∈（0，1）是信息素挥发系数，表示路径上信息量的损耗程度，ρ的大小关系到算法的全局搜索能力和收敛速度。Δτij为一次遍历结束后路径（i，j）的信息素增量。

2 仿真实验结果及分析

本文选用Matlab7.0平台进行仿真。在Matlab中对基本ACA算法和改进后自适应ACA算法参数进行设置。本文的最大迭代次数为 100，n=30，α=1，β=1，m=50，初始的ρ=1。其中以 Y代表 n个城市的坐标，n×2的矩阵。城市坐标可取随机数，本文取：

基于改进后ACA算法在TSP寻优流程图如1所示。

达尔文有一句名言：“最有价值的知识是关于方法的知识。”根据学生的年龄特征，循序渐进地对学生进行自学、观察、操作、比较、迁移、解题、归纳、总结等方法的指导与训练，发现问题及时纠正，慢慢养成良好的学习习惯，发展他们在自主学习、独立思考、解决问题等方面的能力。生物学科概念繁多，容易混淆，涉及面广，有经验的教师在学完一块内容后会采取适当的手段进行处理：带领学生绘制概念图，必修一用得较多；逻辑关系强的做思维导图，比如体液调节、免疫调节；层次分明但又难记住的用列表进行比较，比如不同的育种方式；涉及随机交配和自交的遗传问题利用公式模型。首先由教师指导，之后让学生针对不同内容自己确定方法并独立完成。

这下可好了，总算来了个说人话的！我连忙起身道歉，坐到另外那张床上。这女人反身关上门，坐在我对面床上，摸过洋烟，点起一支叼在嘴上。她又把烟盒递向我，我摇摇头，她顺手一丢，就把烟盒丢到床头柜上。我抬眼打量她，见她正放肆地盯着我，眼都不眨一下！她缓缓吐出一串烟雾，还是盯着我，突然哈哈大笑起来，“这东洋人还真是他娘的馋，连老妈子也稀罕！”

图1 TSP寻优流程图

将基本的ACA算法和改进后的ACA自适应算法同时用于TSP中进行比较分析，通过Matlab绘出的最优解变化图形如图2、图3所示。在Matlab7.0中编程对ACA算法和改进后自适应ACA算法参数进行设置、种群初始化及寻找初始最优值。图 2（a）与图 2（b）为两次运行基本蚁群算法所得出的最优解，分别为433.623和438.302 2，即所得到的结果稳定性很不好，且每次运行得出的结果相差都较大。图3为改进后算法所得最优路径，仿真中输出为426.465 3。在图中可清晰看到最优值明显比基本算法中有所改进，表明改进后的自适应蚁群算法搜索效率和收敛速度明显提高了。

7.2.3 便秘症状有效 定义为基于中医证候的《症状体征分级量化标准》（见表1）中的主症计分和减少至少50%。

图2 基本ACA算法寻优结果

图3 自适应ACA算法寻优结果

本文研究基于蚁群算法的TSP问题，描述了TSP的相关问题和蚁群算法原理。基本的蚁群算法具有较强的鲁棒性，但收敛速度缓慢。针对传统蚁群算法存在搜索时间长、易陷局部最优解，在算法中改进重要的参量——信息素与信息素残留因子，形成动态的自适应信息素，并应用于TSP问题中使运算。论证了将改进后蚁群算法在TSP问题研究应用的可行性，平衡各路径的信息量，使蚂蚁在初始阶段在较大范围内进行搜索，能尽快地找到目标点，并找到最优路径，以避免陷入局部最优。仿真结果表明，相比一般ACA算法，使用改进后的算法可以完成预期的规划效果，在收敛速度、搜索质量和局部寻优方面有了显著的提高。

[1]DORIGO M，GAMBARDELLA L M.Ant colonies for the traveling salesman problem[J].Bio-Systems， 1997， 43（2）：73-81.

[2]DORIGO M， MANIEZZO V， COLORNIA.Theant system：Optimization by a colony of coorperating agents[J].IEEE Transations on System， Man， and Cybernetics-Part B，1996：26（1）：29-41.

[3]段海滨.蚁群算法原理及其应用[M].北京：科技出版社，2005.

[4]杨志晓，郭胜国，等.基于改进蚁群算法的机器人路径规划算法[J].微计算机信息，2008（7-2）：252-253.

[5]覃刚力，杨家木.自适应调整信息索的蚁群算法[J].信息与控制，2002，31（13）：198-201.

[6]王颖，谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报，2002，14（1）：31-33.