ga_tsp-wrong.m

用遗传算法编写的一个程序,其目的是求解旅行商问题.

clear
pop=[1 2 3 4 5 6;
    5 3 4 2 1 6;
    3 4 2 1 6 5;
    4 6 2 1 5 3;
    2 6 5 1 3 4]
A=[0 5 1 100 6 100;
    5 0 3 3 100 4;
    1 2 3 2 100 100;
    100 3 2 0 7 5;
    6 100 100 7 0 100;
    100,4,100,5,100,0];
%--------------------copy--------------------
l=1
s=0
best(l)=pop(1)
best(l+1)=pop(2)
while(best(l)~=best(l+1))
pop1=pop
[r,c]=size(pop)
for i=1:r
    for j=1:c-2
        d1=A(pop(i,j),pop(i,j+1))+A(pop(i,j+1),pop(i,j+2))
    end
        d=d1+A(pop(i,c) ,pop(i,1))
        f(i)=1/d
        s=s+f(i)
end
s1=rand(r,1).*s;
k=1;
m=1;
j=1;
s2=f(1);
while(j<=r)
    if(s2>=s1(j))
        pop2(j,:)=pop(k,:);
        j=j+1;
        continue
    else if (m<=r)
            m=m+1;
            s2=s2+f(m);
            k=m;
            continue
        end
    end
end
    pop3=pop2;%after copy
    pop4=pop3;
    %---------------------------------------crossover---------
    b=fix(rand(1,2)*10);% (b1,b2)=fix(rand(1,2)*10); ------wrong
    m1=min(b(1),b(2));
    m2=max(b(1),b(2));
    for i=1:r
        for j=1:m1
            pop4(i,j)=0;
        end
        for j=m2:c
            pop4(i,j)=0;
        end
    end
    %____________________________________________________________________-
    for k=1:2:r-1
        for i=1:c
            for j=m1+1:m2-1
               if pop3(k+1,i)==pop4(k,j)
                  pop3(k+1,i)=0;
              else if pop3(k,i)==pop4(k+1,j)
                      pop3(k,i)=0;
                  end
                end
          end 
      end
  end
      %______________________________________________________________
      k=1;
      j=1;
      k1=m2;
      for i=1:2:r-1
          if pop3(i,j)~=0%!= wrong
              while(k<=m1)
                  pop4(i+1,k)=pop3(i,j);
                  k=k+1;
                  j=j+1;
              end
              while(j<=c)
              pop4(i+1,k1)=pop3(i,j);
              j=j+1;
              end
          end
      end
      %--------------------------
      k=1;
      j=1;
      k1=m2;
      for i=1:2:r-1
          if(pop3(i,j)~=0)%!=
              while(k<=m1)
                  pop4(i,k)=pop3(i+1,j);
                 k=k+1;
                 j=j+1;
              end
              pop4(i,k1)=pop3(i+1,j);
             j=j+1;
          end
      end
     %-----------------------------------------------mutation--------------
     %--------
   b=fix(rand(1,4)*10)
   for i=1:r
       temp=pop4(i,b(1));
       pop4(i,b(1))=pop4(i,b(3));
       pop4(i,b(3))=temp
       temp1=pop4(i,b(2))
      pop4(i,b(2))=pop4(i,b(4)); 
      pop4(i,b(4))=temp1
  end
  for i=1:r
      for j=1:c-2
      d1=A(pop4(i,j),pop4(i,j+1))+A(pop4(i,j+1),pop4(i,j+2));
        d=d1+A(pop4(i,c),pop4(i,1));
        f(i)=1/d;  
    end
end
bestpop=pop4(1);
bestf=f(1);
for i=2:r2
    if f(i)>f(1)
        bestpop=pop4(i);
        bestf=f(i);
    end
end 
end
l=l+1;
best(l)=bestpop;
end
end
end