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.
Asexual Replication
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.
Sexual Replication
See the section on SPORES to learn about how the MERGE operation works.
Mutations
This section describes in detail how a genetic program is mutated prior to the creation of a new organism. The user can control the probabilities that these mutations occur using this dialog:
There are 5 types of mutations that are applied:
Duplication: Duplicate an instruction or code block.
Deletion: Delete an instruction or code block.
Insertion: Insert a new instruction or code block.
Transposition: Swap two instructions or code blocks.
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 Type Instruction-level Code Block-level
Duplication Pick a random strand of instructions/numbers and repeat it at a random spot
Pick a random code block and add a copy to end of program
Deletion Pick a random strand of instructions/numbers and remove it
Pick a random code block and remove it.
Insertion Generate a random strand of instructions/numbers and insert it at a random spot.
Insert a new code block and fill with random instructions.
Transposition Pick 2 random strands and swap them
Swap 2 random code blocks
Modification Pick a random strand and modify every instruction/number in it.
Pick a random code block and modify every single instruction or number
Mutation Process in Detail
Right before a new organism is born, its genetic program is mutated using the following process:
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
Each of the five mutations are attempted in this order:
Duplication.
Deletion.
Insertion.
Transpostion.
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
If program has no code blocks (very unlikely), exit without changing anything.
If program already has Max. Code Blocks, then exit without performing this mutation.
Pick a random code block
Pick a random spot to insert a copy of the code block selected in previous step.
Create "gap" by shifting all code blocks down and insert copy.
BEFORE AFTER
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
Pick a random code block
If code block is empty, then exit without changing anything.
Pick a random strand within th code block. (of length 1 to 4).
Insert this random strand at a random spot.
BEFORE AFTER
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
Chose between deleting the code block.
If this program only has one code block, then exit without changing anything.
Pick a random code block
Delete it.
Shift all higher numbered code blocks to fill the gap.
BEFORE AFTER
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
Pick a random code block.
If code block is empty, then exit without changing anything.
Pick a random strand (of length 1 to 4) within this code block.
Delete it, and shift all successive instructions down by 1.
BEFORE AFTER
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
If program already has Max. Code Blocks, then exit without performing this mutation.
Pick a random code block number for the insert to happen.
Shift all code blocks at this number, to create an empty slot for the new code block.
Pick a random length for the new code block (a value between 0 and 4).
Fill new code block with that many random instructions/numbers.
BEFORE AFTER
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
Pick a random code block.
Pick a random spot to insert a new strand (of length between 1 and 4).
Shift all successive instructions to make room for the new strand.
Create a new random instruction sequence (of length 1 to 4) at that spot.
BEFORE AFTER
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
Pick 2 random code block.
If they are same, exit without changing anything.
Swap the code blocks
BEFORE AFTER
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
Choose 2 random code blocks
If either one of them is empty, then exit without changing anything.
choose 2 random strands of equal length (between 1 and 4 instructions long) from each code block.
swap them.
BEFORE AFTER
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
If program has no code blocks (unlikely), exit without changing anything.
Choose a random code block.
Modify all numbers, but leave instructions alone
BEFORE AFTER
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:
Action Probability
+4 1/9
+3 1/9
+2 1/9
+1 1/9
swap sign 1/9
-1 1/9
-2 1/9
-3 1/9
-4 1/9
Modify Instruction
Pick a random code block.
If code block is empty, then exit without changing anything.
Pick a random stand (of length 1 to 4) within this code block.
For each instruction/number in the strand:
If it is a number, increment/decrement the value by 1 to 4 or swap sign. See table above.
If it is an instruction, pick a new instruction (but do not change it to a number).
BEFORE AFTER
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.
Facebook
Twitter
Instagram