%% 使用免疫算法行进求解TSP问题
%常量定义
% 城市坐标值
clear all;
close all;
clc
D = [
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;
];
N = size(D,1);
Dis = Distance(D);%生成城市距离矩阵
Gen = 1000;%迭代次数
NP = 200;%种群大小
M = 10;%克隆个数
BestDis = zeros(1,Gen);
BestPath = zeros(Gen,N);
%% 生成初始种群
for i=1:NP
POP(i,:) = randperm(N);
end
POPLen = Len(POP,Dis);%求出每个个体的路程
[SortLen,Index] = sort(POPLen);
SortPOP = POP(Index,:);%对种群进行排序
%% 进行迭代
for gen=1:Gen
for k=1:NP/2
OnePOP = SortPOP(k,:);%逐个取出前NP/2个个体进行克隆
Clon = repmat(OnePOP,M,1);%对第k个个体进行克隆M个
for t=1:M%对M个克隆体进行单体交换
Pot1 = round(rand*N);
Pot2 = round(rand*N);
while Pot1==0 || Pot2==0 || Pot1==Pot2
Pot1 = round(rand*N);
Pot2 = round(rand*N);
end
%进行单点交换
temp = Clon(t,Pot1);
Clon(t,Pot1) = Clon(t,Pot2);
Clon(t,Pot2) = temp;
end
Clon(1,:) = OnePOP;%保留原个体
ClonLen = Len(Clon,Dis);%克隆体求出路程
[SortLen,Index] = sort(ClonLen);
SortClon = Clon(Index,:);
NewPOP1(k,:) = SortClon(1,:);%保留最优个体
end
%随机产生新种群
for i=1:NP/2
NewPOP2(i,:) = randperm(N);
end
POP = [NewPOP1;NewPOP2];%组合为新的种群
POPLen = Len(POP,Dis);%求出每个个体的路程
[SortLen,Index] = sort(POPLen);
SortPOP = POP(Index,:);%对种群进行排序
BestDis(gen) = SortLen(1);
BestPath(gen,:) = SortPOP(1,:);
end
DDD = min(BestDis)
%% 显示最优路径
disp('最短路程为：');
disp(num2str(SortLen(1)));
disp('其最优路径为：');
path = SortPOP(1,:);
p = num2str(path(1));
for i=2:N
p = [p,'—>',num2str(path(i))];
end
p = [p,'—>',num2str(path(1))];
disp(p);
%% 画出最优路径图
figure(1)
plot(D(:,1),D(:,2),'r*');
hold on
for i=1:N-1
x1 = D(path(i),1);
y1 = D(path(i),2);
x2 = D(path(i+1),1);
y2 = D(path(i+1),2);
plot([x1,x2],[y1,y2],'b-');
hold on
end
hold on
x1 = D(path(N),1);
y1 = D(path(N),2);
x2 = D(path(1),1);
y2 = D(path(1),2);
plot([x1,x2],[y1,y2],'b-');
%% 画出最优路程图
figure(2)
plot(BestDis,'b-');
