clear all;
CityNum=48;
[dislist,Clist]=tsp(CityNum);
inn=48; %初始种群大小
gnmax=300; %最大迭代数
pc=0.8; %交叉概率
pm=0.01; %变异概率
%产生初始种群
s=zeros(inn,CityNum);
for i=1:inn
s(i,:)=randperm(CityNum);
end
[~,p]=objf(s,dislist);
gn=1;
ymean=zeros(gn,1);
ymax=zeros(gn,1);
xmax=zeros(inn,CityNum);
scnew=zeros(inn,CityNum);
smnew=zeros(inn,CityNum);
while gn<gnmax+1
for j=1:2:inn
seln=sel(p); %选择操作
scro=cro(s,seln,pc); %交叉操作
scnew(j,:)=scro(1,:);
scnew(j+1,:)=scro(2,:);
smnew(j,:)=mut(scnew(j,:),pm); %变异操作
smnew(j+1,:)=mut(scnew(j+1,:),pm);
end
s=smnew; %产生了新的种群
[f,p]=objf(s,dislist); %计算新种群的适应度
%记录当前代最好和平均的适应度
[fmax,nmax]=max(f);
ymean(gn)=1000/mean(f);
ymax(gn)=1000/fmax;
%记录当前代的最佳个体
x=s(nmax,:);
xmax(gn,:)=x;
drawTSP(Clist,x,ymax(gn),gn,0);
gn=gn+1;
end
[min_ymax,index]=min(ymax);
drawTSP(Clist,xmax(index,:),min_ymax,index,1);
figure(2);
plot(ymax,'r'); hold on;
plot(ymean,'b');grid;
title('搜索过程');
legend('最优解','平均解');
fprintf('遗传算法得到的最短距离:%.2f\n',min_ymax);
fprintf('遗传算法得到的最短路线');
disp(xmax(index,:));
%------------------------------------------------
%计算所有种群的适应度
function [f,p]=objf(s,dislist)%计算适应度，返回适应度f和累计概率p
inn=size(s,1); %读取种群大小
f=zeros(inn,1);
for i=1:inn
f(i)=CalDist(dislist,s(i,:)); %计算距离函数值，即适应度
end
f=1000./f'; %取距离倒数
%根据个体的适应度计算其被选择的概率
fsum=0;
for i=1:inn
fsum=fsum+f(i)^15;% 让适应度越好的个体被选择概率越高
end
ps=zeros(inn,1);
for i=1:inn
ps(i)=f(i)^15/fsum;
end
%计算累积概率
p=zeros(inn,1);
p(1)=ps(1);
for i=2:inn
p(i)=p(i-1)+ps(i);
end
p=p';
end
%--------------------------------------------------
%根据变异概率判断是否变异
function pcc=pro(pc)
test(1:100)=0;
l=round(100*pc);
test(1:l)=1;
n=round(rand*99)+1;
pcc=test(n);
end
%--------------------------------------------------
%“选择”操作
function seln=sel(p)
seln=zeros(2,1);
%从种群中选择两个个体，最好不要两次选择同一个个体
for i=1:2
r=rand; %产生一个随机数
prand=p-r;
j=1;
while prand(j)<0
j=j+1;
end
seln(i)=j; %选中个体的序号
if i==2&&j==seln(i-1) %%若相同就再选一次
r=rand; %产生一个随机数
prand=p-r;
j=1;
while prand(j)<0
j=j+1;
end
end
end
end
%------------------------------------------------
%“交叉”操作
function scro=cro(s,seln,pc)
bn=size(s,2);
pcc=pro(pc); %根据交叉概率决定是否进行交叉操作，1则是，0则否
scro(1,:)=s(seln(1),:);
scro(2,:)=s(seln(2),:);
if pcc==1
c1=round(rand*(bn-2))+1; %在[1,bn-1]范围内随机产生一个交叉位
c2=round(rand*(bn-2))+1;
chb1=min(c1,c2);
chb2=max(c1,c2);
middle=scro(1,chb1+1:chb2);
scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);
scro(2,chb1+1:chb2)=middle;
for i=1:chb1
while find(scro(1,chb1+1:chb2)==scro(1,i))
zhi=find(scro(1,chb1+1:chb2)==scro(1,i));
y=scro(2,chb1+zhi);
scro(1,i)=y;
end
while find(scro(2,chb1+1:chb2)==scro(2,i))
zhi=find(scro(2,chb1+1:chb2)==scro(2,i));
y=scro(1,chb1+zhi);
scro(2,i)=y;
end
end
for i=chb2+1:bn
while find(scro(1,1:chb2)==scro(1,i))
zhi=logical(scro(1,1:chb2)==scro(1,i));
y=scro(2,zhi);
scro(1,i)=y;
end
while find(scro(2,1:chb2)==scro(2,i))
zhi=logical(scro(2,1:chb2)==scro(2,i));
y=scro(1,zhi);
scro(2,i)=y;
end
end
end
end
%--------------------------------------------------
%“变异”操作
function snnew=mut(snew,pm)
bn=size(snew,2);
snnew=snew;
pmm=pro(pm); %根据变异概率决定是否进行变异操作，1则是，0则否
if pmm==1
c1=round(rand*(bn-2))+1; %在[1,bn-1]范围内随机产生一个变异位
c2=round(rand*(bn-2))+1;
chb1=min(c1,c2);
chb2=max(c1,c2);
x=snew(chb1+1:chb2);
snnew(chb1+1:chb2)=fliplr(x);%将新变异的进行翻转
end
end
%------------------------------------------------
%城市位置坐标
function [DLn,cityn]=tsp(n)
DLn=zeros(n,n);
if n==48
city48=[6734 1453;2233 10;5530 1424;401 841;3082 1644;7608 4458;7573 3716;7265 1268;6898 1885;1112 2049;
5468 2606;5989 2873;4706 2674;4612 2035;6347 2683;6107 669;7611 5184;7462 3590;7732 4723;5900 3561;
4483 3369;6101 1110;5199 2182;1633 2809;4307 2322;675 1006;7555 4819;7541 3981;3177 756;7352 4506;
7545 2801;3245 3305;6426 3173;4608 1198;23 2216;7248 3779;7762 4595;7392 2244;3484 2829;6271 2135;
4985 140;1916 1569;7280 4899;7509 3239;10 2676;6807 2993;5185 3258;3023 1942];
for i=1:48
for j=1:48
DLn(i,j)=((city48(i,1)-city48(j,1))^2+(city48(i,2)-city48(j,2))^2)^0.5;
end
end
cityn=city48;
end
end
%------------------------------------------------
%适应度函数
function F=CalDist(dislist,s)
DistanV=0;
n=size(s,2);
for i=1:(n-1)
DistanV=DistanV+dislist(s(i),s(i+1));
end
DistanV=DistanV+dislist(s(n),s(1));
F=DistanV;
end
%------------------------------------------------
%画图
function drawTSP(Clist,BSF,bsf,p,f)
CityNum=size(Clist,1);
for i=1:CityNum-1
plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');
text(Clist(BSF(i),1),Clist(BSF(i),2),[' ',int2str(BSF(i))]);
text(Clist(BSF(i+1),1),Clist(BSF(i+1),2),[' ',int2str(BSF(i+1))]);
hold on;
end
plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g');
title([num2str(CityNum),'城市TSP']);
if f==0&&CityNum~=10
text(5,5,['第 ',int2str(p),' 代',' 最短距离为 ',num2str(bsf)]);
else
text(5,5,['最终搜索结果：最短距离 ',num2str(bsf),'， 在第 ',num2str(p),' 代达到']);
end
if CityNum==10
if f==0
text(0,0,['第 ',int2str(p),' 代',' 最短距离为 ',num2str(bsf)]);
else
text(0,0,['最终搜索结果：最短距离 ',num2str(bsf),'， 在第 ',num2str(p),' 代达到']);
end
end
hold off;
pause(0.05);
end
