How to stop genetic algorithm population converging to a single value

ignougroup
Problem Detail: 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:

  1. 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)$.
  2. 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 mutating a child from 5% to 50% but I still have the problem that all the individuals in the population become very similar within the first 20 or so iterations. Please advise on what I’m doing wrong. I should point out that the algorithm, despite this problem, does get fairly close to the optimal solution. I know this because the quantity to maximise is the correlation between between two things (no more details, sorry) and I can get to about 0.94 (the maximum physically possible is always 1.0). However, I am concerned that the GA is not covering enough of the solution space, causing it to miss the global maximum. My questions

  1. Are either of the above cross-over methods correct?
  2. Is it ok to re-use parents in cross-over? Stated another way, is polygamy a good idea in this algorithm or should I change that part to ensure that no parent gets used more than once?
  3. Should I mutate the parents as well?
  4. What should I do with the 90% of parents that did not get used in the reproduction?
Asked By : chippies

Answered By : Mangara

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22216