Genetic Algorithms

Genetic algorithms are algorithms for solving problems in AI where you do not care about the path that you took to arrive at the goal, but only the goal. So for example, if you need to find

I will explain the main parts of the algorithm, and for each part explain a bit about the algorithm as we go.  Try to keep normal natural selection rules in mind as we go.  As we go we will discuss the Eight Queens problem.

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3 – Wikipedia

Initial Population

To begin with, you need an initial population.  In real genetics, this would be a representative grouping of the community, but in our case, it will either be a randomly generated solution, or we could start with one that we felt was a better guess of the solution.  So in the eight queens problem mentioned above, we might start with 8 sets of coordinates.  One position for each queen on the board. Storing the position as a row and column.

  member = [(2,4),(4,5),(6,0),(1,3),(2,6),(6,2),(1,0),(3,6)]

However, that randomly created population does not take in all the insights that we might have.  For instance, knowing that queens attack by row, column and diagonal we know that no two queens can be in the same row, or column.  With this in mind, we can significantly improve the speed of the algorithm, simply by removing either row or column from our data.  This would be faster to solve.

  member = [2,5,0,3,6,2,0,6)]

Using intuition and understanding of the problem helps us to choose the best initial population creation method.

Fitness Function

In natural selection, the members that will survive and breed are the fittest.  What that means is that the members that are best suited for their environment. So, we must think of how we would represent being well suited, in a function so that our AI will be able to judge the member’s fitness as a solution to the problem.

In the case of the four queens, we can count the number of queens that are currently attacking, being attacked or count how many attackers each queen has.  We are not judging anyone queen or one position instead we are judging the member or board as a whole.

Let’s say we choose the number of queens under attack as our fitness function. The example above would result in a board like the image below.

As you can see, we have used the numbers to represent their locations in their columns, starting with 0 at the bottom up to 7 as the top row.  Queens can attack in any direction (N, NE, E, SE, S, SW,W,NW.)  So the queen in the first column (col 0) is attacked by 2 queens, so we count that as -1 for the member (members are boards.)  Moving along the second column’s queen is also being attacked by 1 queen, so the member gets -2. Continuing on the member’s value will be -8, as all queens are under attack.

Let’s now randomly generate a few more boards.

  members = [
      [2,4,7,4,6,4,4,2],
      [3,2,7,5,2,4,1,1],
      [2,4,4,1,5,1,2,4],
      [2,5,0,3,6,2,0,6]
]

Each of the members will now be calculated according to our fitness function. The first member is a -7, the second is -7, the third is -7 and the last we already calculated at -8.

Selection

Selection in the wild is dependent on environmental pressure.  Here the pressure is to get the answer!  Looking at our three boards, it seems we would be best to drop the last board, that one will not get the opportunity to breed because its fitness in this world is very poor.

The process of selection is using the fitness function to choose the top members of the population to breed.  Only those top members continue on.  The math behind the selection process is simply to total up all the member’s scores and create a weighted average.  Then randomly select from all the members of the population when we want to breed one.

Let’s say we rolled the dice, and randomly selected our first and second member.

Crossover

This would be the same as mixing the DNA in the wild, or breeding. Mendel would be so proud! With the selected members we have chosen we will breed them. Breeding is whatever action is taken to use parts of each of the solutions in order to try to mix up a better solution.

In our case, we are going to split the member’s boards in half, and take half of each solution, and combine them. So we will create two output boards.  The boards will combine the first six queen positions from one board, and the last four from another.  (The reason I am not picking a 50/50 split, is because they might mate again, and we would end up with the originals again.)

This results in:

  members = [
      [2,4,7,4,6,4,1,1],
      [3,2,7,5,2,4,4,2]
]

Mutation

In the real world, mutations are incredibly rare, and most mutations are not going to help the organism to survive.  But it is a very important part of evolution!  It is also a very important part of our algorithm. As we progress with our population, it is possible to stagnate and have the population not change much, so by introducing random mutations, we can guarantee that we will keep it moving.  Not too much mutation however or you may slow your approach to a good solution.

For this example, we might allow up to one position per member to be mutated, and we might give that a 50/50 chance of happening.  A mutation, in this case, is one position being randomly altered.

Conclusion

Well, with our single change there, we might think we are not on our way to a solution, but I guarantee you we will find one.  And it will be much faster than repositioning each queen one time in a loop and checking if the board is good yet.

I hope that helps make it more understandable, it certainly helped me to write this!

Attribution: Chess Queen