clc;
clear all; %清屏清除工作区
close all;
%% 取得要处理的城市的坐标,作出初始图
%position=load('景区经纬度.txt');
%这句可以读入所需要处理的数据,以下采用的是随机产生的坐标信息
t0=clock;
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
];
xlabel('经度'); %横坐标
ylabel('纬度'); %纵坐标
title('TSP蚁群算法优化'); %图片标题
grid on
%% 计算各个城市之间的距离
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)); %矩阵里元素各自平方后求和
%S(i,j) = sqrt((x(i)-x(j))^2 + (y(i)-y(j))^2); %距离公式
else
D(i,j) = 1e-4; %这里不是零主要是为了之后去的取倒数,对角矩阵修正值
end
end
end
%% 种群初始化,参数的设置
m = 50; % 蚂蚁数量
alpha = 1; % 信息素重要程度因子
beta = 5; % 启发函数重要程度因子
vol = 0.1; % 信息素挥发(volatilization)因子
Q = 100; % 常系数
Heu_F = 1./D; % 启发函数(距离的倒数)
Tau = ones(n,n); % 信息素矩阵
Table = zeros(m,n); % 路径记录表(蚂蚁的数量是行数,列数是城市的数量)
%iter = 1; % 迭代次数初值
iter_max = 200; % 最大迭代次数
Route_best = zeros(iter_max,n); % 各代最佳路径(每一次迭代后的最佳路线)
Length_best = zeros(iter_max,1); % 各代最佳路径的长度
Length_ave = zeros(iter_max,1); % 各代路径的平均长度
%% 迭代寻找最佳路径
for iter = 1:iter_max %迭代开始,用for不用再设置加一(原程序是while)
% 随机产生各个蚂蚁的起点城市(原程序)
%start = zeros(m,1);
%for i = 1:m
% temp = randperm(n); %这里产生的是n以内的一个序列
% start(i) = temp(1); %取了这个序列的第一个值,随机值
%end
for i=1:m
Table(i,1) = unidrnd(n); %这个直接产生的就是n以内的随机值
end
% 构建解空间
citys_index = 1:n;
% 逐个蚂蚁选择
for i = 1:m
% 逐个城市路径选择
for j = 2:n
%table是路径记录表,每次j之前的城市都是被选择过的
has_visited = Table(i,1:(j - 1)); % 已访问的城市集合(禁忌表)
allow_index = ~ismember(citys_index,has_visited);
%citys_index中有元素属于禁忌表中元素的时候取1,取反后变成0,产生的是逻辑数组
allow = citys_index(allow_index); % 剩下待访问的城市集合
P = allow;
% 计算城市间转移概率
for k = 1:length(allow)
P(k) = Tau(has_visited(end),allow(k))^alpha * Heu_F(has_visited(end),allow(k))^beta;
%Heu_F是距离的倒数矩阵,所以说越远概率就会越低
end
P = P/sum(P);
% 轮盘赌法选择下一个访问城市
Pc = cumsum(P); %累加函数,把前几个累加到1
target_index = find(Pc >= rand);
target = allow(target_index(1));
%这里和遗传算法不一样,没有采用二分法
Table(i,j) = target;
end
end
%% 计算各个蚂蚁的路径距离
Length = zeros(m,1);
for i = 1:m