4

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

  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

4

1 回答 1

3

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

仅略读您提供的论文，我无法告诉您他们究竟是如何实施负面信息素的。有几种方法，可能最常见的通用方法是选择生成的最差路径，并为它们的所有图块赋予负信息素，而不是常规的正信息素。在选择一个根据两种不同信息素的水平计算运动可能性的函数时仍然存在设计选择...

在给定的论文中，听起来他们采取了类似的方法并从相应的瓷砖中减去信息素，而不是添加第二个负信息素。因此，他们不需要更改确定移动到相邻图块的可能性的函数。

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

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

所有蚂蚁都被移动，直到它们都达到目标 - 或者满足其他一些终止标准。例如。您可能决定只等到至少 90% 的蚂蚁达到目标，或者您可能包括最大步数。

根据（5）蒸发每个瓷砖上的信息素。

现在考虑所有蚂蚁到达目标的路径。根据给定的函数 (3) 或 (4) 将信息素添加到所有使用的图块，具体取决于您是否要鼓励这条特定路径（例如，所有未达到目标的蚂蚁都是负面信息素的良好候选者）。

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

    Control ant distance from wall
    Prevent backtracking
    Prevent 4 square looping

在选择要移动到的下一个图块时，它们会在一定程度上限制选择。他们希望与所有墙壁保持最小距离，因此他们忽略了直接相邻墙壁的选择（或与它们的其他距离，不知道为什么他们决定在算法中此时包含这一点......）。他们还禁止蚂蚁只来回走动，因此禁止前一个瓷砖 - 以及 4 格循环（即由四个瓷砖组成的循环）。

编辑该算法的一种可能实现可以执行以下操作（我为您选择了停止标准和负信息素的选择）

initialize all cells pheromone levels to some constant > 0

repeat
    set all ants to start location and erase their history
    repeat
        for every ant do
            if this ant is at the goal skip it
            make list of all neighbouring cells that are
                1. not too close to a wall
                2. not equal to the previous cell
                3. not equal to the cell that was visited 3 moves before
            calculate probability for all cells in this list
            choose next cell according to these probabilities
            update current position and history
        end for
    until 80% of all ants have reached the goal
    
    evaporate pheromones
    
    for every ant do
        if it reached the goal
            add pheromones to all cells in this ants history according to (3)
        else
            substract pheromones accoring to (4)
    end for
until length of shortest path has not changed for M iterations

希望这能澄清一点。我会在选择邻居时更改条件 2. 和 3. 以排除任何已经被这只蚂蚁访问过的单元格 - 但它是个人偏好....

于 2014-05-26T17:45:24.827 回答