0
障害物がある地形で最適な経路を見つけるためのアルゴリズムを準備しています。これまで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
です。これはすべて私が発明したものです。私は、データの選択、クロスオーバー、突然変異などの遺伝的アルゴリズムのための他のステップをどうやって行うのか分かりません。私はあなたが私を導き、いくつかのヒントを与えることができることを願っています（もし私が必要とするものの完全なコードがあればそれをチェックして学ぶのも良いでしょう）。
私の個人的な意見は、** A ***のようなものを使用できるときはいつでも、遺伝的アルゴリズムではなく、それに固執すべきだということです。これをやろうとする特別な理由はありますか？ –