While I was using the Genetic Algorithm to generate full correct Sudoku grids starting from a population of random grids, I occasionally face the problem of the process being stuck on a local maxima until the population loses its diversity.
So, I decided to find a mechanism for maintaining the diversity of the population to avoid the problem. What I thought about was:
Measuring the diversity of each individual by computing how different it is from the rest of the population:
For each individual $i$ : $$diversity_i = \sum_j distance(i, j)$$ and I used the hamming distance as the $distance$ function.
Ranking the individuals (for selection) based on both their diversity and their fitness.
I faced two problem with this approach:
- Computing the diversity this way is expensive as it requires $n^2$ call to the $distance$ function (which is itself not a constant time function), raising the following question: what is a relatively optimal way for measuring the diversity of a population?
- How to rank the individuals of a population based on both diversity and fitness?