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?
Measuring and maintaining the diversity of individuals in Genetic Algorithm
genetic algorithms;evolutionary computing
How to rank the individuals of a population based on both diversity and fitness?You can combine diversity and fitness into a single score: $$score(i) = fitness(i) + k \cdot diversity(i)$$It's a standard approach and doesn't require significant changes to the algorithm. Unfortunately $k$ is problem-specific.Alternatively change the standard GA to a multi-objective evolutionary  algorithm (MOEA).This needs a lot of changes (e.g. the algorithm now needs to maintain a set of Pareto optimal individuals).MOEA is probably a overkill for what you're doing. Indeed it's very interesting and a good training.Computing the diversity this way is expensive... What is a relatively optimal way for measuring the diversity of a population?The genotypic / structural approach to diversity isn't the only workable one.Instead of measuring how differently the individuals look like, measure how  differently those individuals behave (phenotypic diversity).A great advantage is the ease of computation: often an acceptable approximation is the simple fitness value.Schemes like Fitness Uniform Selection / Fitness Uniform Optimization generate selection pressure toward sparsely populated fitness regions, not necessarily toward higher fitness:Evolution of the population under FUSS versus standard selection schemes (STD): STD may get stuck in a local optimum if all unfit individuals were eliminated too quickly. In FUSS, all fitness levels remain occupiedwith free drift within and in-between fitness levels, from which new mutants are steadily created, occasionally leading to further evolution in a more promising direction (from Fitness Uniform Optimization - Marcus Hutter & Shane Legg).