Mutation Operators

Mutation operators introduce variation into the population by modifying one or more genes of an individual. In cellular genetic algorithms (CGAs), mutation is a key mechanism that ensures diversity and enables exploration of the solution space, preventing premature convergence.

Understanding Mutation

Mutation in genetic algorithms mimics the natural process of genetic mutation, where random changes occur in an individual’s genome. These changes help the algorithm discover new solutions and improve its overall performance.

The Role of Mutation in CGA

• Diversity Preservation: Mutation ensures that the population does not converge prematurely to suboptimal solutions.

• Exploration: Introduces new solutions to explore unexplored regions of the solution space.

• Fine-Tuning: Makes small adjustments to solutions, aiding in reaching optimal solutions.

Mutation Examples

Below is an example of a Bit-Flip Mutation applied to a binary chromosome:

Figure 1: Bit-flip mutation flips a single gene in a binary chromosome.

Another example is the Swap Mutation, often used for permutation-based problems. It swaps two genes, introducing a small but significant change in the chromosome:

Figure 2: Swap mutation changes the order of two genes in a chromosome.

Common Mutation Types

1. Bit-Flip Mutation: Flips a bit in binary-encoded chromosomes.

2. Swap Mutation: Exchanges two genes in permutation-based chromosomes.

3. Byte Mutation: Applies byte-level changes to real-valued genes.

4. Two-Opt Mutation: Reverses a segment of the chromosome, particularly useful in path optimization.

API References

The following sections provide detailed documentation for the mutation operators available in the pycellga.mutation package.

Bit Flip Mutation

Applies a bitwise flip to binary-encoded chromosomes. This operator is a classic choice for binary genetic algorithms, offering a simple yet effective mutation approach.

class BitFlipMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

BitFlipMutation performs a bit flip mutation on an individual in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the BitFlipMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a bit flip mutation on the candidate individual.

A single bit in the candidate’s chromosome is randomly selected and flipped (i.e., a 0 is changed to a 1, or a 1 is changed to a 0).

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Byte Mutation

Performs mutations at the byte level for real-valued chromosomes. This operator leverages byte manipulation to create small, precise adjustments in the solution space, optimizing the algorithm’s performance for continuous functions.

class ByteMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

ByteMutation operator defined in (Satman, 2013). ByteMutation performs a byte-wise mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the ByteMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a byte-wise mutation on the candidate individual.

A single byte in one of the candidate’s chromosome’s floating-point numbers is randomly selected and either incremented or decremented by 1, wrapping around if necessary.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Randomized Byte Mutation

Introduces randomness at the byte level, enabling broader exploration in real-valued optimization tasks. This operator is particularly effective when a high degree of variation is desirable.

class ByteMutationRandom(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

ByteMutationRandom operator defined in (Satman, 2013). ByteMutationRandom performs a random byte mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the ByteMutationRandom object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a random byte mutation on the candidate individual.

A single byte in one of the candidate’s chromosome’s floating-point numbers is randomly selected and mutated to a random value.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Uniform Float Mutation

Applies uniform random mutations across real-valued chromosomes. This operator is suitable for continuous optimization, where each gene is adjusted within a defined range to enhance solution diversity.

class FloatUniformMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

FloatUniformMutation performs a uniform mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the FloatUniformMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a uniform mutation on the candidate individual.

Each gene in the candidate’s chromosome is mutated by adding or subtracting a random float uniformly sampled from [0, 1]. The mutation is rounded to 5 decimal places.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Insertion-Based Mutation

A mutation strategy tailored for permutation-based representations, such as in sequencing and scheduling problems. This operator repositions a randomly selected gene within the chromosome, altering the order while preserving elements.

class InsertionMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

InsertionMutation performs an insertion mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the InsertionMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform an insertion mutation on the candidate individual.

A gene in the candidate’s chromosome is randomly selected and moved to a new position in the chromosome.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Shuffle Mutation

Randomly rearranges a subset of genes in the chromosome. This operator is effective in permutation-based problems, promoting diversity by shuffling segments without altering individual gene values.

class ShuffleMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

ShuffleMutation performs a shuffle mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the ShuffleMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a shuffle mutation on the candidate individual.

A subsequence of genes in the candidate’s chromosome is randomly selected and shuffled.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Swap Mutation

Swaps the positions of two genes, introducing subtle changes ideal for permutation-based optimizations. This operator is commonly applied in combinatorial problems where order is significant.

class SwapMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

SwapMutation performs a swap mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the SwapMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a swap mutation on the candidate individual.

Two genes in the candidate’s chromosome are randomly selected and swapped.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual

Two-Opt Mutation

A mutation operator frequently used in path optimization problems, such as the Traveling Salesman Problem. It reverses a segment of the chromosome, allowing for new path configurations without altering the gene order.

class TwoOptMutation(mutation_cand: Individual = None, problem: AbstractProblem = None)

Bases: MutationOperator

TwoOptMutation performs a 2-opt mutation on an individual’s chromosome in a Genetic Algorithm.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

__init__(mutation_cand: Individual = None, problem: AbstractProblem = None)

Initialize the TwoOptMutation object.

Parameters:

• mutation_cand (Individual, optional) – The candidate individual to be mutated (default is None).

• problem (AbstractProblem, optional) – The problem instance that provides the fitness function (default is None).

mutate() → Individual

Perform a 2-opt mutation on the candidate individual.

A segment of the candidate’s chromosome is randomly selected and reversed.

Returns:

A new individual with the mutated chromosome.

Return type:

Individual