TSP问题遗传算法通用matlab程序

admin

[mw_shl_code=applescript,true] [原创]TSP问题遗传算法通用matlab程序
%TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序
%D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍，
%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4  ,不宜太大
%alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0
%R为最短路径,Rlength为路径长度
function [R,Rlength]=geneticTSP(D,n,C,m,alpha)

[N,NN]=size(D);
farm=zeros(n,N);%用于存储种群
for i=1:n
    farm(i,=randperm(N);%随机生成初始种群
end
R=farm(1,;%存储最优种群
len=zeros(n,1);%存储路径长度
fitness=zeros(n,1);%存储归一化适应值
counter=0;

while counter<C
   
    for i=1:n
        len(i,1)=myLength(D,farm(i,);%计算路径长度
    end
    maxlen=max(len);
    minlen=min(len);
    fitness=fit(len,m,maxlen,minlen);%计算归一化适应值
    rr=find(len==minlen);
    R=farm(rr(1,1),;%更新最短路径
   
    FARM=farm;%优胜劣汰，nn记录了复制的个数
    nn=0;
    for i=1:n
        if fitness(i,1)>=alpha*rand
            nn=nn+1;
            FARM(nn,=farm(i,;
        end
    end
    FARM=FARM(1:nn,;
   
    [aa,bb]=size(FARM);%交*和变异
    while aa<n
        if nn<=2
            nnper=randperm(2);
        else
            nnper=randperm(nn);
        end
        A=FARM(nnper(1),;
        B=FARM(nnper(2),;
        [A,B]=intercross(A,B);
        FARM=[FARM;A;B];
        [aa,bb]=size(FARM);
    end
    if aa>n
        FARM=FARM(1:n,;%保持种群规模为n
    end
   
    farm=FARM;
    clear FARM
    counter=counter+1
   
end

Rlength=myLength(D,R);   
  

%计算归一化适应值子程序
function fitness=fit(len,m,maxlen,minlen)
fitness=len;
for i=1:length(len)
    fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m;
end


%交*算法采用的是由Goldberg和Lingle于1985年提出的PMX(部分匹配交*)
function [a,b]=intercross(a,b)
L=length(a);
if L<=10%确定交*宽度
    W=1;
elseif ((L/10)-floor(L/10))>=rand&&L>10
    W=ceil(L/10);
else
    W=floor(L/10);
end
p=unidrnd(L-W+1);%随机选择交*范围，从p到p+W
for i=1:W%交*
    x=find(a==b(1,p+i-1));
    y=find(b==a(1,p+i-1));
    [a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1));
    [a(1,x),b(1,y)]=exchange(a(1,x),b(1,y));   
end
function [x,y]=exchange(x,y)
temp=x;
x=y;
y=temp;

% 计算路径的子程序
function len=myLength(D,p)
[N,NN]=size(D);
len=D(p(1,N),p(1,1));
for i=1N-1)
    len=len+D(p(1,i),p(1,i+1));
end
[/mw_shl_code]