On the probability/speed of evolution

Lord Zentei · Post by **Lord Zentei** » 2006-02-16 03:29pm

Here be a nice site showing the speed by which natural selection type genetic algorithms can operate. It uses examples Dawson's Biomorphs as a population (which in turn show the variety that can be gained with surprisingly few genes). Dawson is the guy who wrote The Blind Watchmaker.

Site: www.rennard.org

Dawkins' Biomorphs. Linka

Genetic algorithm: Linka

Keevan_Colton · Post by **Keevan_Colton** » 2006-02-16 06:07pm

Wasnt it Dawkins that wrote The Blind Watchmaker?

Batman · Post by **Batman** » 2006-02-16 06:09pm

Keevan_Colton wrote:Wasnt it Dawkins that wrote The Blind Watchmaker?

Ahem.

Lord Zentei wrote: Here be a nice site showing the speed by which natural selection type genetic algorithms can operate. It uses examples Dawson's Biomorphs as a population (which in turn show the variety that can be gained with surprisingly few genes). Dawson is the guy who wrote The Blind Watchmaker.

Lord Zentei · Post by **Lord Zentei** » 2006-02-16 06:25pm

Keevan_Colton is correct, Batman. It's Richard Dawkins.

Here:

Lord Zentei wrote:Dawkins' Biomorphs.

And yet, above that, I misspelled his name. Twice. How the fuck is that even possible?

In any case, on topic:

The intention with this post was to provide ammunition against anti-evolutionists when they claim that evolution could not progress fast enough. However, the search time is not proportional to the size of the search space.

Batman · Post by **Batman** » 2006-02-16 06:32pm

Oops.

My bad. Sorry, Keevan.

Lord Zentei · Post by **Lord Zentei** » 2006-02-16 06:44pm

Anyway: as I understand it, the reason for the efficiency of genetic algorithms is that each time the correct allele for a given gene is found, the search space is reduced by a factor of N, where N is the number of possible alleles for that gene. The search time grows logarithmically with the search space.

Any biologists and/or computer programmers with knowledge of genetic search algorithms want to comment/correct on this?

Ariphaos · Post by **Ariphaos** » 2006-02-17 02:20am

In order for genetic algorithms to work, you must be able to test your solution, ascertain that one solution is better than others, and be able to represent and evaluate these solutions numerically. This testing is sometimes done by a human (those fancy little creature-evolving games running around, for example), but the point is still valid.

A common introduction to genetic algorithms is using them to find the square root of a number. You pick a number to find the square root of, and generate a population of random floating point numbers to fit.

Depending on how you set up how the mommy and daddy work, how the population works, and how mutations go, you can have vastly different results. The areas you want to resolve the fastest also tend to be those most vulnerable to change - the exponent, for example. So, when scaling your tests, you do want to keep some of the 'bad' population, in case they may have good data, but not the really bad. So, out of a population of 100, you might set it to:

50 new breeds
50 best of old breeds retained from test of previous generation. Read: Incest can help.

The new breeds are made by combining 'mother' and 'father' pairs, which can be quite arbitrary, and then applying a rate of mutation - changing a single bit at random.

It's been a long time since we did this, but IIRC the teacher's example was able to resolve down to the limit of floating point numbers (7 significant digits) in eight generations using a population of 100 or so. Quite impressive, at least in my opinion.

Like neural networks, it's not easy to describe it as a normal computing algorithm. It is a heuristic method, meaning that you give up the ability for a provably good run time and/or the optimal solution. As such, it gets used for those problems where the provably good run times are insane.

In the case of GA's this mostly lies in the realm of knapsack-style problems - scheduling and such. It is also ideal for problems that have potentially complex solutions, ie, if 2 is a better solution than 1 or 3, some algorithms might get stuck on the 2, while a genetic algorithm might check and see that say, 7 is even better.

dworkin · Post by **dworkin** » 2006-02-17 05:25am

What I like best about automata is the demonstration of how mindboggling huge the phase space for them is. In the case of Dawkin's biomorphs IIRC his selection criteria were those 'he liked the look of'. Even so, the number of selected forms remained huge. Likewise organic chemistry and natural selection place huge restrictions on the phase space of 'possiable organisms' but the almost infitesimal remnants are still almost unimaginably huge.