4
$\begingroup$

I was wondering if a genetic algorithm is useful if the optimization problem has several optimal solutions.

My thought was that I should not use it since when combining two members of a population who have good fitness but are close to different optimal solutions, the child will get retarded.

Is this thinking wrong? If so, why?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It sounds as though your approach results in a single child. In our genetic implementations, we always have multiple children; some are averages, some are mutations, etc. However, our generations always additionally contain $n$ top performers from the previous generation and slightly mutated versions of those top performers. We find this allows us to find multiple optimal solutions since we allow multiple paths to be followed. $\endgroup$
    – David Hoelzer
    Commented Nov 26, 2021 at 1:35
  • $\begingroup$ have you checked this article on wikipedia about evolutionary multimodal optimization? en.wikipedia.org/wiki/Evolutionary_multimodal_optimization $\endgroup$
    – Sanyou
    Commented Dec 26, 2021 at 15:33
  • $\begingroup$ I don't think I've ever seen a genetic algorithm applied to a problem where there was a unique optimal solution! $\endgroup$
    – Stef
    Commented Apr 26, 2022 at 12:17

2 Answers 2

Reset to default
1
$\begingroup$

Genetic algorithms (GA) have populations where it has an offspring in every generation usually the same quantity than the original population, so, if a child results from two good solutions (parents) but very different and it has a bad fitness, it will be not selected for being part of the next generation (elitism, where only the best n individual survive). But maybe you can find a new and good solution from that combination, and, in that case, it will be part of the new generation.

Maybe, if your problem has multiple solutions, the population can be formed by clusters of solutions that improve between them.

But there are many algorithms in GA (and Evolutionary Algorithms in general), so you need to read the details. Fortunately, there are many frameworks where only you need to define your problem and it can rapidly make comparisons between them.

Improve this answer
$\endgroup$
0
$\begingroup$

Genetic algorithms like many other machine learning algorithms have two forces in action, exploration and exploitation.

For GAs these are crossover and mutation. Crossover (the production of a child from two parent members) can often produce wildly different children dispersing them around the solution space. Exploring the solution space, if you will.

If two parents are near optimal solutions and their alleles are significantly different unless the crossover happens to also be near another optimal solution it is likely to produce a poorly scoring child.

But that is not the only mechanism. Mutation makes minor adjustments to a member of the population. Along with elitism, often nudging the population towards nearby optimums, exploiting their proximity to a good solution.

So, while crossover between two parents near different optimums may not produce strong children, mutation may move the children of similar parents towards a local optimum. Lastly, lets not forget that crossover need not necessarily widely spread children. It is possible in both single and two point crossover to produce a child which differs from a parent by a single allele.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .