0
장애물이있는 지형에서 최적의 경로 찾기 알고리즘을 준비 중입니다. 지금까지 Dijsktra와 A * 알고리즘을 구현했습니다. 이제 유전자 알고리즘을 구현해야하고 문제가 있습니다.최적의 경로를 찾기 위해 그리드 보드에 유전 알고리즘을 어떻게 구현합니까?
먼저지도 표현이 어떻게 보이는지 보여 드리겠습니다. 지형은 7 가지 종류가 있습니다 (0- 시작, 7- 끝, 통과 할 수있는 1-4 법선, 5-6 통과 할 수 없음). 내가 어떻게 때문에 내지도의 이론적 인 관점에서 유전자 알고리즘을 구현하는 아무 생각이
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
: 여기 파이썬에서 그것을위한 코드 (코드의 가장 중요한 부분은 문제가 기능 neighbors 이해하기 위해, 제 생각에)입니다 이웃 표현과 나는 그들을 바꿀 수 없다.
내가 무슨 짓을 :
내가 거의 그 비용을 확인하지 않고 처음부터 끝까지 가장 쉬운 연결을 찾을 수있는 * 내 (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 ***와 같은 것을 사용할 수있을 때마다 유전자 알고리즘보다는 그걸 고수해야한다는 것입니다. 이를 시도한 특별한 이유가 있습니까? –