32

I was introduced to genetic algorithms recently by this MSDN article, in which he calls them combinatorial evolution, but it seems to be the same thing, and am struggling to understand how combining two potential solutions will always produce a new solution that is at least as good as its parents.

Why is this so? Surely combining might produce something worse.

As far as I understand it, the algorithm is based on the concept that when a male and female of a species produce offspring, those offspring will have characteristics of both parents. Some combinations will be better, some worse and some just as good. The ones that are better (for whatever defintion of "better" is appropriate) stand more chance of surviving and producing offpsring that have the improved characteristics. However, there will be combinations that are weaker. Why isn't this an issue with GA?

  • 12
    However, there will be combinations that are weaker. Why isn't this an issue with GA? -- Because the weaker combinations are discarded. – Robert Harvey Dec 4 '16 at 16:11
  • 6
    We know that the next generation won't be worse because we don't throw away the good ones but we do throw away the bad ones. And there is a reasonable chance that combining some of the good ones will make an even better one, but it's not guaranteed. – immibis Dec 4 '16 at 22:03
  • 7
    Why isn't this an issue with GA? Well, it is, or more exactly, it might be. One of the many (many) parameters to optimize using GAs is the population size : if it's too low, you might only produce weaker individuals, but if it's too high, the computation time associated with the fitness function might be too high. – Loufylouf Dec 5 '16 at 7:14
  • 3
    It's a difference between breeding and weeding: the breeding stage may (will) produce worse offspring, but the weeding stage will (should) eliminate the worst-performing before the next breeding stage. – TripeHound Dec 5 '16 at 13:18
  • Thanks to all of you. If I understand correctly, it was the way he phrased it in the article that threw me off the trail. He said "The new, presumably very good, child Organism replaces a poor Organism" which prompted my question. Seems that was wrong :) – Avrohom Yisroel Dec 5 '16 at 16:22
43

A genetic algorithm tries to improve at each generation by culling the population. Every member is evaluated according to a fitness function, and only a high-scoring portion of them is allowed to reproduce.

You're right, though: there is no guarantee that the next generation will improve on its predecessor's score.

Consider Dawkins' weasel program: "evolving" the string "Methinks it is like a weasel". Starting from a population of random strings, the fitness function evaluates the closest textual match, which is perturbed to produce the next generation. With a simple crossover reproduction, two high-scoring strings that are combined could very easily produce lower-scoring offspring. Even "asexual" random mutation of a single high-fitness string could lower the child's fitness.

It's worth noting, I think, that this is not necessarily a flaw. With this kind of search, there is the idea of local maxima. A member of the population might represent a solution that's not the optimal result, but is the best that can be achieved without getting worse on the way.

Imagine that the fitness function for the weasel program doesn't only find the edit distance, but has some notion of "word", and tests whether the last word of the string is the name of an animal. Any animal name scores well, but "weasel" gets a big bonus.

Now what happens if "Methinks it is like a walrus" is evolved? It scores well. Not as well as the ultimate target string, but better than "Methinks it is like a walrut" or other close variations that could be reached by a single step of mutation.

The walrus string is a local maximum, and the search can get stuck there unless the program allows the next generation's score to be worse.

  • 1
    Relevant: youtube.com/watch?v=YT1vXXMsYak -- the demonstration of Dawkin's computer program is at about 12 minutes in, although the entire lecture is worth watching as it describes the basic theoretical basis on which evolution (whether biological or simulated) is grounded. – Periata Breatta Dec 4 '16 at 18:21
  • 24
    Indeed, you will sometimes allow a certain percentage of weaker scoring members to survive in order to increase "genetic diversity", as well as introduce completely random mutations that are not based on any existing member at all. – Jörg W Mittag Dec 4 '16 at 18:31
  • @JoshCaswell Thanks for this. Although all of the answers were excellent, I'm going to mark this as the accepted one as it covers everything I asked, and a couple of things I hadn't asked yet! – Avrohom Yisroel Dec 5 '16 at 16:31
  • Glad I could help, @AvrohomYisroel – Josh Caswell Dec 5 '16 at 16:40
6

We don't know it will get better, we do know that it won't get worse.

In every generation, does not consist just of the ospring of the best elements, but also includes the best elements themselves -- clones if you will. Since they are still present, they will score the same as before. Meaning that if none of the offspring are better, the previous generations winners will win again -- and be re-mutated / breed.

Consider: With an progenitor individual being a letter, eg A A mutated child being a defined by adding a number eg A1, cross-bread solutions being written with brackets around the parent eg (A1B2) And the fitness core of any indivisual writen after it -- higher being better [12]

For demonstration, consider a Pool of 5, where we keep the best 2. and fill with 1 mutate of each, plus a cross-breed

Generation 1

  • A [10]
  • B [5]
  • C [4]
  • D [3]
  • E [1]

Keep A,B, as they are the best two, and refill other 3 slots with there descendants

Generation 2

  • A [10]
  • B [5]
  • (AB) [7]
  • A1 [12]
  • B1 [4]

Keep A,and (AB), as they are the best 2 -- THis means that grandpa A will still be in the pool as most cildren work weaker

Generation 3

  • A [10]
  • (AB) [12]
  • (A(AB)) [14]
  • A2 [8]
  • (AB)1 [13]

Keep (AB)1 and (A(AB)) -- this time no grandparents were maintained, as two of their children beat them. But if (AB1) has have performed just slightly worse we would have kept (AB) instead.

This continues until the score stablize. Which indicates you've hit some kind of local maxima (potentially a global maxima). One why to detect this would be if the same individuals continue to be "cloned" into the next generation. (though for high dimensional problems that might take too long, so better perhaps to just check improvement < a particular tolerance)

  • 1
    "In every generation, does not consist just of the ospring of the best elements, but also includes the best elements themselves" This depends on the implementation. Some implementations don't do this. Doing so is sometimes called "elitism." – jpmc26 Dec 6 '16 at 1:23
4

In general, genetic algorithms work by creating a number of (random) variations on the parents in each generation. Then some selection function is applied, and the offspring which is most fit according to this function survives. So the offspring is not necessarily better since the variation is random, but combined with selection you get improvement over time.

  • 4
    Ah, so it sounds like the article was a little misleading. He said "The new, presumably very good, child Organism replaces a poor Organism" which is what confused me. I guess if he is combining loads of organisms, then overall we would expect an increase, even though individual new organisms might be weaker than previous ones. Is that right? Thanks – Avrohom Yisroel Dec 4 '16 at 16:47
  • @AvrohomYisroel: Exactly. – JacquesB Dec 4 '16 at 19:00
  • 1
    @AvrohomYisroel : Beware the approximate understanding of non-specialists. (Also, beware the precision "wall of jargon" of specialists.) – Eric Towers Dec 5 '16 at 0:22
  • @EricTowers Yeah, I see the problem! I thought he was an expert, judging by previous articles he's written, but he clearly seems to have made some big mistakes in this article. – Avrohom Yisroel Dec 5 '16 at 16:30
4

When I studied genetic algorithms in college it was explained like this :

Imagine a solution is combination of "genes", where each gene affect how good the solution as a whole is. When two solutions are mated, they genes are picked randomly from each parent.

Now, if gene leads, generally, to good solution, it's frequency in the gene pool increases. In extreme case, the gene will dominate the population.

So when you think about genetic algorithms (and evolution in general), you should not think about individuals. You should think about genes and populations as a whole. Even if one "best" solution is lost, it doesn't mean it's genes are lost.

There is also idea of elitism in genetic algorithms. It means, that best solution(s) are always kept across generations. This might speed up convergence of the algorithm, but it is easier for algorithm to get stuck in local optima.

2

GA algorithms are not deterministic, they don't guarantee to get an improvement in each generation, and they also don't guarantee to find a total optimum. However, the selection phase of an GA, using a fitness function, makes it more likely that "good solutions" will survive.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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