9
$\begingroup$

How exactly are "mutation" and "cross-over" applied in the context of a genetic algorithm based on real numbers (as opposed to just bits)? I think I understood how those two phases are applied in a "canonical" context where chromosomes are strings of bits of a fixed length, but I'm not able to find examples for other situations. What would those phases look like on the domain of real numbers?

$\endgroup$
0

2 Answers 2

6
$\begingroup$

You have a genome with certain genes:

genome = { GeneA: value, GeneB: value, GeneC: value }

So take for example:

genome = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }

A few examples of mutation could be:

  • Switch around two genes: { GeneA: 1, GeneB: 3.4, GeneC: 2.5 }
  • Add/substract a random value from a gene: { GeneA: 0.9, GeneB: 2.5, GeneC: 3.4 }

Suppose you have two genomes:

genome1 = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }
genome2 = { GeneA: 0.4, GeneB: 3.5, GeneC: 3.2 }

A few examples of crossover could be:

  • Taking the average: { GeneA: 0.7, GeneB: 3.0, GeneC: 3.3 }
  • Uniform (50% chance): { GeneA: 0.4, GeneB: 2.5, GeneC: 3.2 }
  • N-point crossover: { GeneA: 1, | CROSSOVER POINT | GeneB: 3.5, GeneC: 3.2 }

You can be pretty imaginative when developing mutation and crossover methods.

$\endgroup$
0
7
$\begingroup$

As @Thomas W said, you can be pretty immaginative when you're developing mutation and crossover methods. Each problem has its own caracteristics and, therefore, requires a different strategy.

BUT, from my experience, I'd say that 90% of crossovers and mutation on real numbers genotypes are solved using the BLX-α algorithm.

Crossover:

BlX-α algorithm range

This algorithm is really simple. Given the parents X and Y and an α value (inside the range [0,1], generally around 0.1/0.15, but it depends by the problem), For each gene of your genotype:

  1. extract the genes xi and yi
  2. find the minimum and the maximum values
  3. the new gene will be a random number in the interval [min - range * α, max + range * α]

A variation of this algorithm is the BLX-αβ, in which we take into account which parent performed better and use two constants (α > β) to increase the probabilities that the new value will be closer to the one of the fittest parent

BLX-αβ algorithm range

Mutation:

With the mutation the situation is similar: we need to get a random value that is related to our problem domain (we do not want the mutations to be destructive! They have the function of exploring the space).
In these cases it is useful to determine a range for the mutation and use that range to find the new value of the gene using BLX-α.

A more sophisticated mutation algorithm can be achieved using BLX-α on boundaries that depend on the actual value of the gene and the fitness function of the individual.
Let's imagine that our individual performs in a very bad way; in that case the mutation operator will be used to shift the individual to a distant point in the search space, where it will probably perform better.
On the other hand, if the individual is already fit we may not want to introduce some dramatic changes using the mutation. In that case the mutation range would be more contained and would have the function of tuning the genotype instead of exploring for better alternatives.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .