pythonoptimizationgenetic-algorithmevolutionary-algorithm

Handling duplicates when using Partially Matched Crossover for Genetic Algorithm


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?


Solution

  • 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