genetic: A C++ repository from maleadt

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<int> represent one
gene, and the list<vector> 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.

maleadt/genetic