1.1.1. CoreWorld

Artificial evolution for self-replicating computer codes has been introduced for the first time in 1990, when Steen Rasmussen created CoreWorld.[1] CoreWorld is a virtual machine which can be controlled by a language called RedCode. This assembler-like language has a pool of ten different instructions that take two addresses as arguments. Rasmussen’s idea was to introduce a random flaw of the MOV command, resulting of random mutations of the self-replicating codes within the environment. The big disadvantage of RedCode was, that nearly all flaws led to a lethal mutation, hence evolution did not occure as wished.

1.1.2. Tierra

In 1992, Tom Ray found out that the problem with RedCode was due to argumented instruction set: Independent mutations in the instruction and its arguments are unlikely to lead to a meaningful combination.[2] Instead of direct connection between the instruction and its argument, Ray developed a pattern-based addressing mechanism: He introduced two NOP-instructions (NOP0 and NOP1). These instructions do not operate themselve, but can be used as marker within the code. A pattern-matching algorithmus would find the first appearence of a complementary marker string given (after the search-command), and returns its addresse.

PUSH        AX        ; push ax
        JMP
        NOP0
        NOP1
        NOP0                ; jmp marker101
        INC        A        ; inc ax
        NOP1
        NOP0
        NOP1                ; marker101:
        POP        CX        ; pop cx
 

There are 32 instructions available in the virtual Tierra world, roughly based on assembler (JMP, PUSH AX, INC B and so on). With these inventions, Ray was able to gain great results for artificial evolution (like parasitism, multi-cellularity[3][4], ...).

1.1.3. Avida

In 1994, Christoph Adami has developed another artificial evolution simulation, called Avida. Beside of some different structures of the simulation, an important change has been made in the artificial chemistry: Instead of hardcoded arguments within the instructions (as in Tierra for example PUSH AX), instructions and arguments are completely separated. The arguments are defined by NOPs (in avida there are three NOPs: nop-A, nop-B, nop-C) following the operation (for example, a nop-A following a PUSH pushes the AX-register to the stack). There are 24 instructions available in avida, again roughtly based on assembler (call, return, add, sub, allocate and so on).

push
        nop-A                ; push ax
        jump-f
        nop-A
        nop-B
        nop-B                ; jmp markerBCC
        inc
        nop-A                ; inc ax
        nop-B
        nop-C
        nop-C                ; markerBCC:
        pop
        nop-B                ; pop bx
 

With that improvements of the virtual simulation, the researchers using avida found out amazing results, among other things about the origin of complex features in organism [5].

Very interesting paper on creating a evolutionary system for native x86 systems. This is an area that has fascinated me since I first studied genetic algorithms. However I didn't realize that this was being done for native x86 instruction sets as well, I always assumed that the environment was a virtual one.