snippetMinor
How to stop genetic algorithm population converging to a single value
Viewed 0 times
howvaluestopgeneticalgorithmconvergingsinglepopulation
Problem
I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem. All seven variables are floating point numbers. The problem is that the entire population seems to converge to very nearly the same point in the solution space within about 20 generations, even if I increase the population size by 10x.
Attempted solutions
Starting with a parent population $\vec{x}^{(j)}$, where $j$ is the individual's index in the population, I take the best 10% (i.e. highest fitness scores) to reproduce. First I perform cross-over producing 2 children for every randomly selected pair of parents. The parents can be re-used (is that a problem?). About 5% of the children get mutated randomly.
I've tried two variations of cross-over but both have the same problem:
-
Calculating a 7 element weights vector $[w_i]$ and calculating the children's elements as $c_i^{(1)}=w_i x_i^{(1)} + (1-w_i)x_i^{(2)}$ and $c_i^{(2)}=(1-w_i)x_i^{(1)} + w_i x_i^{(2)}$. The parents ith elements are $x_i^{(1)}$ for parent 1 and $x_i^{(2)}$ for parent 2. Each weight is a sample from a uniform random variable in $[0.0;1.0)$.
-
Confining the weights $w_i$ to be either $0.0$ or $1.0$, i.e. randomly exchanging elements of the two parents genomes to create the children.
The mutation operation consists of randomly choosing one of the child's 7 elements and adding some Gaussian noise to it. The standard deviation of that noise differs for each element since the elements have different physical units.
Afterwards, I evaluate the fitness of the children and keep the best few hundred or thousand (setting that I choose at the start of the algorithm) out of the combined population of parents and children to give the next generation. Note that the parents do not get mutated, especially since I want to preserve the best from the parent generation in case none of the children improve on it.
I've tried population sizes from 1024 to 20480 and have also tried increasing the probability of m
Attempted solutions
Starting with a parent population $\vec{x}^{(j)}$, where $j$ is the individual's index in the population, I take the best 10% (i.e. highest fitness scores) to reproduce. First I perform cross-over producing 2 children for every randomly selected pair of parents. The parents can be re-used (is that a problem?). About 5% of the children get mutated randomly.
I've tried two variations of cross-over but both have the same problem:
-
Calculating a 7 element weights vector $[w_i]$ and calculating the children's elements as $c_i^{(1)}=w_i x_i^{(1)} + (1-w_i)x_i^{(2)}$ and $c_i^{(2)}=(1-w_i)x_i^{(1)} + w_i x_i^{(2)}$. The parents ith elements are $x_i^{(1)}$ for parent 1 and $x_i^{(2)}$ for parent 2. Each weight is a sample from a uniform random variable in $[0.0;1.0)$.
-
Confining the weights $w_i$ to be either $0.0$ or $1.0$, i.e. randomly exchanging elements of the two parents genomes to create the children.
The mutation operation consists of randomly choosing one of the child's 7 elements and adding some Gaussian noise to it. The standard deviation of that noise differs for each element since the elements have different physical units.
Afterwards, I evaluate the fitness of the children and keep the best few hundred or thousand (setting that I choose at the start of the algorithm) out of the combined population of parents and children to give the next generation. Note that the parents do not get mutated, especially since I want to preserve the best from the parent generation in case none of the children improve on it.
I've tried population sizes from 1024 to 20480 and have also tried increasing the probability of m
Solution
Your selection method may lie at the root of this. You are currently using truncation selection, which applies a very high selective pressure and reduces diversity by not allowing elements from worse solutions to be preserved to possibly be useful again in future generations.
You should try different selection methods, in particular roulette selection or tournament selection, and see if that makes a difference. Most implementations I have seen also keep all generated offspring, regardless of quality. The intuition is that, if a child has low quality they will eventually die out anyway, and they might still carry useful information.
You should try different selection methods, in particular roulette selection or tournament selection, and see if that makes a difference. Most implementations I have seen also keep all generated offspring, regardless of quality. The intuition is that, if a child has low quality they will eventually die out anyway, and they might still carry useful information.
Context
StackExchange Computer Science Q#22216, answer score: 4
Revisions (0)
No revisions yet.