改进的蚁群优化算法在机器人导航中的应用论文

4
我正在尝试理解这篇论文,并进行 改进的蚁群算法在机器人导航中的应用 的实时实现。在我的实现过程中,我有一些问题:
  1. 作者介绍了负信息素沉积(在上述论文第2页第二栏提到)。但我不理解它是什么或者它在哪里使用!在论文中也没有详细说明,我在谷歌上搜索也没找到相关资料。它是什么,我们在哪里使用它?我们已经在做信息素沉积和蒸发。

  2. 在目标寻求算法中(第2页),信息素沉积是在所有蚂蚁移动到下一个位置后以及蒸发后进行的。所以,在那个时候,通过迭代所有蚂蚁并更新它们当前位置的信息素浓度来进行信息素沉积,对吗?

  3. 在目标寻求算法中(第2页),作者谈到“检查是否满足终止条件”。那么,这是指检查蚂蚁是否到达了目标(即目的地位置)吗?如果是,那么执行应该终止。对吗?

  4. 除此之外,在第2页的目标寻求算法中,我不理解他所说的这三行:

    • 控制蚂蚁与墙的距离

    • 防止回溯

    • 防止4个方格循环

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

enter image description here

如果您能解答我的问题,我将不胜感激。

编辑

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


我不认为这个问题严格来说是[so]的离题内容,但我认为[cs.se]更适合这个问题(只是不要跨站发布)(或者甚至[cstheory.se],但我对此并不确定)。 - Bernhard Barker
如果您觉得更合适,可以随意移动到相应的部分。谢谢。 - Vpp Man
请查看此链接:http://programmers.stackexchange.com/questions/238639/ant-colony-optimization-movement-of-ants - Vpp Man
是的,这个问题可以放在cs.stack上讨论,但抵制这种分类其实是一件好事情,因为stackoverflow上的每个问题都属于以下三类:a)算法->cs; b)基于观点(应该选择哪一个)而不适合讨论或c)与特定代码相关-> code-review.stack... - example
1个回答

3
作者介绍了负信息素沉积(在上述论文第2页第2列中提到)。但我不明白它是什么或者它在哪里被使用!在论文中,也没有详细讨论它,我也在Google中搜索了。它是什么,我们在哪里会使用它?我们已经在进行信息素沉积和蒸发。
仅凭快速浏览您提供的论文,我无法告诉您他们如何准确地实现负信息素。有几种方法,可能最常见的通用方法是选择生成的最差路径,并为它们的所有格子提供负信息素,而不是常规的正信息素。不过,在选择基于两种不同信息素水平计算移动可能性的函数时,仍存在设计选择...
在给定的论文中,听起来他们采取了类似的方法,并从相应的格子中减去信息素,而不是添加第二个负信息素。因此,他们不需要更改确定移动到相邻格子的可能性的函数。
在目标寻求算法中(在第2页中),信息素沉积是在所有蚂蚁移动到下一个位置之后以及蒸发之后进行的。那么,在那个时候,沉积信息素是通过迭代所有蚂蚁并更新其当前位置中的信息素浓度来进行的,是吗?
在目标寻求算法中(在第2页中),作者谈到检查是否满足终止条件。那么,这是否意味着检查蚂蚁是否已经到达目标(即目标位置)?如果是,执行应该终止。是吗?
所有蚂蚁都会移动,直到它们全部到达目标位置,或者满足某些其他终止条件。例如,您可能决定仅等待至少90%的蚂蚁到达目标位置,或者您可能包括最大步数。
根据(5)在每个格子上蒸发信息素。
现在考虑所有蚂蚁到达目标的路径。根据给定的函数(3)或(4)向所有使用的格子添加信息素,具体取决于您是否想鼓励这条特定路径(例如,所有未达到目标的蚂蚁都是负信息素的好候选者)。

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
在选择下一步要移动到的瓷砖时,它们会限制选择。他们想要与所有墙壁保持最小距离,因此他们忽略直接邻近墙壁的选择(或者从墙壁某些距离处开始忽略,不知道为什么他们选择在算法的这一点上包括这个...)。他们还禁止蚂蚁来回走动,因此前一个瓷砖是被禁止的 - 以及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,以排除此蚂蚁已经访问过的任何单元格 - 但这是个人偏好...


谢谢你的回复。当我最初选择这篇论文时,它看起来很简单,所以我决定尝试实现它。正如你所看到的那样:http://stackoverflow.com/questions/23584460/ant-colony-optimization-movement-of-ants.目前我感到很困惑。那个问题中的伪代码是我迄今为止所做的。 - Vpp Man
是的,正是出于这个原因,您必须记住蚂蚁走过的完整路径。我所说的“destroy”部分是指在重新开始内部循环之前将所有蚂蚁重置到起点并删除它们的路径历史记录。 - example
你真的是想要这样做吗?那么蚂蚁就不会移动除了它的第一个细胞以外的任何细胞了!或者我理解错了吗?内部循环只考虑每只蚂蚁并移动一个细胞。这是为所有蚂蚁完成的,当该循环结束时(即执行TOTAL_NUM_OF_ANTS次),如果我们尝试将蚂蚁重置回去,那么运动没有改善! - Vpp Man
@VppMan 重复直到所有蚂蚁都到达目标 - 或者满足其他条件,如“已经过了1000步”或“90%的蚂蚁已经到达目标”。 - example
非常抱歉要问这个问题,但您能否提供一些更易于理解的伪代码算法呢?我会非常感激,并且我会加倍奖励(编辑:不确定如何编辑赏金!)。 - Vpp Man
显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接