myga.m

用MATLAB编写的遗传算法求解TSP问题的M文件

%function [result,resultall]=myga;
function [result]=myga;                      %result:从第1个到第N个元素为所求得的最优解，即城市序号的排列， 
%this is a main function                     %       而第N+1和第N+2个元素为该最优解所在最后种群的子群号和个体号。第N+3个元素为目标函数值。

clc;
clear;
N=30;                                         %the number of cities(10,30,50,75)
groupnum=10;                                  %the number of groupnum
c=clock;
 maxnumber=30;                                %the number of generation


resultall=zeros(40,N+3);

% initpop and selecttest
publicmem=ones(N,N);                           %record the information of allpop
submem=ones(groupnum,N,N);                     %record the information of subgrooup's the top six 
[lowest pop publicmem submem]=selecttest(N,initpop(N,groupnum),publicmem,submem);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for number=1:maxnumber          %the number of circyle
    
if number~=1
      [lowest,pop,publicmem,submem]=selecttest(N,pop,publicmem,submem);    
end

temppop=pop;
best=zeros(1,N+3);
tempmax=0;


if mod(number,25)==0
    
%current the best individual
for i=1:groupnum
    for j=1:10
        if temppop(i,j,N+2)==-1 & tempmax<temppop(i,j,N+1)
%         if tempmax<temppop(i,j,N+1)
            tempmax=temppop(i,j,N+1);
            best(1,N+1)=i;
            best(1,N+2)=j;
            best(1,N+3)=temppop(i,j,N+1);
            for k=1:N
                best(1,k)=temppop(i,j,k);
            end
        end
    end
end

%the best result
result=best;
if N==10
    result(1,N+3)=1/result(1,N+3);
else
    result(1,N+3)=1000/result(1,N+3);
end
resultall(number/25,:)=result;

end    %  end of if mod(numble,100)


%create a board recording the information of saved seed in every group
temparraymain=zeros(10,7);
for i=1:groupnum
    m=1;
    for j=1:10
        if pop(i,j,N+2)<0                 %record the six excellent
            temparraymain(i,m)=j;
            m=m+1;
        else
            temparraymain(i,7)=j;             %record a null individual for saving the excellent
        end
    end
end
%ok

% xover
%if number<maxnumber/2 | randint(1,1,[1 10])>6
for i=1:groupnum  
    if temparraymain(i,1)~=0
        for j=1:3
            x=randint(1,1,[1 6]);
            y=randint(1,1,[1 6]);
            while x==y
                y=randint(1,1,[1 6]);
            end
          [pop(i,temparraymain(i,x),:),pop(i,temparraymain(i,y),:)]=xover(pop(i,temparraymain(i,x),:),pop(i,temparraymain(i,y),:),N);
       end
    end
end
%end

% save the best in every group
for i=1:groupnum
    for j=1:10
        if temppop(i,j,N+2)==-1 
            pop(i,temparraymain(i,7),1:N+3)=temppop(i,j,1:N+3);            %record the excellent individual in subgroup
        end
    end
end

% complete the subgroup of pop  
i=lowest;
for j=1:10
    pop(i,j,1:N)=complete(publicmem,N);
end

%complete the individual of pop
for i=1:groupnum
    for j=1:10
        if  pop(i,j,N+2)==0
            pop(i,j,1:N)=complete(publicmem,N);
        end
    end
end

%compute the pop's eval for next selection
for i=1:groupnum
    for j=1:10
        pop(i,j,1:N+3)=mygaeval1(pop(i,j,1:N+3),N);
    end
end

%mutation
rnum=randint(1,1,[1 100]);
if (number>100 & rnum<11) | number>275
for i=1:groupnum
    for j=1:10
        if pop(i,j,N+2)==-1 | randint(1,1,[1 100])<5
             pop(i,j,1:N+3)=mutation(pop(i,j,1:N+3),N);
             pop(i,j,N+3)==-1;
        end
    end
end
                           
for i=1:groupnum                                        %add overordering operation
    for j=1:10
        if pop(i,j,N+2)==-1 | randint(1,1,[1 100])<5
        a=randint(1,1,[1 N]);
        b=randint(1,1,[1 N]);
        while (b==a)
            b=randint(1,1,[1 N]);
        end
            if a>b
               temp=a;
               a=b;
               b=temp;
            end
            pop(i,j,1:N+3)=overorder(pop(i,j,1:N+3),N,a,b);
        end
    end
end
end                                                    %end of if number>100

end                                                       % end of while

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%current the best individual
tempmax=0;
for i=1:groupnum
    for j=1:10
        if  tempmax<pop(i,j,N+1)
            tempmax=pop(i,j,N+1);
            best(1,N+1)=i;
            best(1,N+2)=j;
            best(1,N+3)=pop(i,j,N+1);
            for k=1:N
                best(1,k)=pop(i,j,k);
            end
        end
    end
end

%the best result
result=best;
if N==10
    result(1,N+3)=1/result(1,N+3);
else
    result(1,N+3)=1000/result(1,N+3);
end

endpop=pop;

alltime=etime(clock,c);
%strcat('the result')
% result
strcat('运行时间：',num2str(alltime));