TSP基于matlab差分进化算法求解旅行商问题【含Matlab源码 131期】.zip

close all clear clc %edit % 2021-3-15 city=[1304,2312;3639,1315;4177,2244;3712,1399;3488,1535;3326,1556;... 3238,1229;4196,1004;4312,790;4386,570;3007,1970;2562,1756;2788,1491;... 2381,1676;1332,695;3715,1678;3918,2179;4061,2370;3780,2212;3676,2578;4029,2838;... 4263,2931;3429,1908;3507,2367;3394,3201;3439,3201;2935,3240;3140,3550;2545,2357;2778,2826;2370,2975]; city_num=size(city,1); %计算两两城市之间的距离 for i=1:city_num for j=1:city_num distance(i,j)=sqrt((city(i,1)-city(j,1))^2 + (city(i,2)-city(j,2))^2); end end %相比于其他算法，迭代次数略长 NP=20; NG=2000; F=0.6; CR=0.5; pop=zeros(NP,city_num); x_old=zeros(NP,city_num); x_new=zeros(NP,city_num); pi_old=zeros(NP,city_num); pi_new=zeros(NP,city_num); for i=1:NP for j=1:city_num pop(i,j)=5*rand(); end end k=1; x_old=pop; while k<=NG %将实数编码转换成工件顺序编码 for i=1:NP x_old_decode(i,:)=LOVdecode(x_old(i,:)); end %----find the best value--------------% ind_best = x_old(1,:); for i=2:NP pi_best=LOVdecode(ind_best); if CalLength(distance,pi_best)>CalLength(distance,x_old_decode(i,:)) ind_best = x_old(i,:); end end BestFit=CalLength(distance , LOVdecode(ind_best));%最短时间 Best=LOVdecode(ind_best);%最佳路径 %%--------mutaiton---------------------% for i=1:NP R=randperm(NP); r1=R(1); r2=R(2); r3=R(3); if i==r1 r1=R(4); else if i==r2 r2=R(4); else if i==r3 r3=R(4); end end end for j=1:city_num x_new(i,j) = x_old(r1,j) + F *(x_old(r2,j) - x_old(r3,j)); % if ( x_new(i,j)<xmin) || ( x_new(i,j)>xmax) % x_new(i,j) = x_old(i,j); % end end end %----------crossover----------------% % j=randperm(n); % jrand=j(1); for i=1:NP for j=1:city_num if (rand()<= CR) x_new(i,j)=x_new(i,j); else x_new(i,j)=x_old(i,j); end end end %--------selection------------% for i=1:NP pi_new(i,:)=LOVdecode(x_new(i,:)); %pi_old(i,:)=LOVdecode(x_old(i,:)); if CalLength(distance,pi_new(i,:)) > CalLength(distance, x_old_decode(i,:)) x_new(i,:) = x_old(i,:); else x_old(i,:)=x_old(i,:); end end x_old = x_new; k=k+1; end BSF=Best; BestL=BestFit; %绘制路径图 for i=1:city_num-1 plot([city(BSF(i),1),city(BSF(i+1),1)],[city(BSF(i),2),city(BSF(i+1),2)],'bo-'); hold on; end plot([city(BSF(city_num),1),city(BSF(1),1)],[city(BSF(city_num),2),city(BSF(1),2)],'ro-'); title('差分进化TSP') disp('最佳路径'); disp(BSF); disp('最短路径长度'); disp(BestL)