Replication

The following two figures show the steps involved during asexual and sexual reproduction. They show when MERGE and MUTATE operations occur during the creating of a new organism.

Asexual reproduction involves only one parent. The new organism inherits all of its parent genetic material. The only way that the new organism could differ from its parent is because of the MUTATE process.

Sexual reproduction involves two parents. Each donates their genetic material to the creation (and fertilization) of a spore. The two genetic programs are first merged, and then the MUTATE procedure is applied to the result.

There are 5 types of mutations that are applied:

1. Duplication: Duplicate an instruction or code block.

2. Deletion: Delete an instruction or code block.

3. Insertion: Insert a new instruction or code block.

4. Transposition: Swap two instructions or code blocks.

5. Modification: Modify an instruction or code block.

The parameter, Max. Code Blocks, limits mutations so that the program never exceeds this number of code blocks.

The setting Max. Apply controls the number of time the mutation algorithm is applied before a new organism is born. The default is 10. This means that a random number from 1 to 10 is chosen before mutating a KFORTH program. The mutation algorithm is then applied this many times. To disable mutations you can set this to 0.

The parameter Mutate Code Block, controls the distribution between instruction-level mutations and code block-level mutations. The default, shown here, is 25% which means 1 out every 4 mutations will be applied to a whole code block.

Instruction-level mutations: operate on a small stretch of instructions and numbers. This will be refered to as a 'strand'. The length varies randomly from 1 to 4.

Code block-level mutations: operate on an entire code block.

Therefore each of these five mutation types can have two variants. This table summarized the ten mutation operations:

Mutation Process in Detail

The first step is to decide if we will apply the five mutation types at the instruction-level or the code block-level. Having made this determination we try to peform each of the mutations in this following order:

Mutation Order

1. Duplication.
2. Deletion.
3. Insertion.
4. Transpostion.
5. Modification.

Not all five mutations will occur, nor is it the case that we just pick one of them to occur. Each mutation type has its own probability it will occur. If by chance several of these mutations need to be applied, then this is the order it will happen.

Duplicate Code Block

1. If program has no code blocks (very unlikely), exit without changing anything.
2. If program already has Max. Code Blocks, then exit without performing this mutation.
3. Pick a random code block
4. Pick a random spot to insert a copy of the code block selected in previous step.
5. Create "gap" by shifting all code blocks down and insert copy.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { -4 -1 OMOVE EAT GROW ?loop and }
row2: { call /mod 69 LOOK2 79 ENERGY R4 }
row3: { -4 -1 OMOVE EAT GROW ?loop and }
row4: { 9 call 9 LOOK-SPORE call 8 8 }
row5: { EAT <> negate call }

Code block 2 (row2) was duplicated and inserted after 'main'.

Duplicate Instruction

1. Pick a random code block
2. If code block is empty, then exit without changing anything.
3. Pick a random strand within th code block. (of length 1 to 4).
4. Insert this random strand at a random spot.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop OMOVE EAT GROW and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

The random strand, "OMOVE EAT GROW" (from row2) got duplicated and inserted into a random spot within the same code block.

Delete Code Block

1. Chose between deleting the code block.
2. If this program only has one code block, then exit without changing anything.
3. Pick a random code block
4. Delete it.
5. Shift all higher numbered code blocks to fill the gap.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { -4 -1 OMOVE EAT GROW ?loop and }
row2: { 9 call 9 LOOK-SPORE call 8 8 }
row3: { EAT <> negate call }

The code block row1 was deleted and all successive code blocks were shifted up by 1. Here's an example of emptying the code block:

Delete Instruction

1. Pick a random code block.
2. If code block is empty, then exit without changing anything.
3. Pick a random strand (of length 1 to 4) within this code block.
4. Delete it, and shift all successive instructions down by 1.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

The strand OMOVE EAT GROW was deleted from row2.

Insert Code Block

1. If program already has Max. Code Blocks, then exit without performing this mutation.
2. Pick a random code block number for the insert to happen.
3. Shift all code blocks at this number, to create an empty slot for the new code block.
4. Pick a random length for the new code block (a value between 0 and 4).
5. Fill new code block with that many random instructions/numbers.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -9 negate + 80 }
row3: { -4 -1 OMOVE EAT GROW ?loop and }
row4: { 9 call 9 LOOK-SPORE call 8 8 }
row5: { EAT <> negate call }

At row2 we inserted a brand new chunk of random code. The length shown here is 4. The exising code blocks were shifted down 1 to accomodate the new code block.

NOTE: (1) numbers and instructions have an equal probability of being generated.
(2) New numbers will be selected randomly from the range -99 to 99.
(3) Instructions all have the same probability of being chosen.

Insert Instruction

1. Pick a random code block.
2. Pick a random spot to insert a new strand (of length between 1 and 4).
3. Shift all successive instructions to make room for the new strand.
4. Create a new random instruction sequence (of length 1 to 4) at that spot.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 MAKE-SPORE -9 dup ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

In row1, the instructions MAKE-SPORE -9 dup were added at a random spot.

NOTE: As with Insert Code Block, the process for generating a new instructions is:

(1) numbers and instructions have equal probability of being generated.
(2) New numbers will be selected randomly from the range -99 to 99.
(3) Instructions all have the same probability of being chosen.

Transpose Code Block

1. Pick 2 random code block.
2. If they are same, exit without changing anything.
3. Swap the code blocks

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { EAT <> negate call }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { -4 -1 OMOVE EAT GROW ?loop and }

Rows 2 and 4 were swapped.

Transpose Instruction

1. Choose 2 random code blocks
2. If either one of them is empty, then exit without changing anything.
3. choose 2 random strands of equal length (between 1 and 4 instructions long) from each code block.
4. swap them.

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 EAT GROW ?loop 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE call 9 call and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

The EAT GROW ?loop strand from main was swapped with the call 9 call from row2.

NOTE: This operation could transpose overlapping strands.

Modify Code Block

1. If program has no code blocks (unlikely), exit without changing anything.
2. Choose a random code block.
3. Modify all numbers, but leave instructions alone

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -5 1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

row2 was modified. All instructions are preserved, but numbers are tweaked slighlty. Numbers will be incremented or decremented by 1 to 4 (or the sign is swapped). Thefefore, there are 9 possible tweaks to a number. Each action has the same probablility:

Modify Instruction

1. Pick a random code block.
2. If code block is empty, then exit without changing anything.
3. Pick a random stand (of length 1 to 4) within this code block.
4. For each instruction/number in the strand:
   1. If it is a number, increment/decrement the value by 1 to 4 or swap sign. See table above.
   2. If it is an instruction, pick a new instruction (but do not change it to a number).

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod 69 LOOK2 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

main: { 8 call 9 call 1 call 9 call over }
row1: { call /mod -69 EAT 79 ENERGY R4 }
row2: { -4 -1 OMOVE EAT GROW ?loop and }
row3: { 9 call 9 LOOK-SPORE call 8 8 }
row4: { EAT <> negate call }

In row1 69 LOOK2 was changed to -69 eat.

NOTE: The new instruction is randomly chosen from the set of all instructions. All instructions have equal probability of being chosen.