Notebooks

Evolutionary computation

13 May 1998 18:20

There are lots of ways of getting a computer to mimic evolution, but the one I like best, and has the cleanest conceptual lines, is the "genetic algorithm" invented by John Holland. Take a population of strings, and measure their "fitness" against some criterion. Each string has a random number of descendants, i.e. gets copied a random number of times; the expected number of descendants of a string is proportional to its fitness. These descendants can be mutants, or swap part of their length with another descendant string. (Oral tradition says that this "cross-over" is usually more useful than mutation; when and how much, nobody really knows.) Repeat as needed. For this basic version of the genetic algorithm, Holland proved what is called the "schema theorem", showing that, if certain patterns of strings are fitter than others, then, in the long run, the GA can't help but find them, and the average number of strings in the population matching those patterns will increase exponentially. (This result is a relative, and quite consciously so, of Fisher's "Fundamental Theorem of Natural Selection.") In retrospect, it's an almost obvious idea, and utter idiots can write a workable GA in Fortran. (I have.)

In the normal computer-science manner, this has of course been tweaked and elaborated in hundreds, and by now probably literally thousands, of different ways. John Koza's technique of "genetic programming" replaces the simple strings with a clever technique for only encoding syntactically correct (though possibly useless) programs. (It works best in languages with a very regular syntax, like Lisp or, Heaven help us, Forth.) There are even variants where the fitness is determined (more or less) endogenously, i.e. which use something more like natural than artificial selection. (Obviously, though, artificial selection is the way to go if you want to solve a particular problem.) It's neat, it's significant, and if I here it described once more as "teaching computers how to have sex" or "the merging of life and the machine," I believe I'll scream. Of course it is used in artificial life and machine learning, but if Holland had just picked some dull, boring name, like "stochastic combinatory optimization", nobody would babble about it at all.

See also: Optimization

permanent link for this note   RSS feed for this note

Notebooks: