main.m

一个遗传算法实现TSP问题的基本演示程序

N=200;
popsize=40;
ncity=10;
pcro=0.8;
pmut=0.1;
distance(ncity,ncity)=0;
pop(popsize,ncity)=0;
best(N)=0;
for i=1:popsize
    pop(i,:)=randperm(ncity);
end
for i=1:ncity
    for j=1:2
    point(i,j)=100*rand();
    end
end
for i=1:ncity
    for j=1:i
        if i==j
            distance(i,j)=0;
        end
        distance(i,j)=sqrt((point(i,1)-point(j,1))^2+(point(i,2)-point(j,2))^2);
        distance(j,i)=distance(i,j);
    end
end
small=inf;
for gen=1:N
    sumdis(popsize)=0;
    for i=1:popsize
        for j=1:ncity-1
            sumdis(i)=sumdis(i)+distance(pop(i,j),pop(i,j+1));
        end
        sumdis(i)=sumdis(i)+distance(pop(i,ncity),pop(i,1));
        suit(i)=1/sumdis(i);
    end
    q(1)=suit(1);
    for i=2:popsize
        q(i)=q(i-1)+suit(i);
    end
        pop=select(pop,q,popsize);  %选择函数
        pop=crossover(pop,pcro,popsize,ncity);%交叉函数
        pop=mutation(pop,pmut,popsize,ncity);%变异函数
    
    for i=1:popsize
        s=0;
        for j=1:ncity-1
            s=s+distance(pop(i,j),pop(i,j+1));
        end
        sumdis(i)=s+distance(pop(i,j),pop(i,1));
        if sumdis(i)<small
           small=sumdis(i);
           best_individual=pop(i,:);
           pop(popsize,:)=best_individual;
        end
    end
    best(gen)=small;
    s1=sum(sumdis);
    ave(gen)=s1/popsize;
end
for i=1:N;
    m=0;
    n=0;
    for j=1:i
        m=m+best(j);
        n=n+ave(j);
    end
    on_line(i)=m/i;
    off_line(i)=n/i;
end
a=best_individual;
plot(point(a(:),1),point(a(:),2),'-');
hold on;
plot(point([a(1),a(ncity)],1),point([a(1),a(ncity)],2),'-');
for i=1:ncity
    s=int2str(i);
    text(point(i,1),point(i,2),s);
end 
 figure;plot(ave,'r');
title('每一代的平均值');  
figure;plot(best,'g');
title('每一代的最优值');     
figure;plot(on_line,'k');
title('在线性能');
figure;plot(off_line,'g');
title('离线性能');
clear i;
clear j;
clear m;
clear n;
clear point;
clear a;