patternModerate
Measuring and maintaining the diversity of individuals in Genetic Algorithm
Viewed 0 times
thediversitygeneticalgorithmmeasuringandmaintainingindividuals
Problem
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:
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#69902, answer score: 10
Revisions (0)
No revisions yet.