1

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

我还调整了以下策略：

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

  1. 产生最短路径的蚂蚁使用 Dorigo 的全局更新公式全局更新所使用边缘上的信息素

  2. 多次迭代后，返回所有迭代中找到的最短路径

有没有办法改进算法以获得更好的结果？例如，在 TSPLIB 中找到的 TSP 实例 ch130 的最佳解决方案是 6110，而我的算法返回答案 6223。

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

4

2 回答 2

1

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

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

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

  1. Botee、Hozefa M. 和 Eric Bonabeau。“进化中的蚁群优化。” 复杂系统的进展 1，没有。02n03 (1998): 149-159。
  2. Stützle、Thomas、Manuel López-Ibánez、Paola Pellegrini、Michael Maur、Marco Montes De Oca、Mauro Birattari 和 Marco Dorigo。“蚁群优化中的参数适应”。在自主搜索中，第 191-215 页。施普林格，柏林，海德堡，2011。
于 2018-03-30T13:33:29.493 回答
1

我想提高性能最直接的方法是与本地搜索方法集成，例如 2-opt、3-opt 和 Lin-Ker 启发式。在实践中，通过这些局部搜索方法的集成，一个不是很大的TSP，例如ch130，可以很容易地求解到最优。

于 2019-03-27T07:54:56.590 回答