Last time, we started to work on the thieves’ problem and some of you were able to find a nice solution. You usually used brute force or tuned the parameters of the algorithm. Today, we will learn how to obtain similarly good results with less effort, more effectively and more often.

Genetic operators

During the last lesson, I asked you not to change the genetic operators of the algorithm and let you experiment with the fitness, selection and parameters only, so that you could see how these affect the performance of the evolution.

However, some of you already knew that changing the genetic operators can make a bigger impact.

The choice of genetic operators depends a lot on the encoding of the individual. In our case the encoding is rather simple and therefore we can use simple genetic operators.

We have a few options for the crossover operator:

  • One point crossover - that’s what we used last time, it chooses a random position in the individual and swaps everything after this position between the two individuals
  • Two point crossover - two positions in the individual are chosen randomly and everything between them is swapped between the two parents, you can of course generalize this to n-point crossover
  • Uniform crossover - goes through the individual and decides on each position randomly whether to swap it with the other parent or not, it is in fact a generalization of the n-point crossover

There are also a few simple mutations we can use:

  • Mutation, which changes a random position to a random valid value - we used this one last time, and it is often the first one you will try
  • Mutation, which swaps parts of the encoding inside the individual - it randomly selects two parts of the same individual and swaps them, in the most simple case, each part consist of only one gene

What does the first and second mutation do in our case with the bins? The first mutation takes a thing from one bin and puts in into another. The second one takes things from two bins and swaps them between them (in the case only two genes are swapped, otherwise it is more complicated). Is any of these mutations better for this problem?

Informed operators

The above mentioned operators work completely randomly, however, we can also create operators which take into account the particular instance of the particular problem the algorithm is solving. Such operators are called informed operators.

In our case, we can imagine an informed mutation. It can, for example take a thing from a heavy bin and put it into a light bin. We can go even further and take several things from one bin and other things from another bin in such a way, that the difference between the two bins is minimized.

In the extreme case, we can even solve the problem in the mutation. However, the question is, whether we still have an evolutionary algorithm in such case, whether this kind of approach will be effective, and whether it would not be better to just run the mutation without the rest of the algorithm.

It is also possible to create informed crossover, however it is not easy for the thieves’ problem. Even generally, informed mutation is more common than informed crossover.

Naposledy změněno: pondělí, 19. října 2020, 10.52