95
Description of Evolution Engine Parameters

Description of Evolution Engine Parameters

Luis Da Costa and Marc Schoenauer

Chapter 1
Description of Evolution Engine Parameters

Description  
The Evolution Engine (EE) of an EA contains the parameters of the engine shared by any kind of algorithm. They are described by an XML file (see Table 1.1)
 
  <EVOLUTION_ENGINE>
    <P_MUT>0.1</P_MUT>
    <P_CROSS>0.85</P_CROSS>
    <MIN_MAX>Minimise</MIN_MAX>
    <NUM_GEN activated="true">500</NUM_GEN>
    <NUM_EVAL activated="false">1</NUM_EVAL>
    <MAX_TIME activated="false">1</MAX_TIME>
    <GRAPH_STAT>true</GRAPH_STAT>
    <ENGINE>SteadyState GA</ENGINE>
    <POP_SIZE>100</POP_SIZE>
    <ELITE TYPE="perc">15</ELITE>
    <FERTIL TYPE="perc">85</FERTIL>
    <NB_GEN TYPE="perc">100</NB_GEN>
    <GEN_SEL PARAM="2.0">Tournam.</GEN_SEL>
    <NB_OFFSPR TYPE="perc">100</NB_OFFSPR>
    <SURVIVING_OFFSPR TYPE="perc">100</SURVIVING_OFFSPR>
    <SURVIVING_PARENTS TYPE="perc">25</SURVIVING_PARENTS>
    <RED_PARENT PARAM="2.0">E.P. Trn.</RED_PARENT>
    <RED_OFFSPR PARAM="2.0">E.P. Trn.</RED_OFFSPR>
    <FINAL_RED PARAM="2.0">Sequent.</FINAL_RED>
    <ELITISM>Strong</ELITISM>
  </EVOLUTION_ENGINE>

Table 1.1: XML Structure of an Evolution Engine (EE)
Each one of the tags of the XML file represents one parameter of the engine. These are all encapsulated in class guide.kernel.EvolutionEngine, who then provides methods to access and set the information. An explanation of the parameters is given here:
  1. General Parameters:
  2. Initial Population Parameters:
  3. Intermediate Population Parameters:
  4. Final Population Parameters:
Selectors implemented in GUIDE  
A description of the Selectors implemented in GUIDE is given here. For a very interesting and detailed study of selection procedures, please see the work of Bäck [1]. For each Selection method we give the constant that represents it and its string descriptor (used in between the XML tags on the file description). All constants are defined in guide.kernel.Util.EvolutionSelectionConstants
  1. Roulette Wheel. Represented in GUIDE by the constant EvolutionSelectionConstants.ROULETTE_WHEEL. String descriptor: "Roul. Wh."
    Also called Proportional Selection, this method was introduced by Holland for the Genetic Algorithm [2]. It assigns selection probabilites according to the relative fitness of individuals:
    pi = F(ai)

    l

    j=1 
    F(aj)
    (1.1)
  2. (Linear) Ranking. Represented in GUIDE by the constant RANKING. String descriptor: "Ranking"
    Defined by Baker [3], it uses a linear function to map indices i to selection probabilities pi. Assuming that individuals are sorted according to their fitness, the selection probabilities are given by
    pi =
    h+ - (h+ - h-) * i - 1

    l- 1

    l
    (1.2)
    The couple (h-,h+) define the slope of the linear function. However, notice that the constraint j=1lpi = 1 requires that 1 h+ 2 and h- = 2 - h+. So Eq. 1.2 can be rewritten as in Eq. 1.3.
    pi =
    h+ - 2 * (h+ - 1) * i - 1

    l- 1

    l
    (1.3)
    It is common to use a value of h+ = 1.1. This is the value that GUIDE asks as a parameter of this Selector.
  3. Deterministic Tournament: Represented in GUIDE by the constant TOURNAMENT. String descriptor: "Tournam."
    This selector chooses an individual by selecting a number q ( 2) of individuals at random and selecting the best one. q is usually 2, but can be configured in GUIDE.
  4. Stochastic Tournament. Represented in GUIDE by the constant STOCHASTIC_TOURNAMENT. String descriptor: "Stoch. Trn."
    This selector behaves similarly of Deterministic Tournament. Stochastic Tournament of rate R first choses two individuals from the population, and selects the best one with probability R (the worse one with probability 1-R). Real parameter R should be in [0.5,1].
  5. Random: Represented in GUIDE by the constant UNIFORM. String descriptor: "Uniform"
    This selector is the trivial one: randomly selects the individuals.
  6. Sequential: Represented in GUIDE by the constant SEQUENTIAL. String descriptor: "Sequent."
    It performs a deterministic selection, from best to wrost individuals, in turn.
Reductors implemented in GUIDE  
The way of reducing a population is implemented in GUIDE under the idea of "Reductors". Five of them are implemented: Sequential, Random, Deterministic Tournament, Stochastic Tournament and Evolution Programming Tournament. The first 4 are identical to the ones with the same name described in the Selectors explanation. The fifth (Evolution Programming Tournament) is described here.
Represented in GUIDE by the constant EP_TOURNAMENT and with a String descriptor: "E.P. Trn.", it proceeds by taking the union of the initial population with the intermediate one. For each individual a in this (double) population q individuals are chosen at random and compared with a, with respect with fitness values. This gives a new value for a, the rank of this tournament. Once all individuals have been assigned values, a deterministic algorithm chooses the survivors. GUIDE expects the application to specify the value of q. A typical value is 10.
Default Parameters  
  1. Population
    TO FINISH. Those parameters are NOT GOOD
    size = 100
  2. GUIDE assumes the problem is of type Minimization (i.e., lower fitnesses are better)
  3. the criterium stop is set at 500 generations
  4. 10 per cent of the initial population will go down directly to the final population (so elitism=.1)
  5. 85 percent of the initial pop is fertile (so the parents are chosen from there)
  6. 33 percent of the fertile population will conform the parent population. The way of choosing is by Tournament, size 2
  7. Mutation rate on parents: .1
  8. Crossover probability: .85
  9. Offspring population is 50 per cent as big in size as the parent population
  10. There is an intermediate population that is formed by the sum of 50 per cent of the offspring population, chosen by Tournament, size 2, plus 75 per cent of the non-elite population, chosen by tournament, size 2
  11. Finally, the Final population is chosen with the sum of the Elite (10 percent of the initial population), plus the rest coming from the intermediate population, chosen Sequentially.
Miscellanous  
Details about the Evolution Engine in EO can be found on http://www.lri.fr/~marc/EO/eo/tutorial/html/eoEngine.html

Bibliography

[1]
Thomas Bäck. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms, 1994.
[2]
J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.
[3]
J. E. Baker. Adaptive selection methods for genetic algorithms. In J. J. Grefenstette, editor, Proc. of the 1st International Conference on genetic Algorithms and Their Applications, pages 101-111, Hillsdale, NJ, 1985. Lawrence Erlbaum Associates.



File translated from TEX by TTH, version 3.80.
On 27 Mar 2008, 11:09.