Evolving Elixir Code: Genetic Programming with the Elixir AST
Genetic programming with Elixir’s macro system & abstract syntax tree
Genetic programming is a powerful technique for using evolution and natural selection as a search technique to create algorithms which can solve problems.
In this post, I describe how Elixir’s built-in macro system and abstract syntax tree (AST) representation make it simple to implement a basic genetic programming system that can solve real-world problems.
If you already know about genetic programming and just want to try out the code yourself, head on over to GitHub to checkout QuoteGP.
Evolving Solutions — What is Genetic Programming?
Genetic programming is a artificial intelligence technique in which we attempt to evolve an algorithm which solves a particular problem. We do so by starting with several random solutions, then using evolutionary techniques to guide us to better and better solutions over many generations. If everything works as expected, we find a solution which fits our problem perfectly.
Survival of the Fittest
Genetic programming works by starting with several (perhaps thousands) random pieces of code. We evaluate each program against the problem set to evaluate a fitness value — a number which tells us how good the program is at solving the problem. When we start with random algorithms, they’re almost always really bad (i.e., have very low fitness values). But some, just by chance, are slightly better than others. So then we use a selection process to take the best ones and evolve them slightly to produce a new generation of solutions.
The new generation of solutions is probably still bad, but just a little bit better than the one we started with. If we repeat this process over and over again, we eventually get solutions that are pretty good — and if we keep it up long enough, we may eventually get a perfect solution.
Genetic Operators
So how do we generate new solutions from the existing ones? We do so using a variety of genetic operators. In our QuoteGP system, we a couple of different genetic operators used to produce a new generation of solutions:
- Genetic crossover: take two solutions from the previous generation and mix them (combine parts of both) to produce a new candidate solution
- Mutation: take a solution from the previous generation and alter it randomly to produce a new solution
- Copy: take a solution and copy it “as is”
- Random: generate a fully random new solution
With the exception of the “random” operator, all of these operators use a selection process based on fitness when choosing which program to operate on. That means we prefer to operate on “better” solutions when performing crossover or mutation.
In the wider field of Genetic Programming, there are infinite variations on both the selection process and choice of genetic operators, but we keep it simple in QuoteGP and use the scheme described above.
How to Represent Evolvable Programs
For the purposes of building and testing this system, we’ll consider a class of problems called symbolic regression, in which we attempt to discover a mathematical formula which best represents some training data.
One of the most important considerations in building a GP system is the program representation: what does an executable genome look like?
We might be tempted to try a commonly used real-world programming language like C, Python or Ruby. Though human programmers are most comfortable with these languages, they do not lend themselves particularly well to evolution: in the search space of all representable textual strings, almost none of these strings are syntactically valid programs!
In designing a GP system (or in fact, any kind of evolutionary algorithm), the representation is key: we want a representation in which all representable states are valid programs, and which are robust to genetic operators such as mutation and crossover. This, for the most part, rules out the textual programming languages we’re used to using.
With that in mind, a common GP approach is tree-based genetic programming in which we represent programs as expression trees. Given a set of allowable nodes and terminal values, we can ensure that any tree is a valid program, and also that genetic operators such as mutation and crossover will also generate valid programs.
There are some other representation types such as linear GP which feature linear series of instructions similar to machine byte code or stack-based GP, in which typed stacks are used to store intermediate values, but for this project, we’ll focus on a tree-based representation.
Often, building out a tree-based GP in a language such as C, Java or Python, involves building some sort of novel representation and interpreter. But some languages, like Elixir, have a syntax tree and interpreter built-in as first-class concepts. In that case, we can do genetic programming natively using the language itself!
Homoiconic Languages & Genetic Programming
Some programming languages are homoiconic, meaning that code is data and data is code. In these languages, such as Lisp, genetic programming systems can be very simple to implement because the program representation is the data representation: evolved programs can be executed natively in the language.
Though the Elixir language is not fully homoiconic, it does provide native access and manipulation of a built-in abstract syntax tree (AST) which does feature these homoiconic properties. While Elixir code is not normally written as plain data, it is readily transformable back-and-forth to a plain data representation.
# Turn an Elixir expression into an AST:
iex(1)> quote(do: 1 * 3)
{:*, [context: Elixir, import: Kernel], [1, 3]}# Turn an AST into an Elixir expression:
iex(2)> Macro.to_string({:*, [context: Elixir, import: Kernel], [1, 3]})
"1 * 3"
What this means is that we can use Elixir ASTs as a native genetic programming representation to evolve Elixir code. We can generate random Elixir ASTs (subject to constraints we specify to keep them valid), evaluate their fitness, then perform generic operators on them to produce new ones. And if we find a solution or other program we’re interested in, we can convert it back into Elixir to read it or execute it.
Sample Problems — Symbolic Regression
A symbolic regression problem is a curve-fitting problem in which we try to determine the mathematical expression that will produce a series of output values for a given series of inputs. In order to test our system & demonstrate how it works, we’ll pick some toy symbolic regression problems that the system should be able to solve easily, but which still require some searching & evolution.
Let’s say we’re given a set of data that represents the observation of some process, and we’re trying to figure out a formula which could generate such data. For example, here we have a list of input and output values:
[
[10, 138],
[11, 162],
[12, 188],
[13, 216],
[14, 246],
[15, 278],
...
]We’d like our system to take this data, and evolve the programatic expression which produces it. In this case, the expression we’re after is x*x + 3x + 8. We know that because we made up the data ourselves, but we want to see if our genetic programming systems can figure it out for itself.
Note: though we previously talked about fitness values where higher values are better, in many implementations (including this one) we use error values meaning how far we are from the actual solution. These represent the same thing, only that we are trying to evolve smaller error values instead of higher fitness values. This is only an implementation detail and has no impact on how the system works.
Let’s see what the typical output of our QuoteGP system might look like:
=== Generation 0 best fitness: 252.0 - program: (10 - 1 + 7 * -1 + input) * (input + (3 - -8 / -4))
=== Generation 1 best fitness: 252.0 - program: (10 - 1 + 7 * -1 + input) * (input + (3 - -8 / -4))
=== Generation 2 best fitness: 1008 - program: (input + 4) * (input + -1)
=== Generation 3 best fitness: 203 - program: (7 + -3 - input * -1) * input
=== Generation 4 best fitness: 22.75 - program: input * (input + (3 - -8 / -4 / -4))
=== Generation 5 best fitness: 22.75 - program: input * (input + (3 - -8 / -4 / -4))
=== Generation 6 best fitness: 8.75 - program: -5 - -6 + input * input + (input - input * (-3 - 8 - 9)) / (1 - 1 - -6)
=== Generation 7 best fitness: 2.5968626643538126 - program: -7 + (input + 4) * (input + -1) + (-5 - input * (-3 - 8 - 9)) / input
=== Generation 8 best fitness: 4.861111111111127 - program: input + input * input + (6 * (10 + 7) + 4 - input - input * (-8 - 8 - 9)) / (7 - 1 - -6)
=== Generation 9 best fitness: 1.6155871338926322e-27 - program: input * (input + (3 - -8 / input))
=== Generation 10 best fitness: 1.6155871338926322e-27 - program: input * (input + (3 - -8 / input))
=== Generation 11 best fitness: 0 - program: input + (4 - -4) + input * input + (input + input)In this output, we see the results of the genetic programming system over many generations. At each step, we see the best fitness (or error value) and the best solution. We start off with an error value of 252, telling us how far the best starting solution was from the “correct” solution.
We also see the program which produced the best output. Note that while these expressions are simple and generic looking, they are fully valid Elixir code, provided that we set the expected bindings (value in this example).
Over the course of 12 generations (starting with 0, of course), these error values steadily drop, until we get to error value 0 — an exact match! And we see the ouput, a valid Elixir program:
input + (4 - -4) + input * input + (input + input)# which simplifies to...
input + 8 + input*input + input + input
input*input + 3*input + 8
Try For Yourself
At this point, you might want to take the system for a try yourself. You can do so by trying out QuoteGP on GitHub, and looking at the examples in the samples directory.
As you play with it, there are a couple of things you might notice — which are all real world challenges of working with genetic programming (and with AI search techniques more generally).
The fitness sometimes goes up instead of down
Because the generic operators are applied randomly, sometimes the “best” candidate doesn’t make it to the next generation. There’s a whole body of research around the selection process, and there’s no right answer. Though it might seem intuitive to always favor copying the best programs from one generation to the next, it’s an open question — some research shows that such this approach actually produces worse results over time. (Note: as I research this claim now, I see more recent evidence in favor of this approach— maybe I should add it in to QuoteGP!)
Sometimes the problem doesn’t get fully solved
Yep, this happens.
Genetic programming is really just a particular kind of search technique, and there’s no guarantee that a solution will be found. In fact, most individual real world genetic programming runs won’t find a perfect solution to a problem, because you’re looking for a needle in a haystack. It’s not uncommon to require multiple attempts to find the right solution.
Additionally, in these sample problems we use a stopping criteria of 0, in other words, a completely perfect solution. That’s not typical in the real world — there often isn’t a completely perfect solution to many problems. Instead, finding something with a tiny error value is a valid and useful real world solution.
The programs are getting really long!
“Bloat” is another common problem in genetic programming, also with a body of research dedicated to addressing it. In short, bloat is an increase in program length over time without an increase in fitness due to “dead” or vestigial code. In this simple system, we don’t employ any bloat control techniques, so this is not surprising.
Conclusion & Future Work
So given how nicely evolvable code meshes with Elixir, is it the best system and language for genetic programming? To be honest: no. Most GP systems don’t use normal human programming languages because there’s no need to. They tend to use some other internal representation which is translated to human-readable expressions only when needed. They may even incorporate language features which would make them terrible for human programming, but very useful for evolution.
Furthermore, most GP systems are far more sophisticated than this simple example. See this list of systems for further reading. I personally like (and have worked on) the PushGP system, but there are many many others.
What’s nice about using Elixir for genetic programming, however, is that it’s very simple to implement, inspect and understand, making it an excellent teaching tool for tinkering with genetic programming, understanding how it works, and trying out new ideas.
If you want to try out the code yourself, head on over to GitHub.
Jonathan has over 20 years of engineering leadership experience in startups big & small. If you enjoy this article, please consider joining Medium to support Jonathan and thousands of other authors.
