Evolutionary/Genetic Algorithms

[Loudmouth]

I was not talking to you. You be quiet.

I will not be quiet. I will continue to speak out against anti-science rhetoric when I see it.

 

[Loudmouth]

In other words, when it is stabilized, then the deleting of non-fits (step 3) will not produce more fits. Right?

More than likely, any additional changes will reduce the fitness of the design. In evolution, this is called a fitness peak.

A good way of visualizing this effect is by using playing cards. Deal yourself 5 random cards, and then draw cards 1 by 1, keeping only the cards that improve your poker hand and discarding cards to keep 5 cards in your hand. You will find that you will reach an endpoint where no new cards will improve your hand. At the same time, you may very well reach different hands each time you do the experiment. One time you may reach a straight flush. Another time you may reach 4 of a kind. The key is that there is no way to go from the peak of 4 of a kind to the peak of a straight flush without taking cards that reduce the fitness of your hand.

 

[digitalgoth]

More than likely, any additional changes will reduce the fitness of the design. In evolution, this is called a fitness peak.

A good way of visualizing this effect is by using playing cards. Deal yourself 5 random cards, and then draw cards 1 by 1, keeping only the cards that improve your poker hand and discarding cards to keep 5 cards in your hand. You will find that you will reach an endpoint where no new cards will improve your hand. At the same time, you may very well reach different hands each time you do the experiment. One time you may reach a straight flush. Another time you may reach 4 of a kind. The key is that there is no way to go from the peak of 4 of a kind to the peak of a straight flush without taking cards that reduce the fitness of your hand.

juvenissun this is an excellent example of a situation where not having enough genetic diversity in your population leads to results that are either not very good, or at best, makes it very hard to do well in a variable environment.

For example, the Cheetah is of low variability in the population, so much so that you can graft skin from one to another without rejection (the same reason when you need an organ transplant, your siblings and children are the first people to lack at for donations). Cheetahs lost a lot of genetic variation in their population during the ice age. They are genetically close, and because of this they don't do well in environments that they aren't specifically designed to be in, and zoos have very hard times breeding them in captivity.

Loudmouth's example shows what happens when you have a continuously mutating solution as it's only method of working, or what's known as "Hill Climbing". As the cards are replaced, it keeps getting better and better until it can continue no further. If its initial conditions cause this, there's no way of escaping it because you never will get enough genetic variation to escape it. Having four 6s, you'll have a good hand, but it will never beat a straight flush.

Imagine being in the Himalayas near Mount Everest. It's surrounded by mountains. All you have is an altimeter and told "climb as high as you can". You start walking around the hills and get higher and higher, but if you just happened to talk to a foot hill of Everest, once you reach the top you won't climb any higher. Even if all you had to do was climb down and go to the base of Everest, your altimeter would tell you that you are going down instead of up. You would wander around the hill until you found the maximum altitude of the hill. That would be your local maximum.

Hill Climbing algorithms continually mutate a solution to make it as good as it can, but like in the poker example, you can easily get stuck in a local best, and never get to what you want, a global best.

Genetic Algorithms can help avoid this problem, because it has several solutions being evaluated in parallel. You then breed them together, and then mutate slightly. It would be like several people hiking around the foothills of Everest, then get on the radio with each other compare each others altitudes and 50% of the people that are the highest compare their positions "Hey I'm North-East of you, and you're South West of me, howabout I'll go South East, and you go North West and we'll see if that helps".

Hill climbing is very fast, but is prone to getting stuck because it can't share gained information, it's purely mutation. Genetic Algorithms both share information (selection criteria) and add some randomness (mutation). If your GA is set correctly for your data, you can overcome local maxima to have a better chance of reaching global maxima.

 

[juvenissun]

OK, guys. Thanks for the education on the GA. I got enough for now.
I learned a little bit about AI programming years ago (very basic). I think this field took off at a very fast pace since then.

 

[DogmaHunter]

More than likely, any additional changes will reduce the fitness of the design. In evolution, this is called a fitness peak.

A good way of visualizing this effect is by using playing cards. Deal yourself 5 random cards, and then draw cards 1 by 1, keeping only the cards that improve your poker hand and discarding cards to keep 5 cards in your hand. You will find that you will reach an endpoint where no new cards will improve your hand. At the same time, you may very well reach different hands each time you do the experiment. One time you may reach a straight flush. Another time you may reach 4 of a kind. The key is that there is no way to go from the peak of 4 of a kind to the peak of a straight flush without taking cards that reduce the fitness of your hand.

That's a much clearer example then what I was using. Nice.