RSS 2.0 Feed

» Welcome Guest Log In :: Register

Pages: (12) < [1] 2 3 4 5 6 ... >   
  Topic: Evolutionary Computation, Stuff that drives AEs nuts< Next Oldest | Next Newest >  
dvunkannon



Posts: 1377
Joined: June 2008

(Permalink) Posted: Feb. 05 2012,21:04   

Quote (midwifetoad @ Feb. 02 2012,15:07)
Dumb question:

I've just encountered the term simulated annealing and a discussion of annealing algorithms vs genetic algorithms.

http://www.cs.helsinki.fi/u....sa....sa.html

The difference seems to be that an annealing algorithm selects only one child per generation to produce the next generation.

That would make Weasel and it's relatives an annealing algorithm rather than a genetic algorithm?

This came up in a discussion of Chaitin and his mathematical proof of evolution.

There are a large number of Evolutionary Computation (EC) algorithms that use only one candidate solution. Evolution Strategies (ES) is an example. Weasel, IMHO, fits into the ES model the best.

I don't think the reference you provided does a good job of explaining simulated annealing. The main point of SA is to avoid a local optimum by randomly perturbing away from a good solution that isn't getting any better over several iterations, in the hope of finding a better one. The analogy is to cooling down an object (finding the optimization minimum) then partially reheating and cooling down again. So it is mostly hill climbing (or valley following, depending if you are minimizing or maximizing) with a kick every once in a while to avoid the local optimum.

The population size difference is not the most important difference between SA and GA to my way of looking at things. Even if SA had multiple candidate solutions, hill climbing with an occasional kick isn't the same as a mutation only GA. The SA algorithm is using non-local information (lack of solution improvement over some period of time), most GA algorithms avoid non-local information. SA algorithms usually operate on the real valued parameters directly (the phenotype) while GA algorithms usually apply mutation to the genotype (a binary string) which gets translated into the phenotype. The result of this genotype-phenotype distinction is that a mutation that is local in genotype space can move you arbitrarily far in phenotype space.

Here's an example of the difference. The problem has two real valued parameters, X and Y. If the current best candidate solution is { 0.5, 0.5 }, an SA algorithm might test
{ 0.51, 0.51 }
{ 0.51, 0.49 }
{ 0.49, 0.51 }
{ 0.49, 0.49 }
and if none of them is better, kick you off to  { 0.37, 0.19 }.

In contrast, the GA algorithm is working on a 20 bit string. Let's say the population size was 4, and they all were
10000000001000000000, which gets translated into a phenotype of { 0.5, 0.5 } just like the SA solution. If the mutation rate is 0.05, we would expect 1 bit to change in each 20 bit individual. But a 1 bit change to
00000000001000000000
has moved the phenotype to { 0.0, 0.5 }!

That's not hill climbing!  A lot of people, including our friend Kairosfocus at UD, think mutation = hill climbing. It does not. OK, it does, but only for the simplest of genotype-phenotype mappings. Real world mapping of DNA to protein, where one nucleotide change could flip you from a hydrophobic amino acid to a hydrophillic amino acid, with consequent changes to the 3D folded structure of the protein, isn't simple.

Bottom line - SA and GA are pretty different EC algorithms, Weasel is ES, not SA, and mutation isn't hill climbing. Test at the end of next class.

--------------
Iím referring to evolution, not changes in allele frequencies. - Cornelius Hunter
Iím not an evolutionist, Iím a change in allele frequentist! - Nakashima

  
  355 replies since Mar. 17 2009,11:00 < Next Oldest | Next Newest >  

Pages: (12) < [1] 2 3 4 5 6 ... >   


Track this topic Email this topic Print this topic

[ Read the Board Rules ] | [Useful Links] | [Evolving Designs]