Survivor Selection - danielwilczak101/EasyGA GitHub Wiki

Survivor selection is the process responsible for filling the next generation with enough chromosomes after the children are added.



Use for Survivor Selection

Survivor selection chooses the chromosomes in the current population to be added onto the next population, along with all of the children that were already there.

from EasyGA import GA, Survivor

# Create the Genetic algorithm.
ga = GA()

# Built-in survivor selection implementations:
ga.survivor_selection_impl = Survivor.fill_in_best  # Default
#ga.survivor_selection_impl = Survivor.fill_in_random
#ga.survivor_selection_impl = Survivor.fill_in_parents_then_random

# Run everything.
ga.evolve()

Code for Parent Selection

Survivor selection works by selecting chromosomes from the population and adding them to the mating next population. This may be done by two methods:

  • Use ga.population.append_children(chromosome_list) to append a list of chromosomes to the next population.
  • Use ga.population.add_child(chromosome) to add a single chromosome to the next population.

Fill in Best

Fill in best is one type of survivor selection method. It simply selects the best chromosomes from the population. This is a part of elitism and guarantees the best chromosomes always move to the next population.

ga.survivor_selection_impl = Survivor.fill_in_best

Code:

def fill_in_best(ga):
    """Fills in the next population with the best chromosomes from the last population"""

    needed_amount = len(ga.population) - len(ga.population.next_population)
    ga.population.append_children(ga.population[:needed_amount])

Fill in Random

Fill in random is another type of survivor selection method. It selects the chromosomes randomly from the population. The same chromosome cannot be selected twice here.

ga.survivor_selection_impl = Survivor.fill_in_random

Code:

def fill_in_random(ga):
    """Fills in the next population with random chromosomes from the last population"""

    needed_amount = len(ga.population) - len(ga.population.next_population)
    ga.population.append_children(random.sample(ga.population, needed_amount))

Fill in Parents then Random

Fill in parents then random is another type of survivor selection method. It selects parent chromosomes from the mating pool first followed by random chromosomes in the population. This is essentially a mixture of filling in the best and random chromosomes, using the status of being a parent as an indicator that a chromosome is good. The same chromosome cannot be selected twice here.

ga.survivor_selection_impl = Survivor.fill_in_parents_then_random

Code:

def fill_in_parents_then_random(ga):
    """Fills in the next population with all parents followed by random chromosomes from the last population"""

    # Remove dupes from the mating pool
    mating_pool = set(ga.population.mating_pool)

    needed_amount = len(ga.population) - len(ga.population.next_population)
    parent_amount = min(needed_amount, len(mating_pool))
    random_amount = needed_amount - parent_amount

    # Only parents are used.
    if random_amount == 0:
        ga.population.append_children(
            chromosome
            for i, chromosome
            in enumerate(mating_pool)
            if i < parent_amount
        )

    # Parents need to be removed from the random sample to avoid dupes.
    else:
        ga.population.append_children(mating_pool)
        ga.population.append_children(
               random.sample(
                  set(ga.population) - mating_pool,
                  random_amount
              )
        )

Build your own

There are many forms of survivor selection in the literature which may suit your specific problem better than any of the built-in methods. For example, you may want to avoid selecting chromosomes which are very similar to improve genetic diversity.

To build your own survivor selection method, manually add chromosomes to the next population using either of the following two methods:

  • Use ga.population.append_children(chromosome_list) to append a list of chromosomes to the next population.
  • Use ga.population.add_child(chromosome) to add a single chromosome to the next population.

Example:

Using the example above, we allow the best chromosome to survive along with the best chromosomes which do not have the all of the same genes as the best chromosome.

from EasyGA import GA

# Create the Genetic algorithm.
ga = GA()


# Custom implementation of the survivor selection method.
def survivor_selection_impl(ga):
    needed_amount = len(ga.population) - len(ga.population.next_population)

    # Save the best chromosome
    if needed_amount > 0:
        best_chromosome = ga.population[0]
        ga.population.add_child(best_chromosome)
        needed_amount -= 1
        if needed_amount <= 0:
            return

    # Loop through the population
    for chromosome in ga.population:

        # Add chromosome if any of the genes are different
        if any(best_gene != gene for best_gene, gene in zip(best_chromosome, chromosome))
            ga.population.add_child(chromosome)
            needed_amount -= 1

            # Stop if enough chromosomes survive
            if needed_amount <= 0:
                break


# Setting the survivor selection method.
ga.survivor_selection_impl = survivor_selection_impl

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