Above: Phenotypes from 4 different runs of the same evolution. The goal was to reach a fixed target number of nodes in the colony, in this case 13. The genomes for each shape are sub-programs composed of primitive functions (see genetic programming). This was possible because an important error was removed from the code. See below.
Evolution runs prior to this post were excruciatingly slow. I attributed this, naively, to each growth simulation taking a long time. I even made the simulation runs take half as long, by making the collision computation more efficient. But the evolution runs were still frustrating me. On some level I knew, perhaps intuitively, that they shouldn’t be quite so slow. Individuals simulation runs were pretty quick. So it was frustrating and bewildering that the evolution took so long!
Looking Under the Hood with Dots
At this point I recalled a conversation with my friend Amiti, who is a software developer, about running scripts that take a long time. She mentioned that when dealing with these long computations, she’s gotta see something happening, even if it is just printing out periods or dashes. So I had the evolution script print a “.” each time it did a simulation run. At first I saw the dots appear quickly, like the pattering of rain in a puddle, but then the intervals got longer and longer. Each dot succeeded the next with increasing sluggishness! This definitely wasn’t right. For a sanity check I added a timer and verified that the simulation runs got progressively longer during the course of an evolution.
From there it was pretty easy to deduce that some sort of memory-leak phenomena was occuring. Turns out I was re-using an instance of an object which ‘grows’ the colony. I switched the code to re-instantiate the object each time a simulation ran, and the problem went away. I’m not even sure exactly why this was happening, but for the time being it doesn’t matter. The evolution runs are fast enough now to have a decent population (50-200) and have multiple simulation runs per genome. This is necessary since there is some random variation between each simulation run for the same genotype.
So lesson learned: The lowest cost change that gives any indication of what is going on is highly valuable. Printing dots was more helpful than a fancy tool like profiling, which led me down a bit of a rabbit hole trying to figure out how to use the tool. I am sure profiler’s have their place for me, but only after the simpler methods have been exhausted.
Metaball Skinner: Update (Mar 24, 2017): I made this functionality into a blender add-on! Get it here: https://www.blendermarket.com/products/metaball-skinner
In the midst of working on evolving plant/coral thingmabobs, I am exploring 3d printing some of the earlier shapes I came up with, when I was writing the growth algorithms explicitly. To do this I need a reliable way to ‘skin’ the skeletons (or ‘thicken’ the wireframes). The skeletons consist of one dimensional line-segments, touching end-to-end, and occasionally branching. There are various way to do this.
In blender there is the ‘skin’ modifier, which works quite well, granted a few conditions. One such condition is that segments radiating from a branch point be sufficiently spaced out, otherwise branches interest each other (A). Another is that segments that branch away from connection points are not too short, relative to their neighbors (B). Finally, consecutive segments need to make a sufficiently obtuse angle between one another, otherwise a kink occurs in the mesh, causing self-intersection (C).
The issue with these resulting meshes is that they are often not 3d printable. Meshes that are 3d printable need to be water-tight, meaning that no faces are missing. Some 3d printing processing software also needs all the edges to be manifold. This means that each edge has exactly two faces connected to it. So in the general case of arbitrarily complex wire-frame skeletons, blenders skin modifier breaks down for 3d printing. The problem of skinning an arbitrary wire-frame skeleton so that it is 3d printable, with any number of small branch angles, tight turns, and tiny edges, is difficult. Some approaches, similar in effect to blender’s skin modifier, attempt to create a structured, orderly polygonal mesh composed of regular rods connected by joints. One such method is described in this paper, and has been used in this grasshopper plugin.
I found a work-around to this problem, that is guaranteed to always create water-tight, clean meshes. I made a script in blender that simply adds a metaball rod in place of each line-segment in the wire-frame (see https://en.wikipedia.org/wiki/Metaballs, for a description of metaballs). Where metaball rods overlap they have an additive effect, so this results in slight lumps at the connection points. For the time being this is fine, but it is easy to imagine a specially shaped unitary metaball rod that has a tappered ends, so that when overlap occurs the node region has the same diameter as the rest of the rod. Also conceivable is a more complex program which could alter the size of the ends, so that nodes with many incoming segments are not unnecessarily large. Regardless, this is a neat technique for easily generating 3d-printable structures from blender wire-frames!
Each descendent is connected to its parent or parents by a line. So individual 12 inherited genetic information from 11 and 10. In this run of the evolution there were 5 individuals in a generation and 4 generations. But there are not 20 individuals in the graph! That is because individuals that are selected to mate are kept in the next generation; their offspring replace all discarded individuals from the previous generation. So this graph doesn’t really give a good impression of which individuals consistently got selected. Still this is a starting point for visualizing an evolution. This sort of visualization makes it easier for me to understand what happened in the evolution and which individuals are interesting.
A next step might be to show each generation with the parents copied over. Or perhaps a separate table showing each generation and who got selected.
Here are the phenotypes, roughly laid-out (manually) according to the above graph:
Looks like the first two individuals produce roughly the ‘best’ phenotypes. (best is max number of nodes) So much for the evolution! I think its ok though; this was a small test run and it looks like I did something odd with the selection method. I used tournament selection with the size of each tournament as the population size. When looking at source code, it suggests to me that this means the next generation will consist solely of the highest fitness individual. At the moment I am using the algorithm eaSimple, a default genetic algorithm in the deap package. Anyway I’ll sort out the algorithm soon, the point is that now there can be genealogy trees!
Here is a close up on a phenotype from individual 10:
looks like some of the phenotypes are a little box-like. To avoid this I should make the ‘padding’ between the growing plant bounding box and the world-box a little bigger.
At this point it is pretty hard to see much relation between a child and its parents. The fitness criterion of max nodes makes this visually scrambled mess. Fingers crossed that more subtle fitness criteria lead to something more visually understandable. I don’t want to have to make another algorithm that ‘sees’ the structures! Although such an algorithm may be useful for fitness evaluation. Estimating fractal dimension seems like a natural one, although I don’t have the faintest idea of how I would go about doing it at the moment.
Ok I have had enough rambling. Sorry there is not much context explained for this post! For this to make more sense check out http://joshlopezbinder.com/randomly-generated-growth-rules/
The first shape has been grown using an evolved program! This is part of the plant grower project I am working on. It doesn’t really look like much, but that’s because it is evolved to grow as many nodes as possible in a set amount of time. So it is not surprising that it looks like a dense hairball. I suspect that results will get more visually interesting when the fitness criteria encourages compromise. Here is the shape:
The shape is really a representation of the ‘phenotype.’ A phenotype is ‘the set of observable characteristics of an individual resulting from the interaction of its genotype with the environment.’ (according to google) The genotype is below:
Rather simple, and it is plausible that a human could create such a program. All this program does is take the mean vector between x and x’s unit vector. X is the vector describing the position of a collided sphere-‘nutrient’ relative to the node that just ‘fed.’ What is interesting is that this program was evolved rather than written by a human (me). This evolution ran for five generations, where the population consisted of ten individuals. The evolution is being run using deap. As far as genetic programming goes this is a small population and not many generations to get an interesting result (usually defined in terms of ‘fitness’). But I am just working out the errors first with a simple prototype. For reference this point in the project has been git tagged as
looks like I was too much in a rush to type ‘first’! Not sure what fist-evolving is :)
Here are some more plant-shapes that are ‘grown’ in the same simulation environment, but with different randomly generated growth rules. Note the variety in shapes! See the previous post for a detailed explanation. I am posting the most interesting structures I have come across, but many of the randomly generated rules result in ‘boring’ shapes, like a vertical line. Beware my aesthetic bias!
Since the last post I realized why many of the structures grew preferentially in a certain direction. This was because of the primitive functions ‘add,’ ‘multiply,’ and ‘subtract’ that operated element-wise on two vectors. Such element-wise operations are likely two take two vectors and make all there elements more positive, or more negative, or some combination. Because this affects the y-vector of the next node, this has a positive-feedback effect, resulting in structures that grew in one direction. I removed those functions for now.
gnarly-spindly-tree Below is a structure tagged gnarly-spindly-tree (I am using git tags to keep track of interesting structures along the way.) Kinda reminds me of a blue-oak (Quercus douglasii)
This node-edge shape could be thought of as the ‘phenotype’ in the context of the evolutionary algorithm.
Below is the full processor tree for the above structure. This can be thought of as the ‘genotype.’
Here is a close up of the processor tree ‘genotype.’
I have added some more primitive functions since the last post, like cross product for vectors, extracting the x, y, z component, and finding the angle between vectors.
Here are some more fun shapes!
shagy-wild-bush. For this one the processor tree is so huge its not very informative to look at.
straight-segment-bush I like how simple this processor tree is, but still leads to an interesting growth shape. I probably would not have come up with this myself. Since the processor tree is simple enough to evaluate yourself, I’ll explain its parts: x and y are vectors (see prev. post for description of what they are). Norm( vec ) outputs the length of the input vector. Rotate_vec_np( vec1, vec2, angle ) rotates the first vector about the second vector, by some angle in radians (c1=.5 in this case). If_greater( arg1, arg2, arg3, arg4 ) outputs arg3 if arg1 is greater than arg 2, otherwise it returns arg4. Thats it!
No-Name Alas, the below structure was generated before I created a system for saving and ‘resurrecting’ processor trees.
A note on how I save the processor trees: I mentioned above that I am using a git tag to save out interesting shapes. In the past when working on generative projects like this coral one, I tried to save out lists of parameters with a given shape. The problem with this is that as soon as I changed the code and added new parameters or completely different behavior, those parameter lists were useless! This time around I realized that that the entire code base of the project at the time the form is generated is the ‘DNA’ of a given shape. So really the best way to save that information is using git, a version control system for keeping track of code. I started the practice of committing all relevant code after an interesting shape was found, and then immediately using ‘ git tag some-descriptive-name ‘ to associate that tag with a certain shape. That worked well until I started messing around with the randomly generated programs I have been referring to as ‘processor trees.’ To save these I have the script save a .txt file which contains a text representation of the processor tree. For example straight-segment-bush uses this processor tree:
if_greater(norm(x), norm(y), rotate_vec_np(x, y, c1), y)
If the structure is one I want to save, I copy the file and rename it, and I create a git tag of the same name. That way if I change the primitive set of functions that the processor tree uses, I can still go back to the version of the code where the primitive set was correctly configured for that processor tree. In this case I use
git checkout refs/tags/tag-name
To re-enstate the code. Finally, there is a function in the deap.gp library that can recreate the working processor tree from the text-based representation. That’s how I can resurrect an extinct virtual organism!
Last post I was figuring out how to get a genetic programming package inside of a 3d modeling program called blender. Today I got the simplest use of the genetic programming package woking: generating random trees of functions, to make a sort of ‘processor.’ I took the randomly generated processor and plugged it into the plant/coral simulation I have been developing. In this simulation a bunch of spherical particles jitter downwards, roughly simulating the diffusion of nutrients in water or light in a forest. A point, or collection of points, acts as a ‘seed.’ When a sphere collides with the seed, it creates a new point and an edge. I will refer to the points as ‘nodes.’ Each node decides where to put the new node. For the moment this decision is based on the position of the collided sphere, and it’s relative position to its parent node.
The decision of where to put the new node is where the randomly generated processor comes in. Normally I would write the program or sub-routine that decides where to put the next node. Indeed I have been doing that for a bit. Shapes that are generated from my growth rules are in the renders portion of this website. But I am interested in making generative shapes that evolve! Presumably many of the plant, algae and coral shapes that we observe in the real world have growth rules that have evolved and been subjected to natural selection. Seeing all of that variation makes me want to experiment with virtual growth systems and simulated evolution. So anyway, this is the first step in that direction.
How it works
There is a set of ‘primitive functions’ that are sampled randomly to create a nested series of function calls. There is also a set of ‘terminals’ which are constants and variables that act as inputs to the innermost functions. Here is an example of a randomly generated processor:
mean_vec(mean_vec(rotate_vec_np(y, y, c1), rotate_vec_np(y, y, c1)), scale(rotate_vec_np(y, y, c1), dot(x, y)))
The primitive set included mean_vec, rotate_vec_np, scale and dot. The terminal set consists of the 3d vectors x,y and the constant scalar c1.
This is most easily visualized as a tree (I did not make the code to generate processor trees or visualize them. It is all from the python package deap):
This processor tree takes in two 3d vectors and outputs a new vector. This is intentionally designed to act as the ‘decision maker’ of the node! the vector x is the relative position of the sphere to the collided node. The vector y is the vector from the parent node to the collided node.
Clearly the functions available in the primitive set, and any constants in the terminal set, are going to have an important role in constraining the possible growth behaviors. So I have been playing around with different primitive sets.
Below: some pleasing shapes that resulted, with their associated processing tree on the right.
You might notice some terminals are numbers with alot of decimals. Those are ‘ephemeral constants,’ constants that are randomly picked, in some range, when the processor was generated. Also, some of the structures are a bit lopsided. I accidentally had a setting where particles were being spawned at a side plane of the box as well as the top. In all of these cases the ‘seed’ is a line segment. This way the top most node has a non-zero vector from the parent node. If there was only one node, the y vector would be zero, and more processor trees would result in no visible structure.
In my quest to make lots of different interesting shapes, I am attempting to use DEAP inside of blender. Deap stands for Distributed Evolutionary Algorithms in Python. Deap has a module for implementing genetic programming, which I am curious and excited to use as a way of automatically generating growth rules. Genetic programming evolves computer programs to perform some sort of task well. I am not really sure, at the moment, if it is important that the growing tree-structures perform some task well. However, the deap package includes an interface for easily generating random programs from a collection of predefined ‘primitves’ or basic functions. It also allows one to easily construct a genetic algorithm which uses the randomly generated programs as ‘genomes.’ Anyway, first I need to make the deap package available within blender!
1. Blender’s most current versions use python 3. Deap is written in python 2. So to covert I used the command 2to3 as follows (note I am on OSX):
$ 2to3 --output-dir=/Library/Frameworks/Python.framework/Versions/3.5/lib/python3.5/site-packages/deap -W -n /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/deap
2. The next step is to get blender’s version of python to be aware of deap. The quickest way I found to do this is to add the location of the python 3.5 site-packeges to blender’s path. This is done according to this thread. In blender’s console I did this:
>>> import deap.gp
It works! Of course this a bit of a hacky way of getting deap (or any third-party python module) into blender. More permanent ways of making the module available for import are described here.