EASEA defined sections

Aller à : navigation, rechercher

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:

  1. The genome of the individuals trough the GenomeClass class
  2. 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:

    1. 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

Run parameters section

\Default run parameters:     // Please let the parameters appear in this order
  Number of generations: 100 // Value stored in the global NB_GEN variable
  Time limit: 0              // In seconds, 0 to deactivate
  Population size: 100       // Value stored in the global POP_SIZE variable
  Offspring size: 100%       // Percentage of POP_SIZE, or integer value
  Mutation probability: 1    // MUT_PROB (prob. to call the mutation function)
  Crossover probability: 1   // XOVER_PROB (prob. to call the Xover function)
  Evaluator goal: minimise   // Other possibility is "Maximise"
  Selection operator: Tournament 2
  Surviving parents: 0%      //percentage or absolute  
  Surviving offspring: 100%
  Reduce parents operator: Tournament 2
  Reduce offspring operator: Tournament 2
  Final reduce operator: Tournament 2

  Elitism: Strong                // Weak or Strong
  Elite: 1                       // Nb of elite individuals
  Print stats: true              // true/false
  Generate csv stats file: false // true/false
  Generate gnuplot script: false // true/false
  Generate R script: false       // true/false
  Plot stats: false              // true/false

  Remote island model: false     // true/false
  IP file: ip.txt                // File containing all the remote island's IPs

  Save population: true          // Population saved in project_name.pop
  Start from file: false         // and read from project_name.pop
\end

Finally, the <.ez> file ends with a list of parameters that determine the behaviour of the evolutionary engine. A single pass parsing is made through this list so please, respect the order of the parameters.

Number of generations
This is a stopping criterion on the number of generations. This integer value is accessible in the program through the NB_GEN EASEA defined variable.
Time limit
Another stopping criterion, in seconds. A value of 0 deactivates this criterion.
Population size
The value of this parameter is accessible within the program through the POP_SIZE EASEA defined variable. Right now, it cannot be modified. The population size remains constant.
Offspring size
This is either an integer value (indicating how many children must be created through crossover and mutation at each generation), or a percentage of the population size. A % sign must be added to the percentage value for the parser to differentiate with a number of children.
Note that the number of offspring can be different from the population size. In case of a generational GA, offspring size is 100% of the population size. In a Steady State GA, only one child will be created per generation, and in Evolution Strategies, the number of children can be smaller or larger than the population size.
Mutation probability
As indicated, this is the probability (between 0 and 1) to call the mutation function. A common practice is to keep this value to 1, meaning that the mutation function is called 100% of the time, leaving it to the function to mutate or not the genes individually, as done in this example. The mutation probability is available throughout the program through the MUT_PROB EASEA defined variable.
Crossover probability
Same as the mutation probability, for the crossover function. In case of a generational GA, using a probability lower than 1 allows some parents to make it to the next generations, through children that are their clones. This allows to mimic an Evolution Strategiy Plus, that picks the new generation among a subpopulation made of parents + children.
Evaluator goal
This parameter tells the evolutionary engine whether it should try to minimise or maximise the fitness of the individuals. Selectors will work differently depending on the value of this parameter, that can be tested in the program thanks to the MINIMISE boolean EASEA defined variable. It is not possible to modify this variable during the run.
Selection operator
This parameter determines how parents will be selected in order to create children. It can take the following values: tournament, random, roulette, deterministic<tt>. Note that <tt>roulette is not compatible with a minimisation of the fitness of the individuals.
Tournament expects a parameter that determines the arity of the tournament. If the parameter is smaller than 1, a stochastic tournament is implemented, that returns the best of 2 individuals with a probability within [.5,1]. Therefore, tournament .5 is equivalent to random and tournament 1 is equivalent to tournament 2.
Surviving parents
This is the first of four parameters that are confusing to the beginner.
EASEA is not restricted to Genetic Algorithms (Generational or Steady-State algorithms that evolve bitstrings) or Evolution Strategies (real valued algorithms that create a temporary population made of parents+children before they select the next generation), but can do both as well as a mix of both.
The way to do this is to allow the user to specify exactly what he wants. The Surviving parents parameter allows to tell how many parents should be included in the temporary population that will be used to create the new generation. In case of a Steady State algorithm (that creates only one child per generation), the number of surviving parents should be set to POP_SIZE-1. In order to make things clear, the mainstream evolutionary algorithms page discusses the different algorithms and proposes standard parameter settings to emulate them.
Surviving offspring
This parameter tells how many children should be included in the tempoprary population that will be used to create the new generation. In an Evolutionary Strategy +, this number is typically smaller than the population size. Please refer to the mainstream evolutionary algorithms to understand clearly how things work.
Reduce parents operator
Allows to tell which reduction operator (among tournament, random, roulette, deterministic<tt> to use to select parents to be included in the temporary population. Notice that this is a reductor, and not a selector. The difference between a reductor and a selector is that a reductor cannot select several times the same individual. Even though they share the same name (because they work on the same principle), a reduction tournament is not implemented the same way as a selection tournament.
Reduce offspring operator
Same as above, but to select which children will be part of the temporary population.
Final reduce operator
Reductor to be used to create the new generation out of the temporary population made of children+parents. Please refer to the mainstream evolutionary algorithms to understand clearly how things work.
Elitism
Strong or weak. In the case of strong elitism, some of the best parents are immediately saved into the new generation as a very first step. Then, the algorithm continues, but whatever parents are already in the next generation will remain there. In the case of weak elitism, no parents are cloned into the next generation to start with. Elitism will be performed after the temporary population made of parents + children is created. Some of the best individuals of this temporary population will be transferred to the new generation in a deterministic way. Please refer to the mainstream evolutionary algorithms to understand clearly how things work.
Print stats
True/false. Displays infos on the terminal at each generation.
Generate csv stats file
True/false
Generate gnuplot script
True/false
Generate R script
True/false
Plot stats
True/false
Remote island model
True/false. If true, each run will try to periodically send individuals to some other runs on machines whose ip identifier is listed in the file. Right now, options are hard-coded, but this will change soon.
IP file
must provide a file name containing a list of IPs of machines that will run the same project
Save population
True/false. Saves the population in project_name.pop for a future restart.
Start from file
True/false. Bypasses the initialisation function. The population is initialised from the file project_name.pop that was created during a previously saved run, allowing for a restart with different parameters (or why not a different evaluation function !

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:

  1. CPPFLAGS
  2. 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 :

  1. 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.
  2. 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.