Evolving Digital Trees

L-Systems (short for Lindenmayer Systems) are a rather simple way of modeling the growth of branching structures. They consist of a grammar, or set of rules, that is used to iterate over a string of tokens. The rules tell you how to replace each token with another string. After each iteration, you get a longer string. The tokens have a graphical interpretation, so a string of them can be plotted as some kind of structure. This is not meant to be an L-Systems primer; see this site for a very good introdiction.

Just after we finished Antz, I wrote a library that supports non deterministic, context sensitive L-Systems. Non deterministic means that each production rule can have several possible succesors, each one with a probability, used to pick one at random. Context sensitive means that you can specify which tokens should surround the processed one for the rule to be applied.

This is the kind of trees that can be made with this library:

After playing around a bit, and making some trees like the above, you realize that it is hard to come up with the right rules, and the process is not very intuitive. So I wrote another program, that uses the library to mantain a population of 100 trees. I also wrote a function that mixes two trees into a third one, a function that mutates a tree, and a function that returns a fitness value according to certain criteria.

I implemented a very simple fitness function, that gives the trees points based on two things:

  • How close they get to a given point in space
  • How efficient they are (ie, the fewer segments they use, the better)

    I created an initial population, mixing trees at random from a group of four or five that I had made by hand, like the one above. Here is another example of those first trees:

    Then I let my program run. For each iteration, it would kill a number of the less fit trees and replace them with mixes or mutations of others that were more fit. I marked the goal of the trees with a red ball:

    The idea is that random mutations that make the tree lean towards the ball will be favored, and after a lot of iterations a tree will evolve that will actually touch the ball. The efficiency rule will keep the trees from just exploding into space-filling structures that would touch the ball, but would also be ugly.

    After ten iterations, some trees already show a bias:

    This is after fifty iterations:

    Keep in mind that I'm only showing selected trees from a population of one hundred. In a good run, you get many different kinds of tree "families," each of them leaning towards the ball in their own unique way. Sometimes though, because the population is relatively small and changes can spread quickly, one specially good "genome" contaminates the whole population, and you lose diversity. This is bad because it usually happens with local maximums, meaning that the genome is just better than the rest, but not perfect or optimal. In these cases, the system stays there, producing trees that are all alike and mediocre. You see, biodiversity is good!

    This is one individuone individual born in generation sixty:

    Seventy five:

    One hundred:

    All these trees were generated during the same run, and all are descendants of the same simple set of trees I made by hand. It is amazing how this simple evolution algorithm can generate such complexity. Some times the rules generated are very difficult to make sense of, yet the shapes they generate are very natural and organic.

    Sometimes, a tree learns to get rid of all its branches, and just zig-zag into the red ball:

    These are the most boring ones.

    Other times, a combination of two trees that were good brings one that just wastes too much:


    Lately, I've been playing around with pruning functions and different fitness criteria. I'm trying to determine the shape of the trees with higher level controls.


    • Back to Juan's about page
    Back to Juan's main page