How do I implement genetic algorithm on grid board to find optimal path

Question

I am preparing algorithms for optimal path finding in terrain with obstacles. Till now i implemented Dijsktra and A* algorithms. Now i have to implement genetic algorithm and I have problem.

Firstly I will show you how my map representation looks. There are 7 different kinds of terrain (0- start, 7- end, 1-4 normal which can be passed, 5-6 cannot pass). Here is code for that in Python (the most important part of code, in my opinion, to understand problem is function 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

I have no idea how to implement genetic algorithm from theoretical point because of my map and neighbor representation and i cannot change them.

What I did:

I prepared starting population using modification of my A* which find nearly the easiest connection from start to end without checking cost of that. Here's code

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

That's all I invent. I have no idea how to do other steps for genetic algorithm like selection, crossover and mutation on data i have. I hope you can guide me and give some hints (if there is full code for what I need it would be also good to check and learn from it)

Answer 1

A simple GA-based method for a 2D grid is to fractionate chromosomes (binary strings) into moves, eg:

00 = down
10 = left
01 = right
11 = up

The run(chromosome) function, given a chromosome, performs the moves from the starting point (code 0on the map) and returns the final point reached:

(f_y, f_x) = run(chromosome)

The fitness function is the distance from the goal point:

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

or also:

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

Both fitness functions assume that greater is better.

Now an example:

1. S is the starting point, F is the final point reached, G is the goal point and * a wall
2. chromosome is 00 00 01 01 00 00 00 01 01 11 i.e. ↓ ↓ → → ↓ ↓ ↓ → → ↑

3. run(S, chromosome) operates in the following way:

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

   The function simply ignores impossible moves

4. Fitness is -2

Standard One point crossover / two points crossover (or other forms) can be used, e.g.:

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

The first child (00 00 01 01 00 00 01 01 11 01) has fitness greater than both parents (-1):

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

NOTES

• Instead of ignoring impossible moves (as in the above example), the scheme can be extended using a gene repair operator which erases bad moves and adds random moves to fill up the chromosome (more complex but it takes advantage of full available length).
• Usually, in GA, chromosomes have a fixed length: allowing a length 30% - 40% longer than the best path is a good idea.

• Any path to the goal is considered up to standard. Searching for the best path requires adding a penalty term to the fitness function for deviations from the shortest path, e.g:

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

• A completely different approach is using GA to optimize A* (further details in Using a Genetic Algorithm to Explore A*-like Pathfinding Algorithms by Ryan Leigh, Sushil J. Louis and Chris Miles).

• A third option, probably the most interesting from an AI point of view, is Genetic Programming (see Evolving Pathfinding Algorithms Using Genetic Programming by Rick Strom for an example).
• This is a good example of the flexibility of GA, but A* is ways better.