encodingmachine-learninggenetic-algorithmcrossover

How to crossover the parents when using a value encoding method in genetic algorithm?


There is phase in genetic algorithm where we should choose to crossover the chromosomes from parents to offspring.

It is easy to do via binary form.

But what to do if we encodes the chromosomes using the value encoding?

Let's say one bit in my chromosomes is a DOUBLE type value, let's say 0.99, its range is (0-1) since it will represent a probability.

How to crossover this DOUBLE number?

Convert to binary to crossover then convert back...?


Solution

  • You could use the blend crossover operator (the variant with α = 0):

    p1    first parent
    p2    second parent
    u     random number in [0, 1]
    
    offspring = (1 - u) * p1 + u * p2
    

    Assuming p1 < p2, this crossover operator creates a random solution in the range [p1, p2].

    The blend crossover operator has the interesting property that if the difference between parents is small, the difference between the child and parent solutions is also small. So the spread of current population dictates the spread of solutions in the resulting population (this is a form of adaptation).

    A more advanced version of the blend crossover operator (BLX-α) and another well known operator (Simulated Binary Crossover) are described in Self-Adaptive Genetic Algorithms with Simulated Binary Crossover by Kalyanmoy Deb and Hans-Georg Beyer (a short summary here).


    Differential Evolution is another possibility.