matlab仿真蚁群算法程序源代码报告TSP商旅计算城市距离矩阵迭代寻找最佳路径

蚁群算法MATLAB仿真

• 课题内容和要求

蚁群算法是一种智能优化算法，在TSP商旅问题上得到广泛使用。蚁群算法于1992年由Marco Dorigo首次提出，该算法来源于蚂蚁觅食行为。

由于蚂蚁没有视力，所以在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常，蚂蚁会以较大的概率优先选择信息素浓度高的路径，并且释放一定的信息素，使该条路径上的信息素浓度增高，进而使蚂蚁能够找到一条由巢穴到食物源最近的路径。

但是，随着时间的推移，路径上的信息素浓度会逐渐衰减。用MATLAB完成多点间最短路径的仿真，并计算出最短距离。

二、需求分析

（1）数据准备

为了防止既有变量的干扰，首先将环境变量清空。然后将城市的位置坐标从数据文件（详见源程序里的excel文件）读入程序，并保存到变量为citys的矩阵中（第一列为城市的横坐标，第二列为城市的纵坐标）。

（2）计算城市距离矩阵

根据平面几何中两点间距离公式及城市坐标矩阵citys，可以很容易计算出任意两城市之间的距离。但需要注意的是，这样计算出的矩阵对角线上的元素为0，然而为保证启发函数的分母不为0，需将对角线上的元素修正为一个足够小的正数。从数据的数量级判断，修正为以下，我们认为就足够了。

（3）初始化参数

计算之前需要对参数进行初始化，同时为了加快程序的执行速度，对于程序中涉及的一些过程量，需要预分配其存储容量。

（4）迭代寻找最佳路径

该步为整个算法的核心。首先要根据蚂蚁的转移概率构建解空间，即逐个蚂蚁逐个城市访问，直至遍历所有城市。然后计算各个蚂蚁经过路径的长度，并在每次迭代后根据信息素更新公式实时更新各个城市连接路径上的信息素浓度。经过循环迭代，记录下最优的路径和长度。

（5）结果显示

计算结果用数字或图形的方式显示出来，以便于分析。同时，也可以根据需要把能够显示程序寻优过程的数据显示出来，以直观呈现出程序的寻优轨迹。

三、概要设计

蚁群算法的流程

用蚁群算法求解TSP问题的算法流程如图9-2所示，具体每步的含义如下：

①对相关参数进行初始化，包括蚁群规模、信息素因子、启发函数因子、信息素挥发因子言息素常数、最大迭代次数等，以及将数据读入程序，并对数据进行基本的处理，如将城市的标位置转为城市间的矩阵。

②随机将蚂蚁放于不同的出发点，对每个蚂蚁计算其下一个访问城市，直至所有蚂蚁问完所有城市。

③计算各个蚂蚁经过的路径长度Lk，记录当前迭代次数中的最优解，同时对各个城市接路径上的信息素浓度进行更新。

④判断是否达到最大迭代次数，如果是则返回步骤②，否则终止程序。

⑤输出程序结果，并根据需要输出程序寻优过程中的相关指标，如运行时间、收敛迭代次数等

四、详细设计

·参数设定的准则

通过对以上蚁群算法原理和程序的学习，我们大致可以感受到蚁群算法的特点。特点之一是，蚁群在寻优的过程中，带有一定的随机性。这种随机性主要体现在初始城市（出发点）的选择上。蚁群算法正是通过这个初始点的选择将全局寻优慢慢转化为局部寻优。蚁群算法参数设定的关键是在“全局”与“局部”之间建立一个平衡点。既要使得蚁群算法的搜索空间尽可能大，以寻找可能存在的最优解的解区间；同时，又要充分利用蚂蚁群当前留下的有效信息，以较大的概率尽快收敛到近似的全局最优。

目前蚁群算法中的参数设定尚无严格的理论依据，难以用解析法确定最佳组合，但是可以通过实验来研究算法的寻优规律，从而确定相对合理的参数组合。其实，由于现实事物的复杂性，往往用严格的解析数学很难来描述真实的现实世界，这时我们不妨考虑用比较经典的实验法来研究算法的参数设定，因为在近代科学发展史上，有很多伟大的发现都是通过实验法得到的。

一般来讲，这类智能算法的参数设定遵照以下基本准则：

①尽可以在全局上搜索最优解，保证解的最优性；

②算法尽快收敛，以节省寻优时间；

③尽量反映客观存在的规律，以保证这种仿生算法的真实性。

·信息素因子

同样可以采用以上的实验方法研究其他参数对算法指标的影响，从而确定各参数的合理取值。具体实验过程这里不再赘述，只将一些主要结论总结出来，时间充裕的读者可以根据以上的实验方法来研究其他参数的取值。

信息素因子α反映了蚂蚁在运动过程中所积累的信息量在指导蚁群搜索过程中的相对重要程度。其值过大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性减弱；其值过小，则等同于贪婪算法，易使蚁群的搜索过早陷入局部最优。实验研究发现，当α属于［1,4］时，综合求解性能较好。

·启发函数因子

启发函数因子β反映了启发式信息在指导蚁群搜索过程中的相对重要程度。其大小反映了蚁群寻优过程中先验性、确定性因素的作用强度。β过大时，蚂蚁在某个局部点上选择局优的可能性大，虽然收敛速度加快，但搜索全优的随机性减弱，易于陷入局部最优过程。β过小，蚂蚁群体陷入纯粹的随机搜索，很难找到最优解。实验研究发现，当β属于［3,4.5］时，综合求解性能较好。

·信息素挥发因子、

信息素挥发因子ρ描述了信息素的消失水平，而1-ρ则为信息素残留因子，描述信息素的保持水平。ρ的大小直接关系蚁群算法的全局搜索能力及收敛速度，1-ρ则反映蚂蚁之间个体相互影响的强弱。由于ρ的存在，当问题规模较大时，会使从未被搜索的路径的信息素量减小到接近0，降低全局搜索能力、且当ρ过大时，重复搜索的可能性大，影响随机性和全局搜索能力；当ρ过小时，会使收敛速度降低。实验研究发现，当ρ属于［0.2,0.5］时，综合求解性能较好。

·信息素常数

常系数Q为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作用是为了充分利用有向图上的全局信息反馈量，使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。Q越大，蚂蚁在已遍历路径上的信息素累积越快，有助于快速收敛。

Q越大，信息素收敛速度越快。当Q过大时，虽然收敛速度较快，但易陷入局优，性能也不稳定。当Q过小时，影响算法收敛速度。实验研究发现，当Q属于［10,1000］时，综合性能较好。

·最大迭代次数

最大迭代次数iter＿max控制算法的迭代次数。其值过小，可能导致算法还没收敛，程序就已经结束了；值过大则会导致资源浪费。从上面的程序来看，ASA算法一般经过50～100次的迭代后收敛，为此，最大迭代次数可以取100～500。一般，建议先取200，执行程序后查看算法收敛轨迹，由此判断比较合理的最大迭代次数取值。

9.3.8?组合参数设计策略

由于ACA算法中涉及这些参数，而且这些参数对程序都有一定的影响，为此设计一组较合适的参数组合对程序来说非常重要。通常，可以按照以下策略进行参数的组合设定：

①确定蚂蚁数目，蚂蚁数目与城市规模之比约为1.5；

②参数粗调，即调整取值范围较大的α，β，Q；

③参数微调，即调整取值范围较小的ρ

一共52个点，给出坐标

第一份代码没有可视的仿真过程。第二份有全部功能。这也表露出编代码时的思路。

clear all

clc

% 程序运行计时开始

t0 = clock;

%导入数据

citys=xlsread('Chap9_citys_data.xlsx', 'B2:C53');

%% 计算城市间相互距离

n = size(citys,1);

D = zeros(n,n);

for i = 1:n

for j = 1:n

if i ~= j

D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));

else

D(i,j) = 1e-4; %设定的对角矩阵修正值

end

end

end

%% 初始化参数

m = 75; % 蚂蚁数量

alpha = 1; % 信息素重要程度因子

beta = 5; % 启发函数重要程度因子

vol = 0.2; % 信息素挥发(volatilization)因子

Q = 10; % 常系数

Heu_F = 1./D; % 启发函数(heuristic function)

Tau = ones(n,n); % 信息素矩阵

Table = zeros(m,n); % 路径记录表

iter = 1; % 迭代次数初值

iter_max = 100; % 最大迭代次数

Route_best = zeros(iter_max,n); % 各代最佳路径

Length_best = zeros(iter_max,1); % 各代最佳路径的长度

Length_ave = zeros(iter_max,1); % 各代路径的平均长度

Limit_iter = 0; % 程序收敛时迭代次数

%% 迭代寻找最佳路径

while iter <= iter_max

% 随机产生各个蚂蚁的起点城市

start = zeros(m,1);

for i = 1:m

temp = randperm(n);

start(i) = temp(1);

end

Table(:,1) = start;

% 构建解空间

citys_index = 1:n;

% 逐个蚂蚁路径选择

for i = 1:m

% 逐个城市路径选择

for j = 2:n

tabu = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表)

allow_index = ~ismember(citys_index,tabu); % 参加说明1（程序底部）

allow = citys_index(allow_index); % 待访问的城市集合

P = allow;

% 计算城市间转移概率

for k = 1:length(allow)

P(k) = Tau(tabu(end),allow(k))^alpha * Heu_F(tabu(end),allow(k))^beta;

end

P = P/sum(P);

% 轮盘赌法选择下一个访问城市

Pc = cumsum(P); %参加说明2(程序底部)

target_index = find(Pc >= rand);

target = allow(target_index(1));

Table(i,j) = target;

end

end

% 计算各个蚂蚁的路径距离

Length = zeros(m,1);

for i = 1:m

Route = Table(i,:);

for j = 1:(n - 1)

Length(i) = Length(i) + D(Route(j),Route(j + 1));

end

Length(i) = Length(i) + D(Route(n),Route(1));

end

% 计算最短路径距离及平均距离

if iter == 1

[min_Length,min_index] = min(Length);

Length_best(iter) = min_Length;

Length_ave(iter) = mean(Length);

Route_best(iter,:) = Table(min_index,:);

Limit_iter = 1;

else

[min_Length,min_index] = min(Length);

Length_best(iter) = min(Length_best(iter - 1),min_Length);

Length_ave(iter) = mean(Length);

if Length_best(iter) == min_Length

Route_best(iter,:) = Table(min_index,:);

Limit_iter = iter;

else

Route_best(iter,:) = Route_best((iter-1),:);

end

end

% 更新信息素

Delta_Tau = zeros(n,n);

% 逐个蚂蚁计算

for i = 1:m

% 逐个城市计算

for j = 1:(n - 1)

Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);

end

Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);

end

Tau = (1-vol) * Tau + Delta_Tau;

% 迭代次数加1，清空路径记录表

iter = iter + 1;

Table = zeros(m,n);

end

%% 结果显示

[Shortest_Length,index] = min(Length_best);

Shortest_Route = Route_best(index,:);

Time_Cost=etime(clock,t0);

disp(['最短距离:' num2str(Shortest_Length)]);

disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);

disp(['收敛迭代次数:' num2str(Limit_iter)]);

disp(['程序执行时间:' num2str(Time_Cost) '秒']);

%% 绘图

figure(1)

plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... %三点省略符为Matlab续行符

[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');

grid on

for i = 1:size(citys,1)

text(citys(i,1),citys(i,2),[' ' num2str(i)]);

end

text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点');

text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点');

xlabel('城市位置横坐标')

ylabel('城市位置纵坐标')

title(['ACA最优化路径(最短距离:' num2str(Shortest_Length) ')'])

figure(2)

plot(1:iter_max,Length_best,'b')

legend('最短距离')

xlabel('迭代次数')

ylabel('距离')

title('算法收敛轨迹')

程序说明：

①ismember函数用于判断一个变量中的元素是否在另一个变量中出现，返回0-1矩阵；?4

②cumsum函数用于求变量中累加元素的和,如果A=[1,2,3,4,5],那么cumsum(A)=[1?,3,6,10,15]?。

这是第二份

clear all;

close all;

clc;

m=20; %蚂蚁数量

Alpha=1; %信息素重要程度参数

Beta=5; %启发式重要程度参数

Rho=0.1; %信息素蒸发参数

G=200; %最大迭代次数

Q=100; %信息素增加强度系数

C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...

3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...

2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...

3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...

3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...

2370 2975]; %31个省会城市坐标

%第一步：变量初始化

n=size(C,1); %问题的规模，即城市数目

D=zeros(n,n); %任何两个城市距离间隔矩阵

for i=1:n

for j=1:n

if i~=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;

end

D(j,i)=D(i,j);

end

end

Eta=1./D; %Eta为启发因子，设为距离的倒数

Tau=ones(n,n); %信息素矩阵

Tabu=zeros(m,n); %信息素矩阵

NC=1; %迭代计数器

R_Best=zeros(G,n); %各代最佳路线

L_Best=inf.*ones(G,1); %各代最佳路线长度,inf正无穷

figure(1); %优化解

while NC<=G

%第二步：将m只蚂蚁放到n个城市上

Randpos=[];

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

%第三步：m只蚂蚁按照概率函数选择下一座城市，完成各自周游

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1)); %已访问的城市

J=zeros(1,(n-j+1)); %待访问的城市

P=J; %待访问城市的选择概率分布

Jc=1;

for k=1:n

if isempty(find(visited==k,1))

J(Jc)=k;

Jc=Jc+1;

end

end

%计算待选城市概率分布

for k=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;

end

end

if NC>=2

Tabu(1,:)=R_Best(NC-1,:);

end

L=zeros(m,1);

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(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),:);

%第五步：更新信息素

Delta_Tau=zeros(n,n);

for i=1:m

for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

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);

%历代最优路线

for i=1:(n-1)

plot([C(R_Best(NC,i),1),C(R_Best(NC,i+1),1)],[C(R_Best(NC,i),2),C(R_Best(NC,i+1),2)],'bo-');

hold on

end

plot([C(R_Best(NC,n),1),C(R_Best(NC,1),1)],[C(R_Best(NC,n),2),C(R_Best(NC,1),2)],'ro-');

title(['优化最优距离：',num2str(L_Best(NC))]);

hold off;

pause(0.005);

NC=NC+1;

end

%第七步：输出结果

pos=find(L_Best==min(L_Best));

Shortest_Route=R_Best(pos(1),:); %最佳路线

Shortest_Length=L_Best(pos(1)); %最佳路线长度

figure(2),

plot(L_Best)

xlabel('迭代次数')

ylabel('目标函数值')

title('适应度进化曲线')

五、测试数据及其结果分析

最短距离:7548.9927

最短路径:46? 44? 34? 35? 36? 39? 40? 38? 37? 48? 24?? 5? 15?? 6?? 4? 25? 12? 28? 27? 26? 47? 13? 14? 52? 11? 51? 33? 43? 10? ?9?? 8? 41? 19? 45? 32? 49?? 1? 22? 31? 18?? 3? 17? 21? 42?? 7?? 2? 30? 23? 20? 50? 29? 16? 46

收敛迭代次数:45

程序执行时间:5.835秒

该问题是一个非常有现实意义的题目。初步判断，该问题和TSP问题很相似，但本问题中的各子问题又有不同的要求。但仔细分析后很快发现，这些问题可以很容易转化为TSP问题，也就是说，同样可以用蚁群算法进行求解。此处我们只以第①问的求解为例来解释如何将实际问题转化为相对熟悉的TSP问题，然后利用蚁群算法进行求解。

六、调试过程中的问题

先前的仿真跟注重结果，不注重仿真的过程，修改后可看到随着迭代次数的增加最短路径的变化。

七、课程设计总结

根据蚁群算法的基本思想及求解TSP问题的模型和流程，不难发现，蚁群算法有以下几个特点：

①就算法的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求全局最优解。

②开始时算法收敛速度较快，在随后寻优过程中，迭代到一定次数后，容易出现停滞现象。

③蚁群算法对TSP及相似问题具有良好的适应性，无论城市规模大还是小，都能进行有效的求解，而且求解速度相对较快。

④蚁群算法解的稳定性较差，即使参数不变，每次执行程序都很有可能得到不同的解，为此需要多执行几次，以寻找到最佳的解。

⑤蚁群算法中有多个需要设定的参数，而且这些参数对程序又都有一定的影响，所以选择合适的参数组合在算法设计过程中也非常重要。好在这些参数的设定有一定的经验规律，所以在实际算法设计中，可以根据这些经验快速设定合理的算法参数。

该问题是一个非常有现实意义的题目。初步判断，该问题和TSP问题很相似，但本问题中的各子问题又有不同的要求。但仔细分析后很快发现，这些问题可以很容易转化为TSP问题，也就是说，同样可以用蚁群算法进行求解。此处我们只以第①问的求解为例来解释如何将实际问题转化为相对熟悉的TSP问题，然后利用蚁群算法进行求解。

六、调试过程中的问题

先前的仿真跟注重结果，不注重仿真的过程，修改后可看到随着迭代次数的增加最短路径的变化。

七、课程设计总结

根据蚁群算法的基本思想及求解TSP问题的模型和流程，不难发现，蚁群算法有以下几个特点：

①就算法的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求全局最优解。

②开始时算法收敛速度较快，在随后寻优过程中，迭代到一定次数后，容易出现停滞现象。

③蚁群算法对TSP及相似问题具有良好的适应性，无论城市规模大还是小，都能进行有效的求解，而且求解速度相对较快。

④蚁群算法解的稳定性较差，即使参数不变，每次执行程序都很有可能得到不同的解，为此需要多执行几次，以寻找到最佳的解。

⑤蚁群算法中有多个需要设定的参数，而且这些参数对程序又都有一定的影响，所以选择合适的参数组合在算法设计过程中也非常重要。好在这些参数的设定有一定的经验规律，所以在实际算法设计中，可以根据这些经验快速设定合理的算法参数。

该问题是一个非常有现实意义的题目。初步判断，该问题和TSP问题很相似，但本问题中的各子问题又有不同的要求。但仔细分析后很快发现，这些问题可以很容易转化为TSP问题，也就是说，同样可以用蚁群算法进行求解。此处我们只以第①问的求解为例来解释如何将实际问题转化为相对熟悉的TSP问题，然后利用蚁群算法进行求解。

六、调试过程中的问题

先前的仿真跟注重结果，不注重仿真的过程，修改后可看到随着迭代次数的增加最短路径的变化。

七、课程设计总结

根据蚁群算法的基本思想及求解TSP问题的模型和流程，不难发现，蚁群算法有以下几个特点：

①就算法的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求全局最优解。

②开始时算法收敛速度较快，在随后寻优过程中，迭代到一定次数后，容易出现停滞现象。

③蚁群算法对TSP及相似问题具有良好的适应性，无论城市规模大还是小，都能进行有效的求解，而且求解速度相对较快。

④蚁群算法解的稳定性较差，即使参数不变，每次执行程序都很有可能得到不同的解，为此需要多执行几次，以寻找到最佳的解。

⑤蚁群算法中有多个需要设定的参数，而且这些参数对程序又都有一定的影响，所以选择合适的参数组合在算法设计过程中也非常重要。好在这些参数的设定有一定的经验规律，所以在实际算法设计中，可以根据这些经验快速设定合理的算法参数。

该问题是一个非常有现实意义的题目。初步判断，该问题和TSP问题很相似，但本问题中的各子问题又有不同的要求。但仔细分析后很快发现，这些问题可以很容易转化为TSP问题，也就是说，同样可以用蚁群算法进行求解。此处我们只以第①问的求解为例来解释如何将实际问题转化为相对熟悉的TSP问题，然后利用蚁群算法进行求解。

六、调试过程中的问题

先前的仿真跟注重结果，不注重仿真的过程，修改后可看到随着迭代次数的增加最短路径的变化。

七、课程设计总结

根据蚁群算法的基本思想及求解TSP问题的模型和流程，不难发现，蚁群算法有以下几个特点：

①就算法的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求全局最优解。

②开始时算法收敛速度较快，在随后寻优过程中，迭代到一定次数后，容易出现停滞现象。

③蚁群算法对TSP及相似问题具有良好的适应性，无论城市规模大还是小，都能进行有效的求解，而且求解速度相对较快。

④蚁群算法解的稳定性较差，即使参数不变，每次执行程序都很有可能得到不同的解，为此需要多执行几次，以寻找到最佳的解。

⑤蚁群算法中有多个需要设定的参数，而且这些参数对程序又都有一定的影响，所以选择合适的参数组合在算法设计过程中也非常重要。好在这些参数的设定有一定的经验规律，所以在实际算法设计中，可以根据这些经验快速设定合理的算法参数。