An interactive column using Java applets
by Alex Bogomolny
Mathematics and Biology
April, Mathematics Awareness Month whose theme this year was Mathematics and Biology, is over. Even though, it may not be too late to add my 2 cents for, as Keith Devlin put this in his April's column, ". raising the public awareness of mathematics will always be an uphill battle." In that column, Devlin offers some information about what went on during MAM; more can be found at the official MAM site.
This year's April was my private MAM with exactly Mathematics and Biology theme. My wife, a school psychologist by trade, became fascinated with the modern theory of evolution as expounded by Richard Dawkins in his book The Selfish Gene. The book, that she finished reading in March, afforded us in April a series of interesting family discussions. Among laymen and philosophers, Dawkins is famous for raising the issue of cultural evolution brought about with the emergence of memes, the new kind of replicators. Compared to the Darwinian evolution, cultural evolution is orders of magnitude faster. Our brains are adapted by natural selection to the long-vanished way of life that our ancestors led as foragers in small nomadic bands [Pinker, p 42]. The adaptation took place over thousands of generations. For comparison, mathematical memes succeeded in penetrating the quintessential biological science - the theory of evolution - in a little more than 100 years.
Natural evolution is about replication and propagation of genes. Genes live on chromosomes, chromosomes live in cells. In usual cells, chromosomes live in pairs. In the sex cells, the sperms and eggs, chromosomes come in singles. When two sex cells fuse into one, the newly formed cell receives 1 chromosome from each of the parent cells. From then on, it multiplies by dividing, all the while passing on exact copies of its own chromosomes - in pairs, of course (but not necessarily creating exact copies of itself.) Not unexpectedly, most of the fun occurs in production of sex cells each of which carries single chromosomes. Where do these come from?
Other chapters in Dawkins' book may be easily related to different branches of mathematics. There is no room to even touch on all the possibilities. Clearly mathematical ideas play nowadays an important and vibrant role in biology. Interestingly, the opposite is also true. Biological insights led to the development of the theories of neural networks and genetic algorithms [Goldberg, Holland, Mitchell]. The latter is especially relevant to the theory of evolution.
Possible solutions are represented by a sequence of moves - chromosomes with every move thought of as a gene. The puzzle squares are numbered left to right starting with 0. Moves are designated by the number of the square from which the move is made. At any particular stage of the puzzle, only two moves are possible.
All chromosomes have the same length which I chose to be 5 genes longer than necessary. Crossover is an operator that for a pair of chromosomes produces two other chromosomes. First it cuts the given chromosomes into two by selecting a "crossover point", which is the same for both chromosomes. Next the chromosomes are spliced together but only after swapping the right (or left) pieces. With a certain probability (I took it to be 1/2, although usually that probability is much smaller) the new chromosomes are subject to a random mutation. In addition to a simple gene replacement, I also built in a mutation specifically reflecting the structure of the (puzzle) chromosomes: pick a random sub-chromosome, a contiguous subsequence of genes, and perform a cyclic rotation of genes in that sub-chromosome.
Each chromosome is evaluated by a fitness function to determine its "evolutionary viability". Starting on the left I just count the number of moves that can be performed skipping the "ballast" ones (these are removed when a solution is found). The population of ten chromosomes is sorted according to their fitness. On a single evolutionary step either all but the fittest chromosome are replaced, or I replace only the two worst performers. The mating chromosomes are selected randomly with probabilities proportional to their fitness. That's all.
The search space for a 3 + 3 puzzle has a formidable number of elements: 720. The algorithm usually finds one of the two solutions in less than 1000 iterations. The algorithm takes about 20-30 steps to solve the 2 + 2 puzzle. It requires only little ingenuity to carry out the algorithm for a small puzzle manually.
This must be said: the puzzle may be simple, but searching for a solution in the space just described is not. Sheer size apart, every wrong move leads to a "false", local maximum of the fitness function. Watching the algorithm work, one can easily gain appreciation of the difficulty involved in solving a problem like this.
Genetic algorithms try to mimic natural evolution, but their justification rests on a mathematically sound theory developed by John Holland in the mid 1970s in his book Adaptation in Natural and Artificial Systems (1975). As the title applies, the same mathematical foundation underlies both natural and artificial systems. So it does not matter much whether adaptation of sequences of moves in the Toads and Frogs puzzle is judged artificial or not. It is natural, though, in at least one respect: it takes place in the environment absolutely natural for the bits and bytes that those chromosomes so naturally are.