基于MATLAB的蚁算法解决旅行商问题
姓名：学号：班级：
摘要：旅行商问题的传统求解方法是遗传算法，但此算法收敛速度慢，并不能获得问题的最优化解。蚁算法是受自然界中蚁搜索食物行为启发而提出的一种智能优化算法，通过介绍蚁觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁算法在旅行商问题中的应用，对问题求
解进行局部优化。经过计算机仿真结果表明，这种蚁算法对求解旅行商问题有较好的改进效果。
关键词：蚁算法；旅行商问题；MATLAB；优化
abstract: The traditional method for solving the traveling salesman problem is a genetic algorithm, but this algorithm converges slowly, and can not get the optimal resolve. Ant colony algorithm is affected by acts of nature inspired ants search of food presented an intelligent optimization algorithm, ant foraging process by introducing the pheromone-based shortest path search strategy, ant colony algorithm based on MATLAB is given in the travel business problems in the application of problem solving local optimization. Through computer simulation results show that the ant colony algorithm for solving the traveling salesman problem better improvement results.
一、意义和目标
旅行商问题是物流领域中的典型问题，它的求解具有十分重要的理论和现实意义。采用一定的物流配送方式，可以大大节省人力物力，完善整个物流系统。
已被广泛采用的遗传算法是旅行商问题的传统求解方法，但遗传算法收敛速度慢，具有一定的缺陷。本文采用蚁算法，充分利用蚁算法的智能性，求解旅行商问题，并进行实例仿真。进行仿真计算的目标是，该算法能够获得旅行商问题的优化结果，平均距离和最短距离。
2、国内外研究现状
仿生学出现于20世纪50年代中期，人们从生物进化机理中受到启发，提
出了遗传算法、进化规划、进化策略等许多用以解决复杂优化问题的新方法。
这些以生物特性为基础的演化算法的发展及对生物落行为的发现引导研究人
员进一步开展了对生物社会性的研究，从而出现了基于智能理论的蚁算法，并掀起了一股研究的热潮。
20世纪90年代意大利科学家M.Dorigo M最早提出了蚁优化算法——蚂蚁系统（Ant system, AS），在求解二次分配、图着问题、车辆调度、集成电路设计以及通信网络负载问题的处理中都取得了较好的结果。
旅行商问题（TSP, Traveling Salesman Problem）被认为是一个基本问题，是在1859年由威廉·汉密尔顿爵士首次提出的。所谓TSP问题是指：有N个城市，要求旅行商到达每个城市各一次，且仅一次，并回到起点，且要求旅行路
线最短。这是一个典型的优化问题，对一个具有中等顶点规模的图来说，精确
求解也是很复杂的，计算量随着城市个数的增加而呈指数级增长，即属于所谓
的 NP问题。TSP在工程领域有着广泛的应用，并常作为比较算法性能的标志。如网络通讯、货物运输、电气布线、管道铺设、加工调度、专家系统、柔性制
造系统等方面，
都是TSP广泛应用的领域。求解算法包括贪婪法（GM）、极小代数法（MA）、模
拟退火法（SA）和遗传算法（GA）等。而应用蚁算法求解旅行商问题是近年
来研究的新方向，由于其并行性与分布性，特别适用于大规模启发式搜索，实
验结果证明了其可行性和有效性。
三、蚁系统基本原理
在蚂蚁到食物时，它们总能到一条从食物到巢穴之间的最优路径。
这是因为蚂蚁在寻路径时会在路径上释放出一种特殊的信息素（phero-mone）。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时
释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的
蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这
样形成了一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素
浓度却会随着时间的流逝而消减。最终整个蚁会出最优路径。在整个寻径
过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁之间
交换着路径信息，最终出最优路径。
4、基于MATLAB的蚁算法求解旅行商问题
TSP问题描述如下：
设有n个城市C=（1，2,...,n），任意两个城市i，j之间的距离为d ij ，求一条经过每个城市的路径π=（π（1），π（2），...，π（n）），使得距离
最小。
主要符号说明
C  n个城市的坐标，n×2的矩阵
NC_max最大迭代次数
m蚂蚁个数
Alpha表征信息素重要程度的参数
Beta表征启发式因子重要程度的参数
Rho 信息素蒸发系数
Q 信息素增加强度系数
R_best各代最佳路线
L_best各代最佳路线的长度
求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化。这里的信息素值分布式存储在图中，与各弧相关联。蚂蚁算法求解TSP问题的过程如下：
（1）首先初始化，设迭代的次数为NC。初始化NC=0
（2）将m个蚂蚁置于n个顶点上
（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游
每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。蚂蚁的任务是访问所有的城市后返回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率
matlab 下载来选择下一点。
（4）记录本次迭代最佳路线
（5）全局更新信息素值
应用全局信息素更新规则来改变信息素值。当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息
素值进行更新。
全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最
短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化
学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信
息素值得到增加。
（6）终止
若终止条件满足，则结束；否则NC=NC+1，转入步骤（2）进行下一代进化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。
（7）输出结果
5、数据实验及结果
通过计算机仿真，得出旅行商问题优化结果和平均距离和最短距离，如图
所示：
六、分析与总结
本文设计了一种基于MATLAB实现的蚁算法，用以求解组合优化难题中的典型代表旅行商问题。对30个城市旅行商问题进行了测试，所得结果能达到优

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。