.jpg)
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.
With this algorithm, it is useful to look under the hood immediately
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.
Several algorithms are used to select parents:
In practice, however, I used only the first 2, while the tournament is much easier to implement.
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.
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:
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)
2. In the cycle, we save a few of the best individuals from the previous population in the new population (2b)
3. We choose two parents using a tournament, obtain a child by crossing these parents, and possibly mutate the child (2c)
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 🙂
