%SY0707348宗滿意 遺傳算法求解TSP問題(為選擇操作從新設(shè)計(jì)后程序)
%D是距離矩陣，n為種群個(gè)數(shù)
%參數(shù)a是中國(guó)31個(gè)城市的坐標(biāo)(初始給定)
%C為停止代數(shù)，遺傳到第 C代時(shí)程序停止,C的具體取值視問題的規(guī)模和耗費(fèi)的時(shí)間而定
%m為適值淘汰加速指數(shù),最好取為1,2,3,4,不宜太大
%交叉概率Pc,變異概率Pm
%R為最短路徑,Rlength為路徑長(zhǎng)度
      
function [R,Rlength]=geneticTSP2(D,a,n,C,m,Pc,Pm)
         [N,NN]=size(D);%(31*31)
         farm=zeros(n,N);%用于存儲(chǔ)種群
         for i=1:n
             farm(i,:)=randperm(N);%隨機(jī)生成初始種群
         end
         R=farm(1,:);%一個(gè)隨機(jī)解(個(gè)體)
%在二維圖上畫出所有點(diǎn)
         scatter(a(:,1),a(:,2),'x');
         hold on        
        pause(1)
%畫出隨機(jī)解得路徑圖      
       figure;
       plotaiwa(a,R);
       hold on         
       pause(1)
%輸出隨機(jī)的解得路徑和總距離
       disp('初始種群中的一個(gè)隨機(jī)值:')
       R
       Rlength=myLength(D,R)
       disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%計(jì)算各個(gè)個(gè)體總距離和適配置      
                           %farm(1,:)=R;
        len=zeros(n,1);%存儲(chǔ)路徑長(zhǎng)度
        fitness=zeros(n,1);%存儲(chǔ)適配值
        counter=0;
        
       while counter<C
            for i=1:n
                len(i,1)=myLength(D,farm(i,:));%計(jì)算路徑長(zhǎng)度
            end
            %maxlen=max(len);
            minlen=min(len);
           
            %fitness=fit(len,m,maxlen,minlen);%計(jì)算適應(yīng)度
            rr=find(len==minlen);%返回的是在len中路徑最短的路徑坐標(biāo)(i,1)
            
            R=farm(rr(1,1),:);%更新最短路徑
                                                   %disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
            FARM=farm;%優(yōu)勝劣汰，nn記錄了復(fù)制的個(gè)數(shù)
%選擇,  
          K=30;
          [aa,bb]=size(FARM);
          FARM2=FARM;
          len2=len;
          [len]=sort(len);
          for i=1:aa
              tt= find(len2==len(i,1));
              FARM(i,:)=FARM2(tt(1,1),:);
          end   
          for i=1:K
              j=aa+1-i;
              FARM(j,:)=FARM(i,:);
              
          end
  
                                    
                                    
                                    
                                    
                                    
                                    
                                    
                                    
                                    
                                    
                                    
 %                交叉操作
              [aa,bb]=size(FARM);
               FARM2=FARM;
             
               for i=1:2:aa
                    
                       if Pc>rand&&i<aa %交叉概率Pc
                            A=FARM(i,:);
                            B=FARM(i+1,:);
                            [A,B]=intercross(A,B);
                            FARM(i,:)=A;
                            FARM(i+1,:)=B;
                       end  
                      
               end
              %交叉檢驗(yàn)  (可省去)             
               for i=1:aa
                   if myLength(D,FARM(i,:))>myLength(D,FARM2(i,:))
                       FARM(i,:)=FARM2(i,:);
                   end
               end
               clear FARM2
               
               
               
               
               
               
      
          
             [aa,bb]=size(FARM); %aa=nn2
   
%       變異   
            FARM2=FARM;
            for i=1:aa
                if Pm>=rand                    
                  FARM(i,:)=mutate(FARM(i,:));
                end
            end
             %變異檢驗(yàn)(可省略)  
               for i=1:aa
                   if myLength(D,FARM(i,:))>myLength(D,FARM2(i,:))
                       FARM(i,:)=FARM2(i,:);
                   end
               end
               clear FARM2
%群體的更新
           %FARM2=zeros(n-aa+1,N);
           %if n-aa>=1             
           %    for i=1:n-aa
           %       FARM2(i,:)=randperm(N);%隨機(jī)生成n-aa種群
           %     end
           % end
           FARM=[R;FARM];%將隨機(jī)產(chǎn)生的n-aa個(gè)體加入從后面種群,將上次迭代的最優(yōu)解從前面加入種群
           [aa,bb]=size(FARM);
                                                   %disp('~~~~~~~~~~~~~~~~4~~~~~~~驗(yàn)證zong~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
             %保持種群規(guī)模為n                                         
            if aa>n
                FARM=FARM(1:n,:);
            end   
     
    
                                                    %disp('~~~~~~~~~~~~~~~~~~~5~~~~驗(yàn)證zong~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
            %更新farm
            farm=FARM;
            clear FARM
            %更新迭代次數(shù)
            counter=counter+1 ; 
            
       end
 %結(jié)果輸出
        
        Rlength=myLength(D,R)    
        figure
        plotaiwa(a,R)%畫圖
        disp('迭代次數(shù)c');        
        disp(C);
        disp('迭代后結(jié)果'); 
        R
        Rlength=myLength(D,R)%結(jié)果輸出