3

我开发了蚁群算法。目前它工作得很好。

在一些有争议的问题上，它可能显示的不是最佳路径，而是接近最佳路径。

例如，我有这个图表：

在此处输入图像描述

矩阵是：

    1   2   3   4   5   6   7
1   0   6   5   0   0   2   0
2   6   0   3   2   1   5   0
3   5   3   0   2   5   0   0
4   0   2   2   0   3   0   0
5   0   1   5   3   0   6   0
6   2   5   0   0   6   0   2
7   0   0   0   0   0   2   0

第一列和第一行是顶点名称。

所以可能的路径是（路径 - 路径的长度）：

1. 1-2-5 with length 7
2. 1-6-2-5 with length 8
3. 1-6-5 with length 8

我的程序在 1/10 开始时选择第一条路径，在 7/10 开始时选择第二条路径，在 2/10 开始时选择第三条路径。

它工作正常吗？

对此的解释是蚂蚁有自己的眼睛（视觉，他们看边缘长度），他们也可以检测信息素水平。亲眼所见，1-2边比1-6边长，比1-6边长，所以一般他们会选择1-6边而不是1-2边。6-5 和 6-2 相同：6-2 更有吸引力，因为它更短。

我的假设是否正确？

4

3 回答 3

2

在蚁群优化算法中，蚂蚁在遍历图形时对每个可能的步骤都有概率。通常，此概率基于两​​个因素：本地和全局质量度量。

全局度量通常与边缘中的信息素沉积相关联，因为信息素被添加到蚂蚁所遵循的路径中使用的每个边缘，并且添加的量在某种程度上与这种蚂蚁创建的解决方案的质量有关。

本地度量通常与特定步骤的质量有关：在提供的示例中，边缘的成本。

因此，如果您的蚂蚁只采取贪婪的行动，那么您使用的概率函数可能过于重视局部质量。找到一个在局部和全局搜索之间表现出良好折衷的概率函数是成功应用 ACO 策略的一个基本方面。

于 2014-05-28T14:15:19.187 回答
2

根据这个：http ://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms#Summary ，我可以在你的方法中看到2个问题：

  1. 蚂蚁（最初）随机游荡；它与视觉或相邻边长无关
  2. 你对那些信息素轨迹进行建模吗？

回答问题：蚁群算法是否应该在 100% 的情况下显示最佳路径？不，它根本不需要显示最佳路径。

于 2014-05-27T22:08:57.260 回答
0

你为什么用蚁群做最短路径？如果您正在搜索不需要优化算法的最短路径，则可以使用 A* 算法（具有最佳启发式函数）的多项式时间来实现最佳解决方案。当您将蚁群用于 TSP 问题时，它会更好。

答案是：不 - 请记住，算法是概率性的，因此它可能不会导致最佳解决方案，而是会导致局部最小值

于 2014-05-29T09:07:16.760 回答