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.
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:
There are also a few simple mutations we can use:
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 mutation better for this problem?
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.