Intro Genetic Programming [Desiderius part #15]

I missed a weekend, sorry guys! I was busy babysitting a five year old and contemplating the LambdaConf situation. To make it up I have a totally fresh and new topic to talk about: genetic programming. I do not want to design a bidding systems, I want to make the best one possible, and for that I intend to use genetic programming. The idea of genetic programming is that instead of typing a program, we create it (also called synthesizing).

A quite simple example is the following:

We have a method that returns a string:

function helloFSharpLovers() {
   return "123";
}

Yeah I know this is JavaScript and not F# but I am preparing for an F# conference 🙂 It is JavaScript so I can embed an example later and you and see it in action!

The string we want to return is “HELLO FSHARP LOVERS” So, we can type this, but why? That is so tiring… I want the machines to work for me, using some principles from evolution.

In order to mimic evolution, we need two things: the ability to create new versions of programs (mutation) and knowing which of your children is most likely to succeed (fitness)

Mutation

I can define a number of transformations that mutate my program, like replacing a letter or adding one:

function mutate(input)
{
   var operation = Math.floor(Math.random() * 2);

   var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
   randChar = chars.charAt(Math.floor(Math.random() * chars.length));

   if (operation == 0){
      //get a random location
      var location = Math.floor(Math.random() * input.length);
	
      var firstPart = input.substring(0,location);	
      var secondPart = input.substring(location+1, input.length);
	
      return firstPart + randChar + secondPart;
   }

   if (operation == 1){
      return input + randChar;
   }
}

Survival of the fittests 

Now, when are we going the ‘right way’? For this problem, we could use string distance (Levenshtein distance). So, we mutate the function into returning a slightly different string, and if we are closer to the result, we keep it, if not, we discard it:

function runGenetics(){
   while (code != goal)){
      var mutatedVersion = mutate(code);
      if (levenshteinDistance(mutatedVersion, goal) <= levenshteinDistance(code,goal))
      {
         code = mutatedVersion;			
         editor.setValue(code);
       }
   }
}

Look, mommy, no hands (were hurt writing this code)

In the iframe below you see my code in action. Adapt the program manually and ‘Run current code’ to execute the function in the Ace editor or click ‘Make it so!’ to have the program generated for you!

Cool heh? Next week I will talk about how this works together with a DSL! How to eval() you own code? And what fitness function to use for a bridge bidding machine? Stay tuned!

8 Comments

  1. Maciej Bańkowski

    Cool. Interestingly on the first try the program produced “HELLO FSHARP LOVERSS” with a double ‘S’ at the end 😉

    1. felienne (Post author)

      Yeah, it is slightly hacky 🙂

  2. Pingback: Genetic programming on a DSL [Desiderius #16] – Felienne's blog

  3. J

    There’s an extra ‘return’ here.

    ` if (operation == 1){
    return return input + randChar; `

  4. Justin Blake

    Thanks for this. I’ve played with genetic algorithms before but I’ve never seen it broken down so simply. Definitely makes me want to get back into it.

  5. Pingback: A fitness function for bidding systems [Desiderius part #17] – Felienne's blog

  6. fl0id

    Stupid question, how do you get the Levenshtein distance without typing the string you want at least once … (and where is ‘goal’ defined?)

    1. felienne (Post author)

      No such thing as stupid questions!

      On each run you call the Levenshtein function with the goal and the new version. The goal is defined as a variable before running the genetics function.

Comments are closed.