1

I have implemented a genetic algorithm in python 3, and have posted a question on code review with no answers yet, basically because my algorithm is running very slowly. By selectively commenting out different parts of my code, I have narrowed down the bottleneck to this section of code, the crossover algorithm:

def crossover(self, mum, dad):
    """Implements ordered crossover"""

    size = len(mum.vertices)

    # Choose random start/end position for crossover
    alice, bob = [-1] * size, [-1] * size
    start, end = sorted([random.randrange(size) for _ in range(2)])

    # Replicate mum's sequence for alice, dad's sequence for bob
    for i in range(start, end + 1):
        alice[i] = mum.vertices[i]
        bob[i] = dad.vertices[i]

    # # Fill the remaining position with the other parents' entries
    # current_dad_position, current_mum_position = 0, 0
    #
    # for i in chain(range(start), range(end + 1, size)):
    #
    #     while dad.vertices[current_dad_position] in alice:
    #         current_dad_position += 1
    #
    #     while mum.vertices[current_mum_position] in bob:
    #         current_mum_position += 1
    #
    #     alice[i] = dad.vertices[current_dad_position]
    #     bob[i] = mum.vertices[current_mum_position]
    #
    # # Return twins
    # return graph.Tour(self.g, alice), graph.Tour(self.g, bob)
    return mum, dad

The part which is commented out makes my program runtime go from ~7 seconds to 5-6 minutes (I am running 5000 iterations of the GA). Is there any way this ordered crossover can be carried out more efficiently?

What the crossover function does

For those unfamiliar, I am implementing an order-based crossover (OX2). Given two arrays of consecutive integers (the parents), two random start/end positions are selected.

  mum   =   4   9   2   8   3   1   5   7   6
  dad   =   6   4   1   3   7   2   8   5   9
                    ^           ^
                  start        end

The two children then share the resulting slices:

  child 1   =   _   _   2   8   3   1   _   _   _
  child 2   =   _   _   1   3   7   2   _   _   _
                        ^           ^

Now the remaining slots are filled in with the entries of the other parents in the order in which they appear, as long as repetitions are avoided. So since child 1 has their slice taken from mum, the rest of the entries are taken from dad. First we take 6, then 4, then next we take 7 (not taking 1 and 3 since they already appear in child 1 from mum), then 5, then 9. So

  child 1   =   6   4   2   8   3   1   7   5   9

and similarly,

  child 2   =   4   9   1   3   7   2   8   5   6

This is what I am implementing in the function.

Improve this question

2 Answers 2

Reset to default
0

I can only guess that your problem lies with the fact that your while-loop and the increment within is not limited to the actual size of the vertices vector, put a hard limit and test again:

     while current_dad_position < size and dad.vertices[current_dad_position] in alice:
         current_dad_position += 1

     while current_mom_position < size and mum.vertices[current_mum_position] in bob:
         current_mum_position += 1

I feel compelled to say that this might not necessarily result a unique solution, as I do not know how the how the algorithm, should behave if there are not enough unique unique singular vertices available to chose from because they violate your 'not from the other parent' restriction.

For anybody to test this out, I would recommend to complete your code with an simple example input and not commenting out the code in question, but rather to mark its BEGIN and END with comments.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for your response. There should always be enough, since parents are all permutations of the numbers 1 to n.
you'll have an additional problem because you are not probing for the minus -1 fill-ins that you are using and will be found in both vectors
0

Okay with the knowledge that the problem is uniquely solvable becuae of construction, here is how it should look like:

import random
import numpy as np

def crossover(mum, dad):
    """Implements ordered crossover"""

    size = len(mum.vertices)

    # Choose random start/end position for crossover
    alice, bob = [-1] * size, [-1] * size
    start, end = sorted([random.randrange(size) for _ in range(2)])

    # Replicate mum's sequence for alice, dad's sequence for bob
    alice_inherited = []
    bob_inherited = []
    for i in range(start, end + 1):
        alice[i] = mum.vertices[i]
        bob[i] = dad.vertices[i]
        alice_inherited.append(mum.vertices[i])
        bob_inherited.append(dad.vertices[i])

    print(alice, bob)
    #Fill the remaining position with the other parents' entries
    current_dad_position, current_mum_position = 0, 0

    fixed_pos = list(range(start, end + 1))       
    i = 0
    while i < size:
        if i in fixed_pos:
            i += 1
            continue

        test_alice = alice[i]
        if test_alice==-1: #to be filled
            dad_trait = dad.vertices[current_dad_position]
            while dad_trait in alice_inherited:
                current_dad_position += 1
                dad_trait = dad.vertices[current_dad_position]
            alice[i] = dad_trait
            alice_inherited.append(dad_trait)

        #repeat block for bob and mom
        i +=1

    return alice, bob

with

class Mum():
    def __init__(self):
        self.vertices =[  4,   9,   2,   8,   3,   1,   5,   7,   6 ]

class Dad():
    def __init__(self):
        self.vertices =  [ 6 ,  4  , 1  , 3 ,  7 ,  2  , 8  , 5 ,  9 ]

mum = Mum()  
dad = Dad()
a, b =  crossover(mum, dad) 
# a = [6, 4, 2, 8, 3, 1, 5, 7, 9]
Improve this answer

4 Comments

and just for clearification: your long execution time was probably due that your iteration did not stop, once you overstepped the boundaries of your vertices-vector. You only got the right result, because the int-counter incremented until you got an overflow, which eventually was in the valid range again. But that takes time...
@Marcell Zoll, thanks for your response. This seems to work sometimes, but other times I have -1's left over in Alice, and other times it goes into an infinite loop.
@Luke-Collins : sorry, i had a bug in there (of course; an i loks very much like an 1 in a small typeset), fixed_pos array was wrongly initialized
I thought += i was weird.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.