mathematical-optimizationgenetic-algorithmheuristicsmutationcrossover

What does crossover index of 0.25 means in Genetic algorithm for real encoding?


I am familiar with crossover and mutation indexes in binary representation but in real encoding, I came across with several articles in which crossover index and mutation index are used as parameter values.

For example, we have population size of 300 and 30 decision variables then what does crossover index = 0.25 means?

Also confused about the mutation index of 100+current generation number.


Solution

  • Crossover index

    A number of real-coded crossover operators have been developed that create two children solutions from two parent solutions.

    Maybe the papers you're reading use the Simulated Binary Crossover (SBX).

    For this operator the crossover index (η) is a non-negative real parameter. A large value of η gives a higher probability for creating near parent solutions and a small value of η allows distant solutions to be selected as children solutions.


    The step by step procedure for SBX algorithm is:

    1. Choose a random number u ∈ [0; 1[.
    2. Calculate βq:

      β

    3. Compute children solutions using these equations:

      children

      Here Xi(1, t+1) and Xi(2, t+1) are the children obtained from two parents Xi(1, t) and Xi(2, t).

    A possible implementation in C is here (also take a look at Simulated Binary Crossover (SBX) crossover operator in Scala genetic algorithm (GA) library and Simulated Binary Crossover (SBX) crossover operator example).

    So the probability distribution for creating children solutions of continuous variables when η=2 / η=5 is:

    probability distribution

    Parents are marked with o and you can see how a larger value gives higher probability for creating near-parent solutions.


    The reference paper for SBX is:

    Simulated Binary Crossover for Continuous Search Space

    Kalyanmoy Deb, Ram Bhushan Agrawal

    1995 (PDF here)

    Mutation index

    The mutation index (ηₘ) is (probably) a parameter of the polynomial mutation operator suggested by Deb and Agrawal (1999).

    ηₘ induces an effect of a perturbation of O((b – a) / ηₘ) in a variable, where a and b are lower and upper bounds of the variable.

    Then it's reasonable to use a larger ηₘ for subsequent generations.