如何在网格板上实现遗传算法以找到最佳路径
How do I implement genetic algorithm on grid board to find optimal path
我正在准备在有障碍物的地形中寻找最佳路径的算法。到目前为止,我实现了 Dijsktra 和 A* 算法。现在我必须实现遗传算法,但我遇到了问题。
首先,我将向您展示我的地图表示形式。有7种不同的地形(0-开始,7-结束,1-4正常可以通过,5-6不能通过)。这是 Python 中的代码(在我看来,代码中最重要的部分是理解问题的函数 neighbors
):
class Graph():
def __init__(self, x=10, y=10):
self.width = x
self.height = y
self.board = ((1, 1, 1, 5, 1, 1, 1, 1, 1, 7),
(1, 1, 1, 5, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 5, 1, 5, 1, 1, 1, 1),
(0, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1))
self.time = {0: None,
1: 1,
2: 4,
3: 7,
4: 4,
7: 1}
def cost(self, id):
(x, y)= id
return self.time.get(self.board[y][x])
def canPass(self, id):
(x, y) = id
return self.board[y][x] != 5 and self.board[y][x] != 6 and self.board[y][x] != 0
def inBounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
def neighbors(self, id):
(x, y) = id
nodes = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
nodes = filter(self.inBounds, nodes)
nodes = filter(self.canPass, nodes)
return nodes
由于我的地图和邻居表示,我不知道如何从理论上实现遗传算法,我无法更改它们。
我做了什么:
我使用我的 A* 的修改准备了起始人口,它找到了从头到尾几乎最简单的连接,而没有检查它的成本。这是代码
def heuristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)
def StartingPopulation(graph, start, goal):
(x, y) = start
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = [[0 for i in xrange(10)] for j in xrange(10)]
came_from[start] = None
cost_so_far[y][x] = 0
while not frontier.empty():
current = frontier.get()
(y1, x1) = current
if (y1, x1) == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[x1][y1] + graph.cost(next)
(y2, x2) = next
if cost_so_far[x2][y2] == 0 or new_cost < cost_so_far[x2][y2]:
cost_so_far[x2][y2] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
return came_from, cost_so_far
这就是我的发明。我不知道如何对遗传算法执行其他步骤,例如对我拥有的数据进行选择、交叉和变异。我希望你能指导我并给我一些提示(如果有我需要的完整代码,检查和学习它也很好)
二维网格的一个简单GA-based方法是将染色体(二进制字符串)分成移动,例如:
00 = down
10 = left
01 = right
11 = up
run(chromosome)
函数,给定一个 chromosome
,执行从起点(地图上的代码 0
)到到达的终点 returns 的移动:
(f_y, f_x) = run(chromosome)
适应度函数是到目标点的距离:
def fitness(chromosome):
final = run(chromosome)
return 1.0 - (distance(final, goal) / max_possible_distance)
或者:
# Returns negative values.
# Depending on the selection scheme, it can be problematic.
def fitness(chromosome):
final = run(chromosome)
return -distance(final, goal)
两个适应度函数都假设越大越好。
现在举个例子:
S
是起点,F
是终点,G
是终点,*
一堵墙
chromosome
是 00 00 01 01 00 00 00 01 01 11
即 ↓ ↓ → → ↓ ↓ ↓ → → ↑
run(S, chromosome)
的操作方式如下:
|---|---|---|---|---|---|
| S | |***| | | |
|-|-|---|---|---|---|---|
| | | |***| | | |
|-|-|---|---|---|---|---|
| +---+->***| |***|***|
|---|-|-|---|---|---|---|
| | | |***| F | | G |
|---|-|-|---|-^-|---|---|
| | +-------+ |***| |
|---|-|-|---|---|---|---|
函数简单地忽略了不可能的走法
- 健身
-2
可以使用标准One point crossover / two points crossover(或其他形式),例如:
ONE POINT CROSSOVER
00 00 01 01 00 00|00 01 01 11 PARENTS
11 11 01 01 00 00|01 01 11 01
-----------------^-----------
00 00 01 01 00 00|01 01 11 01 OFFSPRING
11 11 01 01 00 00|00 01 01 11
第一个 child (00 00 01 01 00 00 01 01 11 01
) 的适应度大于两个 parents (-1
):
|---|---|---|---|---|---|
| S | |***| | | |
|-|-|---|---|---|---|---|
| | | |***| | | |
|-|-|---|---|---|---|---|
| +---+->***| |***|***|
|---|-|-|---|---|---|---|
| | | |***| +-> F | G |
|---|-|-|---|-|-|---|---|
| | +-------+ |***| |
|---|---|---|---|---|---|
注释
- 可以使用 基因修复运算符 来扩展该方案,而不是忽略不可能的动作(如上例所示),它会删除错误的动作并添加随机动作来填充染色体(更复杂但它利用了完整的可用长度)。
- 通常,在 GA 中,染色体具有固定长度:允许长度比最佳路径长 30% - 40% 是个好主意。
任何通往目标的路径都被认为是符合标准的。搜索最佳路径需要为偏离最短路径的适应度函数添加惩罚项,例如:
def fitness(chromosome):
final = run(chromosome)
return -distance(final, goal) - length_of_path(chromosome) / 100.0
一种完全不同的方法是使用 GA 优化 A*(Using a Genetic Algorithm to Explore A*-like Pathfinding 中有更多详细信息
算法,作者:Ryan Leigh、Sushil J. Louis 和 Chris Miles)。
- 从 AI 的角度来看,第三个选项可能是最有趣的,它是遗传编程(参见 Rick Strom 的 Evolving Pathfinding Algorithms Using Genetic Programming 示例)。
- 这是 GA 灵活性的一个很好的例子,但是 A* 更好。
我正在准备在有障碍物的地形中寻找最佳路径的算法。到目前为止,我实现了 Dijsktra 和 A* 算法。现在我必须实现遗传算法,但我遇到了问题。
首先,我将向您展示我的地图表示形式。有7种不同的地形(0-开始,7-结束,1-4正常可以通过,5-6不能通过)。这是 Python 中的代码(在我看来,代码中最重要的部分是理解问题的函数 neighbors
):
class Graph():
def __init__(self, x=10, y=10):
self.width = x
self.height = y
self.board = ((1, 1, 1, 5, 1, 1, 1, 1, 1, 7),
(1, 1, 1, 5, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 5, 1, 5, 1, 1, 1, 1),
(0, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 5, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1),
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1))
self.time = {0: None,
1: 1,
2: 4,
3: 7,
4: 4,
7: 1}
def cost(self, id):
(x, y)= id
return self.time.get(self.board[y][x])
def canPass(self, id):
(x, y) = id
return self.board[y][x] != 5 and self.board[y][x] != 6 and self.board[y][x] != 0
def inBounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
def neighbors(self, id):
(x, y) = id
nodes = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
nodes = filter(self.inBounds, nodes)
nodes = filter(self.canPass, nodes)
return nodes
由于我的地图和邻居表示,我不知道如何从理论上实现遗传算法,我无法更改它们。
我做了什么:
我使用我的 A* 的修改准备了起始人口,它找到了从头到尾几乎最简单的连接,而没有检查它的成本。这是代码
def heuristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)
def StartingPopulation(graph, start, goal):
(x, y) = start
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = [[0 for i in xrange(10)] for j in xrange(10)]
came_from[start] = None
cost_so_far[y][x] = 0
while not frontier.empty():
current = frontier.get()
(y1, x1) = current
if (y1, x1) == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[x1][y1] + graph.cost(next)
(y2, x2) = next
if cost_so_far[x2][y2] == 0 or new_cost < cost_so_far[x2][y2]:
cost_so_far[x2][y2] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
return came_from, cost_so_far
这就是我的发明。我不知道如何对遗传算法执行其他步骤,例如对我拥有的数据进行选择、交叉和变异。我希望你能指导我并给我一些提示(如果有我需要的完整代码,检查和学习它也很好)
二维网格的一个简单GA-based方法是将染色体(二进制字符串)分成移动,例如:
00 = down
10 = left
01 = right
11 = up
run(chromosome)
函数,给定一个 chromosome
,执行从起点(地图上的代码 0
)到到达的终点 returns 的移动:
(f_y, f_x) = run(chromosome)
适应度函数是到目标点的距离:
def fitness(chromosome):
final = run(chromosome)
return 1.0 - (distance(final, goal) / max_possible_distance)
或者:
# Returns negative values.
# Depending on the selection scheme, it can be problematic.
def fitness(chromosome):
final = run(chromosome)
return -distance(final, goal)
两个适应度函数都假设越大越好。
现在举个例子:
S
是起点,F
是终点,G
是终点,*
一堵墙chromosome
是00 00 01 01 00 00 00 01 01 11
即↓ ↓ → → ↓ ↓ ↓ → → ↑
run(S, chromosome)
的操作方式如下:|---|---|---|---|---|---| | S | |***| | | | |-|-|---|---|---|---|---| | | | |***| | | | |-|-|---|---|---|---|---| | +---+->***| |***|***| |---|-|-|---|---|---|---| | | | |***| F | | G | |---|-|-|---|-^-|---|---| | | +-------+ |***| | |---|-|-|---|---|---|---|
函数简单地忽略了不可能的走法
- 健身
-2
可以使用标准One point crossover / two points crossover(或其他形式),例如:
ONE POINT CROSSOVER
00 00 01 01 00 00|00 01 01 11 PARENTS
11 11 01 01 00 00|01 01 11 01
-----------------^-----------
00 00 01 01 00 00|01 01 11 01 OFFSPRING
11 11 01 01 00 00|00 01 01 11
第一个 child (00 00 01 01 00 00 01 01 11 01
) 的适应度大于两个 parents (-1
):
|---|---|---|---|---|---|
| S | |***| | | |
|-|-|---|---|---|---|---|
| | | |***| | | |
|-|-|---|---|---|---|---|
| +---+->***| |***|***|
|---|-|-|---|---|---|---|
| | | |***| +-> F | G |
|---|-|-|---|-|-|---|---|
| | +-------+ |***| |
|---|---|---|---|---|---|
注释
- 可以使用 基因修复运算符 来扩展该方案,而不是忽略不可能的动作(如上例所示),它会删除错误的动作并添加随机动作来填充染色体(更复杂但它利用了完整的可用长度)。
- 通常,在 GA 中,染色体具有固定长度:允许长度比最佳路径长 30% - 40% 是个好主意。
任何通往目标的路径都被认为是符合标准的。搜索最佳路径需要为偏离最短路径的适应度函数添加惩罚项,例如:
def fitness(chromosome): final = run(chromosome) return -distance(final, goal) - length_of_path(chromosome) / 100.0
一种完全不同的方法是使用 GA 优化 A*(Using a Genetic Algorithm to Explore A*-like Pathfinding 中有更多详细信息 算法,作者:Ryan Leigh、Sushil J. Louis 和 Chris Miles)。
- 从 AI 的角度来看,第三个选项可能是最有趣的,它是遗传编程(参见 Rick Strom 的 Evolving Pathfinding Algorithms Using Genetic Programming 示例)。
- 这是 GA 灵活性的一个很好的例子,但是 A* 更好。