Types of crossover in genetic algorithm
Crossover is a genetic operator used to introduce enhancement in the offspring’s genetic material. During the process of generating a population, there are chances that the fitness value of the new population stops improving, and one of the participating chromosomes could be a problem.
Crossover is a biological technique to mix the genetic material of the parent chromosomes and produce new offspring. There are chances that the children produced by this process are better than the previous ones and might possess better qualities and features.
There are many types of crossover available in the genetic algorithm. Let’s discuss the most widely used in this Answer.
One-point crossover
In this type of crossover, we mark a point on the parent chromosomes at the same position. The genes before this point remain, but the genes after this point are swapped. A random point of 3 is selected for a one-point crossover. The following illustration below shows the one-point crossover process.
Children’s genetic material is formed by inheriting one part of their genes from one parent and the other from the second parent.
Code example
Let’s see how we can implement a one-point crossover in Python.
# Define the two parents as arraysparent1 = [1, 2, 3, 4, 5, 6, 7, 8]parent2 = [1, 3, 5, 7, 9, 11, 13, 15]# Specify the crossover point (e.g., point 3)crossover_point = 3def one_point_crossover(parent1, parent2, crossover_point):"Perform one-point crossover between two parents at a specified point"# Create offspring by combining parent genes up to the specified crossover pointoffspring1 = parent1[:crossover_point] + parent2[crossover_point:]offspring2 = parent2[:crossover_point] + parent1[crossover_point:]return offspring1, offspring2# Perform one-point crossover on the two parents at the specified pointoffspring1, offspring2 = one_point_crossover(parent1, parent2, crossover_point)# Print the resultsprint("Parent 1: ", parent1)print("Parent 2: ", parent2)print("\n")print("Offspring 1: ", offspring1)print("Offspring 2: ", offspring2)
Code explanation
Lines 2–3: We define the two parents as arrays
parent1andparent2consisting of eight genes each.Line 6: We specify the crossover point to swap the genes.
Lines 8–15: We define the
one_point_crossoverfunction that takes three parameters: two parents and a crossover point. We perform crossover at lines 12–13 and then return the children at line 15.Line 18: We call the
one_point_crossover()function.Lines 21–25: We print both parents and offspring.
Two-point crossover
In this type of crossover, two random points are selected on the mating chromosomes, and the genes of the middle part are swapped. The following illustration below shows the two-point crossover process.
We can see that the genes before the first point and after the second point don’t change in the children while the genes between these two points get changed.
There can be a multipoint crossover where the alternative patches of genes are swapped.
Code example
Let’s see how we can implement a two-point crossover in Python.
# Define the two parents as arraysparent1 = [1, 2, 3, 4, 5, 6, 7, 8]parent2 = [1, 3, 5, 7, 9, 11, 13, 15]# Specify the crossover pointscrossover_point1 = 2crossover_point2 = 5def two_point_crossover(parent1, parent2, point1, point2):"Perform a two-point crossover between two parents at specified points"# Create offspring by exchanging genetic material between parents at the specified pointsoffspring1 = (parent1[:point1] + parent2[point1:point2] + parent1[point2:])offspring2 = (parent2[:point1] + parent1[point1:point2] + parent2[point2:])return offspring1, offspring2# Perform two-point crossover on the two parents at the specified pointsoffspring1, offspring2 = two_point_crossover(parent1, parent2, crossover_point1, crossover_point2)# Print the resultsprint("Parent 1: ", parent1)print("Parent 2: ", parent2)print("\n")print("Offspring 1: ", offspring1)print("Offspring 2: ", offspring2)
Code explanation
Lines 2–3: We define the two parents as arrays
parent1andparent2.Lines 6–7: We specify two crossover points. The first one is 2, and the second is 5.
Lines 9–19: We define the
two_point_crossoverfunction that takes parents and crossover points and performs a two-point crossover operation. Line 19 returns the children generated after the two-point crossover process.Line 22: We call the
two_point_crossoverfunction.Lines 25–29: We print both parents and offspring.
Uniform crossover
In this type of crossover, we don’t swap the genes based on random pointers. We toss a coin for each gene in parent chromosomes. If the toss results in 1, we swap the genes, and if the toss is 0, then the original value of the genes passes to the children. The following illustration below shows the uniform crossover process.
We can see that the children’s genetic material depends on the toss’s value. We only swapped the genes where the toss value was 1.
Code example
Let’s see the implementation of the uniform crossover in Python.
import random# Parent chromosomesparent1 = [1, 2, 3, 4, 5]parent2 = [6, 7, 8, 9, 10]# Probability to swap genescrossover_prob = 1def uniform_crossover(parent1, parent2, crossover_prob):assert len(parent1) == len(parent2), "Parent chromosomes must have the same length"child1 = []child2 = []for gene1, gene2 in zip(parent1, parent2):bit = random.randint(0,1)if bit == crossover_prob:print("bit value=", bit)child1.append(gene2)child2.append(gene1)else:# Keep genes unchanged if no crossover occursprint("bit value=", bit)child1.append(gene1)child2.append(gene2)return child1, child2child1, child2 = uniform_crossover(parent1, parent2, crossover_prob)print("Parent 1:", parent1)print("Parent 2:", parent2)print("\n")print("Child 1 after crossover:", child1)print("Child 2 after crossover:", child2)
Code explanation
Lines 4–5: We define two parent chromosomes.
Line 8: We define crossover probability. This will control the crossover process.
Lines 10–28: We define the
uniform_crossoverfunction that takes parents and the crossover probability as parameters. We generate a random integer at line 18 and check if it equals thecrossover_prob. If it is, we swap the genes otherwise, not.Line 30: We call the
uniform_crossoverfunction.Lines 32–36: We print the parent’s and children’s chromosomes.
Conclusion
In this Answer, we discussed a very important concept, crossover, of genetic algorithm. We discussed three types of crossover and saw their implementation in Python.
Free Resources
