蚁群算法求解TSP问题

1、广东工业大学课 程 作 业课程题目 基于ACO算法求解城市tsp 学生姓名 朱美霞学生学号 2111405091专业班级 计算机技术2015 年2月 15日1. AOC算法的数学模型（1）、基本参数、信息素浓度公式、择路概率设蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为dij，t时刻城市i与城市j之间的信息素浓度为tij(t)，初始时刻，各个城市间连接路径上的信息素浓度相同，不妨记为tij(0)=t0。蚂蚁k(k=1,2,.,m)根据各城市间连接路径上的信息素浓度，决定其下一个要访问的城市，设Pijk(t)表示t时刻，蚂蚁k从城市i到城市j的概率，其计算公式为如下：其中：hij(

2、t)为启发式函数，hij(t)=1/dij，表示蚂蚁从城市i转移到城市j的期望程序；allowk(k=1,2,m)表示蚂蚁k待访问的城市的集合，开始时allowk为其他n-1城市，随着时间推进，其中的元素不断减少，直至为空，表示所有城市访问完，即遍历所有城市。a为信息素的重要程度因子，其值越大，转移中起的作用越大b为启发函数的重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁以较大的概率转移到距离短的城市。蚂蚁释放的信息素会随时间的推进而减少，设参数r(0<r<1)表示信息素的挥发度，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度，需要实时更新。tij(t+

3、1)=(1-r)tij(t)+Dtij，Dtij=其中：Dtijk表示蚂蚁k在城市i与城市j的连接路径上，释放的信息素浓度Dtij表示所有蚂蚁在城市i与城市j的连接路径上，释放的信息素浓度。（2）、Dtijk的计算方法Dtijk=其中：Q为常数，表示蚂蚁循环一次释放的信息素的总量；dij为第k只蚂蚁经过路径的长度，Length；4. 相关程序1、访问每个城市一次也仅一次的最短路径，共有30个2、城市的坐标citys，这是直角坐标，根据二个城市的坐标值，可以用D=可计算出任意二个城市间的距离。citys = 1304 2312 3639 1315 4177 2244 3712 1399 3488

4、 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 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 28263、代码clear allclcload citys_data.mat% 计算城市间相互距离n

5、= size(citys,1); %城市的个数D = zeros(n,n); %n行n列的矩阵，即任意二个城市之间的距离for i = 1:n for j = 1:n if i = j D(i,j) = sqrt(sum(citys(i,:) - citys(j,:).2); else D(i,j) = 1e-4; end end end% 初始化参数m = 50; % 蚂蚁数量alpha = 1; % 信息素重要程度因子beta = 5; % 启发函数重要程度因子rho = 0.1; % 信息素挥发因子Q = 1; % 常系数Eta = 1./D; % 启发函数Tau = ones(n,n)

6、; % 信息素矩阵,全1矩阵Table = zeros(m,n); % 路径记录表，全0矩阵，每只蚂蚁依次走过的城市iter = 1; % 迭代次数初值iter_max = 200; % 最大迭代次数 Route_best = zeros(iter_max,n); % 各代最佳路径 Length_best = zeros(iter_max,1); % 各代最佳路径的长度 Length_ave = zeros(iter_max,1); % 各代路径的平均长度 % 迭代寻找最佳路径while iter <= iter_max % 随机产生各个蚂蚁的起点城市 start = zeros(m,1

7、); %m是蚂蚁的个数,m行1列的矩阵，记录每个蚂蚁的城市编号 for i = 1:m temp = randperm(n); start(i) = temp(1); end Table(:,1) = start; %路径记录表的1列，为每个蚂蚁的起点城市 % 构建解空间 citys_index = 1:n; % 逐个蚂蚁路径选择 for i = 1:m % 逐个城市路径选择 for j = 2:n tabu = Table(i,1:(j - 1); % 已访问的城市集合(禁忌表) allow_index = ismember(citys_index,tabu);%不是tabu的城市就是要访问

8、的城市 allow = citys_index(allow_index); % 待访问的城市集合 P = allow; for k = 1:length(allow) % 计算城市间转移概率 P(k) = Tau(tabu(end),allow(k)alpha * Eta(tabu(end),allow(k)beta; end P = P/sum(P);%规一化 % 轮盘赌法选择下一个访问城市 Pc = cumsum(P);%依次累加，是实现轮盘赌法选择的方法 target_index = find(Pc >= rand); target = allow(target_index(1);

9、 Table(i,j) = target; end end% 结果显示Shortest_Length,index = min(Length_best);Shortest_Route = Route_best(index,:);disp('最短距离:' num2str(Shortest_Length);disp('最短路径:' num2str(Shortest_Route Shortest_Route(1);% 绘图figure(1)plot(citys(Shortest_Route,1);citys(Shortest_Route(1),1),. citys(Sh

10、ortest_Route,2);citys(Shortest_Route(1),2),'o-');grid onfor i = 1:size(citys,1) text(citys(i,1),citys(i,2),' ' num2str(i);endtext(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点');text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点');xlabel(

11、'城市位置横坐标')ylabel('城市位置纵坐标')title('蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')')figure(2)plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:')legend('最短距离','平均距离')xlabel('迭代次数')ylabel('距离')title('各代最短距离与平均距离对比&#

12、39;)end5.结果与分析使用不同的蚁群数量和迭代次数后求得的最短距离和最短路径如下所示：1. 蚁群数50，迭代次数200最短距离:15601.9195最短路径:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 14 2. 蚁群数50，迭代次数100 最短距离:15972.7648最短路径:1 15 13 12 14 29 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 13. 蚁群数100

13、，迭代次数100最短距离:15601.9195最短路径:14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 144. 蚁群数50，迭代次数300最短距离:15601.9195最短路径:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 15. 蚁群数100，迭代次数200最短距离:15601.9195最短路径:14 12 13 11 23 16 5 6 7 2 4

14、8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 15 146. 蚁群数100，迭代次数300最短距离:15553.0468最短路径:10 9 8 4 2 5 6 7 13 12 14 15 1 29 31 30 27 28 26 21 22 18 3 17 19 24 20 25 11 23 16 107. 蚁群数150，迭代次数300最短距离:15601.9195最短路径:1 15 14 12 13 11 23 16 5 6 7 2 4 8 9 10 3 18 17 19 24 25 20 21 22 26 28 27 30 31 29 1 从以上的实验结果可看出，蚁群数量和迭代次数对算法的实验结果有一定影响，当蚁群数确定时，随着迭代次数的增加，最短距离会有所减小，但增加到一定的程度，最短距离将不再变化；当迭代次数不变，随着蚁群数