Measuring and maintaining the diversity of individuals in Genetic Algorithm

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

Here's a thought, not tried, and not backed up by literature. But at least it's more computationally efficient than your current approach. If anyone has thoughts or references, please leave a comment.

I'll assume that your chromosomes consist of binary genes, but an extension to real-valued genes might be possible.

For each gene g you could compute the expected value E(g) of that gene, which is just the average across all individuals. If g is 0 in 20% of the population and 1 in the other 80%, then E(g) would be 0.8. This is an O(#individuals × #genes) computation.

The diversity of an individual i can then be calculated as the inverse of the probability P(i) of encountering that individual. For each gene g in the individual, compute P(g); e.g. if g is 0 in this individual and E(g) is 0.8, then P(g) is 0.2. The final P(i) is simply the product of P(g) over all genes. Since this is lower for more "diverse" individuals, we take the reciprocal 1 / P(g) as a measure for diversity. This is again an O(#individuals × #genes) computation.