Public Types
enum	CrossoverType : uint8_t { CrossoverType::OnePoint = 1, CrossoverType::TwoPoint, CrossoverType::KPoint, CrossoverType::Uniform }

enum	MutatorType : uint8_t { MutatorType::Flip = 1 }

enum	SelectorType : uint8_t { SelectorType::Rank = 1, SelectorType::Uniform, SelectorType::RouletteWheel, SelectorType::Tournament }

enum	MutationRateSchedule : uint8_t { MutationRateSchedule::Constant = 1, MutationRateSchedule::Deterministic, MutationRateSchedule::SelfAdaptive, MutationRateSchedule::Proportional }

Public Member Functions
	GeneticAlgorithm (const GeneticAlgorithm &rhs)=delete

GeneticAlgorithm &	operator= (const GeneticAlgorithm &rhs)=delete

Genome &	GetGenome ()

void	SetCrossoverIgnoreGeneBoundaries (bool crossover_ignore_gene_boundaries)

bool	GetCrossoverIgnoreGeneBoundaries () const

void	SetAllowSameParentCouples (bool allow_same_parent_couples)

bool	GetAllowSameParentCouples () const

void	SetTournamentSize (size_t tournament_size)

size_t	GetTournamentSize () const

void	SetKPointCrossoverPointCount (size_t k_point_crossover_point_count)

size_t	GetKPointCrossoverPointCount () const

void	SetSelfAdaptiveMutationDiversityFloor (double self_adaptive_mutation_diversity_floor)

double	GetSelfAdaptiveMutationDiversityFloor () const

void	SetSelfAdaptiveMutationAggressiveRate (double self_adaptive_mutation_aggressive_rate)

double	GetSelfAdaptiveMutationAggressiveRate () const

void	SetProportionalMutationBitCount (size_t proportional_mutation_bit_count)

size_t	GetProportionalMutationBitCount () const

void	SetTotalGenerations (size_t total_generations)

size_t	GetTotalGenerations () const

void	SetMutationRate (double mutation_rate)

double	GetMutationRate () const

void	SetCrossoverRate (double crossover_rate)

double	GetCrossoverRate () const

void	SetCrossoverType (CrossoverType crossover_type)

CrossoverType	GetCrossoverType () const

void	SetSelectorType (SelectorType selector_type)

SelectorType	GetSelectorType () const

void	SetEliteCount (size_t elite_count)

size_t	GetEliteCount () const

void	SetMutatedEliteCount (size_t mutated_elite_count)

size_t	GetMutatedEliteCount () const

void	SetMutatedEliteMutationRate (double mutated_elite_mutation_rate)

double	GetMutatedEliteMutationRate () const

void	SetMutationRateSchedule (MutationRateSchedule mutation_rate_schedule)

MutationRateSchedule	GetMutationRateSchedule () const

void	SetMutatorType (MutatorType mutator_type)

MutatorType	GetMutatorType () const

void	SetUserData (void *user_data)

void *	GetUserData () const

void	SetFitnessFunction (FitnessFunction fitness_function)

FitnessFunction	GetFitnessFunction () const

void	SetPopulationSize (size_t population_size)

size_t	GetPopulationSize () const

size_t	GetCurrentGeneration () const

const Population &	GetPopulation () const

void	Initialize ()

void	SetInitialPopulation (const std::vector< BitVector > &initial_population)

void	Step ()

void	Run ()

Protected Member Functions
void	Crossover (const Individual &parent1, const Individual &parent2, Individual *offspring)

void	Mutate (Individual *individual, double mutation_percentage)

double	GetCurrentMutationRate ()

void	InitializeSelector (Population *population)

std::pair< const Individual &, const Individual & >	SelectParents (const Population &population)

const Individual &	SelectOne (const Population &population)

Population &	GetCurrentPopulation ()

Population &	GetLastGenerationPopulation ()

Member Enumeration Documentation

◆ CrossoverType

enum panga::GeneticAlgorithm::CrossoverType : uint8_t

strong

Type of crossover we will perform on selected parents in order to produce offspring for the next generation.
Actual crossover is performed by the Chromosome itself.

See also: Crossover; SetCrossoverType; GetCrossoverType; Chromosome

Enumerator
OnePoint	Perform one-point crossover. The parent chromosomes will be split into two pieces (based on one cut point) with the offspring receiving the left part of one parent and the right part of the other parent. The point at which to cut the parent chromosomes is determined randomly. See also Chromosome::KPointCrossover
TwoPoint	Perform two-point crossover. Similar to one-point crossover, but the parent chromosomes will be split into three pieces (based on two cut points) with the offspring receiving the first and last part from one parent and the middle part from the other parent. The points at which the parent chromosomes is cut will be determined randomly. See also Chromosome::KPointCrossover
KPoint	Perform k-point crossover. Similar to two-point crossover, but the parent chromosomes will be split into k+1 pieces (based on k cut points) with the offspring receiving pieces from both parents alternating. The points at which the parent chromosomes is cut will be determined randomly. k is determined by k_point_crossover_point_count_. See also k_point_crossover_point_count_ SetKPointCrossoverPointCount GetKPointCrossoverPointCount Chromosome::KPointCrossover
Uniform	Perform uniform crossover. Each bit in the chromosome has an equal chance of being copied from either parent. See also Chromosome::UniformCrossover

◆ MutationRateSchedule

enum panga::GeneticAlgorithm::MutationRateSchedule : uint8_t

strong

Method by which the mutation rate is adjusted over the course of running the genetic algorithm.

See also: SetMutationRateSchedule; GetMutationRateSchedule; GetCurrentMutationRate; SetMutationRate; GetMutationRate

Enumerator
Constant	The mutation rate is constant and does not vary from generation to generation. The rate will always be mutation_rate_. See also mutation_rate_ SetMutationRate GetMutationRate
Deterministic	The mutation rate varies by generation. Early generations introduce a lot of mutation which slowly tapers off to 0 by the last generation. (last generation is controlled by total_generations_) Strictly, when the current generation has passed total_generations_, we will set the current mutation rate to mutation_rate_ instead of 0 because we do not want to stall the evolution. The computed mutation rate has nothing to do with mutation_rate_ unless we have run-past total_generations_. This mutation schedule does a good job of using the mutation operator to search the solution-space of the chromosome. See also total_generations_ mutation_rate_ SetMutationRate GetMutationRate SetTotalGenerations GetTotalGenerations
SelfAdaptive	Attempt to increase mutation when the population converges too much. Uses the population diversity score as a metric. When this diveristy falls below a floor value (self_adaptive_mutation_diversity_floor_), we will introduce more aggressive mutation in order to increase diversity and keep the evolution from converging. The more aggressive mutation rate is configurable via self_adaptive_mutation_aggressive_rate_. When diversity is not below the floor value, we use a constant mutation rate controlled by mutation_rate_. See also mutation_rate_ SetMutationRate GetMutationRate self_adaptive_mutation_diversity_floor_ SetSelfAdaptiveMutationDiversityFloor GetSelfAdaptiveMutationDiversityFloor self_adaptive_mutation_aggressive_rate_ SetSelfAdaptiveMutationAggressiveRate GetSelfAdaptiveMutationAggressiveRate
Proportional	Calculates the mutation rate required to flip a number of bits in the chromosome. The number of bits is controlled by proportional_mutation_bit_count_. See also proportional_mutation_bit_count_ SetProportionalMutationBitCount GetProportionalMutationBitCount

◆ MutatorType

enum panga::GeneticAlgorithm::MutatorType : uint8_t

strong

The type of mutation we will perform on new individuals when they are added to the next generation population.

See also: Mutate; SetMutatorType; GetMutatorType

Enumerator
Flip	Perform the flip mutator. This randomly flips bits in the Individual based on the mutation rate provided. Every bit in the chromosome has a mutation rate chance of flipping. See also Chromosome::FlipMutator

◆ SelectorType

enum panga::GeneticAlgorithm::SelectorType : uint8_t

strong

Algorithm we want to use when we select individuals from the current population to become parents of an offspring in the next generation population.
Actual selection is done by the Population itself.

See also: SetSelectorType; GetSelectorType; SelectParents; SelectOne; Population

Enumerator
Rank	Rank selector. Always returns the fittest individual from a population. When allow_same_parent_couples_ is false, returns the top two individuals when we select a couple from a population. See also Population::RankSelect
Uniform	Uniform selector. Always returns a random individual from a population. See also Population::UniformSelect
RouletteWheel	Roulette wheel selector. Selects an individual with higher fitness more often but has a chance to select any individual in a population. This can be visualized by imagining a roulette wheel where each individual is assigned one slice of the wheel. The size of each slice is determined by the fitness of the individual where more fit individuals are assigned a larger slice. Then the wheel is spun and whichever slice is chosen will cause the associated individual to be selected. See also InitializeSelector Population::RouletteWheelSelect
Tournament	Tournament selector. Chooses n individuals randomly from the population and selects the one with the highest fitness. This tends to select individuals with higher fitness but the tournament size has an effect. If n is 1, tournament selector is identical to uniform selector. If n is the population size, tournament selector is identical to rank selector. You can control n with the tournament_size_ property. See also tournament_size_ SetTournamentSize GetTournamentSize Population::TournamentSelect

Member Function Documentation

◆ Crossover()

void panga::GeneticAlgorithm::Crossover	(	const Individual &	parent1,
		const Individual &	parent2,
		Individual *	offspring
	)

protected

See also: SetCrossoverType; CrossoverType

◆ GetCurrentGeneration()

size_t panga::GeneticAlgorithm::GetCurrentGeneration ( ) const

Return the current generation.
The generation increases after every step.

◆ GetCurrentMutationRate()

double panga::GeneticAlgorithm::GetCurrentMutationRate ( )

protected

Get the mutation rate we should use for the current generation.
Note: May depend on the previous population being evaluated so the value returned may be undefined when called while the initial population is the current population. ie: This rate may only make sense during generations greater than 0.

◆ GetCurrentPopulation()

Population & panga::GeneticAlgorithm::GetCurrentPopulation ( )

protected

We store two populations and alternate between them between generations. In this way, the previous and current generations are always available.
This function will always return the current population.
The current population is the one which is being built, evaluated, and scored during the current generation of the genetic algorithm.

See also: populations_; GetLastGenerationPopulation

◆ GetGenome()

Genome & panga::GeneticAlgorithm::GetGenome ( )

Get the writable genome we will use to construct Individuals which make up the populations of each generation. Note: Don't change the genome while the genetic algorithm is running.

◆ GetLastGenerationPopulation()

Population & panga::GeneticAlgorithm::GetLastGenerationPopulation ( )

protected

We store two populations and alternate between them between generations. In this way, the previous and current generations are always available.
This function will always return the population from the previous generation.
The previous generation population is the one which was built, evaluated, and scored during the previous generation of the genetic algorithm.

See also: populations_; GetCurrentPopulation

◆ GetPopulation()

const Population & panga::GeneticAlgorithm::GetPopulation ( ) const

Get the current genetic algorithm population.

◆ Initialize()

void panga::GeneticAlgorithm::Initialize ( )

Initialize the state of the GeneticAlgorithm.
Initializes missing population members randomly.

See also: SetInitialPopulation

◆ InitializeSelector()

void panga::GeneticAlgorithm::InitializeSelector ( Population * population )

protected

If the selector we're using requires some initialization based on the population, this function will perform that initialization.

◆ Mutate()

void panga::GeneticAlgorithm::Mutate	(	Individual *	individual,
		double	mutation_percentage
	)

protected

Uses the selected mutation operator to mutate |individual| by |mutation_percentage|.

See also: MutatorType; SetMutatorType

◆ Run()

void panga::GeneticAlgorithm::Run ( )

Run the GeneticAlgorithm totalGenerations steps.

◆ SelectOne()

const Individual & panga::GeneticAlgorithm::SelectOne ( const Population & population )

protected

Uses the selector to choose one Individual from |population|.

See also: SelectorType; SetSelectorType

◆ SelectParents()

std::pair< const Individual &, const Individual & > panga::GeneticAlgorithm::SelectParents ( const Population & population )

protected

Uses the selector to choose a pair of individuals from |population|.
Respects the allow_same_parent_couples_ flag to enable/disable choosing the same individual for both parents.

See also: SetAllowSameParentCouples; SelectOne

◆ SetAllowSameParentCouples()

void panga::GeneticAlgorithm::SetAllowSameParentCouples ( bool allow_same_parent_couples )

When we choose parents to use for crossover, should we allow the same Individual to be used as both parents?
This could be useful because crossover returns the same parent if both parents are identical.
If this flag is false, we will not allow the same Individual to be selected as both parents when we select a couple for crossover.
If this flag is true, it is possible that both parents in the couple selected for crossover will be the same Individual. This flag is true by default.

◆ SetCrossoverIgnoreGeneBoundaries()

void panga::GeneticAlgorithm::SetCrossoverIgnoreGeneBoundaries ( bool crossover_ignore_gene_boundaries )

When we perform crossover, should we respect gene boundaries such that all of the bits making up a gene are copied from one parent?
This could be useful if the bits underlying the gene don't make as much sense when they are split up.
If this flag is false, we will respect the boundary of each gene and not split a gene up during crossover.
If this flag is true, we will ignore gene boundaries during crossover and treat the chromosome as a big chunk of binary data which will be split according to the crossover operator chosen.
In general, this flag should be left at the default of true.

◆ SetCrossoverRate()

void panga::GeneticAlgorithm::SetCrossoverRate ( double crossover_rate )

Set the crossover rate.
During each step, construct new individuals for the next generation.
We will select two Individuals and perform crossover to produce the offspring in the next generation with a crossover rate chance.
Instead of crossover, we will copy one Individual from the old population over into the new one with (1 - crossover rate) chance.

◆ SetCrossoverType()

void panga::GeneticAlgorithm::SetCrossoverType ( CrossoverType crossover_type )

Set the crossover type.
We will use this type to crossover two parent individuals in order to produce offspring for the next generation.

See also: CrossoverType

◆ SetEliteCount()

void panga::GeneticAlgorithm::SetEliteCount ( size_t elite_count )

When constructing the next generation, always copy some of the best Individuals from the current generation. These elite Individuals are copied as they are and are not crossed-over or mutated.

Parameters

eliteCount Number of elites.

◆ SetFitnessFunction()

void panga::GeneticAlgorithm::SetFitnessFunction ( FitnessFunction fitness_function )

Set the fitness function used to evaluate the fitness of each Individual.
The fitness function takes a pointer to an Individual and a void* which is the user data previously set via GeneticAlgorithm::SetUserData.

◆ SetInitialPopulation()

void panga::GeneticAlgorithm::SetInitialPopulation ( const std::vector< BitVector > & initial_population )

Initialize the GeneticAlgorithm population based on |initial_population|.
Note: We need to call this before calling Initialize().

Parameters

initial_population We will construct new population members and interpret these values as binary chromosome data.

◆ SetKPointCrossoverPointCount()

void panga::GeneticAlgorithm::SetKPointCrossoverPointCount ( size_t k_point_crossover_point_count )

Set the number of points we'll use to cut up the parent chromosomes during k-point crossover.

◆ SetMutatedEliteCount()

void panga::GeneticAlgorithm::SetMutatedEliteCount ( size_t mutated_elite_count )

Mutated elites are the same as ordinary elite Individuals except they are subjected to the mutation operator according to mutatedEliteMutationRate.

See also: SetMutatedEliteMutationRate

◆ SetMutatedEliteMutationRate()

void panga::GeneticAlgorithm::SetMutatedEliteMutationRate ( double mutated_elite_mutation_rate )

Set the rate at which mutated elite individuals will be mutated.

◆ SetMutationRate()

void panga::GeneticAlgorithm::SetMutationRate ( double mutation_rate )

Set the mutation rate.
After we perform crossover, mutate each offspring Individual by this rate according to the mutation operator.
During execution, the actual mutation rate is calculated based on the mutation rate schedule.

See also: MutatorType; MutationRateSchedule; GetCurrentMutationRate

◆ SetMutationRateSchedule()

void panga::GeneticAlgorithm::SetMutationRateSchedule ( MutationRateSchedule mutation_rate_schedule )

Set the mutation rate schedule we will use to determine the mutation rate over the course of many generations.

See also: MutationRateSchedule

◆ SetMutatorType()

void panga::GeneticAlgorithm::SetMutatorType ( MutatorType mutator_type )

Set the mutator type.
We will use the mutator to mutate each new offspring before adding it to the next generation population.

See also: MutatorType

◆ SetPopulationSize()

void panga::GeneticAlgorithm::SetPopulationSize ( size_t population_size )

Each generation, we will construct and evaluate |population_size| Individuals.

◆ SetProportionalMutationBitCount()

void panga::GeneticAlgorithm::SetProportionalMutationBitCount ( size_t proportional_mutation_bit_count )

Set the number of bits we should attempt to mutate with each mutation operation.

◆ SetSelectorType()

void panga::GeneticAlgorithm::SetSelectorType ( SelectorType selector_type )

Set the selector type.
We will use the selector specified to select two parent individuals on which to perform crossover to produce offspring for the next generation.

See also: SelectorType

◆ SetSelfAdaptiveMutationAggressiveRate()

void panga::GeneticAlgorithm::SetSelfAdaptiveMutationAggressiveRate ( double self_adaptive_mutation_aggressive_rate )

Set the aggressive mutation rate we will switch to when the population diversity falls below the self-adaptive mutation diversity floor.

◆ SetSelfAdaptiveMutationDiversityFloor()

void panga::GeneticAlgorithm::SetSelfAdaptiveMutationDiversityFloor ( double self_adaptive_mutation_diversity_floor )

Set the floor value for the population diversity, below which we will more aggressively mutate the population.

◆ SetTotalGenerations()

void panga::GeneticAlgorithm::SetTotalGenerations ( size_t total_generations )

Set the total number of generations we want to evolve.
If you call Run(), we will execute this many generations.
If you manually call Step(), you can run more than total generations.
This number is used to calculate mutation rate in some mutation rate schedules.

◆ SetTournamentSize()

void panga::GeneticAlgorithm::SetTournamentSize ( size_t tournament_size )

Set the number of Individuals we should include in the tournament when using tournament selector.

◆ SetUserData()

void panga::GeneticAlgorithm::SetUserData ( void * user_data )

Set some data which will be passed into the fitness function called to score each Individual.

◆ Step()

void panga::GeneticAlgorithm::Step ( )

Perform one step of the genetic algorithm:

Use the previous generation population to construct the new current generation population.
- Uses a combination of elitism, crossover, and mutation to construct the new population.
- Individuals are chosen from the previous population based on their fitness scores.
Score the current population of individuals.
- This will either be the initial population (if current generation is 0) or the population we constructed during the previous step operation.
- The score operation will leave the population sorted.
Advance the current generation.

The documentation for this class was generated from the following files:

src/GeneticAlgorithm.h
src/GeneticAlgorithm.cc

Public Types

Public Member Functions

Protected Member Functions

Member Enumeration Documentation

◆ CrossoverType

◆ MutationRateSchedule

◆ MutatorType

◆ SelectorType

Member Function Documentation

◆ Crossover()

◆ GetCurrentGeneration()

◆ GetCurrentMutationRate()

◆ GetCurrentPopulation()

◆ GetGenome()

◆ GetLastGenerationPopulation()

◆ GetPopulation()

◆ Initialize()

◆ InitializeSelector()

◆ Mutate()

◆ Run()

◆ SelectOne()

◆ SelectParents()

◆ SetAllowSameParentCouples()

◆ SetCrossoverIgnoreGeneBoundaries()

◆ SetCrossoverRate()

◆ SetCrossoverType()

◆ SetEliteCount()

◆ SetFitnessFunction()

◆ SetInitialPopulation()

◆ SetKPointCrossoverPointCount()

◆ SetMutatedEliteCount()

◆ SetMutatedEliteMutationRate()

◆ SetMutationRate()

◆ SetMutationRateSchedule()

◆ SetMutatorType()

◆ SetPopulationSize()

◆ SetProportionalMutationBitCount()

◆ SetSelectorType()

◆ SetSelfAdaptiveMutationAggressiveRate()

◆ SetSelfAdaptiveMutationDiversityFloor()

◆ SetTotalGenerations()

◆ SetTournamentSize()

◆ SetUserData()

◆ Step()