2
$\begingroup$

Let's say I'm writing a GA to find an optimal path to travel from point $A$ to point $B$. Genotypes are a list of directions (north, south, east, west) to follow.

So a genotype "NENWEE" will move north once, east once, then north again, west once, and finally east twice.

The directions are encoded as follows:

N : 00
E : 01
W : 10
S : 11

Our first genotype, "NENWEE" (let's call it $P$), will thus be encoded as follows: $00\,01\,00\,10\,01\,01$

Let $Q$ be a second genotype, say "EENEWW", which is encoded as follows: $01\,01\,00\,01\,10\,10$

Now let's do a one-point crossover operation on genotype $Q$, from $P$. The randomly-chosen crossover point is between the $9$-th and $10$-th bit, so bits $10$, $11$ and $12$ from genotype $P$ will replace those same bits from genotype $Q$. Let's call the resulting genotype $Q'$.

P  :  00 01 00 10 01 01
Q  :  01 01 00 01 10 10
Q' :  01 01 00 01 11 01

After decoding $Q'$ we find that the result is "EENESE". However neither $P$ nor $Q$ contained direction south.

My question is, do crossover operators imply a certain degree of mutation by definition?

$\endgroup$
  • 2
    $\begingroup$ When you do crossover, a part of your individual gets replaced by a part from another individual, if you will. But mutation changes a part to something completely random usually. Roughly, with crossover, you move to a direction that is maybe a good idea. With mutation, you move to a direction you have no idea whether it's a good idea, but you try to ensure you don't get stuck to a local optimum somewhere. Does that answer your question? $\endgroup$ – Juho Jan 25 '15 at 8:54
  • $\begingroup$ I guess I should clarify my question further. What I ask is, do crossover operators imply a certain degree of mutation by definition OR is the mutation merely the result of an implementation detail? In our case, for example, if we always choose an odd crossover point instead of an even one (e.g. the crossover point being between the 8th and 9th bit instead of between the 9th and 10th bit), the crossover operator will cease to introduce mutations. $\endgroup$ – trakmack Jan 25 '15 at 12:21
  • $\begingroup$ They don't, it is perfectly fine to use a crossover operation that doesn't mutate individuals in any way. I like to think as crossover and mutation as separate entities. $\endgroup$ – Juho Jan 25 '15 at 12:27
  • $\begingroup$ @lucasoliveira Please don't use $...$ to typeset things that aren't mathematics. "GA" certainly isn't mathematics; strings of compass points arguably aren't mathematics. It makes things much harder to read if the font keeps changing for no reason. $\endgroup$ – David Richerby Jan 30 '15 at 8:13
2
$\begingroup$

I have contacted Inman Harvey from the University of Sussex and here is his answer to my question:

In your example you have given each genotype $6 \,\,\,\, 2$-bit 'genes'. Let's look at how different your example parents $P$ and $Q$ are:

In genes $2 (01)$ and $3 (00)$, the genes are identical in $P$ and $Q$ In genes $1, 4, 5$ and $6$ the $2$-bit genes differ

Ie $2/3$ of the genes differ between parents.

If you have $1$-point crossover at any of $12$ positions on the genotype (including here the non-functional case where the crossover-point is 'off-the-end', then:

$6$ of the possible crossover points are between-genes and hence do not count as sort-of mutations. $2$ of the possible crossover points are within the $2$-bit genes that are identical in $P$ and $Q$ – hence do not result in any 'crossover-style-mutation' in $Q'$

$4$ of the possible crossover points are within non-identical genes, and hence DO result in a crossover-style-mutation in $Q'$.

So -- with your specific example, $4$ out of $12$, ie $1/3$ of the time, crossover will produce a crossover-style-mutation. Sounds a lot. Sounds like maybe you should be worried about this in terms of impacting on effective mutation rates...

BUT WRONG!! Your example was atypical. You will find in practice, after only a few generations of evolution, your parents $P$ and $Q$ will be genetically very similar to each other. This is the basic SAGA insight, see any of my papers with SAGA in the title. If you doubt this, then run any binary-style GA for as few as $10$ generations and check on how similar any $2$ randomly chosen parents are. It won't be (as in your example above) $67\%$ of genes differing between parents, it will be more like order of $1\%$ (if your genotypes are say $100$ bits long) differ between parents. Don't believe me, run the tests yourself, it is very easy to do!

... and hence your concern about these crossover-style-mutations should, I suggest, diminish to near vanishing point when you take account of the reality that most parents have mostly identical genotypes.

Anecdotally and simplistically, if human genotypes are $98\%$ similar to chimpanzee genotypes, then you should expect your average human-human parental couple to be $99.99\%$ genetically identical, and only $0.01\%$ open to the possibilities that worry you above (that $\sim 0.01\%$ is of course important and interesting for different reasons). Elephant mating with a flea, then you can expect problems -- in fact what you are discussing above relates closely to inter-species breeding problems. Your standard $GA$ does not run into such problems.

I hadn't thought of it this way. So in fact crossover operators may introduce unwanted mutations in early generations (depending on how they are implemented) but these mutations will have little, if any, effect on the actual optimal mutation rate.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Did you get Harvey's permission to post his answer here? $\endgroup$ – David Richerby Jan 30 '15 at 8:11
  • 1
    $\begingroup$ @DavidRicherby Thanks for bringing this to my attention. I now have his permission :) $\endgroup$ – trakmack Jan 30 '15 at 21:19

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.