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?
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.