Member 10539396 Ответов: 0

Как реализовать генетический алгоритм на сеточной плате для поиска оптимального пути

Привет
Я готовлю алгоритмы поиска оптимального пути на местности с препятствиями. До сих пор я реализовывал алгоритмы Dijsktra и A*. Теперь мне нужно реализовать генетический алгоритм, и у меня есть проблема. Во-первых, я покажу вам, как выглядит мое представление карты. Есть 7 различных видов местности (0 - начало, 7 - конец, 1-4 нормальных, которые можно пройти, 5-6 не пройти). Вот код для этого в Python (самая важная часть кода, на мой взгляд, для понимания проблемы-это соседи функций:
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


Это все, что я придумываю. Я понятия не имею, как сделать другие шаги для генетического алгоритма, такие как отбор, скрещивание и Мутация на данных, которые у меня есть. Я надеюсь, что вы можете направлять меня и давать некоторые подсказки (если есть полный код для того, что мне нужно, было бы также хорошо проверить и узнать из него)

0 Ответов