Optimization in digital organisms involves finding algorithms for which less CPU time is required to effect a replication. This is always a selective force, regardless of how the environmental parameters of the Tierran universe are set. However, selection may also favor reduction or increase in size of the creatures, depending on how CPU time is allocated to the creatures. If each creature gets an equal share of CPU time, selection strongly favors reduction in size. The reason is that all other things being equal, a smaller creature requires less CPU time because it need copy fewer instructions to a new location in memory.
Under selection favoring a decrease in size, evolution has converted an original eighty-two instruction creature (instruction set four) to creatures of as few as twenty-three instructions, within a time span of four hundred generations. Different runs under the same initial parameters, but using different seeds to the random generator, achieved different degrees of optimization. These runs have plateaued at forty-three, thirty-five, twenty-six, twenty-four and twenty-three instructions.
An obvious interpretation of these results is that evolution gets caught on a local optima, from which it can not reach the global optima [6]. However, analysis of the ``sub-optimal'' (larger) final algorithms suggests an alternative interpretation. An efficiency measure was calculated for each resultant organism, in which the total number of CPU cycles expended in replication is divided by the size of the organism. The efficiency index measures the cost of moving a byte of information by that algorithm, in units of CPU cycles per byte.
Table 2: Comparisons of Size, Efficiency and Complexity in Evolved Algorithms from eight runs of instruction set four. The first column, ``Run'', refers to which of the eight runs this result occurred in (compare to Table 1). The second column, ``Genotype'', lists the name of an example of an algorithm of the smallest size evolved in that run. The third column, ``Efficiency'', lists the efficiency of that algorithm, calculated as CPU cycles expended for each byte moved during reproduction. The rows of the table are sorted on this value, with the highest efficiency (least CPU cycle expenditure) at the top of the table. The fourth column, ``Unrolling'', is an indication of the complexity of the central loop of the algorithms. This indicates the level to which the central loop is ``unrolled'' (see explanation in text). An asterisk in the final column indicates that the assembler code for this algorithm can be found in Appendix C. The algorithm 0082aaa is the ancestral program, written by the author, and is included for the sake of comparison.
Run Genotype Efficiency Unrolling R6 0043crg 3.33 3 R4 0035bfj 3.49 3 * R3 0026ayz 3.73 2 R5 0024aah 3.96 2 * R2 0023awn 4.96 1 * R1 0023api 5.04 1 R7 0023aod 5.09 1 R0 0026abk 5.19 1 RX 0082aaa 8.39 1 *
Table 2 ranks the evolved organisms by this measure of efficiency. They arrange themselves almost perfectly in reverse order of size. With the exception of the last algorithm, 0026abk, the evolved algorithms show a pattern in which the larger algorithms are the most efficient. Examination of the individual algorithms shows that the larger individuals have discovered an optimization technique called ``unrolling the loop''. This technique involves the production of more intricate algorithms.
The central loop of the copy procedure of the ancestor (0082aaa) for instruction set four (see appendix B) performs the following operations: 1) copies an instruction from the mother to the daughter, 2) decrements the CX register which initially contains the size of the parent genome, 3) tests to see if CX is equal to zero, if so it exits the loop, if not it remains in the loop, 4) jumps back to the top of the loop.
The work of the loop is contained in steps 1 and 2. Steps 3 and 4 are overhead associated with executing a loop. The efficiency of the loop can be increased by duplicating the work steps within the loop, thereby saving on overhead. The creatures 0024aah and 0026ayz had repeated the work steps twice within the loop, while the creatures 0035bfj and 0043crg had repeated the work steps three times within the loop.
These optima appear to represent stable endpoints for the course of evolution, in that running the system longer does not appear to produce any significant further evolution. The increase in CPU economy of the replicating algorithms is even greater than the decrease in the size of the code. The ancestor for instruction set four is 82 instructions long and requires 688 CPU cycles to replicate. A creature of size 24 only requires 95 CPU cycles to replicate, a 7.24-fold difference in CPU cycles, and a 2.12-fold difference in efficiency (CPU cycles expended per byte moved). A creature of size 43 requires only 143 CPU cycles to replicate, a 4.81-fold difference in CPU cycles, and a 2.52-fold difference in efficiency.
Unrolling of the loop is not unique to instruction set four. It has also been observed in the original instruction set. Appendix D contains the central copy loop of the ancestor (0080aaa) of instruction set one, and also the central copy loop of an organism that evolved from it (0072etq), which exhibits loop unrolling to level three.