AI research environment for artificial code generation (metaprogramming).
Check out corresponding Medium article: Meta Intelligence - Writing Programs That Write Programs (Part 1: Genetic Evolution)
Given an esoteric and minimalistic, though Turing complete programming language Brainfuck, we aim to artificially generate programs that perform specific tasks.
Brainfuck has only 8 instructions making it very easy to read for computers (check python interpreter brainfuck_interpreter.py) but on the other hand, very hard to understand for humans, thus the name.
">" Increment the pointer.
"<" Decrement the pointer.
"+" Increment the byte at the pointer.
"-" Decrement the byte at the pointer.
"." Output the byte at the pointer.
"[" Jump forward past the matching ] if the byte at the pointer is zero.
"]"] Jump backward to the matching [ unless the byte at the pointer is zero.
"," Input a byte and store it in the byte at the pointer.
Our goal is to generate a brainfuck program that outputs a given target string. Example usage for a target string of 'HI': python3 genetic_evolution_meta_programmer.py 'HI'
- We are going to start with a population of random chromosomes where every chromosome will be a brainfuck program represented as a string of random instructions. Example chromosome:
[->+]+.-><>+. Keep in mind that the vast majority of randomly generated programs will be syntactically incorrect so we need to validate them with interpreter before adding to the population. - Then we are going to proceed to the selection phase where we are going to pick top performing programs. Programs are evaluated with a fitness function that calculates score for every character with the following function:
fitness_score += ASCII_CHARS_COUNT-abs(input_score-target_score)which is basically calculating the distance from the given character to the desired one on the ASCII table. The closer we are to the target character. The bigger the score, the closer we are to our target withASCII_CHARS_COUNTas a max per character. Maximum fitness score per chromosome is calculated aslen(self.target)*ASCII_CHARS_COUNT. - Next we are going to pair chromosomes with roulette selection and perform a crossover.
- Finally we are going to perform mutation. Some programs after mutation are invalid so we are going to replace them with the random valid ones to keep the population constant in size.
- We are going to repeat steps 1-3 until we find the target string.
POPULATION = 100
MUTATION_RATE = 0.115
MAX_MUTATION_ATTEMPTS = 500
SELECTION_RATE = 0.9
PROGRAM_LENGTH_LOWER_BOUND = 10
PROGRAM_LENGTH_UPPER_BOUND = 100
FOUND SOLUTION: +++++++++++++++++++++++++++++++++. for: '!' in: 5 minutes
FOUND SOLUTION: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+. for: 'HI' in: 27 minutes
FOUND SOLUTION: +++++-+++[>+++++++<-]>-+.+.+. for: '123' in: 20 minutes
Coming soon!
Greg (Grzegorz) Surma
