Top-Performance Genetic Programming
Can Only C++ Get You There?
In this talk we will introduce "Genetic Programming", a variant of genetic algorithms in which the individuals are actual programs, evolved via natural selection.
This classical artificial intelligence technique has proved its worth; for example, it evolved electronic circuit designs that were patented.
Top performance is critical: to find the fitness of each individual in the population, every program is executed in its target environment. This means tens of thousands of instructions for tens of thousands of programs, over thousands of generations!
This scenario is great to show an approach to performance based on the Generic Programming Paradigm ("Stepanov-style" Generic) that is rather unique to C++ in both the results and the programmer effort leverage.
We get so close to the edge of what is possible in terms of performance that we see C++ beginning to be insufficient, such as the practical inability to encode what ought to be emitted as computed jumps.
Implementing top performance Genetic Programming also gives us experience with valuable techniques including JIT (Just In Time optimization), the statistical "alias" sampling method, and a host of principles that are unexpectedly general and important. For example, it surprised me to discover that exponential backoff in Ethernet is very similar to solutions to something called the "multi-armed bandit problem", which I later learned is not arcana, but a classic decision-making problem critical in fields as dissimilar as choosing treatments for diseases and advertising optimization, and the study of this problem in turn is very similar to the question of which individuals "deserve" to be bred into the new generation, a key concern of genetic algorithms...
We have two concrete examples, including the famous “Santa Fe Trail” ants, that show how genetic programming generates control programs that are very hard to beat with manual programming and that often have a surprising resiliency: unlike most hand-written code, they tend to keep working after minor changes.
We will make an interactive demonstration of the evolution of programs by showing text-animations of the best "ants" each generation.
Eduardo Madrid
High Performance and Generic Programming C++ Software Engineer, with experience in financial technologies and other fields.
Presenter several times at users groups and C++ conferences