I once again spoke at 28C3 in Berlin, Germany for Part-Time Scientists. Today, the topic was Evolving Custom Communication Protocols. We used Cartesian Genetic Programming to create the finite state machines of a transceiver, including all packet flow control logic. This only works when there is at least some trivial adversary, such as Outer Space for our moon mission. The technique works even better when an attacker is included and allowed full access to all data and is coevolved with the transceiver. For our runs, transceivers evolved with and without an attacker both handle a validation case equally well, but the transceivers evolved with an attacker are accelerating their evolution and will soon out perform their less-stressed cousins.
Code, data, and the presentation PDF/PPT are online here:
http://dl.dropbox.com/u/5001972/EvolvingCustomCommunicationProtocols.zip
The YouTube video is here:
http://www.youtube.com/watch?v=zoOOpiMJQ8s
Wes Faler's Blog 
1. Great talk & a big thumbs up for sharing the code!
2. Can we expect a technical paper on using (c)GP for evolving interplanetary com protocols?
2.1 When? 😉
3. Do you know about any other finished projects/reports that used (c)GP for their solution?
4. Your thoughts on developers using cGP for developing better numerical/xy algos?
5. Will the GPU code be on github/bitbucket?
5.1 When?
6. You said there isn’t any general template project for cGP. Will this be an equivalent of pyevolve?
7. Except the literature you state at the end of the talk, any other recommendations? There seem to be many theoretical/based on experiments reasons for some parameters… any recommended articles before diving into the code?
tnx
1. Danke Terry. Last session slot of the conference, I’m just glad people had energy to show up!
2. Yes, focusing on the use of complex chromosomes with shared state as event handlers. From a coder perspective, this approach is a natural fit with simulations.
2.1 In a month or two most likely. The rent check needs lots of CPU time for a while.
3. Only the few examples I’ve seen online. The book on CGP makes use of CGP for real-world projects. I’ve personally used tree-based GP to recover equations from a compiled Matlab module with lost source code, and to create an algorithm for postal address correction which is in use commercially.
4. Interesting… A quick response (pardon the jetlag) is that numerical algorithms are tricky because they need to be well matched to the problem. Perhaps “seed” a CGP grid with a general-purpose algorithm then evolve it for the problem at hand. For speed, evolve with a large tolerance and validate with a smaller tolerance. Fitness tests on problems with unknown answers would have to be centered around tolerance (for zero-crossing problems) and stability (fuzzing inputs and initial guesses).
5. Likely, yes. The goal is to put up the code and documentation not just a quick .zip file.
5.1 When can you start helping? 😉 See 2.1.
6. None that I’ve been able to find. pyevolve looks nice for human learning – essential for humans adjusting the scoring algorithm and problem statement. Perhaps the CGP code can be integrated into pyevolve?
7. The CGP book was very useful. I put together an implementation before the book was published but didn’t get good results until following the advice for mutation rates and sizing. At 28C3, Aleke Nolte passed along some interesting information on meta parameter optimization using Covariance-Matrix-Adaptation-Evolution-Strategy (CMA-ES). Experiments are essential to tune parameters. Use lots of short runs and automate the gathering of details from the runs.
Hello, thank you for such a nice talk as well as sharing your code!
I was watching the talk and at the end there was some discussion about code complexity. I think it might be useful to have certain fitness rules appear after a certain number of generations (or other criteria). For example, it is most important to evolve good protocol code first and have it be minimal complexity second. So perhaps you could start with the protocol fitness criteria alone and then after a fitness score of 1,000 or 200,000 generations then add in the complexity criteria to minimize energy consumption on the mission. Perhaps the runs could have several “phases” of fitness according to stricter and stricter criteria.
Danke and agreed about the fitness phases. I tried something similar with the image CGP – once all test cases were met, minimize program size – and liked the results. It would be cool to save results and restart the population when a new fitness phase is devised. In my limited experience, the hardest part of a fitness function is learning what we humans really want. We can draw a line from point A to B, but if we do so with a 1 meter wide paint roller, it won’t pass on a classroom exam. Fitness phases feel like a way of evolving a solution as our understanding of the real requirements evolves. It’s not clear though if the resulting solution is the same as when the full fitness was applied from the beginning. Maybe in a few hundred more test projects it’ll all become clear.
Hi Wes,
Great stuff thanks for sharing, I have started to play with CGP myself. I like the visualization you created in the PNG files. Did you use a package to create these images as I would like to do something like this myself to do a sanity test of the output.
-Greg
Thank you Greg. The package used is Graphviz. The CGP code writes “.dot” files in Graphviz’s Dotty language then I run a script to make PNGs out of them, something like: for /f %%a IN (‘dir /b *.dot’) do dot -Tpng %%a >%%~na.png
If you can, I’d love to see some examples of your system’s output as well!
-Wes
Hi Wes,
Great tool! I have coded up a conversion to DOT. I have my first PNG file, I don’t see a way to load it up on your blog, how do I get it to you?
-Greg
Hi Wes,
I am not sure you got my reply emails. I sent you a PNG file, I have better ones now. I Love Graphviz!
-Greg
Hi Greg. Yes, I got your images – very nice. Can you send the new ones? Do you mind if I share them here?
-Wes