Single Point Crossover in Genetic Algorithm using Python

By Prashanth Gowda R S

In this algorithm, we will learn the single-point crossover in the genetic algorithm using python. In genetic algorithms, the crossover is also known as recombination. It will combine the genetic information of two parents’ chromosomes to generate new offspring. In a single-point crossover, we will pick two parent chromosomes and select a crossover point. We will swap the genetic information to the right of that point between the parents’ chromosomes. As a result, we will get two offspring which contain some genetic information from their parents.

Example:

Parent1: 10110001010100101110
Parent2: 01001001011010110101
Crossover point = 4

Offspring1: 10111001011010110101
Offspring2: 01000001010100101110

Parent1: 10110001010100101110
Parent2: 01001001011010110101
Crossover point = 15

Offspring1: 10111001011010101110
Offspring2: 01000001010100110101

Single-point Crossover

• We will pick two parents’ chromosomes and select a crossover point using a random.randint(range).

  parent1 = '10110001010100101110'        #parents' Chromosomes
  parent2 = '01001001011010110101'
  
  point = random.randint(1,len(parent1))  #Crossover point

• We will recombine the chromosomes by swapping the bits to the right of the Crossover point between the parents’ chromosomes. Since strings are immutable, they don’t support item assignment. As a result, we will convert the strings to lists, swap the genetic information to the right of the crossover point and again join the elements of the list to make it as a string. Hence, the resultant strings are the offspring.

  p1,p2 = list(parent1),list(parent2) #convert str to list
  for i in range(point,len(p1)):
      p1[i],p2[i] = p2[i],p1[i]       #swap the genetic information
  p1,p2 = ''.join(p1),''.join(p2)     #Convert list to str

Here is how the complete code should look like

import random

def Crossover(parent1,parent2,point):
    p1,p2 = list(parent1),list(parent2) #convert str to list
    for i in range(point,len(p1)):
        p1[i],p2[i] = p2[i],p1[i]       #swap the genetic information
    p1,p2 = ''.join(p1),''.join(p2)     #Convert list to str
    return p1,p2

parent1 = '10110001010100101110'        #parents' Chromosomes
parent2 = '01001001011010110101'
print('Parent1:',parent1)
print('Parent2:',parent2)

point = random.randint(1,len(parent1))  #Crossover point
print('Crossover Point:',point)

offspring1,offspring2 = Crossover(parent1,parent2,point)
print('Offspring1:',offspring1)         #Offspring Chromosomes
print('Offspring2:',offspring2)

Output:

Parent1: 10110001010100101110
Parent2: 01001001011010110101
Crossover Point: 8
Offspring1: 10110001011010110101
Offspring2: 01001001010100101110

I hope you have understood the code..!
You may also read Insertion and deletion in a binary search tree.

If you have any queries, please feel free to drop in your comments.
Thank you…😊

2 responses to “Single Point Crossover in Genetic Algorithm using Python”

1. AC says:

   June 13, 2020 at 4:13 pm

   If parents are integers, should I still make the same conversion? Thanks for this, anyway! Helped me understand crossover better!

   Reply
2. Prashanth Gowda R S says:

   June 13, 2020 at 11:00 pm

   Your welcome. But yes, we need to convert the values to its binary form.

   Reply