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?
2 Answers
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.
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:
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:
- extract the genes xi and yi
- find the minimum and the maximum values
- 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
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.
-
$\begingroup$ Is it correct to say that with the BLX-α algorithm we can move to points outside the interval of the initial population? That is, assuming an 1d optimization problem, if the values for the initial population were in $[a, b]$, by applying the BLX-α we can move to a point in $[c, d]$ where $c > a$ and $d > b$? $\endgroup$– ado sarMay 20 at 11:49
-
$\begingroup$ @adosar The whole point of the BLX-α crossover (and most of the crossover algorithms) is to produce a result that is in the range of the parents' genes. So, although the new range is an extended version of it [a-α, b+α], you still want to explore the local space, rather than displacing yourself in a different point. If you were to choose a high value for α, you might move away from the initial population interval, but that will probably be counterproductive, as genes of individuals that performed well won't be passed down easily to the next generation. Short answer: no :) $\endgroup$ May 22 at 7:07
-
$\begingroup$ It is a tradeoff between exploration and exploitation I think. It is not bad idea per se to move away from the initial population. Of course, we should somehow exploit the ``strength" of the parent genes so we can't set a very large value of $\alpha$. $\endgroup$– ado sarMay 23 at 19:47
-
$\begingroup$ @adosar yes you are correct. If what you care about is to diverge from the initial population, you can set an initially high α, that decreases over time. I don't really see the point of doing so though, you could simply spread it more when it is initially generated. After all, a good initial population is nicely spread over the whole exploration space $\endgroup$ May 24 at 20:03