mytsp.m

遗传算法求解TSP问题（10个城市）

%function MyTSP
%initial;
%for G=1:N
%    calulate; 计算每个个体的适应度
%    code;     编码  imp
%    keepbest; 根据计算结果进行保优
%    crossover;交叉
%    mutation; 变异
%    selection;选择并产生新种群
%    decode;   解码
%end
%绘制图形显示结果

clear all;
close all;

%初始化函数，随机形成规模为20初始种群
n=10;
%popo(20,10)=0;           %生成初始种群函数
best_individual(10)=0;  %最优个体
%adapt_ave(10)=0;       %种群平均适应值
new_pop(20,10)=0;
%adapt_best(10)=0;
ppcode(20,10)=0;
adapmin(400)=0;
%初始种群
popo=[1 3 6 4 5 8 9 7 2 10;1 2 10 9 8 7 5 6 3 4;2 6 9 8 7 4 5 1 3 10;...
    5 1 6 9 3 2 4 8 7 10;10 8 9 6 7 4 2 3 5 1;9 1 7 6 3 4 5 2 8 10;...
    1 9 4 5 6 8 7 2 10 3;4 6 5 1 7 8 9 2 3 10;7 4 1 5 6 9 8 10 3 2;...
    3 6 9 8 7 4 10 2 1 5;8 9 7 6 4 2 3 5 1 10;6 2 3 4 5 1 7 8 9 10;...
    8 3 2 4 7 5 6 1 9 10;1 2 7 4 9 10 3 5 6 8;6 7 10 2 3 5 9 8 1 4;...
    3 10 2 7 9 1 5 6 8 4;4 1 6 10 3 2 7 9 5 8;1 6 3 2 10 5 4 8 9 7;...
    2 5 3 8 6 10 1 4 7 9;1 7 3 9 2 5 10 4 8 6];

%十个城市坐标
xlabel=[1 3 4 9 7 8 2 6 5 10];
ylabel=[2 4 7 9 1 3 5 10 6 8];
%生成城市距离表
distance(10,10)=0;
for i=1:n
    for j=1:n
       distance(i,j)=sqrt((xlabel(i)-xlabel(j))^2+(ylabel(i)-ylabel(j))^2);
    end
end

for G=1:400    %循环开始
    
%计算适应度
% function [adapt,ada_ave]=adapting(pop)
adapt(20)=0;
for i=1:20
    sum=0;
    for j=1:9
        k=popo(i,j);
        h=popo(i,j+1);
        %distance=sqrt((xlabel(k)-xlabel(h))^2+(ylabel(k)-ylabel(h))^2);
        sum=sum+distance(k,h);
    end
    k1=popo(i,10);
    h1=popo(i,1);
    extra=sqrt((xlabel(k1)-xlabel(h1))^2+(ylabel(k1)-ylabel(h1))^2);
    adapt(i)=sum+extra;
end

%寻找最优个体及保优
min=inf;
p=0;
for i=1:20
    if adapt(i)<min
        min=adapt(i);
        p=i;
    end
end
adapmin(G)=min;
best_pos=p;
for j=1:10
    best_individual(j)=popo(best_pos,j);
end

%编码
for i=1:20
    stan=[1 2 3 4 5 6 7 8 9 10];
    for j=1:10
        k=1;
        for h=1:10;
            if popo(i,j)==h;
                temp=k;
                stan(h)=0;
                break;
            end
            if stan(h)~=0
                k=k+1;
            end
        end
        ppcode(i,j)=temp;
    end
    %ppcode(i,10)=1;
end

%交叉操作
for i=1:2:20
    cross_P=rand;       %产生一个随机数，用于和交叉概率进行比较
    if cross_P<0.6   %(-0.6*G+180.6)/300  %交叉概率线性变换，由0.6下降到0.002
        cross_pos=round(10*rand);   %交叉位置为1-10
        if cross_pos==0  %若位置为0，则不进行交叉操作
            %continue;    %跳出for循环
        else
           for j=cross_pos:10
              temp=ppcode(i,j);
              ppcode(i,j)=ppcode(i+1,j);
              ppcode(i+1,j)=temp;
           end
        end
    end
end

%变异操作，单点变异
for i=1:20
    for j=1:9
       if rand<0.1;               %(0.09*G+0.19)/200
%          M_pos=round(10*rand);   
%          if M_pos~=0              %若变异位为0则无意义
             temp=ppcode(i,j)+fix(rand*10);
             s=fix(temp/(11-j));
             ppcode(i,j)=temp-s*(11-j);
             if ppcode(i,j)==0
                 ppcode(i,j)=fix(rand*(10-j))+1;
             end
%          end
       end
    end
end

%计算平均适应度
%adapt_ave(G)=0;
%for i=1:40
%    adapt_ave(G)=adapt_ave(G)+adapt(i);
%    if adapt_best(G)<adapt(i)
%        adapt_best(G)=adapt(i);
%    end
%end
%adapt_ave(G)=adapt_ave(G)/40;  %平均适应度

% The select operator function
ada_sum=0;

for i=1:20
    ada_sum=ada_sum+adapt(i);
end

for i=1:20      %选择19次，最后一个个体留给历代最优解
    r=rand*ada_sum;  %随机产生一个数
    ada_temp=0;      %初始化累加值为0
    j=0;
    while(ada_temp<r)
        j=j+1;
        ada_temp=ada_temp+adapt(j);  
    end               %退出循环时的j值即为被选择的个体序号
    for k=1:10
        new_pop(i,k)=ppcode(j,k);
    end
end

%最优解复制
%for j=1:10
%    new_pop(20,j)=best_individual(j);
%end

%将选择产生的新群体复制给popo种群
for i=1:20
    for j=1:10
        popo(i,j)=new_pop(i,j);
    end
end

%解码
for n=1:19
   stan=[1 2 3 4 5 6 7 8 9 10];
   for i=1:10
      k=0;
      for j=1:10
          if stan(j)~=0
            k=k+1;
          end
          if popo(n,i)==k
             temp=j;
             stan(j)=0;
             break;
          end
      end
      popo(n,i)=temp;
   end
end

for j=1:10
    popo(20,j)=best_individual(j);
end
if G==2
    disp(popo);
end

end    %主程序结束

%最终结果显示
figure(1)
for i=1:10
    scatter(xlabel,ylabel);
    hold on;
end
disp('最优解:');
disp(best_individual);
for i=1:9
    x_1=best_individual(i);
    x_2=best_individual(i+1);
    t=[xlabel(x_1) xlabel(x_2)];
    t_next=[ylabel(x_1) ylabel(x_2)];
    line(t,t_next);
    hold on;
end
t=[xlabel(best_individual(10)) xlabel(best_individual(1))];
t_next=[ylabel(best_individual(10)) ylabel(best_individual(1))];
line(t,t_next);
hold on;
figure(2);
n=1:400;
plot(n,adapmin);
disp('遗传代数:');
disp(G);
disp('最短距离:');
min=10000;
for i=1:400
    if adapmin(i)<min
        min=adapmin(i);
    end
end        
disp(min);
disp('@copyright Zhang Dongya');
disp('2007 11 10');