HUNAN UNIVERSITY 课程作业
课程题目智能优化算法
学生姓名李小燕
学生学号 S131020016
专业班级计算机科学与技术
学院名称信息科学与工程学院
指导老师杨圣洪
2014 年6月 8日
蚁群算法求解TSP问题
摘要：蚁群算法是一种分布式内在并行算法。单个蚂蚁的搜索过程是彼此独立的，易于局部最优，通过个体间不断的信息交流和传递有利于发现较好解；并且该算法是一种正反馈算法。路径上的信息素浓度较高，将吸引更多的蚂蚁沿这条路径运动，又使得信息素浓度增加，加快了算法的进化过程。本文通过求解TSP问题，通过在特定情况下对路径进行逐步遍历比较来降低陷入局部最优解的可能性, 找出最优解。
关键词：蚁群算法；TSP；信息素；遍历
1. 引言
TSP问题又称最短路径问题，还称为旅行商问题，是一种比较经典的 NP 难题，问题描述较简单，而获得最优解却十分困难。求解 TSP 问题不仅为其他算法提供了使用平台，而且算法的优劣性能也可通过其求得 TSP 问题的解集来验证。旅行商问题的经典描述为：已知N 个城市及相互间的距离，旅行商从某城市出发遍历这 N 个城市后再回到原点，在旅行商每个城市都只访问一次的前提下确定一条最短路径。
蚁群算法是一种基于种群的启发式仿生进化系统。该算法通过模拟自然界的蚂蚁觅食过程对目标进行搜索，而在搜索过程中人工蚂蚁会在其经过的路径上释放信息素，蚁群依赖于同类散发在周围环境中的特殊物质—信息素的轨迹来决定自己的去向。当某些路径上走过的蚂蚁越来越多时，留下的信息素也会越来越多，以致后蚂蚁选择该路径的概率也越来越高，从而更增加了该路径的吸引强度，逐渐形成了一条它们自己事先并未意识到的最短路线。
蚁群算法实现TSP 过程为：将 m 只蚂蚁放入到 n 个随机选择的城市中，那么每个蚂蚁每步的行动是：根据一定的依据选择下一个它还没有访问的城市；同时在完成一步（从一个城市到达另一个城市）或者一个循环（完成对所有 n 个城市的访问）后，更新所有路径上的信息素浓度。
2. 蚁群算法的数学模型
（1）、基本参数、信息素浓度公式、择路概率
设蚂蚁的数量为m ，城市的数量为n ，城市i 与城市j 之间的距离为dij ，t 时刻城市i 与城市j 之间的信息素浓度为t ij (t)，初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为t ij (0)=t0。
蚂蚁k(k=1,2,..,m)根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市，设P ij k (t)表示t 时刻，蚂蚁k 从城市i 到城市j 的概率，其计算公式为如下：
ij [()][()][()][()]
P 0ij ij k
k
ij ij s allow
k
t t t s allow t t t s allow αβ
αβηη∈??∈???=?????∑
其中：
ij
(t)为启发式函数，
ij
(t)=1/dij ，表示蚂蚁从城市i 转移到城市j 的
期望程序；
allow k (k=1,2,…,m)表示蚂蚁k 待访问的城市的集合，开始时allow k 为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市。
为信息素的重要程度因子，其值越大，转移中起的作用越大
为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁以较大的概率转移到距离短的城市。 蚂蚁释放的信息素会随时间的推进而减少，设参数
(0<
<1)表示信息素
的挥发度，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度，需要实时更新。
t ij (t+1)=(1-)t ij (t)+t ij ，t ij =1
n
k
ij
k t =?∑
其中：
t ij k 表示蚂蚁k 在城市i 与城市j 的连接路径上，释放的信息素浓度 t ij 表示所有蚂蚁在城市i 与城市j 的连接路径上，释放的信息素浓度。 （2）、
t ij k 的计算方法
t ij k
=/0
k
Q L k ???
第只蚂蚁从城市i访问城市j
其他
其中：
Q 为常数，表示蚂蚁循环一次释放的信息素的总量； d ij 为第k 只蚂蚁经过路径的长度，Length ；
3. 算法实现步骤
1、初始化参数
蚂蚁数量m ，信息素重要程度
，启发函数重要程度
，信息素挥发因子
，信息素释放总量Q ，最大迭代次数iter_max 。获取各城市之间的距离dij ，为了保证启发式函数
ij
=1/dij 能顺利进行，对于i=j 即自己到自己的距离不
能给为0，而是给成一个很小的距离，如10-4或10-5。 2、构建解空间
将各个蚂蚁随机地置于不同出发点，对每个蚂蚁按归照下式，确定下一城市。
ij [()][()][()][()]P 0ij ij k k ij ij s allow
k
t t t s allow t t t s allow αβ
αβηη∈??∈???=?????
∑
3、更新信息素
计算各个蚂蚁经过的路径长度Lk ，记录当前迭代次数中的最优解(即最短路径)，根据如下公式更新信息素：
t ij (t+1)=(1-)t ij (t)+t ij ，t ij =1
n
k
ij
k t =?∑
t ij
k
=/0k Q L k ???
第只蚂蚁从城市i访问城市j
其他
4、判断是否终止
若没有到最大次数，则清空蚂蚁经过路径的记录表，返回步骤2。
4. 相关实验
4.1 实验内容
1、访问我国每个省会城市一次也仅一次的最短路径，共有31个
2、如果采用枚举法，巡回路径可能1.326
1032种。
3、城市的坐标citys，这是直角坐标，根据二个城市的坐标值，可以用
可计算出任意二个城市间的距离。
citys = 1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
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 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975
4.2 实验代码
%% 清空环境变量
clear all
clc
load citys_data.mat %% 导入数据
%% 计算城市间相互距离
n = size(citys,1); %城市的个数
D = zeros(n,n); %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 = 50; % 蚂蚁数量
alpha = 1; % 信息素重要程度因子
beta = 5; % 启发函数重要程度因子
rho = 0.1; % 信息素挥发因子
Q = 1; % 常系数
Eta = 1./D; % 启发函数
Tau = ones(n,n); % 信息素矩阵,全1矩阵
Table = zeros(m,n); % 路径记录表，全0矩阵，每只蚂蚁依次走过的城市
iter = 1; % 迭代次数初值
iter_max = 200; % 最大迭代次数
Route_best = zeros(iter_max,n); % 各代最佳路径
Length_best = zeros(iter_max,1); % 各代最佳路径的长度
Length_ave = zeros(iter_max,1); % 各代路径的平均长度
%% 迭代寻找最佳路径
while iter <= iter_max
% 随机产生各个蚂蚁的起点城市
start = zeros(m,1); %m是蚂蚁的个数,m行1列的矩阵，记录每个蚂蚁的城市编号
for i = 1:m
temp = randperm(n);
start(i) = temp(1);
end
Table(:,1) = start; %路径记录表的1列，为每个蚂蚁的起点城市 % 构建解空间
citys_index = 1:n;
% 逐个蚂蚁路径选择
for i = 1:m
% 逐个城市路径选择
for j = 2:n
tabu = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表)
allow_index = ~ismember(citys_index,tabu);%不是tabu的城市就是要访问的城市
allow = citys_index(allow_index); % 待访问的城市集合 P = allow;
for k = 1:length(allow) % 计算城市间转移概率
P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;
end
P = P/sum(P);%规一化
% 轮盘赌法选择下一个访问城市
Pc = cumsum(P);%依次累加，是实现轮盘赌法选择的方法
target_index = find(Pc >= rand);
target = allow(target_index(1));
Table(i,j) = target;
end
end
%% 结果显示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp(['最短距离:' num2str(Shortest_Length)]);
disp(['最短路径:' num2str([Shortest_Route Shortest_Route(1)])]);
%% 绘图
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
[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(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')
4.3 实验结果与分析
使用不同的蚁群数量和迭代次数后求得的最短距离和最短路径如下所示：
1. 蚁群数50，迭代次数200
最短距离:15601.9195
最短路径:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 14
2. 蚁群数50，迭代次数100
最短距离:15972.7648
最短路径:1 15 13 12 14 29 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 1
3. 蚁群数100，迭代次数100
最短距离:15601.9195
最短路径:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 14
4. 蚁群数50，迭代次数300
最短距离:15601.9195
最短路径:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1
5. 蚁群数100，迭代次数200
最短距离:15601.9195
最短路径:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 14
6. 蚁群数100，迭代次数300
最短距离:15553.0468
最短路径:10 9 8 4 2 5 6 7 13 12 14 15 1 29 31 30 27 28 26 21 22 18 3 17 19 24 20 25 11 23 16 10
7. 蚁群数150，迭代次数300
最短距离:15601.9195
最短路径:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1
从以上的实验结果可看出，蚁群数量和迭代次数对算法的实验结果有一定影
响，当蚁群数确定时，随着迭代次数的增加，最短距离会有所减小，但增加到一定的程度，最短距离将不再变化；