Crossover - danielwilczak101/EasyGA GitHub Wiki

Crossover is the process responsible for creating new chromosomes based on the mating pool and adding them to the population.

View the source code here.



Use for Crossover

Crossover is broken down into population and individual methods. The population methods are used to select pairs of parents from the mating pool. The individual methods are used to cross pairs of parents.

from EasyGA import GA, Crossover

# Create the Genetic algorithm.
ga = GA()

# Built-in decorators for implementing custom crossover:
#@Crossover._check_weight
#@Crossover._gene_by_gene

# Built-in crossover population implementations:
ga.crossover_population_impl = Crossover.Population.sequential  # Default
#ga.crossover_population_impl = Crossover.Population.random_mate

# Built-in crossover individual implementations:
ga.crossover_individual_impl = Crossover.Individual.single_point  # Default
#ga.crossover_individual_impl = Crossover.Individual.multi_point
#ga.crossover_individual_impl = Crossover.Individual.uniform
#ga.crossover_individual_impl = Crossover.Individual.Arithmetic.average
#ga.crossover_individual_impl = Crossover.Individual.Arithmetic.extrapolate
#ga.crossover_individual_impl = Crossover.Individual.Arithmetic.random_value
#ga.crossover_individual_impl = Crossover.Individual.Permutation.ox1

# Run everything.
ga.evolve()

Code for Crossover Methods

View the source code here.

Crossover population methods work by selecting pairs parents from the mating pool and then crossing them. The new chromosome is made and saved using the crossover individual methods.

A local helper function randround is used to round up or down randomly, depending on which is closer. These are used to keep integer genes in some methods.

# Round to an integer near x with higher probability
# the closer it is to that integer.
randround = lambda x: int(x + random.random())

Decorators

Decorators make it easier to write crossover methods. EasyGA comes with several built-in decorators.

Check Weight

Checks if the weight is between 0 and 1 before running. Otherwise throws a value error. May occur when using ga.adapt with a crossover method that does not allow weights outside this range, which will catch the error and redo with valid weight.

@Crossover._check_weight

Code:

def _check_weight(individual_method):
    """Checks if the weight is between 0 and 1 before running.
    Exception may occur when using ga.adapt, which will catch
    the error and try again with valid weight.
    """

    def new_method(ga, parent_1, parent_2, *, weight = individual_method.__kwdefaults__.get('weight', None)):

        if weight is None:
            individual_method(ga, parent_1, parent_2)
        elif 0 < weight < 1:
            individual_method(ga, parent_1, parent_2, weight = weight)
        else:
            raise ValueError(f"Weight must be between 0 and 1 when using {individual_method.__name__}.")

    return new_method

Gene by Gene

Create a singular chromosome by crossing each gene from the parents individually.

@Crossover._gene_by_gene

Code:

def _gene_by_gene(individual_method):
    """Perform crossover by making a single new chromosome by combining each gene by gene."""

    def new_method(ga, parent_1, parent_2, *, weight = individual_method.__kwdefaults__.get('weight', 'None')):

        ga.population.add_child(
            individual_method(ga, value_1, value_2)
            if weight == 'None' else
            individual_method(ga, value_1, value_2, weight = weight)
            for value_1, value_2
            in zip(parent_1.gene_value_iter, parent_2.gene_value_iter)
        )

    return new_method

Population Methods

Crossover Population methods are used to select pairs of parents from the mating pool. Each pair of parents selected is then crossed to produce children using the Crossover Individual methods.

Sequential

Sequential is one type of crossover population method. Sequential crosses sequential pairs of parents from the mating pool so that each parent mates with its neighboring parents.

ga.crossover_population_impl = Crossover.Population.sequential

Code:

def sequential(ga):
    """Select sequential pairs from the mating pool.
    Every parent is paired with the previous parent.
    The first parent is paired with the last parent.
    """

    mating_pool = ga.population.mating_pool

    for index in range(len(mating_pool)):  # for each parent in the mating pool
        ga.crossover_individual_impl(      #     apply crossover to
            mating_pool[index],            #         the parent and
            mating_pool[index-1]           #         the previous parent
        )

Random Mate

Random mate is another type of crossover population method. Random mate crosses each parent with another random parent in the mating pool.

ga.crossover_population_impl = Crossover.Population.random_mate

Code:

def random_mate(ga, mating_pool):
    """Select random pairs from the mating pool.
    Every parent is paired with a random parent.
    """

    mating_pool = ga.population.mating_pool

    for parent in mating_pool:          # for each parent in the mating pool
        ga.crossover_individual_impl(   #     apply crossover to
            parent,                     #         the parent and
            random.choice(mating_pool)  #         a random parent
        )

Individual Methods

Crossover Individual methods are used to cross pairs of parents provided by the Crossover Population methods. Each pair of parents is combined to produce a child chromosome. A weight parameter is used to determine which parent the child will become closer to. If the weight is closer to 0, the first parent is used less. If the weight is closer to 1, the second parent is used less.

Single Point

Single point crossover is one type of crossover individual method. The genes of the parents are swapped at a random index.

ga.crossover_individual_impl = Crossover.Individual.single_point

Code:

@_check_weight
def single_point(ga, parent_1, parent_2, *, weight = 0.5):
    """Cross two parents by swapping genes at one random point."""

    minimum_parent_length = min(len(parent_1), len(parent_2))

    # Weighted random integer from 0 to minimum parent length - 1
    swap_index = int(ga.weighted_random(weight) * minimum_parent_length)

    ga.population.add_child(parent_1[:swap_index] + parent_2[swap_index:])
    ga.population.add_child(parent_2[:swap_index] + parent_1[swap_index:])

Uniform

Uniform is another type of crossover individual method. The genes at each index are chosen randomly from both parents.

ga.crossover_individual_impl = Crossover.Individual.uniform

Code:

@_check_weight
@_gene_by_gene
def uniform(ga, *gene_values, *, weight = 0.5):
    """Cross two parents by swapping all genes randomly."""
    return random.choices(gene_values, cum_weights = [weight, 1])[0]

Arithmetic Methods

The individual crossover methods also contain the arithmetic methods. Arithmetic methods are specific to numerical gene types and are not suitable for other data types, such as string genes. To cross two genes, a numerical value is chosen between them. This value may be selected randomly or as a weighted average.

Average

Average is another type of crossover individual arithmetic method. The average value of each gene is chosen from the parents. This method is useful for most problems with numerical genes.

If a negative weight is given, this method turns into the extrapolate method.

ga.crossover_individual_impl = Crossover.Individual.Arithmetic.average

Code:

@_gene_by_gene
def average(ga, value_1, value_2, *, weight = 0.5):
    """Cross two parents by taking the average of the genes."""

    average_value = weight*value_1 + (1-weight)*value_2

    if type(value_1) == type(value_2) == int:
        average_value = randround(value)

    return average_value

Extrapolate

Extrapolate is one type of crossover individual arithmetic method. Extrapolating is equivalent to averaging but with negative weights, which produces chromosomes which lie on the opposite side of the 1st parent compared to the 2nd parent. This method is useful for problems where the solution is best approached from only one direction, which makes averaging an infeasible crossover technique.

If a negative weight is given, this method turns into the average method.

ga.crossover_individual_impl = Crossover.Individual.Arithmetic.extrapolate

Code:

@_gene_by_gene
def extrapolate(ga, value_1, value_2, *, weight = 0.5):
    """Cross two parents by extrapolating towards the first parent.
    May result in gene values outside the expected domain.
    """

    extrapolated_value = weight*value_1 + (1-weight)*value_2

    if type(value_1) == type(value_2) == int:
        extrapolated_value = randround(value)

    return extrapolated_value

Random Value

Random value is one type of crossover individual arithmetic method meant for integer or float data types. A random gene is chosen numerically between the genes from the parents.

ga.crossover_individual_impl = Crossover.Individual.Arithmetic.random_value

Code:

@_check_weight
@_gene_by_gene
def random_value(ga, value_1, value_2, *, weight = 0.5):
    """Cross two parents by taking a random integer or float value between each of the genes."""

    value = value_1 + ga.weighted_random(weight) * (value_2-value_1)

    if type(value_1) == type(value_2) == int:
        value = randround(value)

    return value

Permutation Methods

The individual crossover methods also contain the permutation methods. Permutation methods are specific to chromosomes based on permutating values e.g. a random shuffling of values.

OX1

OX1 is one type of crossover individual permutation method. A random segment of genes is taken from one parent and the remaining genes from the second parent are filled in sequentially.

ga.crossover_individual_impl = EasyGA.Crossover_Methods.Individual.Permutation.ox1

Code:

@_check_weight
def ox1(ga, parent_1, parent_2, *, weight = 0.5):
    """Cross two parents by slicing out a random part of one parent
    and then filling in the rest of the genes from the second parent.
    """

    # Too small to cross
    if len(parent_1) < 2:
        raise ValueError("Parent lengths must be at least 2.")

    # Unequal parent lengths
    if len(parent_1) != len(parent_2):
        raise ValueError("Parents do not have the same lengths.")

    # Swap with weighted probability so that most of the genes
    # are taken directly from parent 1.
    if random.choices([0, 1], cum_weights = [weight, 1]) == 1:
        parent_1, parent_2 = parent_2, parent_1

    # Extract genes from parent 1 between two random indexes
    index_2 = random.randrange(1, len(parent_1))
    index_1 = random.randrange(index_2)

    # Create copies of the gene lists
    gene_list_1 = [None]*index_1 + parent_1[index_1:index_2] + [None]*(len(parent_1)-index_2)
    gene_list_2 = list(parent_2)

    input_index = 0

    # For each gene from the second parent
    for _ in range(len(gene_list_2)):

        # Remove it if it is already used
        if gene_list_2[-1] in gene_list_1:
            gene_list_2.pop(-1)

        # Add it if it has not been used
        else:
            if input_index == index_1:
                input_index = index_2
            gene_list_1[input_index] = gene_list_2.pop(-1)
            input_index += 1

   ga.population.add_child(gene_list_1)

Build your own

There are many crossover methods in the literature which may suit your specific problem better than any of the built-in methods. For example, your problem may involve 10 random integer genes from 0 to 25 such that the sum of all of the genes are equal to 100. This could represent a spending budget, with the genes representing where things are spent. For this problem you may want to take average integer genes rounded down and then adding 1 to random genes less than 25 until the total sum is 100.

The built-in methods allow for easy defining of custom crossover methods without dealing with a lot of the GA structure. To define your own individual method for crossing two parents, you may return a collection of values, genes, or make the chromosome yourself.

Note that you must accept the ga, the two parents (or two values if using @Parent._gene_by_gene), and the (kwarg) weight as inputs.

Example:

Using the example above, we show the following code:

import random
from EasyGA import GA


class MY_GA(GA):
    """Example GA with custom crossover_individual_impl method."""

    def crossover_individual_impl(self, parent_1, parent_2, weight):

        # get gene values
        value_iter_1 = parent_1.gene_value_iter
        value_iter_2 = parent_2.gene_value_iter

        # list of average gene values
        value_list = [
            (value_1+value_2) // 2
            for value_1, value_2
            in zip(value_iter_1, value_iter_2)
        ]

        value_sum = sum(value_list)

        # ensure the sum adds up to 100
        while value_sum < 100:

            # add onto a random gene, if possible
            index = random.randrange(len(value_list))
            if value_list[index] < 25:
                value_list[index] += 1
                value_sum += 1

        return value_list


# Create the Genetic algorithm.
ga = My_GA()

# Run everything.
ga.evolve()
⚠️ **GitHub.com Fallback** ⚠️