蚁群算法TSP问题工具箱

function [Route_Best,Length_Best,Length_Average,Shortest_Route,Shortest_Length,Time]=ACMTSP(City,Loop_Max,Ant_Count,Alpha,Beta,Volatile,Q) %%根据城市的坐标运行，使用蚁群算法求解最优化问题，并最后绘制运行结果的图形。 %%使用说明：[Route_Best,Length_Best,Length_Average,Shortest_Route,Shortest_Length]=ACMTSP(City,Loop_Max,Ant_Count,Alpha,Beta,Volatile,Q) %% 主要符号说明 %%City_Count:城市的个数. %% City:City_Count个城市的坐标，City_Count×2的矩阵. %% Loop_Max:最大循环次数，即迭代的次数 %% Ant_Count:蚂蚁个数 %% Alpha:表征信息素重要程度的参数 %% Beta:表征启发因子(期望)重要程度的参数 %% Volatile：信息素挥发系数 %% Q：信息素强度的系数，一般是一个常量 %% Route_Best：代表最佳路线 %% Length_Best：代最佳路线的长度 %%Length_Average:代表平均路径长度 %%Shortest_Route：表示找到的最短的路径，其中包含城市节点序列 %%Shortest_Length：表示最短路径的长度 %%Time：程序运行时间，不包括绘图时间. %%========================================================================= %第一步：变量初始化 City_Count=size(City,1);%City_Count表示问题的规模（城市个数） D=zeros(City_Count,City_Count);%D表示完全图的赋权邻接矩阵 for i=1:City_Count for j=1:City_Count if i~=j D(i,j)=((City(i,1)-City(j,1))^2+(City(i,2)-City(j,2))^2)^0.5; else D(i,j)=eps; %i=j时不计算，应该为0，但后面的启发因子要取倒数，用eps（浮点相对精度）表示 end D(j,i)=D(i,j); %对称矩阵 end end %D表示城市之间的距离，D（i，j）表示第i个城市距离第j个城市之间的距离. %D这个矩阵应该是对称的。 Expectation=1./D;%Eta为启发因子，这里设为距离的倒数 T_Pheromone=ones(City_Count,City_Count); %T_Pheromone为信息素矩阵 T_Ant_Passed=zeros(Ant_Count,City_Count); %存储并记录每个蚂蚁经过的路径 NC=1; %迭代计数器，记录迭代次数 Route_Best=zeros(Loop_Max,City_Count);%每代找到的最佳路线 Length_Best=inf.*ones(Loop_Max,1); %每代最佳路线的长度 Length_Average=zeros(Loop_Max,1); %每代路线的平均长度 tic while NC<=Loop_Max %停止条件之一：达到最大迭代次数，停止 %%第二步：将m只蚂蚁放到n个城市上 Rand_Position=[]; %随即存取 for i=1:(ceil(Ant_Count/City_Count)) Rand_Position=[Rand_Position,randperm(City_Count)]; end T_Ant_Passed(:,1)=(Rand_Position(1,1:Ant_Count))'; %将蚂蚁放在城市上，并记录蚂蚁访问过的城市的编号 %%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游 for j=2:City_Count %所在城市不计算 for i=1:Ant_Count visited=T_Ant_Passed(i,1:(j-1)); %记录已访问的城市，避免重复访问 No_Visited_City=zeros(1,(City_Count-j+1)); %待访问的城市 P=No_Visited_City; %待访问城市的选择概率分布 No_V_C_Count=1; for k=1:City_Count if isempty(find(visited==k, 1)) %开始时置0 No_Visited_City(No_V_C_Count)=k; No_V_C_Count=No_V_C_Count+1; %访问的城市个数自加1 end end %下面计算待选城市的概率分布 for k=1:length(No_Visited_City) P(k)=(T_Pheromone(visited(end),No_Visited_City(k))^Alpha)*(Expectation(visited(end),No_Visited_City(k))^Beta); end P=P/(sum(P)); %按概率原则选取下一个城市 Pcum=cumsum(P); %cumsum，元素累加即求和 Select=find(Pcum>=rand); %若计算的概率大于原来的就选择这条路线 %------------------------- %Select=find(P>=rand); %若计算的概率大于原来的就选择这条路线 %while(isempty(Select)) % Select=find(P>=rand); %end %------------------------- to_visit=No_Visited_City(Select(1)); T_Ant_Passed(i,j)=to_visit; end end if NC>=2 T_Ant_Passed(1,:)=Route_Best(NC-1,:); end %%第四步：记录本次迭代最佳路线 L=zeros(Ant_Count,1); %开始距离为0，Ant_Count*1的列向量 for i=1:Ant_Count R=T_Ant_Passed(i,:); for j=1:(City_Count-1) L(i)=L(i)+D(R(j),R(j+1)); %原距离加上第j个城市到第j+1个城市的距离 end L(i)=L(i)+D(R(1),R(City_Count)); %一轮下来后走过的距离 end Length_Best(NC)=min(L);%最佳距离取最小 pos=find(L==Length_Best(NC)); Route_Best(NC,:)=T_Ant_Passed(pos(1),:); %此轮迭代后的最佳路线 Length_Average(NC)=mean(L); %此轮迭代后的平均距离 NC=NC+1; %迭代继续 %%第五步：更新信息素 Delta_Tau=zeros(City_Count,City_Count); %开始时信息素为City_Count*City_Count的0矩阵,Delta_Tau表示信息数的增量即为：Δau for i=1:Ant_Count for j=1:(City_Count-1) Delta_Tau(T_Ant_Passed(i,j),T_Ant_Passed(i,j+1))=Delta_Tau(T_Ant_Passed(i,j),T_Ant_Passed(i,j+1))+Q/L(i); %此次循环在路径（i，j）上的信息素增量 end Delta_Tau(T_Ant_Passed(i,City_Count),T_Ant_Passed(i,1))=Delta_Tau(T_Ant_Passed(i,City_Count),T_Ant_Passed(i,1))+Q/L(i); %此次循环在整个路径上的信息素增量 end T_Pheromone=(1-Volatile).*T_Pheromone+Delta_Tau; %考虑信息素挥发，更新后的信息素 %%第六步：禁忌表清零 T_Ant_Passed=zeros(Ant_Count,City_Count); %%直到最大迭代次数 end Time=toc; %%第七步：输出结果 Pos=find(Length_Best==min(Length_Best)); %找到最佳路径（非0为真） Shortest_Route=Route_Best(Pos(1),:); %最大迭代次数后最佳路径 Shortest_Length=Length_Best(Pos(1)); %最大迭代次数后最短距离 figure; subplot(1,2,1) %绘制第一个子图形 DrawRoute(City,Shortest_Route) %画路线图的子函数 subplot(1,2,2) %绘制第二个子图形 plot(Length_Best) hold on grid on %保持图形 plot(Length_Average,'r') legend('最短距离','平均距离') title('平均距离和最短距离') %标题 function DrawRoute(City,R) %%========================================================================= %% DrawRoute.Ant_Count %% 画路线图的子函数 %%------------------------------------------------------------------------- %% City Coordinate 节点坐标，由一个N×2的矩阵存储 %% R Route 路线 %%========================================================================= N=length(R); M=size(City,1); scatter(City(:,1),City(:,2)); hold on for i=1:M text(City(i,1)+0.2,City(i,2)+0.2,num2str(i)); end Begin=R(1); text(City(Begin,1)+0.5,City(Begin,2)+0.5,'起点') arrowplot([City(R(N),1),City(R(N),2)],[City(R(1),1),City(R(1),2)],'g'); grid on for ii=2:N arrowplot([City(R(ii-1),1),City(R(ii-1),2)],[City(R(ii),1),City(R(ii),2)],'g'); end title('旅行商问题优化结果 ') function arrowplot(P,V,color) % 二维空间中画箭头 % 输入：P=[x0,y0],V=[x1,y1] % 将以P（x0，y0）为起点，以V（x1，y1）为终点画出箭头 % color为颜色，如‘r’ %可以进一步修改为三维空间到箭头 if nargin<3 color='r'; end x0 = P(1);y0 = P(2); a = V(1)-P(1); b = V(2)-P(2); axis on; quiver(x0,y0,a,b,color);