基于MATLAB的蚁群算法解决旅行商问题附带源程序仿真.docx
《基于MATLAB的蚁群算法解决旅行商问题附带源程序仿真.docx》由会员分享，可在线阅读，更多相关《基于MATLAB的蚁群算法解决旅行商问题附带源程序仿真.docx（10页珍藏版）》请在冰点文库上搜索。
基于MATLAB的蚁群算法解决旅行商问题附带源程序仿真
基于MATLAB的蚁群算法解决旅行商问题-（附带源程序、仿真）
LT
Q信息素增加强度系数
R_best各代最佳路线
L_best各代最佳路线的长度
求解TSP问题的蚂蚁算法中，每只蚂蚁是一个独立的用于构造路线的过程，若干蚂蚁过程之间通过自适应的信息素值来交换信息，合作求解，并不断优化。
这里的信息素值分布式存储在图中，与各弧相关联。
蚂蚁算法求解TSP问题的过程如下：
（1）首先初始化，设迭代的次数为NC。
初始化NC=0
（2）将m个蚂蚁置于n个顶点上
（3）m只蚂蚁按概率函数选择下一座城市，完成各自的周游
每个蚂蚁按照状态变化规则逐步地构造一个解，即生成一条回路。
蚂蚁的任务是访问所有的城市后返回到起点，生成一条回路。
设蚂蚁k当前所在的顶点为i，那么，蚂蚁k由点i向点j移动要遵循规则而不断迁移，按不同概率来选择下一点。
（4）记录本次迭代最佳路线
（5）全局更新信息素值
应用全局信息素更新规则来改变信息素值。
当所有m个蚂蚁生成了m个解，其中有一条最短路径是本代最优解，将属于这条路线上的所有弧相关联的信息素值进行更新。
全局信息素更新的目的是在最短路线上注入额外的信息素，即只有属于最短路线的弧上的信息素才能得到加强，这是一个正反馈的过程，也是一个强化学习的过程。
在图中各弧上，伴随着信息素的挥发，全局最短路线上各弧的信息素值得到增加。
（6）终止
若终止条件满足，则结束；否则NC=NC+1，转入步骤
（2）进行下一代进化。
终止条件可指定进化的代数，也可限定运行时间，或设定最短路长的下限。
（7）输出结果
四、数据实验及结果
通过计算机仿真，得出旅行商问题优化结果和平均距离和最短距离，如图所示：
五、分析与总结
本文设计了一种基于MATLAB实现的蚁群算法，用以求解组合优化难题中的典型代表旅行商问题。
对30个城市旅行商问题进行了测试，所得结果能达到优化作用，实现了本文的研究目标。
经过对旅行商问题的深入理解，得到了能解决问题的基本数学模型，然后设计算法的基本思想，技术路线，最后编码。
在多次调试，修改后，本算法成功运行，并实现了最初的设定目标。
另外，MATLAB具有丰富的绘图函数，对于绘图十分方便，这是选择MATLAB解决TSP问题的算法编写、调试的原因。
蚁群算法研究处于初期，还有许多问题值得研究，如算法的参数选择、蚂蚁数的比例等只能通过仿真实验，无法给出理论指导。
附录：
蚁群算法解决旅行商问题MATLAB程序
functionyy=ACATSP
x=[413754257268715483641822839125245871748718138262584541444]';
y=[94846762649958446269605460463838426971787640407323521263550]';
C=[xy];
NC_max=50;
m=30;
Alpha=1.5;
Beta=2;
Rho=0.1;
Q=10^6;
%%-------------------------------------------------------------------------
%%主要符号说明
%%Cn个城市的坐标，n×2的矩阵
%%NC_max最大迭代次数
%%m蚂蚁个数
%%Alpha表征信息素重要程度的参数
%%Beta表征启发式因子重要程度的参数
%%Rho信息素蒸发系数
%%Q信息素增加强度系数
%%R_best各代最佳路线
%%L_best各代最佳路线的长度
%%=========================================================================
%%第一步：
变量初始化
n=size（C,1）;%n表示问题的规模（城市个数）
D=zeros（n,n）;%D表示完全图的赋权邻接矩阵
fori=1:
n
forj=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;%i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示
end
D（j,i）=D（i,j）;%对称矩阵
end
end
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=[];%随即存取
fori=1:
（ceil（m/n））
Randpos=[Randpos,randperm（n）];
end
Tabu（:
1）=（Randpos（1,1:
m））';
%%第三步：
m只蚂蚁按概率函数选择下一座城市，完成各自的周游
forj=2:
n%所在城市不计算
fori=1:
m
visited=Tabu（i,1:
（j-1））;%记录已访问的城市，避免重复访问
J=zeros（1,（n-j+1））;%待访问的城市
P=J;%待访问城市的选择概率分布
Jc=1;
fork=1:
n
iflength（find（visited==k））==0%开始时置0
J（Jc）=k;
Jc=Jc+1;%访问的城市个数自加1
end
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）;%cumsum，元素累加即求和
Select=find（Pcum>=rand）;%若计算的概率大于原来的就选择这条路线
to_visit=J（Select
（1））;
Tabu（i,j）=to_visit;
end
end
ifNC>=2
Tabu（1,:
）=R_best（NC-1,:
）;
end
%%第四步：
记录本次迭代最佳路线
L=zeros（m,1）;%开始距离为0，m*1的列向量
fori=1:
m
R=Tabu（i,:
）;
forj=1:
（n-1）
L（i）=L（i）+D（R（j）,R（j+1））;%原距离加上第j个城市到第j+1个城市的距离
end
L（i）=L（i）+D（R
（1）,R（n））;%一轮下来后走过的距离
end
L_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*n的0矩阵
fori=1:
m
forj=1:
（n-1）
Delta_Tau（Tabu（i,j）,Tabu（i,j+1））=Delta_Tau（Tabu（i,j）,Tabu（i,j+1））+Q/L（i）;
%此次循环在路径（i，j）上的信息素增量
end
Delta_Tau（Tabu（i,n）,Tabu（i,1））=Delta_Tau（Tabu（i,n）,Tabu（i,1））+Q/L（i）;
%此次循环在整个路径上的信息素增量
end
Tau=（1-Rho）.*Tau+Delta_Tau;%考虑信息素挥发，更新后的信息素
%%第六步：
禁忌表清零
Tabu=zeros（m,n）;%%直到最大迭代次数
end
%%第七步：
输出结果
Pos=find（L_best==min（L_best））;%找到最佳路径（非0为真）
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）;
holdon%保持图形
plot（L_ave,'r'）;
title（'平均距离和最短距离'）%标题
functionDrawRoute（C,R）
%%=========================================================================
%%DrawRoute.m
%%画路线图的子函数
%%-------------------------------------------------------------------------
%%CCoordinate节点坐标，由一个N×2的矩阵存储
%%RRoute路线
%%=========================================================================
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）],'g'）;
holdon
forii=2:
N
plot（[C（R（ii-1）,1）,C（R（ii）,1）],[C（R（ii-1）,2）,C（R（ii）,2）],'g'）;
holdon
end
title（'旅行商问题优化结果'）
升级会员 