Mutation - danielwilczak101/EasyGA GitHub Wiki

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



Use for Mutation

Mutation is broken down into population and individual methods. The population methods are used to select chromosomes to mutate. The individual methods are used to mutate the selected chromosomes.

from EasyGA import GA, Mutation

# Create the Genetic algorithm.
ga = GA()

# Built-in decorators for implementing custom mutation:
#@Mutation._check_chromosome_mutation_rate
#@Mutation._check_gene_mutation_rate
#@Mutation._loop_selections
#@Mutation._loop_mutations

# Built-in mutation population implementations:
ga.mutation_population_impl = Mutation.Population.random_avoid_best  # Default
#ga.mutation_population_impl = Mutation.Population.random_selection

# Built-in mutation individual implementations:
ga.mutation_individual_impl = Mutation.Individual.individual_genes  # Default
#ga.mutation_individual_impl = Mutation.Individual.Permutation.swap_genes

# Run everything.
ga.evolve()

Code for Mutations

Decorators

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

Check Chromosome Mutation Rate

Checks if the chromosome mutation rate is a float between 0 and 1 before running a mutation population method.

@Mutation._check_chromosome_mutation_rate

Code:

def _check_chromosome_mutation_rate(population_method):
    """Checks if the chromosome mutation rate is a float between 0 and 1 before running."""

    def new_population_method(ga):

        if not isinstance(ga.chromosome_mutation_rate, float):
            raise TypeError("Chromosome mutation rate must be a float.")

        elif 0 < ga.chromosome_mutation_rate < 1:
            population_method(ga)

        else:
            raise ValueError("Chromosome mutation rate must be between 0 and 1.")

    return new_population_method

Check Gene Mutation Rate

Checks if the gene mutation rate is a float between 0 and 1 before running a mutation individual method.

@Mutation._check_gene_mutation_rate

Code:

def _check_gene_mutation_rate(individual_method):
    """Checks if the gene mutation rate is a float between 0 and 1 before running."""

    def new_individual_method(ga, index):

        if not isinstance(ga.gene_mutation_rate, float):
            raise TypeError("Gene mutation rate must be a float.")

        elif 0 < ga.gene_mutation_rate < 1:
            individual_method(ga, index)

        else:
            raise ValueError("Gene mutation rate must be between 0 and 1.")

    return new_individual_method

Loop Selections

Changes a population method selecting a single chromosome by index for mutations to a method selecting multiple chromosomes.

@Mutation._loop_selections

Code:

def _loop_selections(population_method):
    """Runs the population method until enough chromosomes are mutated."""

    def new_population_method(ga):

        # Loop the population method until enough chromosomes are mutated.
        for _ in range(ceil(len(ga.population)*ga.chromosome_mutation_rate)):
            population_method(ga)

    return new_population_method

Loop Mutations

Changes a individual method mutating a chromosome by reference once to a method which mutates a chromosome by index multiple times.

@Mutation._loop_mutations

Code:

def _loop_mutations(individual_method):
    """Runs the individual method until enough
    genes are mutated on the indexed chromosome.
    """

    # Change input from index to chromosome.
    def new_individual_method(ga, index):

        # Loop the individual method until enough genes are mutated.
        for _ in range(ceil(len(ga.population[index])*ga.gene_mutation_rate)):
            individual_method(ga, ga.population[index])

    return new_individual_method

Population Methods

Mutation Population methods are used to select chromosomes from the population by index. Each selected chromosome is mutated using the individual methods.

Random Selection

Random selection is one type of mutation population method. Random selection selects chromosomes randomly from the population for mutation.

ga.mutation_population_impl = Mutation.Population.random_avoid_best

Code:

@_check_chromosome_mutation_rate
@_loop_selections
def random_selection(ga):
    """Selects random chromosomes."""

    index = random.randrange(len(ga.population))
    ga.mutation_individual_impl(ga, index)

Random Avoid Best

Random avoid best is another type of mutation population method. Random avoid best selects chromosomes randomly from the population for mutation but avoids selecting the best chromosomes. This is a part of elitism and guarantees the best chromosomes do not change between generations.

ga.mutation_population_impl = Mutation.Population.random_avoid_best

Code:

@_check_chromosome_mutation_rate
@_loop_selections
def random_avoid_best(ga):
    """Selects random chromosomes while avoiding the best chromosomes. (Elitism)"""

    index = random.randrange(
        int(len(ga.population)*ga.gene_mutation_rate/2),
        len(ga.population)
    )
    ga.mutation_individual_impl(ga, index)

Individual Methods

Mutation Individual methods are used to modify the genes of a selected chromosome.

Individual Genes

Individual genes is one type of mutation individual method. It randomly selects genes to randomize according to the given chromosome or gene implementation.

ga.mutation_individual_impl = Mutation.Individual.individual_genes
@_check_gene_mutation_rate
@_loop_mutations
def individual_genes(ga, chromosome):
    """Mutates a random gene in the chromosome."""

    index = random.randrange(len(chromosome))

    # Using the chromosome_impl
    if ga.chromosome_impl is not None:
        chromosome[index] = ga.make_gene(ga.chromosome_impl()[index])

    # Using the gene_impl
    elif ga.gene_impl is not None:
        chromosome[index] = ga.make_gene(ga.gene_impl())

    # Exit because no gene creation method specified
    else:
        raise Exception("Did not specify any initialization constraints.")

Permutation Methods

Mutation permutation methods are special types of mutation individual methods. Unlike other mutation methods, they do not create new genes. Instead, they rearrange the order of the genes in the chromosome. These are useful for problems such as the traveling salesman problem.

Swap Genes

Swap genes is one type of mutation individual permutation method. It randomly selects pairs genes to swap.

ga.mutation_individual_impl = Mutation.Individual.Permutation.swap_genes
@_check_gene_mutation_rate
@_loop_mutations
def swap_genes(ga, chromosome):
    """Swaps two random genes in the chromosome."""

    # Indexes of genes to swap
    index_one = random.randrange(len(chromosome))
    index_two = random.randrange(len(chromosome))

    # Swap genes
    chromosome[index_one], chromosome[index_two] = chromosome[index_two], chromosome[index_one]

Build your own

There are many mutation methods in the literature which may suit your specific problem better than any of the built-in methods. For example, it may be necessary to use a pseudo-permutation method, which randomizes the first half of the genes and swaps the second half. Or a more custom method for selecting chromosomes may be wanted to improve speed by choosing the middle fittest of the population.

The built-in decorators allow for easy checking of certain parameters as well as contains the looping structure of the mutation methods. This makes it easier to write your own mutation methods. Use the following format for building population and individual methods:

  • The population method should use ga.mutation_individual_impl(ga, index) to mutate the indexed chromosome.
  • The individual method should use chromosome[index] = new_gene to mutate the indexed gene in the chromosome.

Example:

Using the above example, mutating the middle of the population can be done similarly to the Random Avoid Best method by restricting the range of possible indexes. Using the above example, mutating the first half of the chromosome with new genes and the second half of the chromosome with swapping can be done again by restricting the range of possible indexes for each.

import random
from EasyGA import GA, Mutation

# Create the Genetic algorithm.
ga = GA()


# Custom implementation of the mutation population method.
@Mutation._check_chromosome_mutation_rate
@Mutation._loop_selections

def mutation_population_impl(ga):

    # indexes surrounding the middle of the population
    low_index = int(len(ga.population)*(1-ga.gene_mutation_rate)/2)
    upp_index = int(len(ga.population)*(1+ga.gene_mutation_rate)/2)

    index = random.randrange(low_index, upp_index)
    ga.mutation_individual_impl(ga, index)


# Custom implementation of the mutation individual method.
@Mutation._check_gene_mutation_rate
@Mutation._loop_mutations

def mutation_individual_impl(ga, chromosome):

    index = random.randrange(len(chromosome))

    # Use swapping
    if index > len(chromosome)/2:
        index_1 = index
        index_2 = random.randrange(index, len(chromosome))  # Stay in range.

        chromosome[index_1], chromosome[index_2] = chromosome[index_2], chromosome[index_1]  # Swap genes.

    # Make a new gene using chromosome_impl
    elif ga.chromosome_impl is not None:
        chromosome[index] = ga.chromosome_impl()[index]

    # Make a new gene using gene impl
    elif ga.gene_impl is not None:
        chromosome[index] = ga.gene_impl()

    # Can't make new gene
    else:
        raise Exception("Did not specify any initialization constraints.")


# Setting the mutation methods.
ga.mutation_population_impl = mutation_population_impl
ga.mutation_individual_impl = mutation_individual_impl

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