29
Dec
11

Algorithm Invention with Cartesian Genetic Programming

A couple of days ago, I got the honor of presenting at 28C3 in Berlin, Germany for the Part-Time Scientists!  The topic was “Automatic Algorithm Invention” and featured my foray into Cartesian Genetic Programming.  The topic is exciting actually and much easier to get started with than you might think!  To prove it, I’ve posted the presentation materials and code:

http://dl.dropbox.com/u/5001972/AutomaticAlgorithmInvention.zip

There is also a YouTube video of the presentation:

http://www.youtube.com/watch?v=tQvFZVlM2Gk

For me, the heart of the technique is the addition of “state” to the input and output variables.  Chromosomes each get private state and share common state.  They are evolved to cooperate and share information via this state.

Danke everyone that turned out and I look forward to hearing about your adventures with evolving algorithms!

Advertisements

6 Responses to “Algorithm Invention with Cartesian Genetic Programming”


  1. 1 CGPFan
    March 18, 2012 at 6:04 pm

    I thought your talk was great. Took me from not knowing to knowing. Also, I am really happy you shared your code. A clean sample implementation can cut through 100 wordy papers!

  2. November 2, 2012 at 12:26 pm

    I’ve been writing a genetic programming library recently, and have been looking at your code. One question which arises is why you don’t appear to be using crossover to produce the next generation, but only mutation. Also the requirement that child genomes be at least as fit as parents surely has the hazard to getting stuck in local fitness maxima.

    • November 2, 2012 at 1:10 pm

      Crossover isn’t used for two reasons: a) other researchers found it useless with regular CGP, and b) I haven’t figured out modular CGP where it has helped. The fitness issue is an interesting one. We promote a child that is the same fitness as the parent, carrying forward unexpressed mutations. The hope is that some future child will get the one lucky mutation that favorably expresses all the accumulated mutations. I’ve tried CGP only promoting a better child and it does get hopelessly stuck. Promoting an equal, but mutant, child still has slow progress after a while but it still does make progress. The initial population’s form remains critical though, so I’ve found it best to do many runs with initial populations – a simple “island” system. Perhaps some system to take big jumps when progress gets slow would make sense as well. What do you recommend?

      • November 2, 2012 at 1:34 pm

        I don’t yet have any recommendations, since I’ve not done enough experimenting. In the library which I’m writing I’m going to support both classical and Cartesian genetic programming, with configurable function sets.

        The latent information situation is similar to the biological case, where you have diploid chromosomes containing information which can be inherited but which isn’t necessarily expressed in the current phenotype.

        I’d not seen anything about the “island” system previously, and am not sure that I really understand it. It sounds like a gated lock system where you have water at different levels (like populations at different average fitness levels) and that once individuals rise to a similar capability then can then migrate upwards or downwards between populations.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: