4
$\begingroup$

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?
$\endgroup$
6
$\begingroup$

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:

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

$\endgroup$
  • 1
    $\begingroup$ This visualization is great. $\endgroup$ – Gabriel Feb 7 '17 at 11:27
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.