一种改进的蚁群算法求解TSP问题及实验结果分析（完整版）实用资料(可以直接使用，可编辑完整版实用资料，欢迎下载）一种改进的蚁群算法求解TSP问题及实验结果分析何开成（四川大学电子信息学院四川成都610064）摘要：首先对蚁群算法的基本模型进行介绍，其次针对算法容易陷入局部最优解，在算法中加入扰动量，扩大搜索范围，从而有效控制算法陷入局部最优解。针对蚁群算法收敛速度慢，利用蚁群在最差路径上的信息，对蚁群算法信息素更新规则上进行改进。实验结果表明，提出的改进蚁群算法有效的避免程序过早的陷入局部最优解，同时提高蚁群算法的速度。关键词：蚁群算法；扰动量；算法改进；局部最优解中图分类号：TP301文献标识码：A文章编号：1671－7597（2021）0820071－021蚁群算法基本模型许多种类的蚂蚁在食物搜索过程中都存在释放信息素和信息素引导的现象。Deneubourg利用一个简单的试验模型说明了这种以自组织为基础的路径选择方式。在此模型中，蚁穴和食物之间被一座有两个等长支路的桥所分离。开始时，由于两条支路上都没有信息素分布，蚂蚁们将按照相同的概率进行路径选择。引入随机波动后，将有一条路径上通过的蚂蚁会更多一些，这将增加该路径上的信息素浓度，于是就会引导更多的蚂蚁选择这条路径。在Deneubourg设计的试验中，遗留在路径上的信息素浓度与经过的蚂蚁数量成正比，而且不考虑信息素的挥发问题。在这种简化的模型中，蚂蚁选择路径的依据就是己经过该路径的蚂蚁总数。设减和尽双为第i个蚂蚁经过桥之后，分别选择了路径A和B的蚂蚁数。则第i+l只蚂蚁选择路径A和B是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：模拟退火算法，禁忌搜索算法，Hopfield神经网络优化算法，蚁群算法，遗传算法，混合优化策略。3蚁群算法求解旅行商问题模型以求解平面上n个城市的旅行商问题为例说明蚁群系统的基本模型。旅行商问题就是给定n个城市的位置和两两城市之间的距离，要求确定一条经过各城市当一次且只有一次的最短路线。其图论描述为：给定图（V，A），其中v为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的回路，即遍历所有顶点一次且只有一次的最短回路。为了更好地说明问题，首先引入如下记号M：蚁群中蚂蚁数量；bi（t）：t时刻位于城市i的蚂蚁的个数，i和j之间的距离；nij：边（i，j）的能见度，城市i和j之1/diji，j）上的信息素轨迹强度；k在边（i，jk的转移概率，j是尚未访问的城市。每只蚂蚁都是具有如下特征的简单实体；1）在从城市派到城市j的运动过程中或是在完成一次循环后，蚂蚁在边（i，j）上释放一种物质，成为信息素轨迹；2）蚂蚁按概率选择下一个将要访问地城市，这个概率是城市间的距离和连接两城市的路径上存有的轨迹量的函数；3）为了满足问题的约束条件，在完成一次循环以前，不允许蚂蚁选择己经选择过的城市。=C（C为常数）。蚂蚁k（k=1，2，3，…，m）在运动过程中根据各条路径上的信息素量决定转移方向。蚁群系统使用随机比例转移规则进行状态的转移。转移规则给出了位于城市i的蚂蚁kk在城市i选择城市j的转移概率式中：allowed={0，1，k下一步允许选择的城市。经过n个时刻，当m只蚂蚁都经过一次搜索周期后，在路径上的信息素量的改变根据下面式子进行更新：上述公式对这种选择方式进行了量化。参数n决定了选择函数的非线性度，n较大时，只要一条路径上的信息素浓度稍高于另外一条路径，则下一只蚂蚁选择前一路径的概率就会更大。参数k反映了未标记路径的吸引力，k越大，则进行非随机化选择所需的信息素浓度要求越高。这种概率表达方式是实际的蚂蚁路径选择试验推导而来的。比较适合试验需要的参数设置是n=2和k=20。2旅行商问题旅行商问题（TravelingSalesmanProblem，简称TSP）即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：1）对称旅行商问题（dij=diji，j=1，2，3，…，n）；2）非对称旅行商问题（dijdiji，j=1，2，3，…，n）。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V={v1，v2，v3，…，vn}的一个访问顺序为T={t1，t2，t3，…ti，…，tn}，其中ti