王爽瑶 范 爽 王 健 沈镕荣

(合肥工业大学宣城校区商学系 安徽 宣城 242000)

基于ACO的TSP问题研究

王爽瑶 范 爽 王 健 沈镕荣

(合肥工业大学宣城校区商学系 安徽 宣城 242000)

从1991年意大利学者DorigoM等首次提出蚁群算法以来，蚁群算法作为一种自然计算方法，由解决TSP问题开始，从一维静态优化问题到多维动态优化问题，发展到今天已经相对成熟了，蚁群算法可以用来解决一些尚未找到有效算法的问题，而且蚁群算法还是元启发式算法(Metaheuristic)，是一种算法框架，可以在其基本思想上针对不同问题做改进从而应用到不同问题上去。

Tsp问题；蚁群算法

一、概述

旅行商问题：假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

旅行商问题是一个典型的组合优化问题，并且是一个NP难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解。目前，对TSP问题的研究主要是通过一些启发式算法，如遗传算法、蚁群算法、模拟退火算法等，且都取得了一定的成果。

二、基于TSP问题的蚁群算法模型

这里为了让TSP问题更加的清晰可视，便于基于TSP问题的蚁群算法模型的研究，我们先用数学语言描述TSP。

记G=(V,E)为赋权图，V=(1,2,…,n)为顶点集，E为边集，各顶点间的距离为dij，已知(dij>0,dij=∞,i,j∈V)。设当(i,j)在最优回路上，χij取得1值，其他为0，则

则，经典的TSP问题可写为如下的数学规划模型

上式中，S的绝对值为集合S中所包含的顶点集。约束(a)和约束(b)意味着对每个点来说，仅有一条边进一条边出；约束(c)则说明了没有任何字回路。于是，满足上面三个约束条件的解就构成了一条回路。这便是TSP问题的数学表达方式。

根据上述TSP问题数学表达可知，在TSP问题中，城市的数目成为该问题的阶数。综合对比TSP问题和蚁群算法两者之间各自的特性，通过蚁群算法解决旅行商问题不失为一种相对有效的方式。

根据对TSP问题的分析，结合蚁群算法模型，蚂蚁可以按照下列公式选择下一个访问的节点：

由上式可知，转移概率与[τis(t)]α*(ηis(t))β成正比，与真正的蚂蚁相比，一个人工蚁群系统有一个记忆内存，为了满足所有蚂蚁必须通过所有城市的约束条件，对于每个蚂蚁这里应该要建立一个数据结构，也就是禁忌表，但为了更方便的进行模拟仿真，我们这里建立与禁忌表功能类似的城市数据数组表，记录在时刻t蚂蚁还没有通过的城市，即：蚂蚁在时刻t能够选择的下一个城市的集合，在这个循环周期内，蚂蚁只能从城市数据数组表中选择城市进行下一步的转移。在一个循环周期结束后，城市数据数组表是用来记录该蚂蚁当前所形成的解决方案，即蚂蚁所行走的路径，然后，城市数据数组表将为空值，蚂蚁重新选择行走 路径。

值得注意的一点是，为了防止残余信息素太多掩盖了启发信息，在完成所需要的步骤或完成整个城市之旅之后，要人工对信息素进行更新处理，这种机能类似于人类大脑的记忆。

根据上述提示，在仿真应用上，每次迭代优化前，需要对各个节点上残留的信息素进行更新，可以参照下列公式进行。

τij(t+n)=(1-ρ)·τij(t)+Δτij(t)

上式中，

Δτij(t,t+n)表示本次循环中路径(i，j)上的信息素增量；

值得注意的是，对于信息素的增量Δτij(t,t+n)，我们采取的是蚁量算法，即：

其中Lk表示第k只蚂蚁在所走的路径长度。

三、算法步骤

Step1 初始化参数：初始化蚂蚁个数，α、β、ρ、Q，最大循环次数，当前较优解、最优解

Step2 输入每个城市的名字和坐标，根据坐标计算两两城市间的距离，并将所有蚂蚁置于起点城市

Step3 重复Step4～Step7，直至最大迭代次数

Step4蚂蚁从存有城市状态的数组里搜索，从起点城市开始，利用状态转移函数先计算出选择下一个没有去过城市的概率，然后利用轮盘随机选择下一个出发城市。当蚂蚁走完所有城市的时候，计算整条路径的距离，并保存蚂蚁在两两城市间新留下的信息素。

Step5 每一只蚂蚁重复Step4，直到一组的所有蚂蚁走完所有城市

Step6 将每组蚂蚁的较优解保存在数组里，并利用信息素更新规则更新信息素。

Step7 迭代次数n+1

Step8 在保存较优解的数组里找出最优解，输出每次的较优路径及长度到控制台，输出最佳路径及长度到控制台

王爽瑶(1996.07-)，女，汉族，重庆人，合肥工业大学宣城校区商学系，2014级本科生，研究方向：物流管理。