仿真的多目标优化（蚁群算法在旅行商问题中的应用）

蚁群算法在旅行商问题中的应用

（多目标优化模型）

蚁群算法在旅行商问题中的应用

摘要

本文将对蚁群算法的仿真学原理进行概要介绍和对蚁群算法产生、发展、优化进行介绍以及阐述蚁群算法的几点重要基本规则，并对蚁群算法的优缺点进行讨论。蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用。

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

1

一、 问题重述

旅行商问题(TSP)是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品， 该推销员从一个城市出发， 需要经过所有城市后，回到出发地。应如何选择行进路线， 以使总的行程最短。从图论的角度来看， 该问题实质是在一个带权完全无向图中， 找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列， 随着顶点数的增加， 会产生组合爆炸， 它是一个N P完全问题。 随着问题规模的增大，人们对复杂事物和复

杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下发展起来的。本文将使用一种近似算法或启发式算法—蚁族算法。

1、蚁群算法的提出

蚁群算法(Ant Colony Optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

2、蚁群算法的仿生学原理

蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特 征启发而得出的。蚂蚁是一种群居昆虫，在觅食、清理巢穴 征启发而得出的。蚂蚁是一种群居昆虫，在觅食、 等活动中，彼此依赖、相互协作共同完成特定的任务。 等活动中，彼此依赖、相互协作共同完成特定的任务。就个 体来讲，单个蚂蚁的智力和体力是极其有限的， 体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个 群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、 群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、 在完成任务过程中所体现的自组织特征等反应出蚁群具有较 高的智能和自我管理能力，具有很高层次组织性， 高的智能和自我管理能力，具有很高层次组织性，这使得蚁 群能够完成一些复杂的任务。 群能够完成一些复杂的任务。

蚁群的行为是整体协作，相互分工，蚁群的行为是整体协作，相互分工，以一个整体去解决一 些对单个蚂蚁看上去是不可能完成的任务。 些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为.当蚂蚁出外寻找食物时，会在自己走过的路 径上释放一种称为信息家的物质，径上释放一种称为信息家的物质，后续的蚂蚁一般更愿意走 那些信息素强度更高的路径。这样，那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多(浓度更高) 通过的蚂蚁数目较多，留下的信息素也较多(浓度更高)，对蚂蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。 妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这 就形成了一个正反馈机制， 就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到 食物源的最短路径. 食物源的最短路径.

3、蚁群算法实现的重要规则 （1）范围

蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范

2

围之内。

（2）环境

蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。

（3）觅食规则

在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

（4）移动规则

每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。

（5）避障规则：

如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。

（6）播撒信息素规则：

每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

二、问题分析

旅行商问题的各个城市间的距离可以用代价矩阵来表示，就是邻接矩阵表示

c??法。如果(i,j)?E，则ij。

先说明旅行商问题具有最优解结构。设

s1,s2,.....,sp,s是从s出发的一条路径

长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求s1到S的最短路径，显然设

s1,s2,.....,sp,s一定构成一条从s1到S的最短路径，如果不然，

s1,r1,r2,.....,rq,s是一条从s1到S的最短路径且经过n-1个城市，则

s,s1,r1,r2,.....,rq,s将是从S出发的路径长度最短的简单回路且比

s,s1,s2,.....,sp,s要

短，从而导致矛盾。所以，旅行商问题一定满足最优性原理。

3