Genetic Algorithms in Java Basics by Lee Jacobson & Burak Kanber

Author:Lee Jacobson & Burak Kanber
Language: eng
Format: epub
Publisher: Apress, Berkeley, CA

Single Point Crossover

Single point crossover is an alternative crossover method to the uniform crossover method we implemented previously. Single point crossover is a very simple crossover method in which a single position in the genome is chosen at random to define which genes come from which parent. The genetic information before the crossover position comes from parent1, while the genetic information, after the position, comes from parent2.

Single point crossover is reasonably easy to implement and allows contiguous groups of bits to be transferred from parents more effectively than in uniform crossover. This is a valuable property of crossover algorithms. Consider our specific problem, where the chromosome is an encoded set of instructions based on six sensor inputs, and each instruction is more than one bit long.

Imagine an ideal crossover situation as follows: parent1 is great at the first 32 sensor operations, and parent2 is great at, say, the last 16 operations. If we were to use the uniform crossover technique from Chapter 2, we’d get jumbled bits everywhere! Individual instructions would be changed and corrupted in the crossover due to the uniform crossover choosing bits at random to exchange. The two-bit instructions may not be preserved at all, because one of the two bits per each instruction might get modified. However, single point crossover lets us capitalize on this ideal situation. If the crossover point is directly in the middle of the chromosome, the offspring would end up with 64 uninterrupted bits representing 32 instructions from parent1, and the great 16 instructions from parent2 as well. So, the offspring now excels at 48 of the 64 possible states. This concept is the underpinning of genetic algorithms: that the offspring may be stronger than either parent because it takes the best qualities from both.

Single point crossover is not without its limitations, however. One limitation of single point crossover is that some combinations the parents’ genomes are simply not possible. For example, consider two parents: one with a genome of “00100” and the other with a genome of “10001”. The child “10101” isn’t possible with crossover alone, although the genes required are available in the two parents. Fortunately, we also have mutation as an evolution mechanism, and the genome “10101” is possible if both crossover and mutation are implemented.

Another limitation of single point crossover is that genes toward the left have a bias of coming from parent1, and genes towards the right have a bias of coming from parent2. To address this problem, two-point crossover can be implemented where two positions are used allowing the partition to span the edges of the parent’s genome. We leave two-point crossover as an exercise for the reader.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.