龙源期刊网 http://www.qikan.com.cn
蚁群算法在解决TSP问题中的应用
作者：陈灵佳
来源：《电子技术与软件工程》2017年第10期
文章首先对蚁群算法与TSP问题进行简要介绍，在此基础上对蚁群算法在解决TSP问题中的应用进行论述。期望通过本文的研究能够对TSP问题的解决有所帮助。 【关键词】蚁群算法 TSP问题 最优解 1 蚁群算法与TSP问题简介 1.1 蚁群算法
蚁群算法是一种随机的、概率搜索算法，它是目前求解复杂组合优化问题较为有效的手段之一，借助信息反馈机制，能够进一步加快算法的进化，从而更加快速地找到最优解。蚁群算法可在诸多领域中应用，借助该算法能够求得TSP问题的最短路径。蚁群寻找最短路径的过程如图1所示。
蚁群算法之所以在多个领域获得广泛应用，与其自身所具备的诸多优点有着密不可分的关联，如自组织性、正负反馈性、鲁棒性、分布式计算等等，其最为突出的优点是能够与其它算法结合使用。但是在应用实践中发现，虽然蚁群算法的优点较多，其也或多或少地存在一定的不足，如搜索时间较长，规模越大时间越长；容易出现停滞现象等等。 1.2 TSP问题
TSP是旅行商的英文缩写形式，这一术语最早出现于1932年，在1948年时，美国兰德公司（RAND）引入了TSP，由此使得TSP广为人知。从数学领域的角度上讲，TSP问题是NP-完备组合优化问题，这是一个看似简单实则需要天文数字计算能力方可获得最优解的过程，其适用于搜索算法解决不了的复杂与非线性问题。 2 蚁群算法在解决TSP问题中的应用 2.1 蚁群算法的改进
（1）大量的实验结果表明，标准蚁群算法在TSP问题的求解中，很容易陷入局部最优解。这是因为，蚁群的转移主要是由各条路径上的信息素浓度及城市间的距离来引导的，信息素浓度最强的路径是蚁群的首选目标，该路径与最优路径极为接近。然而，各个路径上初始信息素的浓度全部相同，因此，蚁群在对第一条路径进行创建时，主要依赖于城市间的距离信息，这样一来很难确保蚁群创建的路径是最优路径，如果以此为基础，那么信息素便会在该局部最优路径上越积累越多，其上的信息素浓度将会超过其它路径，从而造成全部蚂蚁都会集中
龙源期刊网 http://www.qikan.com.cn
于该路径之上，由此便会造成停滞现象，不但会使搜索的时间增长，而且所求得的解也无法达到理想中的效果。
（2）由于本文研究的是利用蚁群算法来解决TSP问题，所以对蚁群算法的改进应当以此为依据，具体的改进方法如下：对于初始的TSP而言，利用蚁群算法求取最优解时，应考虑的首要问题是预处理环节，可采用近邻法建立一个初始游历，并对信息素的初始值进行计算；利用Ant-Q Systems算法，基于随机性和确定性相结合的策略，在搜索的过程中，对状态转移概率进行调整；对信息素的更新可使用在线单步更新信息素与离线全局更新信息素相结合的方法予以实现。
2.2 改进蚁群算法在TSP求解中的应用 2.2.1 对算法进行初始化
对所有城市的坐标进行获取，以此为依据，对距离矩阵Distmatrix进行计算，同时对随机发生器状态进行初始化，并以随机的形式从n个城市中选出初始的出发城市，并将该城市设定为：
p（1）=round（Ncities*rang+0.5），其中的Ncities代表城市的数目。
通过最近邻法创建一个初始游历，并对距离矩阵进行更新，同步计算出距离总长度len在此基础上对信息素的初始值Q0进行设定，即Q0=1/（Ncities*len）。 2.2.2 算法循环
Step1：对相关参数进行初始化，令NC（循环初始迭代）=1，MaxNC（最大循环次数）=5000，A（信息素因子）=1，B（启发信息因子）=2，P1（局部挥发系数）=P2（全局挥发系数）=0.1，M（蚁群数量）=10，R0（选择概率）=0.9。 Step2：将初始化信息素矩阵进行设定为： Pheromone=Q0*ones（Ncities，Ncities） 同时将启发信息矩阵设定为： Heuristic=1./DistMatrix
在将初始化允许矩阵设定为：allow0=repmat（1：Ncities，M，1） 该矩阵的初始值设为0，最后将M置于Ncities个元素上。 Step3：设循环计数器NC=NC+1。
龙源期刊网 http://www.qikan.com.cn
Step4：设蚂蚁禁忌表索引号AK=1，蚂蚁的数目=AK+1。
Step5：蚂蚁个体按照Ant-Q Systems算法提出的状态转移概率，选择下个城市j并前进。 Step6：对允许矩阵进行更新，使其变为allow（AK，j）=0，即将蚂蚁所选城市标号在该矩阵中对应位置的值重新设定为0。
Step7：如果蚂蚁为遍历集合C中的所有元素，即AK
Step8：对每只蚂蚁找到的路径长度进行计算，并对最优的路径长度及其对应的遍历顺序进行保存，记录并找到最优解的蚂蚁的搜索轨迹。
Step9：若NC≥MaxNC，则整个循环过程结束，如果未达到这一要求，则清空禁忌表，并跳转至Step3，直至达到要求为止。 2.2.3 算法输出
先将全局最优解的轨迹变化图绘制出来，然后再绘制出全局最优解的路线图，最后将最优的遍历顺序、最优的遍历结果以及总体运行时间输出，便可完成对TSP问题的求解。 3 结论
综上所述，蚁群算法以其自身诸多的优点在多个领域中获得了广泛应用，但标准蚁群算法的搜索时间较长，并且容易出现停滞现象。对此，本文提出一种改进的蚁群算法，并对其在TSP问题解决中的应用进行分析。经过改进之后，不但缩短了搜索时间，而且停滞问题也随之消除。 参考文献
[1]杜鹏桢，唐振民，孙研.一种面向对象的多角色蚁群算法及其TSP问题求解[J].控制与决策，2014（10）：85-88.
[2]扈华，王冬青.蚁群算法解决TSP问题图形化软件设计[J].电脑编程技巧与维护，2014（10）：98-100.
[3]徐胜，马小军，钱海.基于遗传-模拟退火的蚁群算法求解TSP问题[J].计算机测量与控制，2016（03）：125-127. 作者单位
同济大学 上海市 201804