7
$\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$
  • $\begingroup$ @ben-n you changed the title of my question from "Example of mutation and crossover in real coded genetic algorithm" to "Mutation and crossover in practical genetic algorithm", but "real coded" refers, in my understanding, to GA where genes are real numbers, not "bits" as usually done, so, to something very specific. "practical GA" seems to me instead related to a generic, not well specified, broader class of GA, so, it's my feeling that the meaning of the question changed with your update. What do you think ? $\endgroup$ – danidemi Jun 6 '17 at 7:58
  • $\begingroup$ Follow what the master says.and you will master all his techniques like a real ninja $\endgroup$ – quintumnia Jun 6 '17 at 9:14
  • $\begingroup$ @danidemi My apologies, I thought you meant something else by "real coded." Hopefully my newest revision explains what you're thinking - if not, you can edit the question too. $\endgroup$ – Ben N Jun 6 '17 at 12:46
  • $\begingroup$ @ben-n thx! I think it represents what I had in mind much better that what I wrote initially. $\endgroup$ – danidemi Jun 6 '17 at 12:49
3
$\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$
  • $\begingroup$ @danidemi I also think it's quite useful to have someone with experience break it down. $\endgroup$ – DukeZhou Jun 5 '17 at 20:07
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.