tsp.txt

求解旅行商问题 已知n个城市之间的相互距离

求解tsp问题的遗传算法
function [bestpop,trace]=ga(D,termOps,num,pc,cxOps,pm,alpha)
%
%????????????????????????
%[bestpop,trace]=ga(D,termOps,num,pc,cxOps,pm,alpha)
%D:距离矩阵
%termOps:种群带数
%num:每带染色体的个数
%pc:交叉概率
%cxOps:由于本程序采用单点交叉，交叉点的设置在本程序中没有很好的解决，所以本文了采用定点，即第cxOps，可以随机产生。
%pm:变异概率
%alpha:评价函数eval(Vi)=alpha*(1-alpha).^(i-1).
%bestpop:返回的最优种群
%trace:进化轨迹
%------------------------------------------------
%####@@@##版权所有！欢迎广大网友改正，改进！##@@@####
%E-mail:[e-mail]
%####################################################
%
citynum=size(D,2);
n=nargin;
if n<2
    disp(?缺少变量！！?)
    disp(?^_^开个玩笑^_^?)
end
if n<2
    termOps=500;
    num=50;
    pc=0.25;
    cxOps=3;
    pm=0.30;
    alpha=0.10;
end
if n<3
    num=50;
    pc=0.25;
    cxOps=3;
    pm=0.30;
    alpha=0.10;
end
if n<4
    pc=0.25;
    cxOps=3;
    pm=0.30;
    alpha=0.10;
end
if n<5
    cxOps=3;
    pm=0.30;
    alpha=0.10;
end
if n<6
    pm=0.30;
    alpha=0.10;
end
if n<7
    alpha=0.10;
end
if isempty(cxOps)
    cxOps=3;
end
[T]=initializega(num,citynum);
for i=1:termOps
[L]=f(D,T);
[x,y]=find(L==max(L));
trace(i)=-L(y(1));
bestpop=T(y(1),:);
[T]=select(T,L,alpha);
[G]=grefenstette(T);
[G1]=crossover(G,pc,cxOps);
[G]=mutation(G1,pm);  %均匀变异
[T]=congrefenstette(G);
end
---------------------------------------------------------
function [T]=initializega(num,citynum)
for i=1:num
    T(i,:)=randperm(citynum);
end
-----------------------------------------------------------
function [L]=f(D,T)
[m,n]=size(T);
for k=1:m
    for i=1:n-1
      l(k,i)=D(T(k,i),T(k,i+1));
    end
      l(k,n)=D(T(k,n),T(k,1));
      L(k)=-sum(l(k,:));
end
-----------------------------------------------------------
function [T]=select(T,L,alpha)
[m,n]=size(L);
T1=T;
[beforesort,aftersort1]=sort(L,2);%fsort from l to u
for i=1:n
    aftersort(i)=aftersort1(n+1-i);      %change 
end
for k=1:n;
    T(k,:)=T1(aftersort(k),:);
    L1(k)=L(aftersort(k));
end
T1=T;
L=L1;
for i=1:size(aftersort,2)
    evalv(i)=alpha*(1-alpha).^(i-1);
end
m=size(T,1);
q=cumsum(evalv);
qmax=max(q);
for k=1:m
    r=qmax*rand(1);
    for j=1:m
        if j==1&r<=q(1)
            T(k,:)=T1(1,:);
        elseif j~=1&r>q(j-1)&r<=q(j)
            T(k,:)=T1(j,:);
        end
    end
end
--------------------------------------------------
function [G]=grefenstette(T)
[m,n]=size(T);
for k=1:m
    T0=1:n;
   for i=1:n
       for j=1:length(T0)
           if T(k,i)==T0(j)
              G(k,i)=j;
              T0(j)=[];
              break
           end
       end
    end
end
-------------------------------------------
function [G]=crossover(G,pc,cxOps)
[m,n]=size(G);
ran=rand(1,m);
r=cxOps;
[x,ru]=find(ran<pc);
if ru>=2
    for k=1:2:length(ru)-1
       G1(ru(k),:)=[G(ru(k),[1:r]),G(ru(k+1),[(r+1):n])];
       G(ru(k+1),:)=[G(ru(k+1),[1:r]),G(ru(k),[(r+1):n])];
       G(ru(k),:)=G1(ru(k),:);
    end
end
--------------------------------------------
function [G]=mutation(G,pm)    %均匀变异
[m,n]=size(G);
ran=rand(1,m);
r=rand(1,3);      %dai gai jin
rr=floor(n*rand(1,3)+1);
[x,mu]=find(ran<pm);
for k=1:length(mu)
    for i=1:length(r)
        umax(i)=n+1-rr(i);
        umin(i)=1;
        G(mu(k),rr(i))=umin(i)+floor((umax(i)-umin(i))*r(i));
    end
end
---------------------------------------------------
function [T]=congrefenstette(G)
[m,n]=size(G);
for k=1:m
    T0=1:n;
   for i=1:n
      T(k,i)=T0(G(k,i));
      T0(G(k,i))=[];
   end
end