如何在网格板上实现遗传算法来找到最佳路径

Question

我正在准备在有障碍物的地形中寻找最佳路径的算法。到目前为止，我实现了 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

这就是我发明的一切。我不知道如何对遗传算法执行其他步骤，例如对我拥有的数据进行选择、交叉和变异。我希望你能指导我并给出一些提示（如果有我需要的完整代码，那么检查并从中学习也是很好的）

Answer 1

一种简单的基于 GA 的二维网格方法是将染色体（二进制字符串）分解为移动，例如：

\n\n

00 = down\n10 = left\n01 = right\n11 = up\n

\n\n

该run(chromosome)函数给定 a chromosome，从起点（0地图上的代码）执行移动并返回到达的最终点：

\n\n

(f_y, f_x) = run(chromosome)\n

\n\n

适应度函数是距目标点的距离：

\n\n

def fitness(chromosome):\n    final = run(chromosome)\n    return 1.0 - (distance(final, goal) / max_possible_distance)\n

\n\n

或者也可以：

\n\n

# Returns negative values.\n# Depending on the selection scheme, it can be problematic.\ndef fitness(chromosome):\n    final = run(chromosome)\n    return -distance(final, goal)\n

\n\n

两个适应度函数都假设越大越好。

\n\n

现在举个例子：

\n\n

\n
1. S是起点，F是到达的终点，G是目标点和*墙
\n
2. chromosome是00 00 01 01 00 00 00 01 01 11即\xe2\x86\x93 \xe2\x86\x93 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x93 \xe2\x86\x93 \xe2\x86\x93 \xe2\x86\x92 \xe2\x86\x92 \xe2\x86\x91
\n

3. run(S, chromosome)按以下方式运作：

   \n\n

   |---|---|---|---|---|---|\n| S |   |***|   |   |   |\n|-|-|---|---|---|---|---|\n| | |   |***|   |   |   |\n|-|-|---|---|---|---|---|\n| +---+->***|   |***|***|\n|---|-|-|---|---|---|---|\n|   | | |***| F |   | G |\n|---|-|-|---|-^-|---|---|\n|   | +-------+ |***|   |\n|---|-|-|---|---|---|---|\n

   \n\n

   该函数只是忽略不可能的动作

\n
4. 健身是-2
\n

\n\n

可以使用标准的一点交叉/两点交叉（或其他形式），例如：

\n\n

ONE POINT CROSSOVER\n\n00 00 01 01 00 00|00 01 01 11      PARENTS\n11 11 01 01 00 00|01 01 11 01\n-----------------^-----------\n00 00 01 01 00 00|01 01 11 01      OFFSPRING\n11 11 01 01 00 00|00 01 01 11\n

\n\n

第一个孩子 ( 00 00 01 01 00 00 01 01 11 01) 的适应度大于父母双方 ( -1)：

\n\n

|---|---|---|---|---|---|\n| S |   |***|   |   |   |\n|-|-|---|---|---|---|---|\n| | |   |***|   |   |   |\n|-|-|---|---|---|---|---|\n| +---+->***|   |***|***|\n|---|-|-|---|---|---|---|\n|   | | |***| +-> F | G |\n|---|-|-|---|-|-|---|---|\n|   | +-------+ |***|   |\n|---|---|---|---|---|---|\n

\n\n

笔记

\n\n

\n
• 该方案不是忽略不可能的移动（如上面的示例），而是可以使用基因修复算子进行扩展，该算子会擦除错误的移动并添加随机移动来填充染色体（更复杂，但它利用了完整的可用长度）。
\n
• 通常，在 GA 中，染色体具有固定长度：允许长度比最佳路径长 30% - 40% 是一个好主意。
\n

• 任何实现目标的途径都被认为是符合标准的。搜索最佳路径需要在适应度函数中添加一个惩罚项来补偿与最短路径的偏差，例如：

  \n\n

    def fitness(chromosome):\n      final = run(chromosome)\n      return -distance(final, goal) - length_of_path(chromosome) / 100.0\n

\n

• 一种完全不同的方法是使用 GA 来优化 A*（更多详细信息请参见 Ryan Leigh、Sushil J. Louis 和 Chris Miles 的《使用遗传算法探索 A* 类寻路\n算法》）。

\n
• 第三种选择，从人工智能的角度来看可能是最有趣的，是遗传编程（参见Rick Strom 的使用遗传编程进化寻路算法的例子）。
\n
• 这是 GA 灵活性的一个很好的例子，但A* 更好。
\n

\n