This section discusses the theory behind the time slicing schemes used in avida. Time slicing is the method by which the creatures in the grid are allocated CPU time to execute their code. Some creatures have faster CPUs than others, so the time slicing code must make sure they all run at the appropriate (relative) rates. Each creature has a merit which determines the speed of its CPU; the time slicer will adjust this merit as creatures perform tasks deemed desirable in this environment.
The mechanism by which portions (or slices) of CPU time are distributed to the individual processors on the grid significantly influences the global behavior of the population; here we examine it in detail.
The idea behind a system such as avida is to explore the complexity that the chemistry of self-replication has introduced, without actually simulating chemical reactions. Rather, the chemistry of the polypeptides coded for in the DNA is replaced by executing the string of instructions. As in chemistry, we expect different genomes to have different properties, most of which are reflected by either a greater or lesser amount of CPU time triggered by the cell. This is the equivalent of endothermic or exothermic reactions. Replication and execution of instructions costs CPU time, thus consuming energy.
On the other hand, certain instructions executed in the right order can trigger large amounts of bonus CPU time, the equivalent of a catalyzed reaction which benefits replication. As in real chemistry, it is problematic to specify which sequence of instructions is beneficial; rather, we construct the environment by rewarding effects, such as we did in our experiments with integer computation (discussed below). In the remainder of this section, we point out how this mechanism can be used to breed desired traits.
In addition to this external bonus structure, which effectively distinguishes one environment from another, we specify basic systems of CPU-time distribution that describe the low-level aspects of the virtual chemistry we are constructing. This is the time-slicing system proper. To define the time slicer, we have to decide how much time a cell should be worth by default, i.e., without studying the effect this string has when executed in a population.
A simple choice would be to give each string a constant time slice regardless of its size. This is the primary mechanism used in the tierra system. With such a choice, all cells attempt to minimize the length of their code by shedding superfluous instructions. The shorter they are, the less they have to copy, and the more copies they can make of themselves in the fixed amount of time they are given. The gestation time is roughly linear in the length of the cell. The advantage gained by shrinking the code is so dramatic, however, that cells might even choose to shed sections of code that trigger moderate bonuses. Such a method certainly provides for very efficient optimization while discouraging the evolution of complex code by magnifying the barrier to neighboring local minima in the fitness landscape. As far as the structure of the fitness landscape for the strings is concerned, such a slicer increases the local slopes and thus accelerates convergence to a local energy minimum while reducing ergodicity.
Another possibility is to distribute CPU time in a manner proportional to the length of the code. This is the size-neutral scheme also used in tierra. The resulting fitness landscape is intuitively much smoother; strings that behave in the same way but differ in length of code are degenerate as far as their replication rate is concerned and far-lying regions in genotype-space can be accessed easily. Clearly this mechanism is much more conducive to the evolution of complexity. However, it has a certain disadvantage from a practical point of view, as the instruction set provides the possibility to jump over sections of code. The cells soon discover that they can earn free CPU time by developing code that is neither executed, nor properly copied. This does not exist in real chemistry, as even DNA that is not expressed still participates in chemical interactions.
We therefore developed two mechanisms to handle this. The first counts only those instructions that were copied into the creature, or alternatively (as defined during the configuration of the run) only those instructions executed by the creature, in evaluating the effective length. Under these conditions, lean cells are favored over those that carry sections of un-executed, un-copied code. The second mechanism forces a creature to copy at least 70 percent of itself into its daughter, and execute at least 70 percent of itself, or else all divides will fail. The precise parameters are, again, configurable in the genesis file.
The slicers discussed here can be distinguished by a simple formula that describes the mechanism. Specifically, the time doled out (allocated) to each cell a priori is proportional to the creature's merit, where merit is determined by the number of instructions copied into (or executed by, depending on the configuration) the creature, times any bonuses given to a creature through its interaction with the environment. This multiplication (as compared to the method of addition of bonuses used in previous incarnations of avida and in tierra) serves to ensure that there is no size bias in evolution. In the case where bonuses are additive, they will soon overshadow the size component of the merit thus bringing back the constant time-slice paradigm. Note that enforcing size neutrality is strictly speaking un-biological, as it is known that self-replicating strings will shed all unnecessary instructions if given the opportunity. In avida, size neutrality is necessary in order to jump start the evolution of complexity.
Since the time slicer defines the landscape (and thus the ``physics'' and artificial chemistry) associated with self-replication, we can superimpose any landscape we deem interesting. This is done by specifying bonus CPU time associated with the phenotype of the string. By rewarding actions rather than a particular sequence of commands within a genotype, we introduce the possibility for open-ended evolution. As the set of possible strings that have the same phenotype is effectively infinite if no bounds are put on the length of strings, it is impossible to construct a string with maximum fitness given a complex enough environment. The complexity of the landscape (here identified roughly as proportional to the number of distinct local minima) increases exponentially with the number of distinct bonuses specified, as they can in principle be triggered simultaneously and in any order (often integrated so precisely that the same section of code will work on multiple tasks at once). As an example, consider the landscape we constructed in such a way that the adapted population would reflect a phenotype capable of adding integer numbers.
As a first step, we reward doing any form of input and output. We then further reward the correct input/output (I/O) structure (i.e., a minimum of two get and one put command, in that order). For each such step, we multiply the creature's merit by a fixed amount. This is admittedly a deviation of the principles just stated, as we reward a genotypical signature rather than a phenotype. However, since I/O is a low-level characteristic (achieved by executing the single instructions get and put), this deviation appears to be warranted. Also, any additions to the instruction set which also allow for manipulation of the input and output buffers should also trigger their bonuses.
Next, we reward the capability to echo numbers (which were read from the input) into the output. This reward is phenotypic, as it can be obtained in a number of distinct ways, all which which are rewarded as long as they properly complete the task. Finally, if a put command writes into the output buffer a number which is the sum of two previously read numbers, the string is rewarded with another bonus. Each of these rewards can be triggered multiple times each gestation period, typically to a maximum of three. By default, the bonuses multiply the creature's merit by a fixed factor the first time they are triggered, while only multiplying them by a smaller factor (1.25) thereafter. This is both to encourage diversity in ability, and because it is typically easier to perform a task multiple times than it was to learn it initially.
How such a bonus structure carves a landscape in the space of all fitness improvements becomes obvious (or at least intuitive) if we analyze the population shortly after it adapted to the echo bonus. At that point, mutated strings write all sorts of numbers into the output, numbers that are obtained via random manipulations. Among those we find sums, differences and multiples of the input numbers. The gene for addition is simply filtered out by rewarding this particular task out of all those currently being performed. Any other task can be filtered in the same manner. Quite literally, rewarding addition creates a valley that only those cells with the appropriate gene can occupy. Since cells in the lower regions of the landscape obtain more offspring than those higher up, they soon dominate the population and drive strings missing the gene into extinction. Once this is achieved, the adapted population spreads in diversity via the effects of mutation, to explore new regions of the landscape where perhaps more crevices can be found. Such a sequence of adaptations results in a fitness curve resembling a staircase, which can be a true fractal if the environment is complex enough.
The fitness of a cell in such simple systems is given by the total effective number of offspring it can generate in its environment. Theoretically, this is given by the merit M earned by the cell, divided by the time it takes to generate an offspring, the gestation time tg
fitness = M / tg
This fitness measurement is a unitless quantity which can be directly compared to the fitness of any other creature to determine their relative reproduction speeds. If one creature has twice the fitness of another then it will be able to have twice the number of offspring per unit time.
These algorithms handle the details of grid execution; they ensure that cells are executed with simulated parallelism to minimize any advantage dependent on execution order which may occur.
This system provides a method of time-keeping independent of grid size; in tierra, the standard time measure is one million instructions, which depends entirely on the population size. In a large population, several measurement periods might pass before the population is entirely executed even once. In avida, as the grid becomes larger, the entire grid is executed during each measurement period, and as the time slicer allocates more time (more energy) the cells run correspondingly faster in relation to the measurement periods. In addition, many of the algorithms provide a natural interface to distribute the avida system across multiple processors (see below).
In order to properly configure the time-slicing scheme, edit the ``Time Slicing'' section of the genesis file (see the Configuration section). The first value, AVE_TIME_SLICE will set the average number of instructions a creature should execute every update. By default, this value is set to 30.
Next we have SLICING_METHOD; this is an important control which determines just how the time blocks are doled out. The options are:
The next variable that can be configured for time-slicing is the SIZE_MERIT_METHOD. This determines what the base value of the creature's merit is proportional to: its full size, its executed size, its copied size, the smallest of the latter two, or just a constant value (independent of size). In avida, the default method is to select the minimum of executed and copied size to determine base merit. The relative value of the different methods is briefly discussed above. These different choices allow for a varying amount of junk (i.e., unexecuted or even uncopied) code to develop in the creature's genome.
Finally, we have TASK_MERIT_METHOD, which simply determines if tasks should be used in determining merit. This is a binary switch, turned on by default.
NEXT: Reproduction
PREV: An Overview of Avida
Page maintained by Charles Ofria
Send all comments to
charles@krl.caltech.edu