3
$\begingroup$

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?
Improve this question
$\endgroup$
5
  • $\begingroup$ Why should the results not be very close? $\endgroup$
    – Christopher Louden
    Feb 19, 2014 at 15:35
  • $\begingroup$ I don't mind if the population converges to a single solution eventually after a few hundred iterations, but converging so quickly means it isn't exploring much of the solution space. $\endgroup$
    – chippies
    Feb 19, 2014 at 18:16
  • $\begingroup$ How do you generate your initial population? I would also suggest using a known "GA framework". That is, instead of rolling everything out yourself, consider testing your methods in say MATLAB with the GA toolbox. $\endgroup$
    – Juho
    Mar 3, 2014 at 12:46
  • $\begingroup$ @Juho The initial population is generated using a normal distribution for each of the 7 variables. The centre of that spread of points get determined using a brute force search. I have tried increasing and decreasing the standard deviations for the random values by a factor of 10 each way without resolving this problem. All that happens if I choose too large a standard deviation is that the GA converges to a worse solution, but it still converges very rapidly. $\endgroup$
    – chippies
    Mar 3, 2014 at 13:01
  • $\begingroup$ @Juho I rolled my own version because the fitness function is slow to evaluate on a CPU, but can be done quickly on a GPU. I do not have access to the latest version of Matlab with its CUDA functionality, not that that would work as the powerful GPUs I have access to are all AMD Radeons. $\endgroup$
    – chippies
    Mar 3, 2014 at 13:04

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Mangara, I've implemented tournament selection by shuffling the population (with all previous generations) then, each tournament, uses the first K individuals from the shuffled list and removes them. Once the list is empty, I reshuffle the population and keep going. This seems to be working but is it theoretically sound or am I abusing shuffling? I have gone this route because it is the fastest I can come up with. $\endgroup$
    – chippies
    Apr 2, 2014 at 11:15
  • $\begingroup$ No, that sounds like it should work. It reduces the randomness a little bit by guaranteeing that each individual will be picked the same number of times, but that shouldn't change too much. If the answer helped, please mark it as accepted. $\endgroup$
    – Mangara
    Apr 2, 2014 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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