I am new to Genetic Algorithms and am working on a python implementation. I am up to the crossover step and am attempting a Partially Matched Crossover. For my final output I am hoping for a list that contains no duplicated numbers. However, in some cases, I am introducing duplicates. For example, Take the lists
Mate 1 [1,2,3,5,4,6]
Mate 2 [6,5,4,3,2,1]
If the crossover portion is [3,5,4] -> [4,3,2]
Then the offspring before mapping becomes [1,2,4,3,2,6]. My understanding of the algorithm is the mapping outside the crossover is 4 -> 3, 5 -> 3 and 2 -> 4. However, this results in an output of [1,4,4,3,2,6] which has duplicates and is missing a 5.
How do I work around this problem? Does the first 4 just become a 5? And how would this scale to larger lists that might introduce multiple duplicates?
I am not sure you have implemented it right:
for Partially Matched Crossover (see explanation), if your crossover points are 2 and 5 as suggested in the example then you can only obtain
offspring1 = [6, 2, 3, 5, 4, 1]
offspring2 = [1, 5, 4, 3, 2, 6]
if you select 3,5,4 from mate1 and fill the rest in the order of mate2 you will get offspring 1 but if you select 4,3,2 from mate2 and fill the rest in the order of mate 1 you will get offspring 2
See implementation below:
mate1 = [1,2,3,5,4,6]
mate2 = [6,5,4,3,2,1]
crossoverpoint1 = 2
crossoverpoint2=5
child = []
#fill in the initial genes in order of mate1
count = 0
for i in mate1:
if(count == crossoverpoint1):
break
if(i not in mate2[crossoverpoint1:crossoverpoint2]):
child.append(i)
count= count+1
#select the genes within the crossover points from mate2
child.extend(mate2[crossoverpoint1:crossoverpoint2])
#fill in the remaining genes in order of mate1
child.extend([x for x in mate1 if x not in child])
print(child)
output:
[1, 5, 4, 3, 2, 6]
to obtain offspring1 swap mate1 for mate2. you can also try different crossover points, let me know if this helps