algorithm - 蚁群优化—— Ant 的运动

Question

我正在尝试实现蚁群优化。试图引用这篇论文:Improved ant colony optimization for robot navigation paper .由于我没有得到这些问题的任何答案，所以我在实现过程中卡在了一半。所以我现在问与蚁群有关的具体问题:

1. 到目前为止，我所做的是设置一个二维数组 map ， map 周围的边界和障碍物的值为 0。

2. 通过在该数组中随机 [row,column] 插入 0 来在随机位置生成障碍物。

3. 我已将所有 Ant 开始旅程的来源放在左下角。我已经将目标位置放在右上角。

4. 已编写代码，使用 VB.Net 中的图形函数直观地绘制 map ，效果很好。信息素的颜色渐变显示在 map 上(即白色阴影越多，信息素在 map 上沉积越多，否则阴影越深)

我当前的实现伪代码如下所示:

for each ant from 1 to colonysize
  create an ant and insert it to the ant_array
  set the ant's current position to the starting position in the map
end for

for each rows in map array
  for each column in map array
    if it is first row or first column or last row or last column(these holds the boundary), then...
       assign 0 as value to <row,column> in the map array
    otherwise,
       assign INITIAL_PHEROMONE_FACTOR as value to <row,column> in the map array 
    end if
  end for
end of

for 5 random locations in map(ie. <row, column> )
  insert 0 as value to denote obstacle
end for

for 1 to TOTAL_NUMBER_OF_ITERATIONS
  for 1 to TOTAL_ANTS_IN_COLONY

     find the neighbors of the current ant in top, right, bottom and left positions

     choose randomly a neighboring position from the above 
     check whether that location has an obstacle or is a boundary (ie. if it has 0 as value in array map)
     if so, 
    repeat the above two steps of randomly chosing another neighboring position which was not already considered
     otherwise, continue to the next line..


     set the neighbor position we have selected above as the current position of the ant
     save this position to the ant's local path storage

     if the current position of this ant is the destination location, 
    then end program

  end for

  evaporate pheromones in the map at a constant factor
  deposit pheromones on the current location of all the ants


  draw the visual representationg of the map
end for

这是我到目前为止所做的截图:

目前，实现卡住了。当我阅读其他论文以及在谷歌中提到时，据说， Ant 起初是随机行走的。但是路径上的信息素浓度会被其他 Ant 用来选择路径。也就是说，如果一只 Ant 找到了目标，它应该返回巢穴而不是终止程序？其他 Ant 如何选择信息素浓度高的路径？不能保证其他 Ant 在正确的路径上移动。

我真的很困惑。我了解简单的现实世界示例。 Ant 最初是随机移动寻找食物，如果找到食物，它会回到巢穴并再次返回，因此该路径上的信息素沉积会更高，其他 Ant 会选择该路径。

但是当我尝试实现时，它变得越来越棘手和令人困惑。我真的很感激一些简单的想法或解释。我不是在寻找代码。这就是为什么我编写伪代码而不是发布我目前完成的实际实现代码的原因。

Answer 1

蚁群优化的作用如下:

1. 派出第一只 Ant 。由于最初棋盘上没有信息素，第一只 Ant 只能随机移动来寻找通往食物的路径。
2. 将形成第一只 Ant 找到的路径的所有细胞的信息素值略微增加。
3. dispatch 另一只 Ant ，这只 Ant 应该通过选择下一个要前往的单元格找到一条路径，使得信息素值高的单元格比信息素值低的单元格更有可能被选中。由于随机因素， Ant 有时会选择信息素较低的路径，这偶尔会产生更好/更短的路径。
4. 如果 Ant 成功，则增加该路径上的信息素值，这样路径上的细胞更有可能被选中。如果 Ant 没有成功，则中止 Ant 并重新开始。
5. 有时，减少整个板上的信息素，这样不太成功的细胞就会越来越少被选中。
6. 重复 3 直到路径足够好。

在一段时间内，最成功的路径将比不太成功的路径包含更多的信息素。

There is no guarantee that the other ants are moving in the right path!

这就是算法中随机性的要点。如果 Ant 只使用经过试验和测试的路径，那么它永远无法改进路径。使用加权随机性来选择下一个单元格的要点是，一只迷路的 Ant 可能会偶然发现比原始路径更好的路径。