%main
clear;
clc;
%%%%%%%%%%%%%%%输入参数%%%%%%%%
N=25; %%城市的个数
M=100; %%种群的个数
ITER=2000; %%迭代次数
%C_old=C;
m=2; %%适应值归一化淘汰加速指数
Pc=0.8; %%交叉概率
Pmutation=0.05; %%变异概率
%%生成城市的坐标
pos=[-0.0596300734351115 -0.851297433985992;
0.438398458335735 0.841724248850041;
-0.251804207069105 -1.30744728793171;
1.17790692164388 0.0952195708913433;
1.66427009988301 -0.133382476901910;
-0.337308956003599 -0.407225198007313;
0.311862707690034 -0.431724333072457;
0.182396732713558 -0.157788333124223;
0.0378390295101906 -0.367920724129644;
-0.853709951356673 0.0363449796675028;
-1.64191242274810 -0.565028275383299;
-0.821481309108439 -1.36166562718530;
-0.0666502703726364 0.756667745411741;
2.25931856568426 -1.30140683361980;
0.759098750479421 2.81038357991309;
-0.00925105144207478 0.672464995693229;
0.862239245550680 -0.576524359942781;
-0.742512628202077 0.740723643506810;
0.371005938734921 -0.835740815137822;
0.677683424862960 -0.284758907693345;
-1.48234180628974 0.955162776644004;
0.452806831664590 0.608019647737753;
1.22196689592397 -0.878318328597688;
0.352173262723895 1.60512181080303;
1.80729484625293 0.593061432086341
];
%%生成城市之间距离矩阵
D=zeros(N,N);
for i=1:N
for j=i+1:N
dis=(pos(i,1)-pos(j,1)).^2+(pos(i,2)-pos(j,2)).^2;
D(i,j)=dis^(0.5);
D(j,i)=D(i,j);
end
end
%%生成初始群体
popm=zeros(M,N);%设置种群
for i=1:M
popm(i,:)=randperm(N);%随机排列，比如[2 4 5 6 1 3]
end
%%随机选择一个种群
R=popm(1,:);
figure(1);
scatter(pos(:,1),pos(:,2),'rx');%画出所有城市坐标
axis([-3 3 -3 3]);
figure(2);
plot_route(pos,R); %%画出初始种群对应各城市之间的连线
axis([-3 3 -3 3]);
%%初始化种群及其适应函数
fitness=zeros(M,1);
len=zeros(M,1);
for i=1:M%计算每个染色体对应的总长度
len(i,1)=myLength(D,popm(i,:));
end
maxlen=max(len);%最大回路
minlen=min(len);%最小回路
%归一化操作
fitness=fit(len,m,maxlen,minlen);
rr=find(len==minlen);%找到最小值的下标，赋值为rr
R=popm(rr(1,1),:)%提取该染色体，赋值为R
for i=1:N
fprintf('%d ',R(i));%把R顺序打印出来
end
fprintf('\n');
fitness=fitness/sum(fitness);
distance_min=zeros(ITER+1,1); %%各次迭代的最小的种群的路径总长
nn=M;
iter=0;
while iter<=ITER
fprintf('迭代第%d次\n',iter);
%%选择操作
p=fitness./sum(fitness);
q=cumsum(p);%累加
%随机复制操作
for i=1:(M-1)
len_1(i,1)=myLength(D,popm(i,:));
r=rand;
tmp=find(r<=q); %寻找随机数小于q的个体
popm_sel(i,:)=popm(tmp(1),:);
end
[fmax,indmax]=max(fitness);%求当代最佳个体
popm_sel(M,:)=popm(indmax,:);%第100个染色体设为当代最佳个体
%%交叉操作
nnper=randperm(M);
% A=popm_sel(nnper(1),:);
% B=popm_sel(nnper(2),:);
%%
for i=1:M*Pc*0.5
A=popm_sel(nnper(i),:);
B=popm_sel(nnper(i+1),:);
[A,B]=cross(A,B);
% popm_sel(nnper(1),:)=A;
% popm_sel(nnper(2),:)=B;
popm_sel(nnper(i),:)=A;
popm_sel(nnper(i+1),:)=B;
end
%%变异操作
for i=1:M
pick=rand;
while pick==0 %防止随机数为0
pick=rand;
end
if pick<=Pmutation
popm_sel(i,:)=Mutation(popm_sel(i,:));
end
end
%%求适应度函数
NN=size(popm_sel,1);
len=zeros(NN,1);
for i=1:NN
len(i,1)=myLength(D,popm_sel(i,:));
end
maxlen=max(len);
minlen=min(len);
distance_min(iter+1,1)=minlen; %当前迭代最小值
fitness=fit(len,m,maxlen,minlen); %对交叉变异复制之后的种群再次进行（类似于归一化操作）
rr=find(len==minlen); %寻找最小值编号
fprintf('minlen=%d\n',minlen);
R=popm_sel(rr(1,1),:); %最小值的染色体
for i=1:N %直接输出染色体
fprintf('%d ',R(i));
end
fprintf('\n');
popm=[];
popm=popm_sel; %将原种群清空，将复制交叉变异操作后的种群复制进来
iter=iter+1;
%pause(1);
end
%end of while
figure(3)
plot_route(pos,R);
axis([-3 3 -3 3]);
figure(4)
plot(distance_min);
