EASEA defined sections
User definition fields
User Declarations
Description
This is the section where the user can declare some global variables and some global function.
EASEA syntax
\User declarations : ... \end
Example
\User declarations : #define SIZE 100 //Problem size #define Abs(x) ((x) < 0 ? -(x) : (x)) //Definition of the Abs global function #define MAX(x,y) ((x)>(y)?(x):(y)) //Definition of the MAX global function #define MIN(x,y) ((x)<(y)?(x):(y)) //Definition of the MIN global function #define PI 3.141592654 //Definition of the PI global variable \end
User functions
Description
This is the section where the user can declare the different functions he will need.
EASEA syntax
\User functions : ... \end
Example
\User functions : float gauss() /* Generates a normally distributed random value with variance 1 and 0 mean. Algorithm based on "gasdev" from Numerical recipes' pg. 203. */ { int iset = 0; float gset = 0.0; float v1 = 0.0, v2 = 0.0, r = 0.0; float factor = 0.0; if (iset) { iset = 0; return gset; } else { do { v1 = (float)random(0.,1.) * 2.0 - 1.0; v2 = (float)random(0.,1.) * 2.0 - 1.0; r = v1 * v1 + v2 * v2; } while (r > 1.0); factor = sqrt (-2.0 * log (r) / r); gset = v1 * factor; iset = 1; return (v2 * factor); } } \end
User Classes
Description
This is the section where the user will be able to declare:
- The genome of the individuals trough the GenomeClass class
- Different classes that will be needed.
The GenomeClass field has to be present and ideally not empty. All the variables defined in this field (the genome) will be accessible in several other fields using the 'Genome' variable. Other "hidden" variables can be accessed such as:
- The fitness (variable: fitness. Ex: Genome.fitness)
EASEA syntax
\User Class : ... GenomeClass{ ... } \end
Example
\User classes: Element { int Value; Element *pNext; } GenomeClass { Element *pList; int Size; } \end
Genetic operators
Genome Initialiser
Description
Uses the Genome EASEA variable to access the individual's genome.
EASEA syntax
\GenomeClass::initialiser: ... \end
Initialiser Example
\GenomeClass::initialiser: // or initializer for(int i=0; i<SIZE; i++) { Genome.x[i] = random(X_MIN,X_MAX); Genome.fSigma[i]=random(0.,0.5); } \end
Note that the random
easea function is overloaded: it will return a value of the same type as its operands (it will return an int if its operands are integers, a float if its operands are floats ...).
Genome Crossover
Description
Binary crossover that results in the production of a single child.
Uses parent1 and parent 2 EASEA predefined reserved variables to access the parents' genome and child to access the child's genome.
By default, when entering the function, child is already a clone of parent1 (meaning that you only need to modify child with the contents of parent 2 to perform the crossover).
Not reevaluating a child that is the clone parent1
If for some reason your crossover function does not modify the child, then you can specify:
child.valid = true;
so that child keeps its fitness value (a.k.a. the value of parent1), therefore saving on evaluation time.
EASEA syntax
\GenomeClass::crossover: ... \end
Crossover examples
Example of a single point GA crossover. In this example, we use the possibility of not modifying the child (= not doing the crossover) in 10% of the cases, to show how child.valid=true;
can be used to not reevaluate the child. If the crossover does nothing, then the child is the clone of parent1. (Note that this is the same what is done if, in the parameters section, the crossover probability is set to 0.9.)
\GenomeClass::crossover : if (tosscoin(.1)) { // 10% chance to NOT perform the crossover child.valid = true; // to save on evaluation time as the fitness of the child will be the same as the fitness of parent1 else { int nLocus=random(1,SIZE); // calls the EASEA random function, that will return a value in [1,SIZE[ for (int i=nLocus; i<SIZE; i++) // child already initialized to parent1 so only need to import values of parent2 child.x[i] = parent2.x[i]; } \end
A more standard crossover function that would always modify the child with contents of parents2 would be:
\GenomeClass::crossover : int nLocus=random(1,SIZE); // calls the EASEA random function, that will return a value in [1,SIZE[ for (int i=nLocus; i<SIZE; i++) // child already initialized to parent1 so only need to import values of parent2 child.x[i] = parent2.x[i]; \end
Example of a floating point barycentric crossover:
\GenomeClass::crossover : for (int i=0; i<SIZE; i++){ float fAlpha = random(0.,1.); // choosing a weight for parent1 gene child.x[i] = fAlpha*parent1.x[i] + (1.-fAlpha)*parent2.x[i]; } \end
Genome Mutator
Description
Must return the number of mutations in older versions of EASEA. Not needed anymore since version ???
Uses the Genome variable to access the individual's genome to be modified by the mutation.
EASEA syntax
\GenomeClass::mutator: ... \end
Mutator examples
The mutator below goes over all the SIZE genes of Genome.x and depending on what is returned by tossCoin(.01), randomly adds a value to Genome.x[i] between 0 and 1.
\GenomeClass::mutator : for (int i=0; i<SIZE; i++) if (tossCoin(.01)) Genome.x[i] += random(); \end
The mutator below is more subtle, as it requires evaluation only if the child is mutated.
\GenomeClass::mutator : child.valid=true; // asks to not reevaluate the child for (int i=0; i<SIZE; i++) if (tossCoin(.01)){ Genome.x[i] += random(); child.valid=false; // asks to reevaluate the child because it was mutated } \end
Genome Evaluator
The evaluation function is expected to be autonomous and independent from the rest of the code, for correct parallelization.
Description
Must return the fitness of the individual.
Uses the Genome defined variable to access the individual's genome.
EASEA syntax
\GenomeClass::evaluator : ... \end
Evaluator examples
The evaluator section can directly contain the code:
\GenomeClass::evaluator: int nScore=0; for (int i=0;i<SIZE;i++) nScore+=Genome.x[i]; return (float) nScore; // the evaluator function returns a float or a double \end
... or call a user function to perform the calculation:
\GenomeClass::evaluator: return weierstrass(Genome.x, SIZE); \end
Genome Display
Description
Uses the Genome variable to access the individual's genome.
EASEA syntax
\GenomeClass::display : ... \end
Display example
\GenomeClass::display : for( size_t i=0 ; i<SIZE ; i++){ cout << Genome.x[i] << ":" << "|"; } cout << Genome.fitness <<< "\n"; \end
Miscellaneous fields
Before everything else function
Description
This function will be called at the start of the algorithm before the parent initialization.
EASEA syntax
\Before everything else function : ... \end
After everything else function
Description
This function will be called once the last generation has finished.
The population can be accessed.
EASEA syntax
\After everything else function : ... \end
At the beginning of each generation function
Description
This function will be called every generation before the reproduction phase.
The population can be accessed.
EASEA syntax
\At the beginning of each generation function : ... \end
At the end of each generation function
Description
This function will be called at every generation after the printing of generation statistics.
The population can be accessed.
EASEA syntax
\At the end of each generation function : ... \end
At each generation before reduce function
Description
This function will be called at every generation before performing the different population reductions.
The parent population AND the offspring population can be accessed (merged into a single population).
EASEA syntax
\At every generation before reduce function : ... \end
User Makefile
Description
This section allows the user to add some flags to the compiler typically to include some custom libraries.
Two flags of the Makefile are accessible to the user in this section:
- CPPFLAGS
- LDFLAGS
EASEA syntax
\User Makefile options : ... \end
Example
\User Makefile options : CPPLAGS += -llibrary LDFLAGS += -I/path/to/include \end
Memetic specific field
Genome Optimiser
Description
The optimiser field is a Genome specific field. It is meant to contain the function defining the way an individual will be locally optimized n times. The function will hence be called sequentially as many times as the user desires for each individual.
EASEA gives the user two possibilities when designing their local optimization function :
- The user can choose to design the function that will enhance the genome of their individuals only in which case the rest of the local optimizer (i.e. creating the local optimizing loop, checking if an individual has improved or not, storing temporary individuals, calling of the evaluation function, etc ...) will be taken care of by the EASEA memetic algorithm. The function will have to be called as many times as specified by the Number of optimisation iterations parameter.
- The user can choose to write the complete local optimizer. This way, he will have the complete freedom to design a more complex and specific optimizer, but he will also have to deal with the creation of the local optimization loop, the management of temporary individuals, the calling of the evaluation function etc... The Number of optimisation iterations parameter will have to be set to 1 as the function desigend by the user will contain it's own optimization loop requiring it's own specific number of optimization iterations.
EASEA syntax
\GenomeClass::optimiser : ... \end
Examples
The two following examples will expose the two different ways the optimizer field can be used. The first example will show a simple mutation function. The second example will show the design of a complete local optimizer. Both examples are GPU compatible.
- Genome optimization only
\GenomeClass::optimiser : float pas = 0.001; Genome.x[currentIteration%SIZE]+=pas; \end
This example shows a simple mutation function that will add a small variation to one of the genes of an individual. The call to this function will be followed by a call to the evaluation function, and a replacement process. If the modification of the genome has improved the individual, it will replace the original one. This is being taken care of by the EASEA memetic algorithm.
- Complete local optimizer
\GenomeClass : : optimiser : // Optimises the Genome float pas=0.001; float fitnesstmp = Genome.fitness ; float tmp[SIZE]; int index = 0; for(int i=0; i<SIZE; i++) tmp[ i ] = Genome.x[ i ]; for(int i=0; i<100; i++){ tmp[index] += pas; fitnesstmp = Weierstrass(tmp, SIZE); if(fitnesstmp < Genome.fitness){ Genome. fitness = fitnesstmp ; Genome.x[ index ] = tmp[ index ]; } else { fitnesstmp = Genome.fitness; tmp[ index ] = Genome.x[ index ]; if( pas < 0 ) index = ( index + 1)%SIZE; pas *= -1; } } \ end
This example shows how to design a complete local optimization function. The genome is almost being changed in the same way as in the first example.