next up previous


In order to compare the process of evolution between runs of the simulator, a simple objective quantitative measure of evolution is needed. One such measure is the degree to which creatures improve their efficiency through evolution. This provides not only an objective measure of progress in evolution, but also sheds light on the potential application of synthetic life systems to the problem of the optimization of machine code.

The efficiency of the creature can be indexed in two ways: the size of the genome, and the number of CPU cycles needed to execute one replication. Clearly, smaller genomes can be replicated with less CPU time, however, during evolution, creatures also decrease the ratio of instructions executed in one replication, to genome size. The number of instructions executed per instruction copied, drops substantially.

Figure 4 shows the changes in genome size over a time period of 500 million instructions executed by the system, for eight sets of mutation rates differing by factors of two. Mutation rates are measured in terms of 1 in N individuals being affected by a mutation in each generation. At the highest two sets of rates tested, one and two, either each (one) or one-half (two) of the individuals are hit by mutation in each generation. At these rates the system is unstable. The genomes melt under the heat of the high mutation rates. The community often dies out, although some runs survived the 500 million instruction runs used in this study. The next lower rate, four, yields the highest rate of optimization without the risk of death of the community. At the five lower mutation rates, 8, 16, 32, 64 and 128, we see successively lower rates of optimization.

Additional replicates were made of the runs at the mutation rate of four (Fig. 5). The replicates differ only in the seed of the random number generator, all other parameters being identical. These runs vary in some details such as whether progress is continuous and gradual, or comes in bursts. Also, each run decreases to a size limit which it can not proceed past even if it is allowed to run much longer. However, different runs reach different plateaus of efficiency. The smallest limiting genome size seen has been 22 instructions, while other runs reached limits of 27 and 30 instructions. Evidently, the system can reach a local optima from which it can not easily evolve to the global optima.

The increase in efficiency of the replicating algorithms is even greater than the decrease in the size of the code. The ancestor is 80 instructions long and requires 839 CPU cycles to replicate. The creature of size 22 only requires 146 CPU cycles to replicate, a 5.75-fold difference in efficiency. The algorithm of one of these creatures is listed in Appendix D.

Although optimization of the algorithm is maximized at the highest mutation rate that does not cause instability, ecological interactions appear to be richer at slightly lower mutation rates. At the rates of eight or 16, we find the diversity of coexisting size classes to be the greatest, and to persist the longest. The smaller size classes tend to be various forms of parasites, thus a diversity of size classes indicates a rich ecology.

An example of even greater optimization is illustrated in Appendix E and discussed above in the section ``an intricate adaptation''. Unrolling of the loop results in a loop which uses 18 CPU cycles to copy three instructions, or six CPU cycles executed per instruction copied, compared to 10 for the ancestor. The creature of size 22 also uses six CPU cycles per instruction copied. However, the creature of Appendix E uses three extra CPU cycles per loop to compensate for a separate adaptation that allows it to double its share of CPU time from the global pool (in essence meaning that relatively speaking, it uses only three CPU cycles per instruction copied). Without this compensation it would use only five CPU cycles per instruction copied.

next up previous

Thomas S.Ray
Thu Aug 3 15:47:29 JST 1995