Handling duplicates when using Partially Matched Crossover for Genetic Algorithm

Question

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?

In your question it looks like you are mapping 3 to both 4 and 5? And also you are mapping 4 to both 2 and 3? This video shows how mapping in PMX works. — krenkz
– krenkz, Commented Feb 27, 2020 at 11:37

Mayowa Ayodele · Accepted Answer · 2020-02-21 11:47:31Z

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

Collectives™ on Stack Overflow

Handling duplicates when using Partially Matched Crossover for Genetic Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related