基于蚁群算法的旅行商问题研究（论文）Word文档格式.docx
《基于蚁群算法的旅行商问题研究（论文）Word文档格式.docx》由会员分享，可在线阅读，更多相关《基于蚁群算法的旅行商问题研究（论文）Word文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
2.1TSP问题
TSP问题即旅行售货商问题（travelingsalesmanproblem）。
描述如下:
给定n个城市的集合{1
2,…,n}及城市之间环游的费用Cij（1£
i,j£
n,i¹
j）。
TSP问题是指找到一条经过每个城市至少一次
且回到起点的最小费用的环游。
若将每个城市看成是图上的一个顶点 ,费用Cij（1£
j）看成连
接顶点Vi
和Vj
的边上的权,则TSP问题就是在一个具有n个顶点的图上找到一条费用最小的Hamilton
回路。
任意两个城市A,B,如果A到B的旅行代价和B到A旅行代价相等,称这样的TSP问题是对称的TSP问题，否则称为不对称的TSP问题。
通常,在没有特别申明的情况下所提及的 TSP问题指对称的
TSP间题。
自TSP问题提出以来其求解方法得到了不断的改进，目前已经可以对上万个城市的TSP问题进行求解。
近年来,以蚁群行为为基础的蚁群算法已成为一种较为有效的TSP问题求解方法。
2.2基本蚁群算法
2.2.1蚁群算法原理
蚁群算法（AntColonyalgorithm,ACA）是DorigoM等人于1991年提出的。
经观察发现,蚂蚁个体之间是通过一种称之为信息素（pheromone）的物质进行信息传递的。
在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动。
因此,蚁群的集体行为便表现出一种信息正反馈现象:
某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的[5]。
2.2.2蚁群算法基本模型
以具有代表性的TSP问题为例,设有n个城市,蚂蚁数量为m,
dij（i,j=1,2,3....n）表示城市i和j
之间的距离,tij（t）表示在t时刻城市i和j之间的路径上残留的信息量,来模拟实际蚂蚁的信息素浓度。
初始化时,m个蚂蚁被放置在不同的城市上,并赋予每条边上的信息量为tij（0）。
蚂蚁k的tabuk（禁忌表）的
ij
第一个元素赋值为它所在的城市。
用Pk（t）表示在t时刻蚂蚁k由城市i转移到城市j的概率,则
ij ij
ì
ta（t）hb（t）
ï
k ï
ta b
jÎ
allowedk
Pij（t）=í
å
is（t）hsi（t）
（1）
其中allowedk
ï
sÎ
allowedk
î
0,otherwise
表示蚂蚁k下一步允许走过的城市的集合,它随蚂蚁k的行进过程而动态改变;
信息
量tij（t）随时间的推移会逐步衰减,a,
b分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂
蚁选择路径中所起的不同作用;
hij（t）为由城市i转移到城市j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有的点,完成一次循环。
此时,要根据下面公式更新各路径上的信息量:
t（t+n）=（1-r）tij（t）+Vtij（t）
其中
（2）
Vt（t）=å
Vt（t）
m
k
k=1
（3）
r表示信息素挥发系数，Vtk（t）
表示蚂蚁k在本次循环中在点i和点j之间留下的信息量,其
计算方法根据计算模型而定,在最常用的antcyclesystem模型中：
QL
,若蚂蚁k在本次循环中经过点和i j
Vtij（t）=í
k
其中Q为常数,Lk为蚂蚁k在本次循环中所走路径的长度。
（4）
2.2.3蚁群算法流程
步骤1：
nc=0（nc为迭代步数或搜索次数）;
每条边上的tij（0）=c（常数）,并且Vtij（0）=0;
放置m
个蚂蚁到n个城市上。
步骤 2：
将各蚂蚁的初始出发点置于当前解集tabuk（s）中;
对每个蚂蚁 k（k=1,…,m）,按概率
Pk（t）移至下一城市j;
将城市j置于tabuk（s）中。
步骤 3：
经过n个时刻,蚂蚁k可走完所有的城市,完成一次循环。
计算每个蚂蚁走过的总路径长度
Lk,更新找到的最短路径。
步骤4：
更新每条边上的信息量t（t+n）。
步骤5：
对每一条边置Vtij=0;
nc=nc+1。
步骤6:
若nc<
预定的迭代次数NCMAX,则转步骤2;
否则,打印出最短路径,终止整个程序。
2.2.4影响蚁群算法效果的因素[6]
（1）局部搜索策略。
人工蚂蚁在选择将要行走的路线时,所采用的策略是随机的局部搜索策略。
这个策略主要基于以下两点:
①蚂蚁个体保留的“经验”;
②问题中公开可用的信息素轨迹和局部信息。
（2）蚂蚁的内部状态。
内部状态主要保留了对决策有用的信息,用于计算生成解的价值、优劣度和每个执行步的贡献。
（3）信息素轨迹。
由于信息素轨迹的正反馈机制,选择某路径的蚂蚁越多,一个执行步得到的回报就越多,该路径对于后继蚂蚁的吸引力也就越大。
（4）蚂蚁决策策略。
蚂蚁的决策策略是由信息素函数与启发信息函数共同决定的,即概率表。
利用基于概率的原理再配合信息素挥发机制,避免了所有蚂蚁都过早地早熟收敛。
3.仿真研究
3.1任务要求
基于ant—cycle模型，采用蚁群算法求解具有30个城市的TSP问题。
各城市坐标如下：
41
，94；
37，84；
54，67；
25，62；
7，64；
2，99；
68，58；
71，44；
54，62；
83，69；
64，60；
18，54
；
22，60；
83，46；
91，38；
25，38；
24，42；
58，69；
71，71；
74，78；
87，76；
18，40；
13，40；
82，7；
62，32；
58，35；
45，21；
41，26；
44，35；
4，50
要求：
1.采用Matlab7.1实现上述优化程序。
给出得到的最短路径，用Matlab画出最短路径所连接的城市地图。
2．分析3个参数：
信息激素的启发因子a、自启发量因子b、信息激素残留系数r取不同值时对
算法性能的影响。
3.2程序分析
function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP（C,NC_max,m,Alpha,Beta,Rho,Q）
%%=========================================================================
%%ACATSP.m
%%AntColonyAlgorithmforTravelingSalesmanProblem
%%-------------------------------------------------------------------------
%%主要符号说明
%%C n个城市的坐标，n×
2的矩阵
%%NC_max最大迭代次数
%%m 蚂蚁个数
%%Alpha 表征信息素重要程度的参数
%%Beta 表征启发式因子重要程度的参数
%%Rho 信息素蒸发系数
%%Q 信息素增加强度系数
%%R_best各代最佳路线
%%L_best各代最佳路线的长度
%%===================================================================C=[41
];
m=31;
Alpha=1;
Beta=5;
Rho=.7;
NC_max=30;
Q=100;
%%第一步：
变量初始化
n=size（C,1）;
%表示问题的规模（城市个数）
D=zeros（n,n）;
%D表示完全图的赋权邻接矩阵
fori=1:
nforj=1:
n
ifi~=j
D（i,j）=（（C（i,1）-C（j,1））^2+（C（i,2）-C（j,2））^2）^0.5;
两个城市之间的距离
else
D（i,j）=eps;
endD（j,i）=D（i,j）;
endend
Eta=1./D;
%Eta为启发因子，这里设为距离的倒数
Tau=ones（n,n）;
%Tau为信息素矩阵
Tabu=zeros（m,n）;
%存储并记录路径的生成
NC=1;
%迭代计数器
R_best=zeros（NC_max,n）;
%各代最佳路线
L_best=inf.*ones（NC_max,1）;
%各代最佳路线的长度
L_ave=zeros（NC_max,1）;
%各代路线的平均长度
whileNC<
=NC_max%停止条件之一：
达到最大迭代次数
%%第二步：
将m只蚂蚁放到n个城市上Randpos=[];
（ceil（m/n））Randpos=[Randpos,randperm（n）];
endTabu（:
1）=（Randpos（1,1:
m））'
;
%%第三步：
m只蚂蚁按概率函数选择下一座城市，完成各自的周游forj=2:
visited=Tabu（i,1:
（j-1））;
%已访问的城市J=zeros（1,（n-j+1））;
%待访问的城市
P=J;
%待访问城市的选择概率分布Jc=1;
fork=1:
iflength（find（visited==k））==0J（Jc）=k;
Jc=Jc+1;
end
%下面计算待选城市的概率分布fork=1:
length（J）
P（k）=（Tau（visited（end）,J（k））^Alpha）*（Eta（visited（end）,J（k））^Beta）;
end
P=P/（sum（P））;
%按概率原则选取下一个城市Pcum=cumsum（P）;
Select=find（Pcum>
=rand）;
to_visit=J（Select
（1））;
Tabu（i,j）=to_visit;
ifNC>
=2
Tabu（1,:
）=R_best（NC-1,:
）;
%%第四步：
记录本次迭代最佳路线L=zeros（m,1）;
mR=Tabu（i,:
forj=1:
（n-1）L（i）=L（i）+D（R（j）,R（j+1））;
endL（i）=L（i）+D（R
（1）,R（n））;
endL_best（NC）=min（L）;
pos=find（L==L_best（NC））;
R_best（NC,:
）=Tabu（pos
（1）,:
L_ave（NC）=mean（L）;
NC=NC+1
%%第五步：
更新信息素Delta_Tau=zeros（n,n）;
（n-1）
Delta_Tau（Tabu（i,j）,Tabu（i,j+1））=Delta_Tau（Tabu（i,j）,Tabu（i,j+1））+Q/L（i）;
Delta_Tau（Tabu（i,n）,Tabu（i,1））=Delta_Tau（Tabu（i,n）,Tabu（i,1））+Q/L（i）;
Tau=（1-Rho）.*Tau+Delta_Tau;
%%第六步：
禁忌表清零Tabu=zeros（m,n）;
%%第七步：
输出结果Pos=find（L_best==min（L_best））;
Shortest_Route=R_best（Pos
（1）,:
Shortest_Length=L_best（Pos
（1））;
subplot（1,2,1）DrawRoute（C,Shortest_Route）
subplot（1,2,2）plot（L_best）holdonplot（L_ave,'
r'
）
title（'
平均距离与最短距离'
functionDrawRoute（C,R）
%%====================================================================
%%DrawRoute.m
%%画路线图的子函数
%%--------------------------------------------------------------------
%%C Coordinate 节点坐标，由一个N×
2的矩阵存储
%%R Route 路线
N=length（R）scatter（C（:
1）,C（:
2））holdon
plot（[C（R
（1）,1）,C（R（N）,1）],[C（R
（1）,2）,C（R（N）,2）]）
holdon
forii=2:
N
plot（[C（R（ii-1）,1）,C（R（ii）,1）],[C（R（ii-1）,2）,C（R（ii）,2）]）
holdonend
旅行商问题优化结果'
在MATLAB中运行上述程序，得出下图3.1：
图3.1旅行商优化结果及最短距离
注：
红线为平均距离，蓝线为最短距离。
由图形可知，当a=1，b=5，r=0.7时，得到的最短距离为428，远小于平均距离，城市的遍历顺
序为（41,94）à
（37,84）à
（2,99）à
（7,64）à
（25,62）à
（22,60）à
（18,54）à
（4,50）à
（13,40）à
（18,40）
à
（24,42）à
（25,38）à
（45,21）à
（41,26）à
（44,35）à
（58,35）à
（62,32）à
（82,7）à
（91,38）à
（83,46）à
（
71,44）à
（68,58）à
（64,60）à
（54,62）à
（54,67）à
（58,69）à
（71,71）à
（83,69）à
（87,76）à
（74,78）。
由
此可知，蚁群算法可以很好地解决旅行商问题。
3.3参数分析
需要指出的是,下述分析是在确定其他参数的前提下,调整其中某一参数来考察算法的收敛效果和性能的。
如何针对参数的组合变化情况对算法的性能进行分析,目前仍没有明确的结论和理论指导。
3.3.1信息激素的启发因子a
当取b=5，r=0.7时，TSP优化结果及最短距离随着a的变化相应地如图3.2~3.5所示：
图3.2a=0
图3.3a=1
图3.4a=50
图3.5a=100
a表示信息素轨迹的相对重要性，a≥0，通过对以上四幅图的对比可知a取1时得到的最优解最好。
但是随着a的增大，收敛速度会随着加快。
3.3.2自启发量因子b
当取a=1，r=0.7时，TSP优化结果及最短距离随着b的变化相应地如图3.6~3.9所示：
图3.6b=0
图3.7b=0.5
图3.8b=5
图3.9b=50
b表示能见度的相对重要性，b≥0。
由上面四幅图的对比可知，b对算法的性能影响较大，这也表明
城市之间的局部路径在蚂蚁算法中得到了充分考虑。
其中b在5左右时算法性能最优，收敛速度也最快。
3.3.3信息激素残留系数r
当取b=5，a=1时，TSP优化结果及最短距离随着r的变化相应地如图3.10~3.13所示：
图3.10r=0
图3.11r=0.3
图3.12
r=0.7
图3.13
r=0.9
r表示信息素轨迹的持久性，0≤r＜1（1-r表示轨迹的挥发系数）。
由上面四幅图的对比可知信息素浓度的残留因子r的取值对算法性能影响不是很大。
当r太小时,后代蚂蚁会受到前辈蚂蚁的路线严重影响,早期收敛减慢,后期容易陷入局部最优,当r过大,初期收敛虽然很快 ,但早期的优选边会因为挥发太快而失去,从而影响最优解的搜索速度。
由以上图形可知r取0.7时，效果相对较好。
4.结论
本文运用蚁群算法的思想在MATLAB 7.1软件里进行了一系列的仿真，通过对30个城市的TSP问题
的分析，讨论了解决TSP的方法。
建立了蚂蚁算法的模型,给出算法实现流程,并编程实现了基于蚂蚁算法的TSP问题的求解，对蚂蚁算法中的α,β,ρ等3个不同参数的设置进行了探讨,分析了单一参数变化时对算法性能的影响，验证了优选参数就是在算法中建立一个平衡点,即在保证算法收敛速度的同时避免陷入局部最小。
但是本文未能综合考虑三个参数对算法性能的影响，这将是下一步努力的方向。
参考文献:
[1]王茂芝、郭科、徐文皙、黄光鑫.蚂蚁算法求解TSP问题的性能分析及改进成都理工大学学报2005.12-35
[2]杨海、王洪国、徐卫志.蚁群算法的应用研究与发展科技信息2007.28
[3]张宏达、郑全弟.基于蚁群算法的TSP的仿真与研究航空计算技术2005.12-35
[4]赵吉东、胡小兵、刘好斌.改进的蚁群算法及其在TSP中的应用计算机工程与应用2010.
[5]李世勇.《蚁群算法及其应用》哈尔滨工业大学出版社2004.9
[6]马良、朱刚、宁爱兵.《蚁群优化算法》科学出版社2007.9
升级会员 