ANNEvolve :: Evolution of Artificial Neural Networks

Using the fairly standard "Travelling Salesman Problem" as a test case, using identical layouts, setups, parameterizations, population sizes and so forth, and the excellent "Mersenne Twister" pseudorandom number generator, I've many times encountered 100:1 ratios between solution times for the same problem using a GA. That makes "when will it be done" predictions nearly worthless.

The reason why is complicated to compute, but not complicated to envision: a GA run succeeds based on a catenated set of concidences of highly unlikely events.

Most mutations make genomes worse, most crossovers hit the wrong spot and also produce a worse genome. GA works because we're willing to throw away so many culls, just like real evolution.

Moreover, the improvements that do happen are usually very small increments, so that it takes bunches of them to produce a good solution from a starting set of bad ones.

Still further, because of the problem of converging on local optima instead of the global one, it takes a limited set of all possible orders of those improvements to get to the global optimum.

Anytime you have to get a particular subset of a series of very unlikely events, the _variance_ of your answer can be expected to be very broad, and that's what you have seen.

Note: The above was taken, with Mr. Dolan's permission, from the middle of a longer message he wrote to comp.ai.neural-nets.

I might mention that the variance that I've seen in the EvSail runs, while large, is not nearly the 100:1 that Mr. Dolan mentions. [Mitchell Timin]

An Aspect of Natural Evolution

Author: Mitchell Timin
Posted: 08/31/2003

Genuine Artificial Intelligence :)

Author: Mitchell Timin
Posted: 08/27/2003