问题标签 [ant-colony]

我正在尝试使用蚁群优化算法解决旅行商问题。我已经附上了我的代码。这对于所有测试用例（我已经测试过的测试用例）现在都可以正常工作并给出正确的答案。但我仍然不满足于此。这是因为：

1. 虽然我更改了 alpha、beta 值，但它根本不会影响解决方案。
2. 虽然我将 MAX_Ants 保持为 1，但它也找到了相同的解决方案。
3. 我认为它只是找到最近的邻居，没有别的，因此需要任何其他东西:(。

这是我的代码：

我想知道我对 ACO 的理解或实施技术是否错误。这段代码如何找到只有一只蚂蚁的解决方案。我哪里错了？或者我在哪里可以纠正一些东西并改进这个算法？

我的猜测是问题在于生成下一个城市和更新信息素表的技术！

在蚁群优化算法中，我们必须提供蚂蚁的数量。是否有任何数学公式来选择蚂蚁的数量？

我正在做蚁群优化算法。我有几个问题。我试图搜索 throw ant-colony，但一无所获。

1 — 算法的结果是什么？

我有一些图表，我需要找到从起点到目标点的最佳路径，对吗？该算法不像 dijkstra 算法（找到一条最短路径）那样工作。其中有一个概率因素。在 10 个循环和 5000 只蚂蚁之后，可以选择最差路径，尽管如此，更好路径上的信息素将增加 1000 倍。我的意思是第 5000 个可以选择路径1 -> 3 -> 5（平均概率为 1%），尽管有 4999 只蚂蚁选择了路径（概率为1 -> 2 -> 599%）。这只是一个例子。所以问题是如何检测最优化（最好，在某些参数上最好？）路径，我应该检测它还是1 -> 2 -> 5在我的例子中是正确的结果（发生......）并且我必须输出最后选择的路径？

2 - 如何输出结果

那么这个答案可能取决于第一个答案。怎么样？我假设，我必须输出每个周期的工作算法和协议的总摘要。

汇总数据将是：

协议将是：

有什么建议么？请帮我处理每次迭代的输出数据。

3 — 信息素水平达到一定值时停止增长

为什么会这样？例如（500 只蚂蚁），最佳路径上的信息素水平增长到大约 10 步搜索（循环），之后变得稳定。这是良好的行为还是意味着我的算法中有一些错误？如果没有错误，为什么会出现这种行为？

4 — 我的程序架构

我认为好的方法是创建onclick处理程序，它调用算法的 NEXT STEP（下一个循环）。我看到了一些例子，它有一段时间循环了（不记得链接，不能给你看：'（现在）。我的方法是可以接受的还是完全错误的？

我试图在蚁群优化问题上获得更好的性能。为此，我使用 openCL 并行运行更新信息素部分。我刚开始学习openCL，这是我开发的内核代码。尽管它比顺序版本运行得更快，但我仍然认为我可以使用它实现更高的性能，但我没有找到其他可以做的事情。有没有办法进一步改进这段代码？

PS：我只在 CPU 上测试了这段代码，因为我正在使用的计算机没有 GPU。

我正在尝试理解这篇论文，并为机器人导航论文进行改进的蚁群优化的实时实现。当我尝试实施时，我有几个问题让我头疼：

1. 作者介绍了负性信息素沉积（在上述论文第2页第二栏提到）。但我不明白它是什么或它在哪里使用！在论文中，它没有谈论它，也没有在谷歌上搜索它。它是什么，我们将在哪里使用它？我们已经在进行信息素的沉积和蒸发。

2. 在目标寻找算法（第 2 页）中，信息素沉积是在所有蚂蚁移动到下一个位置之后以及在进行蒸发之后完成的。那么，那个时候，信息素的沉积是通过迭代所有的蚂蚁，更新它们当前位置的信息素浓度来进行的，不是吗？

3. 在那个目标寻找算法（第 2 页）中，作者谈到了Check if termination criteria met. 那么，这是否意味着检查蚂蚁是否已经到达目标（即目标位置）？如果是这样，则应终止执行。不是吗？

4. 除此之外，我不明白他在第 2 页的目标搜索算法中这三行是什么意思：

   • 控制蚂蚁离墙的距离

   • 防止回溯

   • 防止4方循环

我已经包含了上述论文中相关部分的屏幕截图：

如果您能解决我的上述问题，我将不胜感激。

编辑

由于对此没有回应，我在这里问了另一个问题：https ://softwareengineering.stackexchange.com/questions/238639/ant-colony-optimization-movement-of-ants

我开发了一个 aco 算法。我认为它无法正常工作......这将很难解释，但我会尝试。

问题是信息素水平是浮动的。我认为，必须越来越多地增加最佳路径上的信息素水平，但在我的程序中并非如此。

Optimal path是一条路径，它是通过在起始顶点和目标顶点之间的边上找到最大信息素水平来构建的。

例子：

Optimal path将1 -> 2 -> 3。

权重矩阵：

最佳路径是：1 -> 2 -> 3 (length: 6) 另一条路径（不是最佳路径）：1 -> 3 (length: 10)

---

10 只蚂蚁后的信息素水平：

最佳路径：1 -> 2 -> 3

---

20 只蚂蚁（多 10 只）后的信息素水平：

最佳路径：1 -> 3

---

30 只蚂蚁后的信息素水平：

最佳路径：1 -> 2 -> 3

---

30 只蚂蚁后的信息素水平：

最佳路径：1 -> 3

这只是一个例子，但它代表了我程序中的信息素矩阵的样子。

---

我的程序的伪代码：

那么，为什么我的程序中的信息素水平会浮动？为什么最佳路径没有最多的信息素水平？我知道这个算法中有概率因素，但无论如何它必须显示正确的结果。

---

我在我的程序中做什么？在这里你可以找到我的程序的完整主循环源代码。

1）主循环是一个循环，直到有任何蚂蚁可用于当前迭代。

1.1）在这个循环中，我有另一个循环（内部循环），它将被触发，直到当前蚂蚁有顶点可以到达它们（当前蚂蚁不能访问顶点）。

在内部循环中，我这样做：

1.1.1)计算下式的分母

这个公式将计算选择ij路径的概率（i是当前节点，j是下一个节点）。

代码：

1.1.2)计算上式的分子，得到从当前可用的每个顶点选择的概率

此外，我将所有概率添加到一个区间，这将帮助我决定选择哪个顶点。

代码：

1.1.3）创建从0到1的随机数并根据 intervals数组选择顶点，在前面的代码中定义

代码：

1.1.4）一些说明，设置助手（路径助手，访问帮助）等

1.1.5）下一步，我正在检查建立的顶点是否是目标顶点

如果是（这意味着，那只蚂蚁找到了目标顶点）我正在这样做：

1.1.5.1)获取当前蚂蚁路径的长度

代码：

1.1.5.2)更新这条路径上的信息素水平

代码：

1.2）在主循环结束时，我正在蒸发信息素水平：

代码：

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

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

例如，我有这个图表：

矩阵是：

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

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

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

它工作正常吗？

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

我的假设是否正确？

我正在编写一个算法，其中包括一个旅行推销员问题（TSP）和一个迷宫解决问题。基本上迷宫内有一些点，我们需要找到通往所有这些点的最佳路径并最终退出迷宫。

我们开始使用 ACO 算法来寻找迷宫的出口，它运行良好。但是如何将 TSP 集成到其中。

我们的第一个猜测是强化学习。有任何想法吗？

我正在尝试用 C# 编写 ACO 算法。我无法理解修剪过程。

我的意思是，在我们创建规则之后，我们会修剪该规则：

我参考了许多其他论文，发现在 Pruning 中，我们尝试一个一个地临时删除术语并计算质量，并且在删除时提高质量的术语被永久删除。并且这个缩短的规则再次被修剪，直到没有其他需要考虑：

根据该论文，质量计算基于以下等式：

我对该等式中提到的那些术语有疑问。所以我研究并发现了另一个看起来更好的：

所以在上面的等式中，你会看到术语TP, FP, TN, FN。并且对我们如何找出cases covered by this rule和cases not covered by this rule

是否就像我们尝试计算验证集中与规则中的条款匹配的行数一样？有任何想法吗？我真的被困在这部分了。

我试图弄清楚我们如何在此算法中的规则列表上进行质量计算：

我了解如何使用以下公式计算单个规则的质量：

但是当涉及到规则列表的情况下，我们如何找出规则列表的质量呢？

我们会一一找出规则的质量并加以总结？

---

编辑

基于这篇论文，规则列表的质量是使用这个公式找到的：

所以几乎让我的查询解决了这个问题。但是我对它的分子有疑问。我的意思total examples是验证集中的总行数不是吗？number of correct classification验证集中与我们列表中的规则匹配的行数是什么意思？我的意思是那些与规则条款以及规则的类值相匹配的行？