Simple Method more Valuable than Complex Tool

Category : generative, programming Mar 24th, 2017

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.

Slow Evolutions

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.

Memory Leaks

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.

The Lesson

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.

 

Genealogy Graph of an Evolution

Category : generative, ideas, programming Jan 18th, 2017

Searching around in the documentation of deap, I came across a neat example of displaying a genealogy graph (a.k.a. family tree). I ran an evolution and here is the associated genealogy graph:

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/

 

 

First Evolved Shape, Hairball

Category : art, generative, programming Jan 10th, 2017

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 :)

More Randomly Generated Growth Rules

Category : art, generative, programming Dec 21st, 2016

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!

Randomly Generated Growth Rules

Category : art, generative, ideas, programming Dec 15th, 2016

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.

 

Embedding 3d Models

Category : art, generative, ideas, programming Nov 22nd, 2016

wow neat, an embedded 3d model using  Sketchfab!

This is a shape that I also 3d printed on a Fortus 450:

img_1246

So anyway what is this shape? It is one of many structures generated by a project I am working on simulated coral/plant-like growth. It is a variation on the coral project but grows a skeleton-like structure instead of a surface. Anyway I am playing around with different ways of sharing the project. Its funny working on a generative project like this. It is unclear how best to communicate it: should it be animation? digital images? 3d prints? Virtual reality scenes? Dunno.

In fact I am not really sure what this project is in a bigger sense. I think it is art, but it might be more like a tool for generative games or film or virtual reality. Or maybe its for exploring new engineering techniques for programming growth systems. Or perhaps it is science, for investigating hypothesis about growth systems in nature. Dunno. More on this stuff soon..