GECCO 2008 Contest Problems

Human Evaluation of Evolved L-System Images

The goal of this competition is to evolve an L-System that will recreate a series of image in a defined number of cycles. For details on general L-systems see the Wikipedia article on L-systems. Code for an Lsystem drawing class in C++ can be found here.

A drawing is specified by giving a line length e.g.:

len 50

and an angle e.g.

angle 60

and finally a series of productions e.g.

A = 3(X+F)
X = X+X+

It is assumed the axiom of your system will be A.

The allowable symbols in our L-system for this problem are:

+ - turn turtle left by D degrees
- - turn turtle right by D degrees
A - the axiom for your L-system (see the definition of an L-system)
B - move turtle backward by L distance leaving a line
C - move turtle backward by L distance WITHOUT leaving a line
F - move turtle forward by L distance leaving a line
G - move turtle forward by L distance WITHOUT leaving a line
[ - remember on the state stack the location and direction of turtle
] - pop the location and direction of turtle from the state stack

Variables are supported in our Lsystems and assumed to be a single uppercase letter. Variables are replaced by their value until the depth is reached and then they are translated to the definitions above (excluding the axiom) or nothing if undefined above.

This is a very open ended problem. A problem is specified by giving a spec drawing for one or more depths of evaluation and the number of degrees D, and the length of step L. The drawings are in bit map files (bmp) of the same size for all given depths of evaluation, but may vary from the examples we give with this problem spec. In a sense the objective of the problem is to evolve an Lsystem that reproduces the given drawings. This will require you to write a fitness function that will grade the quality of match between two drawings which probably contain hierarchical detail of an L-system. In fact what should be turned in is the L-system using the above commands. We will draw them for depth 1,2,...K. Each iteration should match, as closely as possible, the target image for that iteration. For the competition, the closeness of the match between the spec image and those generated by the submitted L-system will be determined by a panel of human judges. Thus, part of this competition is to figure out a way to evolve towards an ill-defined, human standard of 'closeness of images'.

Example Problem

Here is an example target image for testing.

bmp picture for depth 2:

given as input to your evolutionary program might evolve this:

len 20
angle 60
X=X+YF++YF-FX--FXFX-YF+
Y=-FX+YFYF++YF+FX--FX-Y

The Target Image

Here is the tar of the target images for levels 6, 7, 8, and 9.

Level 5:

Level 6:

Level 7:

Level 8:

Level 9:

What to Submit

Contestants need to submit:

their L-system as an ASCII file in the format described above
a PDF document containing a brief description of the evolutionary process used to evolve the function. Please include a fairly detailed description of the fitness evaluation process used.

Both of these documents should be tarred into a single file.

Judging

Each submission will be judged on performance and evolutionary 'quality'. Performance is based on a panel's ranking of the image matches for each of the generated images (iteration 5 through 9). Evolutionary quality will be based on the 'human independentness' of the evolutionary process. E.g. an evolutionary system that includes a human designed sub-systems will not be ranked as high as an L-System evolved from only the basic operations.

Questions about these pages or the problems themselves can be sent to [Terry Soule] or [Robert Heckendorn]