优化TSP的蚁群系统

Question

我使用Dorigo的论文从以下链接实现了Java中对称TSP的蚁群系统：http://people.idsia.ch/~luca/acs-bio97.pdf

我还采用了以下策略：

1.虽然并非所有蚂蚁都构建了一个解决方案，但每个蚂蚁都会向一个新城市移动一步并使用Dorigo的本地信息素更新更新使用边缘的信息素。

2. 产生最短路径的蚂蚁在使用Dorigo全局更新公式时使用的边缘上更新信息素
3. 经过多次迭代后，返回在所有迭代中找到的最短路径

有没有办法可以改进算法以获得更好的结果？对于在TSPLIB中找到的TSP实例ch130的示例，最优解是6110并且我的算法返回答案6223。

到目前为止，我的ACS的参数设置为Dorigo论文中定义的参数

Answer 1

您可以采取一些措施来改善解决方案：

1. 增加迭代次数。有可能没有停滞，可以实现新的解决方案。
2. 增加与可见性（启发式）功能相关的参数，以支持其他解决方案的探索。

有关更多详细信息，请查看以下两篇论文。第一个将ACO与遗传算法相结合，以微调用于配置ACO的超参数。作者得出结论，该方法改善了ACO的收敛性。第二篇论文使用自适应过程在运行时设置这些参数。由于作者声称这些参数是特定于问题的并且取决于当前正在解决的问题，因此需要执行调整以改善算法的收敛时间。

1. Botee，Hozefa M.和Eric Bonabeau。 “不断发展的蚁群优化。”复杂系统的进展1，没有。 02n03（1998）：149-159。
2. Stützle，Thomas，ManuelLópez-Ibánez，Paola Pellegrini，Michael Maur，Marco Montes De Oca，Mauro Birattari和Marco Dorigo。 “蚁群优化中的参数自适应。”在自主搜索中，第191-215页。施普林格，柏林，海德堡，2011年。

Answer 2

我想改进性能的最直接的方法是与本地搜索方法集成，例如， 2-opt，3-opt和Lin-Ker启发式。在实践中，通过整合这些本地搜索方法，不是很大规模的TSP，例如ch130可以很容易地解决问题。