Evolution: A view from the 21st Century by James A. Shapiro, reviewed by David vun Kannon

In this slim book, eminent bacteriologist James Shapiro attempts to communicate his view of the most important drivers of evolution for a non-specialist readership. The material is dense, mostly because the text does not rise much above an outline of all discovered processes of genetic variation, no matter how obscure.

Shapiro succeeds in conveying the idea that variations arising from genetic change other than uniformly distributed single nucleotide changes are the most important to understanding the diversity of life today. However, his other agendas, such as displacing Crick's Central Dogma of Biology, are not successful.

Let's deal with some of the positives of the book first.

Shapiro is writing for a wide audience, and does not shy away from addressing some issues related to the "Intelligent Design" controversy. Some in the ID community initially took Shapiro to be their friend, in the "enemy of my enemy" sense. However, Shapiro takes the age of the planet and the evolution of life as ground facts.

The book makes extensive use of online appendices and additional reference material. I read the book on the Nook e-reader from Barnes & Noble, and opening the book using the PC version of the Nook reader application made these materials easy to access. Much of the online reference material is linked directly to Pubmed. Online additional readings link mostly to articles from Scientific American - not the primary literature, but an accessible source for the expected audience. These articles span 60 years of publication and many are of historical interest only.

The book is very complete in its coverage of genomic change processes. And while Shapiro's main point is to focus on sources of variation other than point mutation, when it comes to discuss mutation, the book includes intriguing sources such as viruses (in which mutation can happen at much higher frequencies).

Most readers will probably be quite surprised by the importance of genomic processes other than mutation in shaping the course of evolution. Even if you've been following the developments as an interested non-professional, as I have, the variety of processes discussed is sure to teach you something new.

One insight I got was that the machinery that is used to guide protein production inevitably interacts with the machinery of cell duplication (in single celled organisms) and germ line continuation in metazoa. I failed to see previously how often the genome is opened up and read, and how that necessary process creates the chances for things to break and be repaired differently.

However, it must also be said that the book is far from perfect. Indeed, there are many irritations that spoil the enjoyment of learning.

Shapiro seems to feel that it is his job to carry forward the mantle of "unorthodox biologist" worn by Lynn Margulis and Barbara McClintock, among others. He takes several shots at "evolutionists" for missing the importance of jumping genes and symbiosis, while focusing on the population genetics of single random changes.

With all due credit to McClintock and Margulis, Shapiro's rhetorical stance is unhelpful. He does play into the hands of those that would willfully misrepresent his position by using loaded terms such as Darwinism and evolutionist, without defining them and apparently without concern with how these terms have been used in the popular press. If Shapiro means "evolutionary biologist" when he says evolutionist, he should use the less charged term.

Shapiro repeatedly uses a "microprocessor" metaphor that is painfully inappropriate. A computer CPU is a piece of hardware that can execute any series of instructions stored in memory, given a link to the first address of where to fetch the data. The information of the genome is the data, not the hardware that reads or  acts on the data. The closest thing in the cell to a CPU is the set of molecules that read, transcribe and translate, DNA into protein - the ribosome.

There are many ribosomes working in parallel in the cell, one of several failures of the analogy. As a system, the protein production and genetic machinery are more like a "production system" - a set of if-then rules that work in parallel. This is software, not hardware, but it fits better.

Scientists frequently stretch to find an analogy which will work for a lay reader, to help the reader understand their work. If that is what Shapiro was trying to do, it doesn't work. If he actually thinks the genome instantiated in a cell is a microcircuit, he is sadly mistaken about microelectronics.

Few, if any, people would call a microprocessor "aware", "intelligent", or capable of cognition, yet this book does use such aggressively telic language with respect to the cell and the genome. However, we should only be willing to talk about "cell cognition" if we are also willing to talk about "thermostat cognition". The feedback loops elaborated in the cell are only marginally more complex than your friendly household appliance.

Darwin comes in for some criticism that seems unnecessary, sort of like criticising Newton for not discussing relativity. Yes, Darwin's uniformitarianism was/is a simplification of what we know today, and did reflect philosophical debates of his time. So what? Does this need to be criticised or simply acknowledged?

Repeatedly when dismissing the random mutation of single nucleotides, Shapiro seems to confuse random with 'uniformly distributed' - or read that confusion onto others. We know that SNPs (single nucleotide polymorphisms) are not randomly distributed. They are more likely in some parts of the DNA string than in others. However, they are random, in the sense that we don't know in advance where a change will take place, even if we know they take place at different frequencies. As an analogy, we know that a sample of a radioactive element has a half-life, but we don't know which atom will decay next.

Shapiro seems unconcerned with the Darwinian distinction between selection and sources of variation, giving all the credit to the multiple sources of variation, and little or none to the various forms of selection that can act on an organism. There is also no discussion of the "evolution of evolvability" as a framework for understanding the many mechanisms that are cataloged in the book.

A weakness in the writing is to describe the genetic machinery as "indescribably complex" before launching into a description of it! Phrases like 'indescribably complex' are just more fodder for quote mining by creationists. Similarly, Shapiro's overall anti-reductionist stance obscures the fact that all of the data and research are based on a reductionist paradigm - the genetic machinery of the cell is entirely the arrangement of atoms and the forces acting upon them, as is everything else in the cell. There is no vital elixir or special sauce that defies reduction to these terms.

While referring to it several times, Shapiro never successfully attacks the Central Dogma of Biology, that information flows in the direction of DNA to RNA to protein, but not in reverse. There are ample examples given of proteins attaching to and regulating the genome, but those proteins are always created by the genome.

Relevance to the ID debate

The book does mention Intelligent Design. However, it also treats evolution as a fact. Natural genetic engineering, as Shapiro calls it, is the source of variation used by evolution. These large scale additions and rearrangements are the driver of metazoan evolution - not new sequences.

It has been the mistake of ID supporters to try to find an ally in Shapiro. Obviously, they did not read the whole book, or if they did their memory is quite selective as to its contents.

It should be mentioned that Shapiro published two papers with controversial ID figure Dr. Richard von Sternberg in 2005. Sternberg is thanked in the acknowledgements.

Shapiro also indulges in some 'bignum' argumentation. This is the sort of handwaving probability calculation that concludes that "there is not enough time" for base-by-base change to create the evolutionary results we see. This kind of reasoning has often been proved wrong, usually by pointing out that sexual reproduction allows many changes to be selected in parallel throughout a population and combined, and high rates of reproduction and HGT (horizontal gene transfer) accomplishing the same thing in bacteria.

Indeed, Shapiro's own discussion of viruses as sources of variation for other life does not examine the sources of variation in viruses - uncorrected random mutation.

The telic language, anti-"Darwinism", and "gee, its complicated" attitude are all ID friendly, but in the end Shapiro has a clear vision of who the Intelligent Designer is, and it is the cell itself.

Relation to the GA software paradigm

Much of conventional Genetic Algorithm software is explicitly point mutation based. Mutation and crossover are often the only operators used, and usually mutation is uniform along the genome. This is the strawman view of genetics that Shapiro criticizes most sharply.

I think the book can be read as a set of suggestions for improving our GA algorithm design if we want to achieve more than numerical optimization with GA. Here are some taking off points that I see:

• exon/intron distinctions, and redundant representations
• germ/soma distinctions
• both of the above presuppose a more robust genotype/phenotype distinction
• development of that phenotype aka evo-devo GAs
• fitness testing at multiple points during a phenotype's lifetime
• gene regulatory networks - genetic operators for regulation of the genome

In conclusion, a book well worth reading and thinking about, even with the annoyances and idiosyncrasies of the author.

Hypothesis: Reordering typical GA operations opens up new opportunities

One of the truisms of the area of evolutionary computation is that time spent on the evaluation of the fitness function dominates the the total resource budget of the run. Therefore, we should want to allocate trials as efficiently as possible, even more so as we are using a method which will inevitably allocate trials to poor choices as part of the exploration of the parameter space.
When GAs are introduced, the fitness function evaluation is typically a single test case, for example evaluating f(x) for some x, which is the phenotype constructed from the individual's genotype. The population might have genotypes of binary strings, these strings then become phenotypes of real numbers, and the phenotypes are evaluated.

For more 'real world' problems, the phenotype has to be evaluated across multiple test cases, perhaps thousands of cases. The outcome of all of these test cases contributes to the overall fitness measure of the individual. As noted in this early paper, the test cases can vary greatly in their discriminant utility. The basic idea here is to break down the test cases into a population of individuals that will co-evolve with the population of possible solutions.

My idea is somewhat simpler. Typically, one individual is tested across all test cases, and a cumulative fitness score generated. In my reordering of operations, all of the new population members are generated, then each member is evaluated on the first test case, then all on the second, etc. We stop the evaluation process at some point to compute a partial fitness score. On the basis of this score, we abandon some members of the population and delete them, replacing them with perturbations of high scoring members.

In terms of the biological analogy, reordering the test case evaluations allows us to select from the population at multiple points in each individuals "lifetime", where the lifetime is the sequence of test cases.

The hypothesis is that this reordering, partial fitness selection, and reward of well performing members will lead to more efficient allocation of trials in problems that are amenable to this reordering.

Deceptive genomes

Having worked out the kinks in my BinInt problem, I got my Deception code working also. As with BinInt, I've now scaled the output fitness to adapt to the number and size of subproblems. This isn't important in any one run, or averaging runs with constant parameters, but it does make it easier to compare runs with different parameter choices. I'm happy!

BinInt, finally!

After much delay, I finally got my BinInt GA problem running successfully in ECJ. Part of the issue was setting everything up again on a new laptop, part also was moving to ECJ 18, and part was my own stupidity. But it looks like it is all working now.

BinInt takes the same bit vector as MaxOnes and divides it into several subproblems. Each subproblem is treated as a binary integer, hence the name. The key new feature of this problem is the introduction of exponential scaling. Some bits are worth a lot more than others.

I wrote the fitness function so that it scales the fitness according to the size and number of subproblems. Best fitness is always 1. this way, we can vary the size and number of the subproblems and directly compare the trajectory of different parameter choices in solving the problem.

Topping the charts

Long time no blog, sorry!

So what have I been doing? Well, what I'd like to share with you is some hacking of the charting facility in ECJ.

ECJ's distribution contains some references to the inclusion of JFreeChart and iText, which will enable the production of "publication quality charts". OK, I'm all for it, but then come the caveats. "We don't use the Console app much." "We don't really use that."

So what we've got is the linkage to a good free package for charting, but only the sketchiest pointers on how to integrate it into your ECJ experiments.

There were two things about "publication quality" charts that I wanted to do right away. First, charts in journal articles often show multiple data series on the same chart. Second, data published in journal articles is usually averaged over a significant number of GA runs. ECJ doesn't contain an example of either of these things out of the box.

I've hacked together an example of the first functionality. Now I can chart the best of generation, worst, mean, and standard deviation all on the same chart.

I ran my BinInt experiment with the new chart to show that it worked. Wow! So much nicer than looking at the simple statistics!

One thing that jumps out immediately is that the experiment is wasting more than half its function evaluations because the population has converged. While we can guess this is happening when we see the best of generation fitness stall at a particular value, charting the worst, mean and standard deviation makes it completely obvious that before generation 45 (of 100) the entire population is a single genotype.

(Remember, this is a selectorecombinative GA experiment, so there is no mutation to rescue the population. We expect the population to converge well short of the optimum due to domino convergence and drift, and it does.)

Function evaluations are the currency of evolutionary algorithms. While many systems (including ECJ) let you stop a run if a known optimum is reached, stopping on a convergence criterion seems to be just as useful. I'm not sure why this is not more common, since the bookkeeping necessary is not that great an overhead. In general, you can trust the computational cost of the function evaluations to swamp the cost of the algorithm itself.

Now I'll start tinkering with the second issue, averaging over several runs. I'm going to hack this using the subpopulation mechanism of ECJ. Each subpopulation will be an independent run with a different random seed. However, the statistics gathering (and charting) mechanism can look across the values of each subpopulation and collect the statistics and average them. Is this the right way to do this? I'm not sure, but I'll try it!

The Illusion of Life

The Illusion of Life is actually the name of a beautiful book about the classic Disney style of animation and how it was acheived.

I'm going to use the phrase as a jumping off point to talk about GAs. Genetic Algorithms are explicitly designed to imitate the successful process of optimization seen all around us.

Simple GAs try to tear down the bells and wistles of real biology and use just the core ideas of evolution. Take a finite population, evaluate the fitness of each member. Preferentially select higher fitness members to reproduce or be copied forward. Allow some source of variation to create new population members during reproduction. The most common reproductive operators are mutation and crossover.

A choice of population size, selection algorithm, operators and representation that all work together will take even a simple GA a long way. But GAs are sometimes criticised as being unable (even in principle) to replicate the diversity we see in the natural world.

Most GAs working on an optimization problem are like a microbe evolving drug resistance in a test tube environment. No one is even attempting to recreate the variety of species and niches of real life.

Here are some things that are sometimes brought up as examples of how GAs can be made more "biological", in the belief that this will somehow make them better:

• haploid genomes
• inversion operator
• introns

Now it may be that there are specific optimization problems where each of these tricks might be helpful, but none of them has been shown to be extremely useful.

Notice that these ideas focus on the nitty-gritty of DNA. I have my own list of things I think might be important to bring in to our GA models from biology, but these aren't on my list. Instead, here is my list:

• embodiment - in time and space
• coevolution - a fitness measure in which the other members of the population are explicitly considered, including the possibility of parasitism
• development - genetic cascades, and some form of lifetime fitness measure
• self regulation - in the form of hormones or neurons
• sexual selection

I'm much more interested in the possibilities of a boost from ecology than biology. It may be that one day, very powerful GAs will drop some things that are now considered "essential" such as the population itself! Estimation of distribution algorithms are a step in that direction. Until then, I think we do have a lot to learn from Mother Nature, but I think we need to look in some different directions.

Sex, Lies, and Genetic Algorithms

Moving on from the BinInt problem, the next basic research problem to code in ECJ is the classic "deceptive" problem. In this kind of problem, the optimum point is surrounded by very low fitness points, while the points furthest from the global optimum have the second highest fitness. A hill climbing algorithm is tempted to follow the slope away from the global best towards the suboptimal points.
However, a selectorecombinative GA is not a hill climber. Its ability to find the optimum point is based on shuffling combinations of alleles, trying to find good sets.

If the deceptive subproblem is too big, the GA has little better than random chance of finding the optimum, so here also we will rely on building up a problem by concatenating several subproblems.

Based on calculations shown in The Design of Innovation, p. 160, I verified that my code for the trap function was in fact deceptive. Then I looked at a few other sources, including Franz Rothlauf's Representations for Genetic and Evolutionary Algorithms, and I saw that my code for the trap was basically the same as his.

Testing my BinInt implementation

As a sanity check, I scaled the size of my subproblems down to 1, and compared the performance of the BinInt and MaxOnes problems with identical parameters. Ta dah! Exactly the same results, as you would expect.

Now I'm dialing up the BinInt size gradually. The effect of scaling is obvious, as many bits converge too early, carried along on the coattails of the high value bits. This series of experiments is with a 0.0 mutation rate, to test the powers of a selectorecombinative GA in isolation. In a problem l bits in size, with population and number of generations also held at l for l^2 function evaluations in total, the best fitness over a run is not even reaching half the known optimum.

I'm also still learning lot's of basic things about ECJ, such as how to chart statistics using the gui console. Woot!

ECJ - building a BinInt problem

I've gotten a little farther with my learning of ECJ.

The tutorial 1 provided with ECJ uses the MaxOnes as a sample problem. MaxOnes simply adds up the number of "1" bits in the genome of an individual to create a fitness for that individual.

BinInt changes the problem by reinterpreting the genome as a binary integer. In my version, I've written it so that you can cut the genome up into several integers. For example, a genome of 150 bits can be interpreted as 30 5-bit integers, 5 30-bit integers, or even 16 9-bit integers with one 6-bit integer.

BinInt is a class of problems that imposes two new kinds of difficulty on the GA. First, BinInt shows scaling. Different bits are worth exponentially more than other bits. Secondly, bits are related to each other to form sub-problems. All the bits of a particular sub-problem contribute to the solution of that part of the overall problem.

Scaling in particular challenges a GA. The large fitness contribution from just a few bits can cause individuals lucky enough to have those bits turned on early in the run to quickly dominate the population, even before the population has found the best arrangement for the other bits. This problem is called premature convergence.

I had fun building the BinInt problem in ECJ. It was straightforward to modify the MaxOnes problem fitness evaluation function. The learning came in when I wanted to create a custom parameter to control the sizes of the integers. I invoked the OTSOG (On The Shoulders Of Giants) principle, and asked for help from the ECJ discussion list, with very helpful and immediate answers. Thanks guys!

ECJ - tutorial 1

I set up the Evolutionary Computation in Java (ECJ) system to run under Eclipse. Here is a brief report on using it to run the first tutorial provided with the system. This is the same tutorial covered in the YouTube videos mentioned previously on this blog.



The tutorial description assumes that you are typing in every line of the tutorial1.params file, but since it is provided I went straight to tweaking the different parameters.



The optimization problem in this tutorial is trivial to state. The genome is a set of unrelated bits which are counted, so maximum fitness occurs when all bits are 1, hence the name MaxOnes. As trivial as that sounds, a lot of basic research in GAs is conducted on this and similarly simple functions.



Out of the box, the parameters of interest are

• crossover probability = 1.0 (we will always cross to get a new individual)


• mutation probability = 0.01 (every bit has a 1% chance of changing)


• genome size = 40 bits


• population size = 40


• generations = 100

With this setup, we get

Generation 32
Found Ideal Individual

It took 32*40=1280 function evaluations to find the ideal individual of all ones.

Upping the ante, if we double the genome size to 80

Generation 87
Found Ideal Individual

We found it, but doubling the size of the problem more than doubled the effort to solve it. It almost tripled it. That is disturbing.

Doubling once again to a genome of 160 bits, and the system cannot find the ideal individual, even in 1000 generations. Even if the population size is quadrupled to 160, the system fails.

What has happened? Have we reached the edge of evolution already? Is this all that GAs are capable of, solving trivial problems?

Happily, the answer is no. We are very far from the edge of evolution (if there is such a thing), but we are at the beginning of understanding how GAs work.

One of the great themes of search and optimization algorithms is the tradeoff between exploration and exploitation. When do we look in new areas for an optimum, and when do we try to find the best value in the local area of a solution we already know is "pretty good"?

In GA work, the operators of crossover and mutation are often characterized as typifying exploration and exploitation, respectively. I think this is an acceptable characterization wrt mutation, though it isn't the greatest way to think about genetic operators. Another way to think about mutation is to look at it as a kind of heat source, as in simulated annealing.

What happens if we scale back the mutation rate to 0.001 and go back to our original population size of 40?

Generation 219
Found Ideal Individual

Very interesting! What was happening in our earlier runs? The mutation rate was 1 out of 100. When the genome size was less than 100 bits, individuals could get crossed and then never suffer mutation on their way into the new population. But when the genome size went to 160, we were almost guaranteeing that every individual would suffer, on average, 1.6 bits changed. So the population was constantly dancing around the optimum, but never hitting it exactly.

If there is a final lesson to be drawn from this small example, it is that GAs are not about parameter tweaking. There is always a coupling between the probem and the parameters that needs to be understood.

A Model of Error

Over at UD, math (sic) professor Granville Sewell resurrects one of the silliest posts of 2006, Gil Dodgen's misapprehension of what makes a model. No, the errors in our OS are not part of the model, any more than they are part of your PDE solver or Dr Dembski's MESA or Dr Marks' EIL work.

It is however true that if you are running intense numerical calculations, you need to take into account the quality of your (pseudo)random number generator, your floating point hardware's aptitude for error due to heat, cosmic rays, bad programming by Intel, etc. Taking these things into account is very different from intending them to be part of the model system. No one is going to be impressed by results that need to be run on Windows ME with a lump of uranium lying on the desk next to the CPU.

But it is from this support the Dr Sewell makes a sweeping statement, "Unintelligent forces simply can’t do intelligent things..." Sorry, Dr Sewell. In the words of the prophet, pwned! May I be the first to introduce you to the Humies.

If you're not following the link, I'll just summarize that the Humies are cash based awards for achievement equal or better than human at some intellectual task, by an EA based system. That we can give away awards like this is a testament to the power that GA, GP, etc have already achieved.

Looking back into ANAS

ANAS is John Holland's 1975 monograph, Adaptation in Natural and Artificial Systems. I went back to it recently to review the history of the thinking about linkage learning from the very beginning.

I was struck that Holland's first presentation of a simple genetic algorithm, called a reproductive plan in ANAS, is a steady state GA. In steady state GA, a single individual is replaced at a time in the population. This means that new mixes of genetic material is made available immediately for selection.

I had mis-remembered this. I thought that historically GAs started as generational models in which the entire population was replaced at once, and that steady state GAs were due to Grefenstette.

Similarly, ANAS considers the possibility of evolving algorithms, not just parameter sets. This is the basic distinction between genetic algorithms and genetic programming, which most people attribute to John Koza.

There is a phrase in Pirkei Avot (Ethics of the Fathers) "hufach bo v'hufach bo d'kulla bo." Turn it over, turn it over, because everything is in it. I think it applies just as well to basic texts in the sciences as it does to the Talmud.

Getting back into GAs

I don't remember how I discovered genetic algorithms. At some point, I got a copy of David Goldberg's book, Genetic Algorithms in Search, Optimization, and Machine Learning. It was a great book, and I had a lot of fun writing my own GA package in C (the code in the book was written in Pascal).

Goldberg's next book, The Design of Innovation is even better. The discussion of how to make GAs a principled engineering approach to solving problems, rather than a black box with too many knobs and levers, really energized my interest.

So now I'm learning the ECJ system using Eclipse. With the help of some nice YouTube tutorials on setting up ECJ with Eclipse, I'm off to the races!