Measuring and maintaining the diversity of individuals in Genetic Algorithm 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?
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 occupied
with “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 &amp; Shane Legg).