Evolutionary Computing Tool

This tool has been implemented with the aim to be as general as possible; with C++ in fact is relatively easy to abstract from the type. The implementations is inside the file population.hpp.

The idea behind the tool is the following. The user must define a type, let's say I (that stands for Individual), for example a geometric vector or a Turing machine, with some key member functions:

1. A fitness function. By default the implementation searches for double I::fitness( I& ).
2. A mutation function. By default the implementation searches for void I::mutate( I&, Random& ). An alternative (still have to discuss) could be to use I& I::mutate( const I&, Random& ), meaning that the old individual is kept, and the new one is returned.
3. A crossover function. By default something like void I::crossover( I&, I&, Random& ). The alternative to keep the old individuals here is a little bit more tricky, since we should return a pair of new individuals.
4. (optional) A comparison operator, based on the comparison among fitness values (i.e. the double values representing the fitness). This is by default assumed to be implemented in bool I::operator< ( const I& ).

These functions are then used in the population implementation.

I would suggest to change everything and use the version where the individual passed to crossover/mutation is const, since this also solves another little problem. In our specific case, when we are mutating a machine we need to erase the tape, since she has to be re-evaluated. The population class is not aware of this, while the class that implements the mutation (in our case I == living_tm) it is, and can for example create a new machine with an empty tape.

Crossovers and Mutations

The idea should be that each individual has some probability to be mutated and some probability to be crossed. The implementation of the "with some probability" is easy but there are some points to solve:

1. If one individual has been chosen for mutation, can be chosen also for crossover?
2. If one individual has been chosen for crossover, which other individual choose to actually perform the crossover?

So I think that it's better to write details about this after we discuss.

Fitness function: when evaluate it?

To make the population as general as possible, the details about the execution of the virtual machine has to be kept in another class. From the population point of view the only thing you can say is "calculate the fitness function of an individual" (you don't know how).

So my idea is that a call to the fitness function over a certain individual (machine) can cause its (re) execution. If we are computing a fixed number of steps (case where the S-beaver is known), this is very easy to realize: if a machine is unchanged from the previous generation simply fetch the last computed fitness value. The other case is more complex and if we can't realize it in living-tm.hpp I think we will have to subclass population in order to make this possible.