Single Point Crossover in Genetic Algorithm using Python
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…😊
If parents are integers, should I still make the same conversion? Thanks for this, anyway! Helped me understand crossover better!
Your welcome. But yes, we need to convert the values to its binary form.