Crossover Operators in Genetic Algorithm
Introduction
Myriads of crossover operators have been developed over time. In this article, I’ll be discussing 13 such crossover operators which can further be classified into 3 categories (based on the encoding of parents) as follows:
Single Point Crossover
Step 1- Select two parents for mating.
Step 2- Select a crossover point at random and swap the bits at the right site.
After crossover, the new offsprings generated look as follows:
Two-Point Crossover
Step 1- Select two parents for mating.
Step 2- Select two crossover points at random and swap the bits at the middle site.
After crossover, the new offsprings generated look as follows:
Multi-Point Crossover
Step 1- Select two parents for mating.
Step 2- Select multiple crossover points at random and swap the bits at the alternate sites.
After crossover, the new offsprings generated look as follows:
Uniform Crossover
Step 1- Select two parents for mating.
Step 2- At each bit position of the parents, toss a coin (let H=1 and T=0).
Step 3- Follow the algorithm mentioned below to generate both offsprings:
if Toss=1,
then swap the bits
if Toss=0,
then don’t swap
After crossover, the new offsprings generated look as follows:
Half-Uniform Crossover
Step 1- Select two parents for mating.
Step 2- Toss a coin (let H=1 and T=0) only if the corresponding bits in P1 and P2 do not match.
Step 3- Follow the algorithm mentioned below to generate both offsprings:
if Toss=1,
then swap the bits
if Toss=0,
then don’t swap
After crossover, the new offsprings generated look as follows:
Uniform Crossover with Crossover Mask (CM)
Step 1- Select two parents for mating.
Step 2- Define a Crossover Mask (CM).
Step 3- Follow the algorithm mentioned below:
To generate first offspring O1
------------------------------
if CM=0,
then select P1 bit
if CM=1,
then select P2 bitTo generate second offspring O2
------------------------------
if CM=0,
then select P2 bit
if CM=1,
then select P1 bit
After crossover, the new offsprings generated look as follows:
Shuffle Crossover
Step 1- Select two parents for mating.
Step 2- Select a crossover point at random and shuffle the genes of both parents.
Note: Shuffle genes for the right site and left site separately.
Step 3- Perform Single Point Crossover.
After crossover, the new offsprings generated look as follows:
Matrix Crossover
Step 1- Select two parents for mating.
Step 2- Write parents in a 2-D representation and then divide the resulting matrices into non-overlapping zones.
Step 3- Perform crossover based on zones.
After crossover, the new offsprings generated look as follows:
Three-Parent Crossover
Step 1- Select three parents for mating.
Step 3- Follow the algorithm mentioned below to generate one offspring:
To generate offspring O1 from (P1,P2,P3) combination
----------------------------------------------------
if P1 bit = P2 bit,
then select P1 bit
if P1 bit != P2 bit,
then select P3 bit
After crossover, the new offspring generated looks as follows:
Repeat the same steps to generate offsprings O2 and O3 using (P1, P3, P2) and (P2, P3, P1) combinations respectively.
Note: Sometimes, the third parent can be taken as a Coin Toss or a Crossover Mask (CM).
Linear Crossover
Step 1- Select two parents for mating.
Step 2- Select a single gene (k) at random.
Step 3- Define α and β parameters.
Step 4- Modify kth gene of P1 using the formula mentioned below:
After crossover, the new offsprings generated looks as follows:
Note: We can generate any number of offsprings by giving different α and β values.
Single Arithmetic Crossover
Step 1- Select two parents for mating.
Step 2- Select a single gene (k) at random.
Step 3- Define the α parameter.
Step 4- Modify kth gene of P1 and P2 to generate offsprings:
Partially Mapped Crossover
Step 1- Select two parents for mating.
Step 2- Select a substring from the parents at random using crossover points.
Step 3- Perform Two-Point Crossover.
Step 4- Determine mapping relationship from substring.
Step 5- Use the mapping to legalize offsprings in unselected substrings.
After crossover, the new offsprings generated looks as follows:
Cycle Crossover
Step 1- Select two parents for mating.
Step 2- Find the cycle defined by parents.
Step 3- Follow the algorithm mentioned below to generate one offspring:
To generate offspring O1
------------------------
if P1 bit in cycle,
then select P1 bit
if P1 bit not in cycle,
then select P2 bit
After crossover, the new offspring generated looks as follows:
To generate offspring O2, proceed similarly by first filling with P2 and the remaining with P1.
That will be it for this article.
Don’t forget to 👏 if you liked the article.
If you want to learn more about GA, check out my series of articles:
If you have any questions or would like something clarified, you can find me on LinkedIn.
~happy learning.
