4
\$\begingroup\$

I want to implement cycle crossover in python, and I want to do this in the easiest way. In cycle crossover, a vertex should be copied into the child from one parent, but its position should be inherited from the other parent. Here is a link to how it works:
http://www.rubicite.com/Tutorials/GeneticAlgorithms/CrossoverOperators/CycleCrossoverOperator.aspx

Description

Cycle crossover is an operator in genetic algorithm, to create offsprings for the new population. This crossover is used for problems such as the travel salesman problem, to find the shortest possible route, over generations.

Algorithm

Cycle Crossover Operator The Cycle Crossover operator identifies a number of so-called cycles between two parent chromosomes. Then, to form Child 1, cycle one is copied from parent 1, cycle 2 from parent 2, cycle 3 from parent 1, and so on.

Here's an example:

  • Parent 1: 8 4 7 3 6 2 5 1 9 0
  • Parent 2: 0 1 2 3 4 5 6 7 8 9

Cycle 1
Values: 8 9 0 which will be marked Orange. We start with the first value in Parent 1 and drop down to the same position in Parent 2. 8 Goes to 0. Then, we look for 0 in Parent 1 and find it at the 10th position where we drop down to 9. Again, we look for this value in Parent 1 and find it in the 9th position and drop down to 8. Since we started with 8, we've completed our cycle.

  • Parent 1: 8 4 7 3 6 2 5 1 9 0
  • Parent 2: 0 1 2 3 4 5 6 7 8 9

Cycle 2
Values: 4 1 7 2 5 6 which will be marked Red. We start with 4 and drop down to 1. 1 is found in the 8th position in Parent 1 and we drop down to 7. 7 Drops down to 2, 2 Drops down to 5, 5 drops down to 6, and 6 drops down to 4 - Our cycle is complete.

  • Parent 1: 8 4 7 3 6 2 5 1 9 0
  • Parent 2: 0 1 2 3 4 5 6 7 8 9

Cycle 3
Value: 3 The only possible cycle left is of length 1 and contains the value 3.

Filling in the offspring:

  • Parent 1: 8 4 7 3 6 2 5 1 9 0
  • Parent 2: 0 1 2 3 4 5 6 7 8 9

  • Child 1: 8 1 2 3 4 5 6 7 9 0

  • Child 2: 0 4 7 3 6 2 5 1 8 9

Finishing steps:

  • Copy Cycle 1: Cycle 1 values from Parent 1 and copied to Child 1, and values from Parent 2 will be copied to Child 2. Cycle 2 will by different.

  • Copy Cycle 2: Cycle 2 values from Parent 1 will be copied to Child 2, and values from Parent 1 will be copied to Child 1.

  • Copy Cycle 3: Cycle 3 is like Cycle 1, Parent 1 goes to Child 1, Parent 2 goes to Child 2.

I am wondering that is there an easier way to do this.
Thank you

import numpy as np
from copy import deepcopy

class chromosome():
    def __init__(self, genes, id=None, fitness=-1, flatten= False, lengths=None):
        self.id = id
        self.genes = genes
        self.fitness = fitness   

    def describe(self):
        print('ID=#{}, fitenss={}, \ngenes=\n{}'.format(self.id, self.fitness, self.genes))        

    # gives the length of a chromosome
    def chrom_length(self):
        return len(self.genes)

"Cycle crossover" 
def CX(pop, pop_size, selection_method, pc):
    p1 = chromosome(genes= np.array([8,4,7,3,6,2,5,1,9,0]),id=0,fitness = 125.2)  
    p2 = chromosome(genes= np.array([0,1,2,3,4,5,6,7,8,9]),id=1,fitness = 125.2)     
    chrom_length = chromosome.chrom_length(p1)
    print("\nParents")
    print("=================================================")
    chromosome.describe(p1)
    chromosome.describe(p2)
    c1 = chromosome(genes= np.array([-1]*chrom_length),id=0,fitness = 125.2)  # childs
    c2 = chromosome(genes= np.array([-1]*chrom_length),id=1,fitness = 125.2)

    if np.random.random() < pc:  # if pc is greater than random number
        p1_copy = p1.genes.tolist()
        p2_copy = p2.genes.tolist()
        swap = True
        count = 0
        pos = 0   

        while True:
            if count>chrom_length: break
            for i in range(chrom_length):
                if c1.genes[i]==-1:
                    pos=i
                    break

            if swap==True:
                while True:
                    c1.genes[pos] = p1.genes[pos]
                    count+=1
                    pos = p2.genes.tolist().index(p1.genes[pos])
                    if p1_copy[pos] == -1:
                        swap = False
                        break
                    p1_copy[pos] = -1
            elif swap==False:
                while True:
                    c1.genes[pos] = p2.genes[pos]
                    count+=1
                    pos = p1.genes.tolist().index(p2.genes[pos])
                    if p2_copy[pos] == -1:
                        swap = True
                        break
                    p2_copy[pos] = -1

        for i in range(chrom_length): #for the second child
            if c1.genes[i]==p1.genes[i]:
                c2.genes[i]=p2.genes[i]
            else:
                c2.genes[i]=p1.genes[i]

        for i in range(chrom_length): #Special mode
            if c1.genes[i]==-1:
                if p1_copy[i]==-1: #it means that the ith gene from p1 has been already transfered 
                    c1.genes[i]=p2.genes[i]
                else:
                    c1.genes[i]=p1.genes[i]                               

    else:  # if pc is less than random number then don't make any change
        c1 = deepcopy(p1)
        c2 = deepcopy(p2)
    return c1, c2

cross = CX(20, 10,"tour",1)
print("\nChilds")
print("=================================================")
for i in range(len(cross)):
    chromosome.describe(cross[i])
```
\$\endgroup\$
  • 4
    \$\begingroup\$ Hi, I highly suggest that you explain here what's the "cycle crossover" because your link might rot and because it's the best way to get reviewers involved in the review (I, for example, pretty much never click on an external link, I'd skip the post instead). \$\endgroup\$ – IEatBagels Aug 15 at 15:54
  • 3
    \$\begingroup\$ At the least, the indentation of the code in this question needs to be fixed. \$\endgroup\$ – 200_success Aug 15 at 20:27
  • \$\begingroup\$ Cycle crossover is an operator in genetic algorithm, to create offsprings for the new population. This crossover is used for problems such as the travel salesman problem, to find the shortest possible route, over generations. \$\endgroup\$ – Ali Karazmoodeh Aug 18 at 9:03
  • 1
    \$\begingroup\$ Define 'easiest way'. \$\endgroup\$ – Mast Aug 18 at 15:35
  • 2
    \$\begingroup\$ Do the chromosomes actually have 10 genes, or is that a simplification for posting the problem? \$\endgroup\$ – RootTwo Aug 18 at 18:02
3
\$\begingroup\$

Docstrings

You should include a docstring at the beginning of every method, class, and module you write. It allows anyone to view how to use and implement your method, using your_function_name.__doc__ or help(your_function_name).

Class Naming

PEP-8 Compliance requires that all class names should use the CapWords convention. In your case, since Chromosome is one word, it should be capitalized.

Reserved Keywords

You have an init header like so:

def __init__(self, genes, id=None, fitness=-1, flatten= False, lengths=None):
    ...

It is suggested not to use a variable/parameter name id, or any other reserved keywords. This can cause collision and other issues in your program. As a quick fix, I renamed it id_, but you can rename it to something more meaningful/easier to understand.

Unused Arguments

You have two method headers like so:

def __init__(self, genes, id=None, fitness=-1, flatten= False, lengths=None):
    ...
def CX(pop, pop_size, selection_method, pc):
    ...

You only use four (technically three, since self is required in class methods) in the __init__ method, and one in the CX method. If you finish writing a program/method, and see that some parameters you take in aren't used, remove them. This can prevent confusion later on when you decide to take another look at your code and try to find the significance of the parameters you don't use.

Parameter Spacing

When writing default passed/accepting parameters, there should not be a space between the variable, the =, and the value. So, flatten= False is not okay, but flatten=False is okay. You can look at the updated code, as I fixed every occurrence of this.

Variable/Operator Spacing

On the contrary, when using variables and operators, there should be a space. This allows for better readability. This also accounts for lists. Seeing [8,4,7,3,6,2,5,1,9,0], at least to me, is hard to read. Everything is clumped together. But [8, 4, 7, 3, 6, 2, 5, 1, 9, 0] is easier to read and comprehend. Everything is spaced out, and the numbers jump out at you more.

Main Guard

You have this code lying outside your class/methods:

cross = CX(20, 10,"tour",1)
print("\nChilds")
print("=================================================")
for i in range(len(cross)):
    chromosome.describe(cross[i])

Wrapping this in a if __name__ == '__main__': guard is a good idea. Having a main guard clause in a module allows you to both run code in the module directly and also use procedures and classes in the module from other modules. Without the main guard clause, the code to start your script would get run when the module is imported. [source]

So your new code should look like this:

if __name__ == '__main__':

    CROSS = cycle_crossover(1)
    print("\nChildren")
    print("=================================================")
    for index, _ in enumerate(CROSS):
        Chromosome.describe(CROSS[index])

Notice how I use enumerate() vs range(len()). I explain this change later.

Boolean Comparison

if swap==True:
    ...
elif swap==False:
    ...

This is unnecessary. You can use the variable swap as the value itself. You can check the value of swap itself to see if it's True or False, instead of comparing it to the boolean, like so:

if swap:
    ...
else:
    ...

Also, the second swap==False check is unnecessary. If it doesn't pass the first check of being True, then it has to be False. So only an else is necessary here.

String Formatting f""

This one is my opinion. I like to use f"..." to format my strings. It allows me to directly implement the variables into the string, without having to call the format method on it. I left both versions in the updated code, just comment out the one you don't like.

Meaningful Method Naming

CX. What do you think of when you first see this? To someone reading your code for the first time, they would have no idea what this method is supposed to do. Methods should have meaningful names, so someone can get the general idea about that method by just looking at the name.

Variable Naming

You have variables like p1, p2, c1, c2, etc. My initial thoughts were that p1 and p2 were population one and two, since the parameters in the method were pop and pop_size. It wasn't until I saw the comment that was c1 and c2 were children that I realized p1 and p2 were parents. You should provide more meaningful variable names to avoid this confusion. Also, variable names should be snake_case.

enumerate() vs range(len())

Consider using enumerate vs range(len(...)). I would use enumerate as it's more generic - eg it will work on iterables and sequences, and the overhead for just returning a reference to an object isn't that big a deal - while range(len(...)) although (to me) more easily readable as your intent - will break on objects with no support for len.

Updated Code

"""
Module Docstring:
A description of your program goes here
"""

from copy import deepcopy
import numpy as np

class Chromosome():
    """
    Description of class `Chromosome` goes here
    """
    def __init__(self, genes, id_=None, fitness=-1):
        self.id_ = id_
        self.genes = genes
        self.fitness = fitness

    def describe(self):
        """
        Prints the ID, fitness, and genes
        """
        #print('ID=#{}, fitenss={}, \ngenes=\n{}'.format(self.id, self.fitness, self.genes))
        print(f"ID=#{self.id_}, Fitness={self.fitness}, \nGenes=\n{self.genes}")

    def get_chrom_length(self):
        """
        Returns the length of `self.genes`
        """
        return len(self.genes)

def cycle_crossover(pc):
    """
    This function takes two parents, and performs Cycle crossover on them. 
    pc: The probability of crossover (control parameter)
    """
    parent_one = Chromosome(genes=np.array([8, 4, 7, 3, 6, 2, 5, 1, 9, 0]), id_=0, fitness=125.2)
    parent_two = Chromosome(genes=np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]), id_=1, fitness=125.2)
    chrom_length = Chromosome.get_chrom_length(parent_one)
    print("\nParents")
    print("=================================================")
    Chromosome.describe(parent_one)
    Chromosome.describe(parent_two)
    child_one = Chromosome(genes=np.array([-1] * chrom_length), id_=0, fitness=125.2)
    child_two = Chromosome(genes=np.array([-1] * chrom_length), id_=1, fitness=125.2)

    if np.random.random() < pc:  # if pc is greater than random number
        p1_copy = parent_one.genes.tolist()
        p2_copy = parent_two.genes.tolist()
        swap = True
        count = 0
        pos = 0

        while True:
            if count > chrom_length:
                break
            for i in range(chrom_length):
                if child_one.genes[i] == -1:
                    pos = i
                    break

            if swap:
                while True:
                    child_one.genes[pos] = parent_one.genes[pos]
                    count += 1
                    pos = parent_two.genes.tolist().index(parent_one.genes[pos])
                    if p1_copy[pos] == -1:
                        swap = False
                        break
                    p1_copy[pos] = -1
            else:
                while True:
                    child_one.genes[pos] = parent_two.genes[pos]
                    count += 1
                    pos = parent_one.genes.tolist().index(parent_two.genes[pos])
                    if p2_copy[pos] == -1:
                        swap = True
                        break
                    p2_copy[pos] = -1

        for i in range(chrom_length): #for the second child
            if child_one.genes[i] == parent_one.genes[i]:
                child_two.genes[i] = parent_two.genes[i]
            else:
                child_two.genes[i] = parent_one.genes[i]

        for i in range(chrom_length): #Special mode
            if child_one.genes[i] == -1:
                if p1_copy[i] == -1: #it means that the ith gene from p1 has been already transfered
                    child_one.genes[i] = parent_two.genes[i]
                else:
                    child_one.genes[i] = parent_one.genes[i]

    else:  # if pc is less than random number then don't make any change
        child_one = deepcopy(parent_one)
        child_two = deepcopy(parent_two)
    return child_one, child_two

if __name__ == '__main__':

    CROSS = cycle_crossover(1)
    print("\nChildren")
    print("=================================================")
    for index, _ in enumerate(CROSS):
        Chromosome.describe(CROSS[index])
\$\endgroup\$
2
\$\begingroup\$

The main part of CX can be simplified quite a bit. cycles[pos] is the cycle number of that position, or -1 it hasn't been determined yet. cyclestart is a generator that returns the next place for a cycle to start.

parent1 = [8, 4, 7, 3, 6, 2, 5, 1, 9, 0]
parent2 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

if np.random.random() < pc:  # if pc is greater than random number

    cycles = [-1]*len(parent1)
    cycle_no = 1
    cyclestart = (i for i,v in enumerate(cycles) if v < 0)

    for pos in cyclestart:

        while cycles[pos] < 0:
            cycles[pos] = cycle_no
            pos = parent1.index(parent2[pos])

        cycle_no += 1

    child1 = [parent1[i] if n%2 else parent2[i] for i,n in enumerate(cycles)]
    child2 = [parent2[i] if n%2 else parent1[i] for i,n in enumerate(cycles)]

else:
    ...

print("parent1:", parent1)
print("parent2:", parent2)
print("cycles:", cycles)
print("child1:", child1)
print("child2:", child2)

Prints:

parent1: [8, 4, 7, 3, 6, 2, 5, 1, 9, 0]
parent2: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
cycles: [1, 2, 2, 3, 2, 2, 2, 2, 1, 1]
child1: [8, 1, 2, 3, 4, 5, 6, 7, 9, 0]
child2: [0, 4, 7, 3, 6, 2, 5, 1, 8, 9]

If the chromosomes are really long, it might be worth building a dict as a lookup table instead of using parent1.index(). Also changed it so cycle_no comes from enumerating cyclestart (the enumeration starts at 1, so child1 and child2 aren't swapped from the previous answer).

lookup = {v:i for i,v in enumerate(parent1)}

cycles = [-1]*len(parent1)
cyclestart = (i for i,v in enumerate(cycles) if v < 0)

for cycle_no, pos in enumerate(cyclestart, 1):

    while cycles[pos] < 0:
        cycles[pos] = cycle_no
        pos = lookup[parent2[pos]]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.