TSP蚁群系统的优化

Question

我使用Dorigo的文章在Java中实现了一个用于对称TSP的蚁群系统：http://people.idsia.ch/~luca/acs-bio97.pdf

我还调整了以下战略：

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

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

为了给出更好的结果，我可以对算法进行改进吗？例如，对于TSP实例中的ch130，最优解是6110，我的算法是返回答案6223。

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

Answer 1

要改进解决方案，您可以做几件事：

1. 增加迭代次数。目前还没有出现停滞的可能性，可以找到新的解决办法。
2. 增加与可见性(启发式)函数相关的参数，以利于探索其他解决方案。

了解更多细节，请看下面的两篇论文。第一种算法将蚁群算法与遗传算法相结合，对用于配置蚁群算法的超参数进行微调。作者认为，该方法提高了蚁群算法的收敛性。第二篇论文使用一个自适应过程在运行时设置这些参数。由于作者认为这些参数是问题特有的，并且依赖于目前正在解决的问题，因此需要进行调优以提高算法的收敛时间。

1. 波蒂，霍泽法·M.和埃里克·博纳波。“进化的蚁群优化”复杂系统的进展1，第02n03 (1998)号: 149-159。
2. Stützle、Thomas、Manuel López-Ibánez、Paola Pelle格里尼、Michael Maur、Marco Montes De Oca、Mauro Birattari和Marco Dorigo。“蚁群优化中的参数自适应”“自主搜索”，第191-215页。斯普林格，柏林，海德堡，2011年。

Answer 2

我想提高性能的最直接的方法是与本地搜索方法相结合，例如2-opt、3-opt和Lin启发式。在实际应用中，结合这些局部搜索方法，一个规模不大的TSP，例如ch130，可以很容易地求解到最优解。