机器人导航纸的改进蚁群优化

Question

我试图理解这篇文章，并做一个机器人导航纸的改进蚁群优化的实时实现。当我试图实施的时候，我有几个令我印象深刻的问题：

1. 作者介绍了负信息素沉积(在上述论文第2页第2栏中提到)。但是我不知道它是什么，也不知道它在哪里使用！在报纸里，它并没有提到它，也在谷歌上搜索过它。它是什么，我们将在哪里使用它？我们已经在做信息素沉积和蒸发了。
2. 在目标搜索算法(第2页)中，信息素沉积是在所有蚂蚁被移动到下一个位置以及蒸发之后进行的。所以，在那个时候，信息素的沉积是通过遍历所有的蚂蚁，更新信息素在它们当前位置的浓度来完成的，不是吗？
3. 在目标搜索算法(第2页)中，作者谈到了Check if termination criteria met。那么，这是否意味着检查蚂蚁是否达到了目标呢？目的地)？如果是这样，则应该终止执行。难到不是么？
4. 除此之外，我不明白他在第2页的目标寻找算法中这三行是什么意思：

- Control ant distance from wall 
- Prevent backtracking 
- Prevent 4 square looping

​

我已包括上述文件有关部分的截图：

​

​

如果你能澄清我以上的问题，我将非常感激。

编辑

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

Answer 1

作者介绍了负信息素沉积(在上述论文第2页第2栏中提到)。但是我不知道它是什么，也不知道它在哪里使用！在报纸里，它并没有提到它，也在谷歌上搜索过它。它是什么，我们将在哪里使用它？我们已经在做信息素沉积和蒸发了。

只是浏览一下你提供的文件，我不能告诉你，它们是如何实现负信息素的。有几种方法，可能最常见的通用方法是选择生成的最坏路径，并给它们所有的标签一个负信息素，而不是常规的正信息素。在选择一个根据两种不同信息素水平计算运动可能性的函数时，仍然有一个设计选择。

在给定的论文中，他们似乎采取了类似的方法，从相应的贴片中减去信息素，而不是添加第二个负信息素。因此，他们不需要改变决定移动到邻近瓷砖的可能性的函数。

在目标搜索算法(第2页)中，信息素沉积是在所有蚂蚁被移动到下一个位置以及蒸发之后进行的。所以，在那个时候，信息素的沉积是通过遍历所有的蚂蚁，更新信息素在它们当前位置的浓度来完成的，不是吗？ 在该目标寻求算法(在第2页)，作者谈到了检查是否符合终止条件。那么，这是否意味着检查蚂蚁是否达到了目标呢？目的地)？如果是这样，则应该终止执行。难到不是么？

所有蚂蚁都会被移动，直到它们都达到了目标--或者达到了其他一些终止条件。例如：您可能决定只等待至少90%的蚂蚁达到目标，或者您可能包含了最大数量的步骤。

根据(5)蒸发每个瓷砖上的信息素。

现在来考虑一下所有蚂蚁为了达到目标而采取的措施。根据给定的功能(3)或(4)将信息素添加到所有使用过的瓷砖中，这取决于您是否希望鼓励这条特定的路径(例如。所有未达到目标的蚂蚁都是负信息素的好候选者)。

除此之外，我不明白他在第2页的目标寻找算法中这三行是什么意思： 控制蚂蚁距离墙，防止回溯，防止4平方圈。

当选择要移动的下一个瓷砖时，它们在一定程度上限制了选择。他们希望保持与所有墙壁的最小距离，因此他们忽略了直接相邻墙壁的选择(或与它们的其他距离，不知道为什么在算法中的这个点上包含了这一点)。他们也禁止蚂蚁来回走动，所以以前的瓷砖是被禁止的-以及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.在选择邻居时，排除这只蚂蚁已经访问过的任何牢房--但它个人偏好.