Search code examples
genetic-algorithmevolutionary-algorithmgenetic-programming

Grammatical Evolution (GE)

In the Grammatical Evolution (GE) algorithm (here the web: grammatical-evolution.org) there is the option to make the length of the individuals self-adaptive. I would like to know:

  1. What is the most common strategy used when the individual's length is self-adaptive. In other words, how does the the length of the individual evolve.
  2. Does it increase and decrease the size or just increase.
  3. Is there any well documented or illustrative example.

Thanks in advance.

Solution

  • In GE, the individuals are necessary variable-length in order to be able to encode programs (structures) of variable length.

    Initialization

    The initial population already consists of individuals of varying size. The initialization procedures may vary, but the one I'm familiar the most uses the grammar to create the individuals. You basically do the same thing as when you want to decode the individual into the program (using the grammar) but instead of choosing the grammar expansions using the individual, you do it the other way around - you choose the expansions randomly and record these random decisions. When the expansion is finished, your recorded decisions form an individual.

    Crossover

    The crossover operator in GE already modifies length of the indiviuals. It's a classical single-point crossover, but the crossover points are chosen completely randomly in both parents (in contrast to the classical single-point crossover from GAs where the parents are of the same length and the crossover point is aligned). This mechanism is capable of both growing and shrinking of the individuals.

    Example on crossover: suppose you have two individuals and you have randomly chosen the crossover points

    parent 1:  XXXXXXXXXXXX|XXXX
parent 2:  YYY|YYYYYYYYYYYYYYYYYYYYYY

    After crossover, the children look like this

    parent 1:  XXXXXXXXXXXX|YYYYYYYYYYYYYYYYYYYYYY
parent 2:  YYY|XXXX

    As you can see, the length of the individuals was changed dramatically.

    Pruning

    However, there is a second mechanism that is used for length reduction only. It is the pruning operator. This operator, when invoked (with a probability, in the same way e.g. the mutation is invoked), deletes the non-active part (i.e. if the grammar expansion finished before all codons were used, the remaining part is the non-active part) of the genotype.