The Introduction To Artificial Intelligence Algorithms #4 - Genetic Algorithms

So let's call one solution an individual or a chromosome and several solutions a population or a genome. Who is the strongest individual in the population? The one that is best adapted to life in the environment. We say that this individual has the highest fitness.

Algorithm

With this algorithm, it is useful to look under the hood immediately

1. we create a population = random solutions (individuals, chromosomes)
2. until we are connected to the result
   a. create a new empty population new_population
   b. to new_population, add the elite of the best solutions from the population
   c. until |new_population| < |population|
         i.   parent1 = random individual from the population
         ii.  parent2 = random individual from the population
         iii. child = crossover(parent1, parent2)
         iv. mutation (child)
         v.  new_population add child
   d. population = new_population

So what happens in our cycle (2)? We let a few of the best solutions survive without any change to the next population. And we generate the remaining offspring by crossing and mutations. We select parents for crossing by controlled randomness so that better individuals have a greater chance to participate in crossing. But let's try all these steps in turn.

Selection of parents for crossover (Selection)

Several algorithms are used to select parents:

1. Tournament selection - we select n individuals from the population. For crossing, we select the one with the highest fitness
2. Roulette - each individual of the population gets a piece on the wheel of fortune as big as his fitness is within the population. We spin the wheel and whoever it falls on will be selected for the next population
3. and more

In practice, however, I used only the first 2, while the tournament is much easier to implement.

Crossover

Both parents are chromosomes that we can cut in any place. If we cut both parents in the same place, we can form a new individual from their opposite parts. There will be a picture soon, but first let's imagine what an individual looks like in the problem of eight queens. The individual will consist of 8 numbers. The first number determines on which row in the first column the queen is located.

So, for example, the individual { 1, 3, 5, 3, 7, 7, 0, 5 } represents such a checkerboard.

Thus, by crossing parents { 1, 3, 5, 7, 7, 0, 5 } and { 7, 4, 1, 0, 2, 6, 4, 7} we can get, for example, offspring { 1, 3, 5, 0, 2 , 6, 4, 7 } and { 7, 4, 1, 3, 7, 7, 0, 5}. That is if the crossing point is equal to 3.

‍

Mutation

A mutation is just an additional small (if at all) modification of the offspring. We never apply it to parents. We can imagine it, for example, as follows: With a probability of 10%, choose a random characteristic of an individual and assign it a random value. We would modify the first child from the previous picture by mutation, for example, as follows:

‍

Solution to the 8 checkers problem

Now let's show how exactly we can program the solution for the 8 queens problem. We will follow the instructions above.

1. Let's create a random population (1)

var populacia = (0 until populationSize).map { nahodnyChromozom() }
fun nahodnyChromozom() = (0 until chromosomeSize).map { nahodnyGen() }

2. In the cycle, we save a few of the best individuals from the previous population in the new population (2b)

val najlepsi_jedinci = (0 until pocet_najlepsich).map { populacia[it] }

3. We choose two parents using a tournament, obtain a child by crossing these parents, and possibly mutate the child (2c)

val individual1 = turnaj()
val individual2 = turnaj()
val child = krizenie(individual1, individual2)
mutacia(child)

4. We save the new population and continue (2d)

‍

You can find the full solution to the eight queens problem on this gist. The solution is slower than in the case of simulated annealing. It is practically usable for ~20 ladies. There can be several reasons. Either the mutation rate is low, or the population converges too quickly into too similar individuals, or...or...

Unfortunately, with optimization algorithms, we can never determine the best parameters for our problem for the first time.

Next time, let's try to look at other optimization algorithms. Specifically, ACO and PSO. If these abbreviations do not mean anything to you, at least I will surprise you 🙂