tspga.m

求解TSP问题的遗传算法matlab程序

function  [time,opt,fval]=TspGa(Map,MaxIter,SizeScale,pc,pm ,viprate)
%This is function 
%Input:
%Output:
lminroad=[];
t=cputime;
%MaxIter=100;
%SizeScale=100;
n=max(size(Map));

%compute the roadmatrix
DistMatrix=zeros(n,n);
for i=1:n
    for j=1:n
        DistMatrix(i,j)=distance(Map(i,:),Map(j,:));
    end
end

%to inital the road( oder the cites )
Road=ones(SizeScale,n);
for i=1:SizeScale
    Road(i,:)=randperm(n);
end
%
Dist=zeros(SizeScale,1);
for i=1:SizeScale
    for j=1:(n-1)
        Dist(i)=Dist(i)+DistMatrix(Road(i,j),Road(i,j+1));
    end
end

[MinRoad,II]=min(Dist);

for iter=1:MaxIter 
  
    %计算适应度 
  MinRoad=min(Dist);
   MaxRoad=max(Dist);
   for i=1:SizeScale
        fit(i)=fitness(MinRoad,MaxRoad,Dist(i));
   end
  
 
   
 %三交叉交配
  childRoad=[];
  for i=1:SizeScale
  y1=select(rand,fit);
  y2=select(rand,fit);
  y3=select(rand,fit);
  if rand<pc  %交叉概率
  newroad=crossgens(Road(y1,:),Road(y2,:),Road(y3,:),Map);
  childRoad=[childRoad;newroad];
  end
  end
  
  %变异
  mutateRoad=[];
 for i=1:SizeScale
        if rand<pm  %变异概率
            ChangeLocation=randint(1,2,[1 n]);
            if ChangeLocation(1)==ChangeLocation(2)
                continue;
            end            
            newroad=Road(i,:);
            newroad(ChangeLocation(1))=Road(i,ChangeLocation(2));
            newroad(ChangeLocation(2))=Road(i,ChangeLocation(1));
            mutateRoad=[mutateRoad;newroad];
        end
  end

  Dist1=[];Road1=[];
 %繁殖
vipnum=floor(SizeScale*viprate);
[Dist11,loc]=sort(Dist);
for i=1:vipnum
Road1(i,:)=Road(loc(i),:);
Dist1(i)=Dist11(i);
end
 

%从后代 变异中选优
[size(childRoad),size(mutateRoad)];
generation=[childRoad;mutateRoad];
genum=length(generation);
Distge=zeros(genum,1);
  for i=1:genum
    for j=1:(n-1)
        Distge(i)=Distge(i)+DistMatrix(generation(i,j),generation(i,j+1));
    end
  end

    [Distge1,locge]=sort(Distge);
    i=vipnum+1;k=1;
    while (i<=SizeScale && k<=genum)
        repeat=0;
        for ii=1:i-1
            if sum(Road1(ii,:)==generation(locge(k),:))==n
              repeat=1;break;
            end
        end
        if repeat==0
            Dist1(i)=Distge1(k);
            Road1(i,:)=generation(locge(k),:);
            i=i+1;
        end
        k=k+1;
    end
  
   
    if length(Road1)<SizeScale%没填满
        for i=length(Dist1)+1:SizeScale
             Road1(i,:)=randperm(n);
             Dist1(i)=0;
             for j=1:(n-1)
                    Dist1(i)=Dist1(i)+DistMatrix(Road1(i,j),Road1(i,j+1));
             end
        end
     end
           
Road=Road1;
Dist=Dist1;
[MinRoad,II]=min(Dist);
iter
 MinRoad
 lminroad=[lminroad,MinRoad];
   
end         

plot(Map(:,1),Map(:,2),'*');
hold on
XX=Map(Road(II,:),1);
XX=[XX;Map(Road(II,1),1)];
YY=Map(Road(II,:),2);
YY=[YY;Map(Road(II,1),2)];
plot(XX,YY);
hold off
figure(2)
plot(lminroad)
time=cputime-t;
opt=Road(II,:);
fval=MinRoad;