Digital evolution: some recent studies
I've read some recent studies on Darwinist evolution of the computer code, and what is required to make such evolution computationally feasible. Basically, there are two main problems: almost all mutations of a typical piece of code are lethal, and the rewards landscape is too sparse (only goals we care about are rewarded), so the evolutionary process cannot find a "ladder" to climb to the goals. A couple of recent papers present case studies of systems where these problems were sufficiently rectified to enable nontrivial evolution.
A paper by Richard Lenski et al. shows how to set up a sufficiently dense rewards landscape for the evolution of Boolean functions:
Lenski, R. E., C. Ofria, R. T. Pennock, and C. Adami. 2003. The evolutionary origin of complex features. Nature 423:139-144.
http://myxo.css.msu.edu/lenski/pdf/2003,%20Nature,%20Lenski%20et%20al.pdf
The general idea here that you want to have enough goals of small and intermediate complexity (typically with the value of rewards increasing with the increase of complexity of a goal), so that enough building blocks for more complex goals are created in the process of evolving simpler goals. You don't have to require that more complex goals are made from the simpler goals, all you need is a reasonable expectation that building blocks needed for more complex goals will arise as a side effect of evolving simpler goals.
To make it all work, a system of coding reasonably robust to mutations is needed. A paper by Charles Ofria et al. discribes an apparently successful effort to produce such a system:
Design of Evolvable Computer Languages. Ofria C, Adami C, and Collier TC. IEEE Transactions in Evolutionary Computation 17:528-532 (2002):
http://www.cse.msu.edu/~ofria/home/pubs/papers/IEEE.pdf
They perform evolution on the level of binary code of a virtual computer. One thing they observe is that it helps to have argument-free commands working with fixed stacks and registers (basically, one wants an atomic mutation to make sense). Another feature is that the commands allowing a jump to a numerical address (even if this address is relative to the current place) are harmful to the robustness against mutation. Instead it helps to introduce what they call "templates", and what is just a mechanism of short symbolic labels expressed by a sequence of different "no operation" commands. This is essentially just a method to include short words as symbolic labels right into computer binary code. The jump then seeks the nearest particular label, either forward or backward. This discipline seems to increase the robustness of the code against mutations dramatically.
The experiments were run on the Avida platform, which was developed by the Digital Life Lab at CalTech and is freely available for Mac, Windows, and as a platform-independent source code.
A paper by Richard Lenski et al. shows how to set up a sufficiently dense rewards landscape for the evolution of Boolean functions:
Lenski, R. E., C. Ofria, R. T. Pennock, and C. Adami. 2003. The evolutionary origin of complex features. Nature 423:139-144.
http://myxo.css.msu.edu/lenski/pdf/2003,%20Nature,%20Lenski%20et%20al.pdf
The general idea here that you want to have enough goals of small and intermediate complexity (typically with the value of rewards increasing with the increase of complexity of a goal), so that enough building blocks for more complex goals are created in the process of evolving simpler goals. You don't have to require that more complex goals are made from the simpler goals, all you need is a reasonable expectation that building blocks needed for more complex goals will arise as a side effect of evolving simpler goals.
To make it all work, a system of coding reasonably robust to mutations is needed. A paper by Charles Ofria et al. discribes an apparently successful effort to produce such a system:
Design of Evolvable Computer Languages. Ofria C, Adami C, and Collier TC. IEEE Transactions in Evolutionary Computation 17:528-532 (2002):
http://www.cse.msu.edu/~ofria/home/pubs/papers/IEEE.pdf
They perform evolution on the level of binary code of a virtual computer. One thing they observe is that it helps to have argument-free commands working with fixed stacks and registers (basically, one wants an atomic mutation to make sense). Another feature is that the commands allowing a jump to a numerical address (even if this address is relative to the current place) are harmful to the robustness against mutation. Instead it helps to introduce what they call "templates", and what is just a mechanism of short symbolic labels expressed by a sequence of different "no operation" commands. This is essentially just a method to include short words as symbolic labels right into computer binary code. The jump then seeks the nearest particular label, either forward or backward. This discipline seems to increase the robustness of the code against mutations dramatically.
The experiments were run on the Avida platform, which was developed by the Digital Life Lab at CalTech and is freely available for Mac, Windows, and as a platform-independent source code.