基于蚁群算法的旅行商问题研究(论文)Word文档格式.docx
- 文档编号:1034106
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:17
- 大小:236.13KB
基于蚁群算法的旅行商问题研究(论文)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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 算法 旅行 问题 研究 论文