遗传，模拟退火，蚁群三个算法求解TSP的对比 - 图文(5)

Table(i,j) = target; end end

% 计算各个蚂蚁的路径距离 Length = zeros(m,1); for i = 1:m

Route = Table(i,:); for j = 1:(n - 1)

Length(i) = Length(i) + D(Route(j),Route(j + 1)); end

Length(i) = Length(i) + D(Route(n),Route(1)); end

% 计算最短路径距离及平均距离 if iter == 1

[min_Length,min_index] = min(Length); Length_best(iter) = min_Length; Length_ave(iter) = mean(Length);

Route_best(iter,:) = Table(min_index,:); else

[min_Length,min_index] = min(Length);

Length_best(iter) = min(Length_best(iter - 1),min_Length); Length_ave(iter) = mean(Length); if Length_best(iter) == min_Length

Route_best(iter,:) = Table(min_index,:); else

Route_best(iter,:) = Route_best((iter-1),:); end end

% 更新信息素

Delta_Tau = zeros(n,n); % 逐个蚂蚁计算 for i = 1:m

% 逐个城市计算 for j = 1:(n - 1)

Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) Q/Length(i); end

Delta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i); end

Tau = (1-rho) * Tau + Delta_Tau; % 迭代次数加1，清空路径记录表 iter = iter + 1;

Table = zeros(m,n); 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(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on

for i = 1:size(citys,1)

text(citys(i,1),citys(i,2),[' ' num2str(i)]); end

text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起点'); text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 终点'); xlabel('城市位置横坐标') ylabel('城市位置纵坐标')

title(['蚁群算法优化路径(最短距离:' num2str(Shortest_Length) ')']) figure(2)

plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距离','平均距离') xlabel('迭代次数') ylabel('距离')

title('各代最短距离与平均距离对比')

程序运行结果（蚁群数:50,迭代数200）：

各代最短距离与平均距离：

结论分析：

根据上面算法得出的结论可知：

遗传算法在本例中得出的最短距离为：15426.5219 模拟退火在本例中得出的最短距离为：1.5371e+004 蚁群算法在本例中得出的最短距离为：15601.0734

由此可见模拟退火在本例中最优，遗传算法次之。但是根据最后的结果也可以看出三个算法求解的结果相差不大。

参考文献：

[1]",张",挺.遗传算法在旅行商及网络优化问题中的研究与应用[D].太原:太原理工大学,2008

[2]????.一种改进的遗传算法及其在求解旅行商问题中的应用[J].电脑开发与应用,2008,7(22):35-36.

[3]????,倪志伟,刘慧婷.求解旅行商问题的一个改进的遗传算法[J].计算机工程与应用,2007,6(43):65-68.

[4]苗卉,杨韬.旅行商问题(TSP)的改进模拟退火算法.微计算机信息(管控一体化),2007,23(11):241

[5]吴小菁. 求解旅行商问题的模拟进化算法.福建金融管理干部学院学报,2008,(5):55-56,57.

[6]万军洲.基于模拟退火技术的旅行商问题求解算法.软件导刊,2006,(8):88,88-89.

[7]曲强，陈雪波.基于MATLAB的模拟退火算法的实现.鞍山科技大学学报,2003,26(3):197-198

[8]马良,朱刚,宁爱兵著,蚁群优化算法；2008

[9]李士勇.蚁群算法及其应用[M].哈尔滨：哈尔滨工业大学出版社，2004

[10]周康，强小利，同小军等.求解TSP算法[J].计算机工程与应用，2007，43（29）：43-47.