仿真的多目标优化(蚁群算法在旅行商问题中的应用)
蚁群算法在旅行商问题中的应用
（多目标优化模型）
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
蚁群算法在旅行商问题中的应用
摘要
本文将对蚁群算法的仿真学原理进行概要介绍和对蚁群算法产生、发展、优化进行介绍以及阐述蚁群算法的几点重要基本规则，并对蚁群算法的优缺点进行讨论。蚁群算法是受自然界中蚁群搜索食物行为启发而提出的一种智能多目标优化算法，通过介绍蚁群觅食过程中基于信息素的最短路径的搜索策略，给出基于MATLAB的蚁群算法在旅行商问题中的应用。
关键字：蚁群算法；旅行商问题；仿真；多目标优化
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
一、 问题重述
旅行商问题(TSP)是一个经典的组合优化问题。TSP可以描述为：一个商品推销员要去若干个城市推销商品， 该推销员从一个城市出发， 需要经过所有城市后，回到出发地。应如何选择行进路线， 以使总的行程最短。从图论的角度来看， 该问题实质是在一个带权完全无向图中， 找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列， 随着顶点数的增加， 会产生组合爆炸， 它是一个N P完全问题。 随着问题规模的增大，人们对复杂事物和复
杂系统建立数学模型并进行求解的能力是有限的，目标函数和约束条件往往不能以明确的函数关系表达，或因函数带有随机参、变量，导致基于数学模型的优化方法在应用于实际生产时，有其局限性甚至不适用。基于仿真的优化(Simulation Based Optimization，SBO)方法正是在这样的背景下发展起来的。本文将使用一种近似算法或启发式算法—蚁族算法。
1、蚁群算法的提出
蚁群算法(Ant Colony Optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
2、蚁群算法的仿生学原理
蚁群算法最初是通过对蚂蚁群落的观察，受蚁群行为特 征启发而得出的。蚂蚁是一种群居昆虫，在觅食、清理巢穴 征启发而得出的。蚂蚁是一种群居昆虫，在觅食、 等活动中，彼此依赖、相互协作共同完成特定的任务。 等活动中，彼此依赖、相互协作共同完成特定的任务。就个 体来讲，单个蚂蚁的智力和体力是极其有限的， 体来讲，单个蚂蚁的智力和体力是极其有限的，服务于整个 群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、 群落的生存与发展；就群体来讲，蚁群在行为上的分工协作、 在完成任务过程中所体现的自组织特征等反应出蚁群具有较 高的智能和自我管理能力，具有很高层次组织性， 高的智能和自我管理能力，具有很高层次组织性，这使得蚁 群能够完成一些复杂的任务。 群能够完成一些复杂的任务。
蚁群的行为是整体协作，相互分工，蚁群的行为是整体协作，相互分工，以一个整体去解决一 些对单个蚂蚁看上去是不可能完成的任务。 些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为.当蚂蚁出外寻找食物时，会在自己走过的路 径上释放一种称为信息家的物质，径上释放一种称为信息家的物质，后续的蚂蚁一般更愿意走 那些信息素强度更高的路径。这样，那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多(浓度更高) 通过的蚂蚁数目较多，留下的信息素也较多(浓度更高)，对蚂蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。 妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这 就形成了一个正反馈机制， 就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到 食物源的最短路径. 食物源的最短路径.
3、蚁群算法实现的重要规则 （1）范围
蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
围之内。
（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
要
短，从而导致矛盾。所以，旅行商问题一定满足最优性原理。
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
四、符号说明
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
五、模型的建立与求解
1.旅行商模型：
G (V,E)
为一个带权图,V {1,2, n}为顶点
集,E {eij {(i,j)i,j V,i j}为边集。dij(i,j V,i j)为顶点i到顶点j 的距离， 其中dij 0且dij ，同时dij dji(i,j V),则经典TSP的数学模型为：
minF dijxxij
i j
(1)
(2)
1`,边eij在最优路径上
st..xij
0，边eij不在最优路径上
xij 1,i V
i j
(3) (4) (5)
x
i j
ij
1,j V
s,s是G的子图
i,j s
其中s是图s 的顶点数。（1）为ctsp的目标函数,求经过所有顶点的回路的最小距离。（2）-（4）限定回路上每个顶点仅有一条入边和一条出边。( 5 ) 限
定在回路中不出现子回路。模型实质上是在一个带权图中求一条H a m i l t o
n回路。若对所有i，j,k ∈V， 不等式dij djk dik均成立， 则称该问题是满足三角不等式的。
2.蚂蚁算法求解TSP 问题的具体过程如下：
1
（1）首先初始化，设迭代次数为NC。初始化NC=0，各 (i,j)初始化； 0 nL nn
（2）将m 个蚂蚁置于n 个顶点上；
（3）构造解。每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条线路。蚂蚁任务是访问所有的城市后回到起点，生成一条回路。设蚂蚁k当前所在的顶点为i，那么，蚂蚁k 由点i 向点j 移动要遵循（1）式的状态变化规则而不断迁移，按不同概率来选择下一点。
j
argJ
k allowed
max
(
)( )ijij
q q0q q0
(Exloitation)
(1)
(Exloitation)
（1）式中，alowedk {0,1, n 1} tabuk表示蚂蚁k 当前能选择的城市集合，
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
tabuk为禁忌表，它记录蚂蚁k已路过的城市，用来说明人工蚂蚁的记忆性 ；式中 ij相当于真实蚂蚁沿途散播的信息素，是一个正实数，与图G中弧（i，j）关联，其值在运行时不断改变，用于表示蚂蚁从点i向点j移动的动力； ij用于评价蚂蚁从点i 向点j 移动的启发函数，其值通常用距离的倒数来求得，即
ij d(ci,cj) 1。 , 体现了信息素和启发信息对蚂蚁决策的影响。 取值为1；
参数 0描述启发函数的重要性；参数q0(0 q0 1)决定利用和开发的相对重 要性，利用（Exploitation）是指走最好的路，开发（Exploration）是指按浓度高概率高的原则选路V，这样可以保证选择路径的多样性；q 是在[0，1] 取的随机数，当q q0时，按（1）式选最好的路，否则按（2）式的概率进行选路：
( ij) ( ij)
k( (t))( )ikikpij(t)
k allowed 0
if
j allowedk
otherwise
（4）局部更新信息素值。应用局部信息素更新规则来改变信息素值。在构
造解时，蚂蚁k 对其走过的每条弧用：
newold ij (1 ) ij 0
局部信息素更新规则来改变弧上关联的信息素值，其中0 1是信息素挥发参数。
（5）若所有的m个蚂蚁都构造完解，则转（6） ；否则转（3） ；
（6）全局更新信息素值。应用全局信息素更新规则来改变信息素值。当所有m 个蚂蚁生成了m 个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值按下式更新：
gb
ij(t 1) (1 ) ij(t) ij(t)
gb
1/L(t)gb
ij(t)
0
if
arc(i,j) Tgbotherwise
其中0 1是挥发参数；Lgb(t)是目前得到的全局最优解的路线长度。 全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加；
（7）终止。若终止条件满足，则结束；否则NC=NC+1，转（2）进行下一代
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
进化。终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。
例：一个商品推销员要去若干个城市推销商品， 该推销员从一个城市出发， 需要经过所有城市后，回到出发地。应如何选择行进路线， 以使总的行程最短。
最短路径图
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
每次循环最短路径长度和平均路径长度图
020406080100120140160180200
得出：15-14-25-10-6-28-18-3-7-1-26-8-19-17-27-13-4-2-29-24-5-20-16 22-11-21-9的和最短路径线路
六、模型评价
蚁群算法（ACA） 不仅利用了正反馈原理, 在一定程度上可以加快进化过程, 而且是一种本质并行的算法, 个体之间不断进行信息交流和传递, 有利于发现较好解.单个个体容易收敛于局部最优, 但多个个体通过合作, 很快收敛于解空间的某一子集, 有利于对解空间的进一步探索, 从而不易陷入局部最优。但是ACA也具有速度慢、易陷入局部最优等缺点。蚁群中多个个体的运动是随机的, 当群体规模较大时, 要找出一条较好的路径需要较长的搜索时间。
七、参考文献
[1] 陈文兰,戴树贵.旅行商问题算法研究综述.滁州学院学报,2006年，第8卷：1-6
[2] 尹晓峰,刘春煌,张睢皎. 基于MATLAB的混合型蚁群算法求解车辆路径问题 铁道部科学研究院电子所,2005年，第14卷：32-42
[3] 薛定宇,陈阳泉.高等应用数学问题的MATLAB求解.北京：清华大学出版社，2011，197-209
[4] 司守奎.数学建模算法.大连：海军航空工程学院出版社，2007，395-411
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
八、附件
蚁群算法求解旅行商问题的matlab程序： clear； clc；
%初始化蚁群
m=31;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解
C=[304 312;639 315;177 244;712 399;488 535;326 556;238 229;196 104; 312 790;386 570;107 970;562 756;788 491;381 676;332 695;715 678; 918 179;161 370;780 212;676 578;329 838;263 931;429 908;507 367;
394 643;439 201;935 240;140 550;545 357;778 826;370 975];%城市的坐标矩阵
Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m）
alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象 beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度
rho=0.5;%0<rho<1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数
Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大
%变量初始化
n=size(C,1);%表示TSP问题的规模，亦即城市的数量
D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离 for i=1:n for j=1:n if i<j
D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2); end
D(j,i)=D(i,j); end end
eta=1./D;%启发式因子，这里设为城市之间距离的倒数
pheromone=ones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1
tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度 Nc=0;%循环次数计数器
routh_best=zeros(Nc_max,n);%各次循环的最短路径
length_best=ones(Nc_max,1);%各次循环最短路径的长度
length_average=ones(Nc_max,1);%各次循环所有路径的平均长度
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
while Nc<Nc_max
%将m只蚂蚁放在n个城市上 rand_position=[]; for i=1:ceil(m/n)
rand_position=[rand_position,randperm(n)]; end
tabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在城市上之后的禁忌表，第i行表示第i只蚂蚁，第i行第一列元素表示第i只蚂蚁所在的初始城市 %m只蚂蚁按概率函数选择下一座城市，在本次循环中完成各自的周游 for j=2:n for i=1:m
city_visited=tabu_list(i,1:(j-1));%已访问的城市 city_remained=zeros(1,(n-j+1));%待访问的城市 probability=city_remained;%待访问城市的访问概率 cr=1;
for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=[2 4],则经过此for循环后city_remanied=[1 3 5] if length(find(city_visited==k))==0 city_remained(cr)=k; cr=cr+1; end end
%状态转移规则**************************************** q0=0.5; if rand>q0
for k=1:length(city_remained)
probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta; position=find(probability==max(probability)); to_visit=city_remained(position(1)); end else
for k=1:length(city_remained)
probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta; end
probability=probability/sum(probability); pcum=cumsum(probability); select=find(pcum>=rand);
to_visit=city_remained(select(1)); end
tabu_list(i,j)=to_visit;
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
%************************************************************** end end
if Nc>0
tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失 end
%记录本次循环的最佳路线
total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m
r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径 for j=1:(n-1)
total_length(i)=total_length(i)+D(r(j),r(j+1));%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度 end
total_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i只蚂蚁在本次循环中所走过的路径长度 end
length_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度
position=find(total_length==length_best(Nc+1));%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的
routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径
length_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度 Nc=Nc+1 %更新信息素
delta_pheromone=zeros(n,n); for i=1:m
for j=1:(n-1)
delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))+Q/total_length(i);%total_length(i)为第i只蚂蚁在本次循环中所走过的路径长度（蚁周系统区别于蚁密系统和蚁量系统的地方） end
delta_pheromone(tabu_list(i,n),tabu_list(i,1))=delta_pheromone(tabu_list(i,n),tabu_list(i,1))+Q/total_length(i);%至此把第i只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去
end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去 pheromone=(1-rho).*pheromone+delta_pheromone;%本次循环后所有路径上的信息素
%禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择
仿真的多目标优化(蚁群算法在旅行商问题中的应用)
tabu_list=zeros(m,n); end
%输出结果，绘制图形
position=find(length_best==min(length_best)); shortest_path=routh_best(position(1),:) shortest_length=length_best(position(1)) %绘制最短路径 figure(1)
set(gcf,'Name','Ant Colony Optimization——Figure of shortest_path','Color','r') N=length(shortest_path);
scatter(C(:,1),C(:,2),50,'filled'); hold on
plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)]) set(gca,'Color','g') hold on for i=2:N
plot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)]) hold on end
%绘制每次循环最短路径长度和平均路径长度 figure(2)
set(gcf,'Name','Ant Colony Optimization——Figure of length_best and length_average','Color','r') plot(length_best,'r') set(gca,'Color','g') hold on
plot(length_average,'k')
