How to create my population of genetic algorithm?

Question

A problem given and I should find the 5 best paths from start to Goal with a genetic-algorithm. Image of the playground is shown here:

1

Playground has one start point, one Goal and some barriers. Answers shouldn't clash with barriers. I am going to use Python-3.x for my implementation.

I tried to convert my playground to a 2D numpy array. 1's are tiles which we can't go there because they are barriers, and 0's are the tiles which we can go.

grid = np.array([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

start = (12,0)
goal = (0,10)

Now I don't know how to create my initial population to work with other GA operators such as crossover and mutation.

I think i should have some functions that make a path from start to goal with knowing the limitations and store them as my population.

Answer 1

In genetic algorithm, the population is a collection of candidate solutions, which evolve during iterations. The initial population is usually generated randomly. (link to source)

For example one solution(or one candidate of the initial population) may be this:

([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 1, 1, 1, 0, 0],
[0, *, *, *, *, *, *, *, *, *, *, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[*, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

where a trail of *'s is a path from (12, 0) to (0, 10).

So now you need to figure out a way to randomly generate a path of *'s which start at start at end at end. The naive approach is by using a random direction left, right, up and down. If that direction is blocked by a boundary or 1, choose a different direction. Continue until you reach the end.

Also, a path may have *'s adjacent to each other, as seen above. (3, 11) and (3, 12) contains *'s but are not part of the continuous trail. For this use different numbers to represent the direction or I would suggest using unicode for arrows, e.g. \u2190 is for left arrow.

Hope this helps.

Answer 2

As you already know the size of your search space (it's the size of the square in your figure) you may initialize your population from an integer uniform distribution using this information.

I don't know the square's tile size, but let's suppose it's [15,15]. Each individual of your population is going to be 2D, right? So, as you're using python, and considering the population size equals 10, you should do something like:

import numpy as np
pop = np.random.randint(0,15,[10,2])

Thus, each individual will take place in a position in the square. For now, you don't need to worry if the individual is in a forbidden place. You should handle it as a constraint in your selection phase.

And for sure, you need to formulate your fitness function in order to punish those individuals who are in forbidden places. But you don't use it to start your population, you use to select the best individuals, did you get it?

There are some techniques to handle constraints, and I suggest you read some of them in this paper or just seeing a code example.