基本蚁群算法-蚂蚁觅食路径的演变
2018-10-05 本文已影响0人
我_7
UNITY3D 中进行模拟演算
高清完整版：http://www.acfun.cn/v/ac4623849
经过60代之后
第1代
蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己的行动方向，它们总是朝着信息素强度高的方向移动，因此大量的蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。
某一条路径越短，路径上经过的蚂蚁就越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路的几率也就越高，由此构成正反馈的过程，从而逐渐地逼近最优路径，并找到最优路径。
算法简要流程：
（1）初始化。
（2）选择从初始节点下一步可以到达的所有节点，根据公式
计算出前往每个节点的概率。并利用赌徒轮盘选取下一步的初始点。需要注意的是蚂蚁只能向四周八个节点前进。
第 k 只蚂蚁从节点 i 到节点 j 的概率。
在 t 时刻，表示节点 i 至节点 j 边上的信息激素量，各条边的初始值为同一常数
表示 i，j 两节点间的启发值，与两节点间距离成反比。
α、β 为信息素和启发值得权重参数
网格数量，例如地图(a)中 N=16
保存第 k 只蚂蚁已行的节点。若蚂蚁陷入U型障碍，使得蚂蚁无后续节点选择，则默认该蚂蚁已经死亡，算法删除该蚂蚁及其所寻路径
（3）更新路径以及路径长度。
（4）重复（2）,（3）两步，直到找到食物或者无路可走之后退出。
（5）重复（2）,（3）,（4）直到m只蚂蚁全部完成旅途，一代算是结束。
（6）信息素更新。每次所有蚂蚁旅行完成后对信息素进行全局更新，过去的信息素逐渐消逝，并加入新的信息素。其中没有找到食物的蚂蚁不予以计算。根据公式
挥发系数，一般取0~1之间常数
在 t+1 时刻，节点 i，j 间信息素的量
本次循环中节点 i，j 间信息素的增量
在 t 时刻，第 k 只蚂蚁所寻路径的长度
（7）重复（2）~（6），直到n代蚂蚁全部完成旅行。
地图信息
网格环境(黑色为障碍物)和行动逻辑图
网格与序号关系图
网格规模 N；//网格数量
蚂蚁种群数量 numberOfAnts；
迭代次数 numberOfIterations；
信息素挥发系数 ρ;//一般取0~1之间常数
信息素 τ[i][j]; //留在i，j节点间信息素的量，各条边的初始值为同一常数
信息素权重参数 α；
信息素增量 Δτ[i][j]；//本次循环中节点 i，j 间信息素的增量
启发值 η[]；//计算各个网格节点到目标网格的直线距离的倒数。
启发值权重参数 β；
禁忌表 tabu[][]；//保存蚂蚁已行节点。若蚂蚁陷入U型障碍，使得蚂蚁无后续节点选择，
//则默认该蚂蚁已经死亡，算法删除该蚂蚁及其所寻路径
概率 p[]；//前往各个节点的概率值
路径 path[]；//记录这一代这一只蚂蚁的行动路线
路径表 PATH[][]；//记录每一代每一只蚂蚁的行动路线
路径长度 pathLeagth；//记录这一代这一只蚂蚁的行动路线的距离
路径长度表 PATH_LEAGTH[][]；//记录每一代每一只蚂蚁的行动路线的距离
起点 start；//蚁巢
终点 target；//食物
算法开始前的初始化工作和要用到的公式函数：
//直线和斜线网格之间的移动成本
BET-DISTANCE(_start, _target)
1. dstX = |_startX - _targetX|的绝对值
2. dstY = |_startY - _targetY|的绝对值
3. if dstX > dstY
4. return 1.4 * dstY + 1 * (dstX - dstY)
5. return 1.4 * dstX + 1 * (dstY - dstX)
//欧几里得距离平方。
EUCLID-DISTANCE(_startX, _startY, _targetX, _targetY)
1. dstX = |_startX - _targetX|的绝对值
2. dstY = |_startY - _targetY|的绝对值
3. return (dstX ^ 2 + dstY ^ 2) ^ 0.5
//初始化启发式信息，计算各个网格到目标网格的直线距离的倒数。
//启发值和直线距离成倒数，直线距离越远启发值越小，反之亦然。
1. s = 当前网格序号
1. for i = 0 to 网格坐标x
2. for j = 0 to 网格坐标y
3. if s ≠ 目标网格序号
4. η[s - 1] = 1 / EUCLID-DISTANCE(i, j, target.i, target.j)
5. else
6. η[s - 1] = 999
7. s += 1;
//初始化每条路径上信息素的量
1. for i = 0 to N - 1
2. for j = 0 to N - 1
3. τ[i][j] = 1;
算法开始
1. for iteration = 1 to numberOfIterations - 1
2. for ant = 1 to numberOfAnts - 1
3. currentNode = start
α= 1
β = 8
pathLength = 0
//禁忌表初始化，用来记录这一代这一只蚂蚁走过的路，已经走过的路用 false 表示
4. for i = 0 to 网格坐标x
5. for j = 0 to 网格坐标y
6. tabu[i][j] = true
7. tabu[currentNode.x][currentNode.y] = false//起点不让走了
//下一步可以前往的节点
//GetNeighbours() 见之前发表的 A*网格寻路这篇文章
8. neighbours = GetNeighbours(currentNode);
9. for i = 0 to neighbours.Count - 1
10. neighbour = neighbours[i];
11. if neighbour.不是障碍物 && tabu[neighbour.x][neighbour.y]
12. movableRange.Add(neighbour);//可以前往的节点
//蚂蚁未遇到食物 并且 未陷入死胡同
13. while currentNode ≠ target && movableRange.Count >= 1
//计算走每条路的概率
14. for i = 0 to movableRange.Count - 1
15. t = τ[currentNode.网格序号 - 1][movableRange[i].网格序号]- 1] ^ α
16. e = η[movableRange[i].网格序号 - 1] ^ β
17. p[i] = t * e
18. psum = 0
19. for i = 0 to p.length - 1
20. psum = p[i] + psum
21. for i = 0 to p.length - 1
22. p[i] = p[i] / psum
//用赌徒轮盘选择下一步怎么走
23. pcum[0] = P[0]
24. for i = 1 to movableRange.Count - 1
25. pcum[i] = pcum[i - 1] + p[i]
26. pindex = 0;
27. random = (0.0f, 1.0f)之间的随机小数
28. for i = 0 to movableRange.Count - 1
29. if pcum[i] >= random
30. pindex = i
31. break
32. nextNode = movableRange[pindex];
//状态更新和记录
33. path.Add(nextNode)
34. pathLength = pathLength + BetDistance(currentNode, nextNode)
35. currentNode = nextNode
//已访问过的节点从禁忌表中删除
36. tabu[currentNode.x][currentNode.y] = false
//下一步可以前往的节点
37. neighbours = GetNeighbours(currentNode);
38. for i = 0 to neighbours.Count - 1
39. neighbour = neighbours[i];
40. if neighbour.不是障碍物 && tabu[neighbour.x][neighbour.y]
41. movableRange.Add(neighbour);//可以前往的节点
42. 这里结束 while 循环
//记下每一代每一只蚂蚁的觅食路线和路线长度
43. PATH[iteration][numberOfAnts] = path
44. if path[path.Count - 1] == target
45. PATH_LEAGTH[iteration][numberOfAnts] = pathLeagth
46. else
47. PATH_LEAGTH[iteration][numberOfAnts] = 0
48. 这里结束 for ant = 1 to numberOfAnts 遍历
//更新信息素
49. for i = 0 to N - 1
50. for j = 0 to N - 1
51. Δτ[i][j] = 0;
52. for i = 0 to numberOfAnts - 1
53. if PATH_LEAGTH[iteration][i] ≠ 0
54. pia = PATH[iteration][i]
55. plia= PATH_LEAGTH[iteration][i]
56. for s = 0 to pia.Count - 2
57. x = pia[s]
58. y = pia[s + 1]
59. Δτ[x][y] = Δτ[x][y] + 1 / plia
60. Δτ[y][x] = Δτ[y][x] + 1 / plia
61. τ = (1 - ρ) * τ + Δτ//这里使用矩阵加法和乘法的原则进行计算
62. 结尾
63.
