# Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution

I wanted to make a tool which minimizes the interference between antennas.

Currently, the tool is very limited for prototyping reasons. It can only place an antenna every 1 meters. The available space that the antennas can be placed is 1 dimensional and is 15 meters wide.

The user can only decide how many antennas will be used (e.g. 3 antennas).

I decided to encode the setup as follows: a binary array where 1 represents an antenna and 0 is an empty space because it seemed straightforward. The length of the array is thus the available space to place those antennas (= 15 meters).

For example, here are all the antennas on the left: 11100 00000 00000 and here they are on the right: 00000 00000 00111.

My mutate function enforces that the offspring contains only 3 antennas. If it is not the case the mutate function will try again. Same thing for the crossover.

In this case, the total search space consists of 455 solutions since there are only 455 ways to place those antennas.

I benchmarked a little bit the algorithm and I got the following results:

• If I use a 5% of the search space, thus a population of 7 with 4 generations (7 * 4 = 28) then I got a solution which is better than 96% of the 455 solutions.

• If I use a population of 10% of the search space, thus a population of 9 with 5 generations (9 * 5 = 45) then I got a solution which is better than 98% of the 455 solutions

• The higher the mutation rate the better the results. This one is very strange since the algorithm becomes more and more a random search. I thought that it should normally give worst results. The difference of the results is 1-2% better when using a mutation rate of e.g. 0.8 instead of 1 / n = 1 / 15 (where n is the length of the encoding).

Finally, I have two questions:

I got a good solution but never the best one, even by using 10% of the search space. Is this normal?

A higher mutation rate gives me better results? Is it because I am working with a toy problem? Or is my encoding bad?

• Do you plan on increasing the search space in the future? Why can't you score all 455 possible solutions and take the best? – bbejot May 11 '17 at 2:20
• @bbejot yes I plan to increase the search space significantly but for the first tests, I kept the search space small. This gives me the possibility to see how good my result and if there are any issues with it. – dll May 11 '17 at 7:15

I'll start with the second question because it's easier. How could increasing the mutation rate improve the results?

Genetic algorithms can beat random searches when they converge on the right answer. Similar to other machine learning algorithms, genetic algorithms have an "explore" phase and a "converge" phase. If the algorithm doesn't run long enough (enough rounds) to enter the converge phase, then a higher mutation rate will likely give you better results. The other culprit may be that the utility score of offspring may be independent of the utility score of the parents even though their parameters are very similar. If this is the case (especially around "good" results) then convergence may be impossible and random search would outperform genetic algorithms.

The other question "Why didn't I ever find the best solution?" could also have a few explanations. First, you could have just been unlucky - especially if you didn't run your experiment very many times. Intuitively, a single run searching 10% of the space will have roughly a 10% chance of finding the best solution. Second, it may be that all antenna configurations which are similar to an optimal solution have low scores. This would make it less likely to produce the optimal solution genetically.

I would say you have at least chosen a bad encoding. At minimum, enforcing that all crossover or mutation results have exactly three 1-s limits the possible population members to a very sparse subset of the chosen binary space.

Further, this encoding doesn't appear to work well according to G.A theory. The power of a well-designed genetic search derives (according to theory) from implicit parallelism. The idea here is that each explicit population member - say '1101100010' - also implicitly represents all of its sub-patterns - eg, '1xxxxxxxxx', 'xx011xxxxx', 'x1xxxx0xx0', and so on, where 'x' is a don't-care. If in the current population, all members matching '1xxxxxxxxx' have a higher average fitness than all members matching '0xxxxxxxxx', then members starting with a leading 1 will tend to fill up subsequent generations. These combinations are called 'schema'; while a G.A is explicitly evaluating $N$ explicit designs at a time, it is implicitly evaluating at least $N^3$ schema at a time. But that only works if each schema is manifested by a large number of possible population members. Your encoding seems to greatly cut down the number of achievable schema.

Also, the whole point of crossover is to combine as many good schema from the parent members as possible, while disrupting as few as possible. In your encoding, if (for example) one parent has all three 1-s to the left, and the other has all three 1-s to the right, enforcing only three 1-s in the child actually destroys all meaningful schema from both parents. And that is the typical outcome.

What you need is an encoding where all, or nearly all, possible strings represent legitimate legitimate population members, and where crossover naturally produces legitimate members. For some reason my gut instinct here is to advise you to study the encoding schemes used to apply G.A-s to the Travelling Salesman problem.