Parent Selection - danielwilczak101/EasyGA GitHub Wiki

Parent selection is the process responsible for choosing chromosomes to add to the mating pool, which will be used to create the next generation.

• Use for Parent Selection.
• Code for Parent Selection.
• - Decorators.
• - Methods.
• --- Rank Selection.
• --- Fitness Selection.
• Build your own.

View the source code here.

Use for Parent Selection

Parent selection chooses the chromosomes used to produce new chromosomes.

from EasyGA import GA, Parent

# Create the Genetic algorithm.
ga = GA()

# Built-in decorators for implementing custom parent selection:
#@Parent._check_selection_probability
#@Parent._check_positive_fitness
#@Parent._ensure_sorted
#@Parent._compute_parent_amount

# Built-in parent selection implementations:
ga.parent_selection_impl = Parent.Rank.tournament  # Default
#ga.parent_selection_impl = Parent.Rank.stochastic_geometric
#ga.parent_selection_impl = Parent.Rank.stochastic_arithmetic
#ga.parent_selection_impl = Parent.Fitness.roulette
#ga.parent_selection_impl = Parent.Fitness.stochastic

# Run everything.
ga.evolve()

Code for Parent Selection

View the source code here.

Parent selection works by selecting parents from the population and adding them to the mating pool. This may be done by three methods:

1. Use ga.population.set_parent(index) to add the indexed chromosome from the population to the mating pool.
2. Use ga.population.add_parent(chromosome) to add the chromosome to the mating pool.
3. Directly changing ga.population.mating_pool.

Decorators

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

Check Selection Probability

Checks to make sure the selection probability is between 0 and 1 before running the selection method. Raises a ValueError otherwise.

@Parent._check_selection_probability

Code:

def _check_selection_probability(selection_method):
    """Raises a ValueError if the selection_probability is not between 0 and 1 inclusively.
    Otherwise runs the selection method."""

    def new_method(ga):
        if 0 <= ga.selection_probability <= 1:
            selection_method(ga)
        else:
            raise ValueError("Selection probability must be between 0 and 1 to select parents.")

    return new_method

Check Positive Fitness

Checks to make sure the (converted) fitness values are not negative and not all 0 before running. Raises a ValueError otherwise. Useful for selection methods based on the fitness value of a chromosome.

@Parent._check_positive_fitness

Code:

def _check_positive_fitness(selection_method):
    """Raises a ValueError if the population contains a chromosome with negative fitness.
    Otherwise runs the selection method."""

    def new_method(ga):
        if ga.get_chromosome_fitness(0) > 0 and ga.get_chromosome_fitness(-1) >= 0:
            selection_method(ga)
        else:
            raise ValueError("Converted fitness values can't have negative values or be all 0."
                             + " Consider using rank selection or stochastic selection instead.")

    return new_method

Ensure Sorted

Sorts the population by fitness before running.

@Parent._ensure_sorted

Code:

def _ensure_sorted(selection_method):
    """Sorts the population by fitness and then runs the selection method."""

    def new_method(ga):
        ga.sort_by_best_fitness()
        selection_method(ga)

    return new_method

Compute Parent Amount

Computes the size of the mating pool given the length of the current population and the parent ratio. Uses a minimum of two parents.

def _compute_parent_amount(selection_method):
    """Computes the amount of parents needed to be selected,
    and passes it as another argument for the method."""

    def new_method(ga):
        parent_amount = max(2, round(len(ga.population)*ga.parent_ratio))
        selection_method(ga, parent_amount)

    return new_method

Methods

Rank Selection

Rank selection chooses parents based on their fitness ranking in the population. The best chromosome has some chance of becoming a parent, then the second best chromosome has a smaller chance of becoming a parent, etc., regardless of how close or far the fitness values are from each other.

Tournament

Tournament selection is one type of rank selection. Tournament selection runs multiple tournaments between chromosomes, where the winners are selected as parents. If the selection probability is very low, a tournament might not have a winner, in which case a winner is chosen randomly.

ga.parent_selection_impl = Parent.Rank.tournament

Code:

@_check_selection_probability
@_ensure_sorted
def tournament(ga, parent_amount):
    """
    Will make tournaments of size tournament_size and choose the winner (best fitness) 
    from the tournament and use it as a parent for the next generation. The total number 
    of parents selected is determined by parent_ratio, an attribute to the GA object.
    May require many loops if the selection probability is very low.
    """

    # Choose the tournament size.
    # Use no less than 5 chromosomes per tournament.
    tournament_size = int(len(ga.population)*ga.tournament_size_ratio)
    if tournament_size < 5:
        tournament_size = min(5, len(ga.population))

    # Repeat tournaments until the mating pool is large enough.
    while len(ga.population.mating_pool) < parent_amount:

        # Generate a random tournament group and sort by fitness.
        tournament_group = sorted(random.sample(
            range(len(ga.population)),
            tournament_size
        ))

        # For each chromosome, add it to the mating pool based on its rank in the tournament.
        for index in range(tournament_size):

            # Probability required is selection_probability * (1-selection_probability) ^ index
            # Each chromosome is (1-selection_probability) times
            # more likely to become a parent than the next ranked.
            if random.random() < ga.selection_probability * (1-ga.selection_probability) ** index:
                break

        # Use random in tournament if noone wins
        else:
            index = random.randrange(tournament_size)

        ga.population.set_parent(tournament_group[index])

Stochastic Geometric

Stochastic geometric is another type of rank fitness selection, where the probability of being selected is a geometric progression. It is similar to tournament selection but does not create tournaments. It may be seen as tournament selection where each tournament is the entire population. This method tends to be faster than tournament selection since it does not use tournaments and uses a built-in method to create the entire mating pool all at once. However, this method is less likely to select low ranking parents than tournament selection.

ga.parent_selection_impl = Parent.Rank.stochastic_geometric

Code:

def stochastic_geometric(ga, parent_amount):
    """
    Selects parents with probabilities given by a geometric progression. This
    method is similar to tournament selection, but doesn't create several
    tournaments. Instead, it assigns probabilities to each rank and selects
    the entire mating pool using random.choices. Since it essentially uses the
    entire population as a tournament repeatedly, it is less likely to select
    worse parents than tournament selection.
    """

    # Set the weights of each parent based on their rank.
    # Each chromosome is (1-selection_probability) times
    # more likely to become a parent than the next ranked.
    weights = [
        (1-ga.selection_probability) ** i
        for i
        in range(len(ga.population))
    ]

    # Set the mating pool.
    ga.population.mating_pool = random.choices(ga.population, weights, k = parent_amount)

Stochastic Arithmetic

Stochastic arithmetic is another type of rank fitness selection, where the probability of being selected is a arithmetic progression. It is similar to stochastic geometric selection, but is more likely to select low ranking parents.

ga.parent_selection_impl = Parent.Rank.stochastic_arithmetic

Code:

def stochastic_arithmetic(ga, parent_amount):
    """
    Selects parents with probabilities given by an arithmetic progression. This
    method is similar to stochastic-geometric selection, but is more likely to
    select worse parents with its simpler selection scheme.
    """

    # Set the weights of each parent based on their rank.
    # The worst chromosome has a weight of 1,
    # the next worst chromosome has a weight of 2,
    # etc.
    # with an inflation of (1-selection probability) * average weight

    average_weight = (len(ga.population)+1) // 2
    inflation = (1-ga.selection_probability) * average_weight

    weights = [
        i + inflation
        for i
        in range(len(ga.population), 0, -1)
    ]

    # Set the mating pool.
    ga.population.mating_pool = random.choices(ga.population, weights, k = parent_amount)

Fitness Selection

Fitness selection chooses parents based on their fitness values. For example, if chromosome A has double the fitness of chromosome B, it might be selected as a parent twice as often. These methods usually require positive (converted) fitness values.

Roulette

Roulette selection is one type of fitness selection. Roulette selection assigns each chromosome a relative probability based on their fitness values. Then randomly selects one based on their probability by dividing the fitness of each chromosome by the sum of all (converted) fitnesses.

ga.parent_selection_impl = Parent.Fitness.roulette

Code:

@_check_selection_probability
@_ensure_sorted
@_check_positive_fitness
@_compute_parent_amount
def roulette(ga, parent_amount):
    """Roulette selection works based off of how strong the fitness is of the
    chromosomes in the population. The stronger the fitness the higher the probability
    that it will be selected. Using the example of a casino roulette wheel.
    Where the chromosomes are the numbers to be selected and the board size for
    those numbers are directly proportional to the chromosome's current fitness. Where
    the ball falls is a randomly generated number between 0 and 1.
    """

    # The sum of all the fitnessess in a population
    fitness_sum = sum(
        ga.get_chromosome_fitness(index)
        for index
        in range(len(ga.population))
    )

    # A list of ranges that represent the probability of a chromosome getting chosen
    probability = [ga.selection_probability]

    # The chance of being selected increases incrementally
    for index in range(len(ga.population)):
        probability.append(probability[-1]+ga.get_chromosome_fitness(index)/fitness_sum)

    probability = probability[1:]

    # Loops until it reaches a desired mating pool size
    while len(ga.population.mating_pool) < parent_amount:

        # Spin the roulette
        rand_number = random.random()

        # Find where the roulette landed.
        for index in range(len(probability)):
            if (probability[index] >= rand_number):
                ga.population.set_parent(index)
                break

Stochastic

Stochastic selection is another type of fitness selection. Stochastic selection assigns each chromosome a relative probability based on their fitness values. Then randomly selects one based on their probability by dividing by the largest (converted) fitness. Its advantage over roulette selection is it tends to be faster because it does not have to search for the chromosome the roulette lands on but rather runs individual roulettes for random chromosomes.

ga.parent_selection_impl = Parent.Fitness.stochastic

Code:

@_check_selection_probability
@_ensure_sorted
@_compute_parent_amount
def stochastic(ga, parent_amount):
    """
    Selects parents using the same probability approach as roulette selection,
    but doesn't spin a roulette for every selection. Uses random.choices with
    weighted values to select parents and may produce duplicate parents.
    """

    # All fitnesses are the same, select randomly.
    if ga.get_chromosome_fitness(-1) == ga.get_chromosome_fitness(0):
        offset = 1-ga.get_chromosome_fitness(-1)

    # Some chromosomes have negative fitness, shift them all into positives.
    elif ga.get_chromosome_fitness(-1) < 0:
        offset = -ga.get_chromosome_fitness(-1)

    # No change needed.
    else:
        offset = 0

    # Set the weights of each parent based on their fitness + offset.
    weights = [
        ga.get_chromosome_fitness(index) + offset
        for index
        in range(len(ga.population))
    ]

    inflation = sum(weights) * (1 - ga.selection_probability)

    # Rescale and adjust using selection_probability so that
    #   if selection_probability is high, a low inflation is used,
    #     making selection mostly based on fitness.
    #   if selection_probability is low, a high offset is used,
    #     so everyone has a more equal chance.
    weights = [
        weight + inflation
        for weight
        in weights
    ]

    # Set the mating pool.
    ga.population.mating_pool = random.choices(ga.population, weights, k = parent_amount)

Build your own

There are many parent selection methods in the literature, some of which may work better or faster for a specific problem than the provided built-in methods. For example, it may be fine to simply select half of the mating pool as the best chromosomes in the population and the other half to be random chromosomes.

The built-in decorators allow for easy checking of certain parameters before running the parent selection method. To write your own parent selection method, add selected chromosomes to the mating pool. This may be done by three methods:

1. Use ga.population.set_parent(index) to add the indexed chromosome from the population to the mating pool.
2. Use ga.population.add_parent(chromosome) to add the chromosome to the mating pool.
3. Directly changing ga.population.mating_pool.

Example:

Using the example above with half of the mating pool as the best chromosomes in the population and the other half to be random chromosomes.

import random
from math import ceil
from EasyGA import GA


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

    def parent_selection_impl(self):
        """Custom parent selection method which selects the best for half of the mating pool
        and then randomly for the rest of the mating pool."""

        mating_pool_size = ceil(len(ga.population)*ga.parent_ratio)
        ga.population.mating_pool = ga.population[:mating_pool_size//2]  # Select the best half
        for _ in range((mating_pool_size+1)//2):  # Select the random half
            ga.population.add_parent(random.choice(ga.population))  # Random chromosome from the population


# Create the Genetic algorithm.
ga = My_GA()

# Run everything.
ga.evolve()