algorithm - 机器人导航论文的改进蚁群优化

Question

我正在尝试理解这篇论文并实时执行 improved ant colony optimization for robot navigation paper .当我尝试实现时，我有几个问题让我印象深刻:

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

2. 在目标搜索算法(第 2 页)中，信息素沉积是在所有 Ant 移动到下一个位置以及进行蒸发之后完成的。那么，那个时候信息素的沉积就是通过遍历所有的 Ant ，更新它们当前所在位置的信息素浓度来进行的，不是吗？

3. 在该目标搜索算法(第 2 页)中，作者谈到了检查是否满足终止条件。那么，这是否意味着检查 Ant 是否已到达目标(即目的地位置)？如果是，则应终止执行。不是吗？

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

   • 控制 Ant 离墙的距离

   • 防止回溯

   • 防止4方 block 循环

我已经包含了上述论文相关部分的截图:

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

编辑

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

Answer 1

The author introduced negative pheromone depositing(mentioned in page 2 second column of the above paper). But I didn't understood whatit is or where it is used! Inside the paper, it doesn't talk about itas well googled about it. What is it and where would we use it? We arealready doing pheromone deposition and evaporation.

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

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

In the goal seeking algorithm (in page 2), the Pheromone deposition is done after all the ants are moved to the next positionas well as after the evaporation is carried out. So, at that time, thedepositing of the pheromones is carried out by iterating through allthe ants and updating the pheromone concentration in their currentlocation, isn't it?

In that goal seeking algorithm (in page 2), the author talks about Check if termination criteria met. So, does that mean check whetherthe ant had reached the goal(ie. destination location)? If so, theexecution should be terminated. Isn't it?

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

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

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

Apart from that, I didn't understood what he meant by these three lines in the goal seeking algorithm in page 2:

    Control ant distance from wall
    Prevent backtracking
    Prevent 4 square looping

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

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

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. 在选择邻居时排除任何已经被这只 Ant 访问过的单元格——但它是个人偏好....