Introduction

This application provides a modular framework for genetic evolutionary algorithms. In order to use this framework, two parts are required:

• The client: this is the framework provided by this application, which handles the evolutionary aspects. Its input is a DNA string/container, and its output is the evolved variant of that set of instructions.
• The environment: this part of the evolutionary application should be provided by the user. It evaluates the evolved DNA string, and calculates a fitness value according to its performance. That fitness value is given back to the client, which handles accordingly

Application contents

This application consists out of three sets of files:

• client one evolutionary client, which can be re-used with several environments
• environment some example environments, which use the client
• generic routines which can be used in both the client and environment

1) DNA format

The client accepts DNA in two different forms:

• string a queue containing int
• container a list of vectors of int's, in which the vector represent one gene, and the list is the encapsulating DNA code

Genes consist out of bytes, ranging between 1 and 254 (so 253 instructions are possible). The environment can interprete genes the way it likes, which increases the amount of possibilities hugely. I.e., an environment in which a creature moves through a world, could instruct the first byte of a gene to be the instruction (move, shoot, jump), and the two following bytes to be the coördinates. This interpretation does not change the way the client mutates the bytes.

When using the queue representation, there are some special possibilities: 255: marks the DNA bounds, every queue should start and end with 255 0: sperates genes

2) Description of the environment

The client will call the environment on several occasions, so it needs to have implemented a certain amount of functions.

• int fitness(DNA) this is the most important routine, which describes how performant a certain DNA set is. The sky is the limit, but a value of -1 is interpreted as "invalid DNA", which will cause the DNA set to be dropped
• int alphabet() this function returns the highest possible value of a gene byte (maximum = 254)

History

Over time, this application has been written and re-written several times. Mostly because of the lack of preparation, but also because the subject isn't documented much and thus difficulties tend to get discovered on-the-run.

1) Initial Perl version

This first implementation, written in Perl, works quite well but only supports a single hard-coded environment (creature running through a obstacle-filled world), and a single-straight evolutionary path. Still, it is cleanly written and demonstrates the principles of evolutionary code.

Download: "/trunk/archive/attempt 1/" @ r81

2) C++ rewrite

Essentially this is the raw C++ rewrite of the initial Perl version. Although it only adds one important features (simple population-based evolution), its mutation algorithms are more advanced and it generally works a lot faster. The environment though is still hard-coded. However, the project seems to contains some memory-leaks, which I did not find.

Download: "/trunk/archive/attempt 2/" @ r81

3) STL rewrite

Due to the memory leaks in the previous version, I attempted another rewrite, eliminating use of pointers and replacing them with STL containers. During the write however, I decided it was flawed by design, and decided to abandon this version and include modularity in the design. Still, this version worked well, apart from a memory leak and a yet undiscovered segmentation fault.

Download: "/trunk/archive/attempt 3/" @ r81

4) Modularity

This rewrite introduced modularity, using a user-implementable Environment.

Download: "/trunk" @ r62

5) DNA redesign

Download: "/trunk" @ HEAD