Growing programs

New Year's holidays have passed and I remembered BrainFuck. There was no desire to write my own sea ​​battle , but I wanted to, like in the fairy tale “Well, ka, bend, write yourself!”.

The basis was the article “Hello world!” Using genetic algorithms . Therefore, I will immediately proceed to the solution of the following problem: to write a program that will write programs using the BrainFuck genetic algorithm, which outputs the given string. Implement it in Java.

First we need the BF code interpreter, we will not reinvent the wheel, we will use the BFI library * Copyright © 2003 Thomas Cort . For experiments, I added her the ability to run as a separate thread.

Class for program description:
class Individ implements Comparable
{
//
String data;
//
double fitness;

// .
// fitness ""
public int compareTo(Object o)
}

')
Now let's start writing the genetic algorithm. The steps of the algorithm are shown in the figure:


The first is the formation of a population; we get it by randomly arranging operands from the vocabulary of the BF language.

The reproduction function is responsible for crossing, it takes two random individuals into two parts and sticks together the resulting halves in pairs for the whole population.

Implemented three types of mutations:
1) replacement of one operand by another;
2) adding an operand to a random position;
3) adding a loop.
The third item is introduced because the cycle consists of "[" and "]" and if you add one at a time, the program will not be correct.

The most difficult function is to calculate the fitness of an individual. The suitability value indicates how much the result of the program has deviated from the desired value.
The first thing that came to mind is to consider the sum of the difference in characters in a string, for example, abc - aaa = 3, but with this approach, the genetic algorithm quickly finds a point of local extremum and then goes in a loop.
Let's look at an example. We want to get the string "abb" and the program:
+++++++ [<++++++++++++++> -] <…
displays “bbb” the suitability of such a program 1. To get at the first position to get “a” we need to put “-” after the cycle:
+++++++ [<++++++++++++++> -] - <…
this program already displays “aaa”, but its suitability has become 2, which is worse and such an “individual dies”.
Therefore, suitability will be considered depending on the position of the symbol, for example, abc - aaa = | a - a | * 100 ^ 3 + | b - a | * 100 ^ 2 + | c - a | * 100 ^ 1 = 100200. Thanks to this approach, the symbol to the left has higher priority.

The selection is a simple sort by descending value of fitness.

And until we get the program we will multiply and mutate.

And here is the result of the program, for the string "Hello":

449th generation
Program Length: 236 characters Program text: +++++++++++++++++++ ++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++ ++> ++++++++++++++ +++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++ ++ - ++++++++++++++++++++ ++ ++++++++ +++.>

Source code at code.google.com
Mirror on ifolder