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:

1. 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?
2. 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 & Shane Legg).

• This visualization is great. – Gabriel Feb 7 '17 at 11:27

What you suggest is OK, but should be done with caution. After all, there is no functional difference between keeping the population from converging on a local peak and keeping the population from converging on the global peak.

One approach is to use this variant of @manlio's formula $$\mathrm{score}(i) = \mathrm{fitness}(i) + k(g)\, \mathrm{diversity}(i)\,,$$ where now instead of a scaling constant $k$ we apply a scaling function $(g)$ that decreases with increasing generation number $g$. The idea is that initially $k(g)$ is high, keeping diversity up, but drops with time as the population becomes more and more likely to have generated a point in the vicinity of the global peak, allowing convergence to that peak.

Of course, like all suggestions, this one comes with no guarantees.