mainga9.m

多个城市间最短距离算法~希望对大家有借鉴作用~

%遗传算法求解TSP程序
clear;
time1 = clock;          %观察时间
%设置输入参数
popsize = 200;          %群体规模,为偶数
Lchrom = 144;           %染色体长度，这里即为城市个数
probcross = 0.9;        %交叉概率
probmuta = 0.001;       %变异概率

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%取得城市坐标
temp = load('D:\作业和实验\遗传算法\Homeworks\tsp144.txt','r');
xPos = temp(1:144,1)';
yPos = temp(1:144,2)';
plot(xPos,yPos,'o');axis([0 80 0 90]);          %画出输入点
grid on;xlabel('x');ylabel('y');title('城市坐标');

%随机选取一组初始群体
for j=1:popsize
    startPop(j,1:Lchrom) = randperm(Lchrom);   %随机排序,以n城市的遍历次序作为算法的编码
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

done = 0;
gen = 0;
while(~done)
%计算适应度,适应度函数取路径长度Td的倒数,若结合TSP的约束条件(每个城市经过且只经过一次),则适应度函数可
%表示为:f=1/(Td+k*Nt),其中Nt是对TSP路径不合法的度量,k为惩罚系数.本实验只采用f=1/Td.
for i=1:popsize
    fittemp1(i) = 0;
    for j=1:Lchrom-1
        fittemp1(i) = fittemp1(i) + (xPos(startPop(i,j+1))-xPos(startPop(i,j)))^2 + (yPos(startPop(i,j+1))-yPos(startPop(i,j)))^2;  %两城市距离
    end
    fittemp2(i) = (xPos(startPop(i,Lchrom))-xPos(startPop(i,1)))^2 + (yPos(startPop(i,Lchrom))-yPos(startPop(i,1)))^2;
    T = sqrt(fittemp1(i) + fittemp2(i));
    singlefit(i) = 1/T;                           %单个个体适应度
end   %适应度结束
totalfit = sum(singlefit);                        %总体适应度

plot(gen,max(singlefit),'r*');
hold on;
drawnow;

%赌轮方法选择select
prob=cumsum(singlefit/totalfit);
rNums=sort(rand(popsize,1)); 		%Generate random numbers
fitIn=1;newIn=1;
while newIn<=popsize
    if(rNums(newIn)<prob(fitIn))
        endPop(newIn,:) = startPop(fitIn,:);
        newIn = newIn+1;
    else
        fitIn = fitIn + 1;
   end
end  %选择结束

%交叉，类似于OX交叉方式
for i1=1:popsize/2 
     ac = round(rand.*popsize + 0.5); 	     %产生1到popsize的随机数
     bc = round(rand.*popsize + 0.5); 	
     p1 = endPop(ac,:);                      %选择两个父代
     p2 = endPop(bc,:);   
     
     while(p1==p2)                           %保证每次用两个不同的父代进行交叉
         ac = round(rand.*popsize + 0.5); 	 %产生1到popsize的随机数
         bc = round(rand.*popsize + 0.5); 	
         p1 = endPop(ac,:);     
         p2 = endPop(bc,:);    
     end
        
     %用交叉概率判断是否要进行交叉操作
     probtemp = rand;
     if(probcross<probtemp)    %如果交叉概率小于随机概率不进行交叉
         child1 = p1;
         child2 = p2;
     else                      %否则进行交叉
        pos1 = round(rand.*Lchrom + 0.5);  %产生交叉点pos1,pos2，交叉点从1到Lchrom
        pos2 = round(rand.*Lchrom + 0.5);
        pos1 = min(pos1,pos2);
        pos2 = max(pos1,pos2);
        cutlength = pos2 - pos1 + 1;
                
        %产生子代     
        childtemp1 = [p2(pos1:pos2) p1]; 
        childtemp2 = [p1(pos1:pos2) p2];
        for i=(cutlength+1):(Lchrom+cutlength)         %将子代1相同的城市码删除
            for j=1:cutlength
                if(childtemp1(i)==childtemp1(j))
                    childtemp1(i) = 0;
                end
            
            end
       end
        
       for i=(cutlength+1):(Lchrom+cutlength)         %将子代2相同的城市码删除
           for j=1:cutlength
               if(childtemp2(i)==childtemp2(j))
                   childtemp2(i) = 0;
               end
           end
       end        
    end
    
    k=1;
    for i=1:(cutlength+Lchrom) 
        if(childtemp1(i)>0)
            childtemp11(k) = childtemp1(i);
            k=k+1;
        end
    end
    k=1;
    for i=1:(Lchrom+cutlength) 
        if(childtemp2(i)>0)
            childtemp22(k) = childtemp2(i);
            k=k+1;
        end
    end
        endPop(ac,:) = childtemp11(1:Lchrom); 
        endPop(bc,:) = childtemp22(1:Lchrom);
 end  %交叉结束

   %1，交换变异
  for i = 1:popsize
      am = round(rand.*popsize + 0.5);     %选择一个父代
      cm = endPop(am,:);
      probtemp = rand;
      if(probmuta<probtemp)                %不进行变异
         cm = cm;
      else                                 %否则进行变异
        %换位
        ivePos1 = round(rand.*Lchrom + 0.5);
        ivePos2 = round(rand.*Lchrom + 0.5);
        mutatemp1 = cm(ivePos1);
        cm(ivePos1) = cm(ivePos2);
        cm(ivePos2) = mutatemp1;
      end
        endPop(am,:) = cm;
 end   %交换变异结束

 %2:逆转变异
  for i = 1:popsize
      %am = round(rand.*popsize + 0.5); 	%Pick a parent
      cm = endPop(i,:);
      %计算父代适应度
        cmfittemp1 = 0;
        for j=1:Lchrom-1
            cmfittemp1 = cmfittemp1 + (xPos(cm(j+1))-xPos(cm(j)))^2 + (yPos(cm(j+1))-yPos(cm(j)))^2;  %两城市距离
        end
        cmfittemp2 = (xPos(cm(Lchrom))-xPos(cm(1)))^2 + (yPos(cm(Lchrom))-yPos(cm(1)))^2;
        T = sqrt(cmfittemp1 + cmfittemp2);
        cmFatherfit = 1/T;                           
        %逆转
    for q=1:40
        ivePos1 = round(rand.*Lchrom + 0.5);
        ivePos2 = round(rand.*Lchrom + 0.5);
        maxinvese = max(ivePos1,ivePos2);
        mininvese = min(ivePos1,ivePos2);
        cm(mininvese:maxinvese) = cm(maxinvese:-1:mininvese);
        %计算逆转后cm适应度
        cmfittemp1 = 0;
        for j=1:Lchrom-1
            cmfittemp1 = cmfittemp1 + (xPos(cm(j+1))-xPos(cm(j)))^2 + (yPos(cm(j+1))-yPos(cm(j)))^2;  %两城市距离
        end
        cmfittemp2 = (xPos(cm(Lchrom))-xPos(cm(1)))^2 + (yPos(cm(Lchrom))-yPos(cm(1)))^2;
        T = sqrt(cmfittemp1 + cmfittemp2);
        cmSonfit = 1/T;                           %单个个体适应度
        
        if(cmSonfit>cmFatherfit)                  %在逆转变异中引入局部搜索
            endPop(i,:) = cm;
            cmFatherfit = cmSonfit;
        else
            cm = endPop(i,:);
        end
     end
 end   %逆转变异结束 
 
 %计算适应度，若子代的个体的最高适应度大于父代个体的最高适应度，则用子代代替父代
  for i=1:popsize
    fittemp1(i) = 0;
    for j=1:Lchrom-1
        fittemp1(i) = fittemp1(i) + (xPos(endPop(i,j+1))-xPos(endPop(i,j)))^2 + (yPos(endPop(i,j+1))-yPos(endPop(i,j)))^2;  %两城市距离
    end
    fittemp2(i) = (xPos(endPop(i,Lchrom))-xPos(endPop(i,1)))^2 + (yPos(endPop(i,Lchrom))-yPos(endPop(i,1)))^2;
    T = sqrt(fittemp1(i) + fittemp2(i));
    newsinglefit(i) = 1/T;                           %单个个体适应度
 end  
newtotalfit = sum(newsinglefit);                     %总体适应度

if(max(newsinglefit) > max(singlefit))
    maxsinglefit = max(singlefit);
    startPop1 = startPop;
    for p=1:1%popsize*0.05
        [bestfather,position] = max(singlefit);                %最佳保留策略，取出父代个体中适应度最高的个体，直接代替子代中适应度最低的个体
        [worstson,position1] = min(newsinglefit);
        endPop(position1,:) = startPop1(position,:);
        singlefit(position) = 0;
        startPop1(position,:) = 0;
    end
    startPop = endPop;
else
    startPop = startPop;
end
    
  gen = gen + 1;
  if(gen>2500)
      done = 1;
  end
 
end  %主循环结束

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%计算适应度
for i=1:popsize
    fittemp1(i) = 0;
    for j=1:Lchrom-1
        fittemp1(i) = fittemp1(i) + (xPos(startPop(i,j+1))-xPos(startPop(i,j)))^2 + (yPos(startPop(i,j+1))-yPos(startPop(i,j)))^2;  %两城市距离
    end
    fittemp2(i) = (xPos(startPop(i,Lchrom))-xPos(startPop(i,1)))^2 + (yPos(startPop(i,Lchrom))-yPos(startPop(i,1)))^2;
    T = sqrt(fittemp1(i) + fittemp2(i));
    singlefit(i) = 1/T;                           %单个个体适应度
end   
totalfit = sum(singlefit);                        %总体适应度

plot(gen,max(singlefit),'r*');
xlabel('经过代数');ylabel('个体最高适应度');
drawnow;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%用line()函数画线
[best,position] = max(singlefit);
plot(gen,best,'b*');
figure;
    for j=1:Lchrom-1
        x1 = [xPos(startPop(position,j)) xPos(startPop(position,j+1))];
        x2 = [yPos(startPop(position,j)) yPos(startPop(position,j+1))];
        line(x1,x2);
    end
x1 = [xPos(startPop(position,Lchrom)) xPos(startPop(position,1))];
x2 = [yPos(startPop(position,Lchrom)) yPos(startPop(position,1))];
line(x1,x2);
hold on;
plot(xPos,yPos,'o');         %画出城市位置坐标
title('144个城市最优路径');
time2 = clock;
alltime = (time2 - time1);