31个城市的TSP问题

clearclcglobaln;globalg;m=31;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解A=[13042312;36391315;41772244;37121399;34881535;33261556;32381229;41961004;4312790;4386570;30071970;25621756;27881491;23811676;1332695;37151678;39182179;40612370;37802212;36762578;40292838;42632931;34291908;35072367;33942643;34393201;29353240;31403550;25452357;27782826;23702975];%城市的坐标矩阵alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha过大时，算法迭代到一定代数后将出现停滞现象beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度rou=0.5;%0rho1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大n=31;initao=1;NCmax=100;D=zeros(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离fori=1:nforj=1:nD(i,j)=sqrt((A(i,1)-A(j,1))^2+(A(i,2)-A(j,2))^2);endendx=A(:,1);y=A(:,2);fori=1:nforj=1:nifj~=itao(i,j)=initao;yita(i,j)=1/D(i,j);endendendinitao=initao.*ones(n,n);detatao=zeros(n,n);bestsolution=1000000000000;forNC=1:NCmaxtabu=zeros(m,n);fork=1:mg(NC,k)=fix((n-1)*rand(1))+1;tabu(k,g(NC,k))=1;maxp(1)=0;forj=1:niftabu(k,j)==0psum_medium0(1,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta);elsepsum_medium0(1,j)=0;endendpsum_medium=psum_medium0.';psum(k,1)=sum(psum_medium(:,1));forj=1:niftabu(k,j)==0;p(1,j)=(tao(g(NC,k),j)^alpha).*(yita(g(NC,k),j)^beta)/psum(k,1);elsep(:,j)=0;endifmaxp(1)p(1,j);maxp(1)=p(1,j);endendLinear_index=find(maxp(1)==p(1,:));size1=[1,n];[r_index,c_index]=ind2sub(size1,Linear_index(1));solution_medium(k,1)=D(g(NC,k),c_index(1));route(k,1)=c_index(1);tabu(k,c_index(1))=1;tao(g(NC,k),c_index(1))=(1-rou)*tao(g(NC,k),c_index(1))+rou*initao(g(NC,k),c_index(1));tao(c_index(1),g(NC,k))=(1-rou)*tao(c_index(1),g(NC,k))+rou*initao(c_index(1),g(NC,k));solution(k)=solution_medium(k,1);fors=2:(n-1);c_index(s)=0;r_index(s)=0;Linear_index(s)=0;maxp(s)=0;forj=1:niftabu(k,j)==0psum_medium0(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta);elsepsum_medium0(s,j)=0;endendpsum_medium=psum_medium0.';psum(k,s)=sum(psum_medium(:,s));forj=1:niftabu(k,j)==0;p(s,j)=(tao(route(k,s-1),j)^alpha).*(yita(route(k,s-1),j)^beta)/psum(k,s);elsep(s:(n-1),j)=0;endifmaxp(s)p(s,j);maxp(s)=p(s,j);endendLinear_index=find(maxp(s)==p);size2=[n-1,n];[r_index(s),c_index(s)]=ind2sub(size2,Linear_index(1));solution_medium(k,s)=D(c_index(s-1),c_index(s));route(k,s)=c_index(s);tabu(k,c_index(s))=1;tao(c_index(s-1),c_index(s))=(1-rou)*tao(c_index(s-1),c_index(s))+rou*initao(c_index(s-1),c_index(s));tao(c_index(s),c_index(s-1))=(1-rou)*tao(c_index(s),c_index(s-1))+rou*initao(c_index(s),c_index(s-1));solution(k)=solution(k)+solution_medium(k,s);endtao(c_index(n-1),g(NC,k))=(1-rou)*tao(c_index(n-1),g(NC,k))+rou*initao(c_index(n-1),g(NC,k));tao(g(NC,k),c_index(n-1))=(1-rou)*tao(g(NC,k),c_index(n-1))+rou*initao(g(NC,k),c_index(n-1));solution_medium(k,n)=D(c_index(n-1),g(NC,k));solution(k)=solution(k)+solution_medium(k,n);solution_NC(NC,k)=solution(k);bestsolution_NC(NC)=solution_NC(NC,1);endfork=1:mifbestsolution_NC(NC)solution_NC(NC,k)bestsolution_NC(NC)=solution_NC(NC,k);endendLinear_index1=find(bestsolution_NC(NC)==solution_NC(NC,:));size3=[NC,m];[r_index1(NC),c_index1(NC)]=ind2sub(size3,Linear_index1(1));bestroute_NC(NC,:)=route(c_index1(NC),:);[aa,bb]=size(Linear_index1);fori=1:bb[r_index1_t(NC,i),c_index1_t(NC,i)]=ind2sub(size3,Linear_index1(i));detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=Q/solution(c_index1_t(NC,i));detatao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))=(1-rou)*tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1))+rou*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),1));tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))=(1-rou)*tao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)))+rou*detatao(route(c_index1_t(NC,i),1),g(NC,c_index1_t(NC,i)));detatao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=Q/solution(c_index1_t(NC,i));detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=Q/solution(c_index1_t(NC,i));tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))=(1-rou)*tao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)))+rou*detatao(route(c_index1_t(NC,i),n-1),g(NC,c_index1_t(NC,i)));tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))=(1-rou)*tao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1))+rou*detatao(g(NC,c_index1_t(NC,i)),route(c_index1_t(NC,i),n-1));fors=2:n-1detatao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))=Q/solution(c_index1_t(NC,i));detatao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))=Q/solution(c_index1_t(NC,i));tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i),s-1))=(1-rou)*tao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i)),s-1)+rou.*detatao(route(c_index1_t(NC,i),s),route(c_index1_t(NC,i)),s-1);tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i),s))=(1-rou)*tao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i)),s)+rou.*detatao(route(c_index1_t(NC,i),s-1),route(c_index1_t(NC,i)),s);endendifbestsolutionbestsolution_NC(NC)bestsolution=bestsolution_NC(NC);endLinear_index2=find(bestsolution==bestsolution_NC);size4=[1,NC];