Jim Susinno 2000
Deciduous Evolution in 3D - v1.0
- Abstract
A 3D recursive algorithm is developed for drawing binary trees using intersecting cylinders in 3D space. All adjustable aspects of this algorithm are parameterized, and these parameters are evolved using a genetic algorithm. Statistics describing various metrics of the tree are instantiated, and fitness is calculated based on a number of weighted functions of these statistics. The goal of this project is to manipulate these weights to most accurately reflect the laws of nature, and observe the resulting trees. Using only a simple set of parameters, a recursive binary tree's growth can strikingly resemble that found in nature.
Included files:
earth.c <the source> threedtree.c <tree functions> Makefile README.deciduous <this file>
- Installation
Copy all source files to a directory(untar the archive). type make, then run the earth executable.- Requirements
OpenGL or free equivalent( Mesa...)- Instructions
Most of the interface is done through Glut's key press handler, which means that the window in which the trees are drawn must be the front window in order for commands to be issued. (window focus == Deciduous Evolution ) Commands are as follows: '[' - cycle one tree left through family ']' - cycle one tree right through family 's' - print the current tree's statistics 'g' - run one generation 'j' - run a batch of generations 'J'(capital) - change the number of generations per batch
'q' - change 3D control to camera reference point 'w' - change 3D control to red pointer cube 'e' - change 3D control to camrera location Mouse - move current 3D control along axis:
Left: xy
Middle: yz
Right: xz
The best way to cycle through an evolutionary sequence of trees is to use [ and ] to browse through the present selection of trees, looking for the tree with highest fitness. Once found, iterate successively through generations until the tree changes, indicating that a tree with higher fitness has been created. Find this tree and repeat.
The Algorithm:
A standard genetic algorithm was implemented for this problem, with all tree growth parameters in the float array encoded into a bit string for evolution. Each generation is structured as follows:
calculate mean fitness
for (all trees) {
if ( fitness < mean ) {
replace tree with most fit offspring:
mutated child of two best trees
-or- random tree
}
}
A non-repeatable instance of anomalous behavior in the GA has been observed: on occasion, the algorithm will discard all trees with a high fitness, replacing them with new, lower fitness random trees. Evolution will continue from this point toward the most fit tree, but will be significantly set back. This event tends to occur during a large generation batch size, making the exact cause of the problem difficult to pnpoint and correct.
The Tree: (threedtree.c)
The tree was recursively drawn in 3D using OpenGL. The draw_tree function resembles the following:
void draw_tree( int height, float *p ) {
draw_root_recurse( height, p ); }
void draw_root_recurse( int height, float *p ) {
// the following parameters are stored
// in float array p(passed in)
///////////////////////////////////////
draw_cylinder(
lower_cylinder radius = p[2];
upper_cylinder radius = p[3];
cylinder length = p[4]; );
translate( to top of cylinder );
rotate( p[5] degrees about vector defined by p[6],p[7],p[8] );
draw_root_recurse( height - 1, p );
rotate( p[9] degrees about vector defined by p[10],p[11],p[12] );
draw_root_recurse( height - 1, p );
}
Accompanying the draw function are a few analogous recursive functions to determine tree attributes used for calculating fitness.
float get_tree_height(float p);
float get_tree_surface_area(float p);
float get_tree_volume(float p);
float get_tree_symmetry(float p);
The fitness:
The calculation of a particular tree's evolutionary fitness was done with a weighted sum of a
number of factors.
When a tree's parameter array is populated with random numbers all within the range of their
respective parameter, odd-looking spherical and non-complete trees are produced, which look
nothing like real trees. When evaluated for fitness as described below, these trees are
invariably weeded out by the GA, as they evaluate quite poorly.
After only about 3 generations, the trees start to noticeably tend
toward objects that actually look like trees, and by 500 generations the best tree produced
most often resembles a natural tree quite closely.
The Parameters:
...of degree 1...
-Surface area to volume ratio k_sv*(surface_area/volume) see <surfaceAreaToVolume.jpg>
Produced the most natural trees. Alone, however, trees
tended toward the extremely small, and the extremely thin.
A minimum radius was imposed on all trees, but more
parameters were needed if the tree was to approach a
larger scale.
-Symmetry k_s*(symmetry) see <symmetric.jpg>
Promotes trees in which the two rotation angles
and axes are approximately equivalent,
with partial credit for partial matches.
-Radius to length ratio k_rl*(radius/length)
see <radiusToLength.jpg>
Added into the fitness to encourage fuller trees.
...of degree 1/2...
-Volume k_v*(volume)^(1/2)
see <volume.jpg>
Promotes larger trees.
-Height k_h*(height)^(1/2)
Promotes taller trees. Height is calculated with
the sine of the two rotation angles, so this parameter
encourages long cylinder length in conjunction with
small rotation angle.
-Straightness k_s*(straight)^(1/2)
see <straight.jpg>
Promotes straighter trees. Straightness is inversely
proportional to the average rotation angle theta.
- Conclusion
The range of different types of trees that can be derived from six simple fitness rules is virtually infinite. Through controlled manipulation of random permutations of tree parameters, better and more physically fit trees can emerge. Alteration of the fitness calculation scheme allows selection of different "species" of tree, suited for a specific environment. It is most notable that the single most crucial parameter for realistic tree growth is the surface area to volume ratio.