基于MATLAB的蚁族算法求解旅行商问题

龙源期刊网 https://www.wendangku.net/doc/ef17905552.html,

基于MATLAB的蚁族算法求解旅行商问题作者：李艳平

来源：《计算机光盘软件与应用》2013年第14期

摘要：目前求解旅行商问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法，

本文对蚁群算法的仿真学原理进行概要介绍，蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过蚁群觅食过程中最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用，并通过实例仿真结果表明，此算法有一定优越性。

关键词：蚁群算法；旅行商问题；仿真；多目标优化

中图分类号：TP301.6

旅行商问题（TSP）是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点

数的增加，会产生组合爆炸，它是一个N P完全问题。随着问题规模的增大，人们对复杂事物和复杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化（Simulation Based Optimization，SBO）方法正是在这样的背景下发展起来的。近年来应用蚁群算法求解旅行商问题，由于其并行性与分布性，特别适用于大规模启发式搜索，实验结果表明这种研究方法是可行的。

1 蚁群算法的仿生学原理

蚁群算法最早是由意大利学者M.Dorigo提出来的，它的灵感来源于蚂蚁在寻找食物过程中发现路径的行为，蚂蚁集体寻找路径时，利用称为“外激素”的生物信息激素选择后继行为的智能过程。蚂蚁是一种群居昆虫，在觅食等活动中，彼此依赖、相互协作共同完成特定的任务。

蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁来说不可能完成的任务。总体来讲，蚁群有三个方面的行为特征对算法研究具有一定的启发意义，分别是觅食行为、任务分配和死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴过程。当蚂蚁外出寻找食物时，会在自己走过的路径上释放一种称为信息素的物质。每只蚂蚁都朝向信息素最多的方向移动，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向走下去。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一个位置最近已经走过了，它就会尽量避开。蚂蚁一般倾向于走那些信息素强度更高的路径，较短路