#include <evolution_strategy.h>

Inheritance diagram for ultra::alps_es< E >:

Public Member Functions
	alps_es (const problem &, E &)
template<LayeredPopulation P>
auto	operations (P &, typename P::layer_iter, const evolution_status< individual_t, fitness_t > &) const
template<LayeredPopulation P>
void	init (P &) const
template<LayeredPopulation P>
auto *	refinement_subgroup (P &) const noexcept
template<LayeredPopulation P>
void	after_generation (P &, const summary< individual_t, fitness_t > &)
template<LayeredPopulation P>
std::size_t	max_parallelism (const P &) const noexcept
template<LayeredPopulation P>
auto	operations (P &pop, typename P::layer_iter iter, const evolution_status< individual_t, fitness_t > &starting_status) const
template<LayeredPopulation P>
void	init (P &pop) const
template<LayeredPopulation P>
auto *	refinement_subgroup (P &pop) const noexcept
template<LayeredPopulation P>
std::size_t	max_parallelism (const P &) const noexcept
template<LayeredPopulation P>
void	after_generation (P &pop, const summary< individual_t, fitness_t > &sum)
Public Member Functions inherited from ultra::evolution_strategy< E >
template<Population P>
void	init (P &) const
template<Population P>
P *	refinement_subgroup (P &) const noexcept
template<Population P>
void	after_generation (P &, const summary< individual_t, fitness_t > &)
const problem &	get_problem () const noexcept
template<Population P>
std::size_t	max_parallelism (const P &) const noexcept
template<LayeredPopulation P>
bool	valid_layer (P &pop, typename P::layer_iter iter)
template<Population P>
P *	refinement_subgroup (P &pop) const noexcept
template<Population P>
std::size_t	max_parallelism (const P &pop) const noexcept
template<Population P>
void	after_generation (P &pop, const summary< individual_t, fitness_t > &sum)

Static Public Member Functions
static parameters	shape (parameters)
Static Public Member Functions inherited from ultra::evolution_strategy< E >
static parameters	shape (const parameters &p)

Additional Inherited Members
Public Types inherited from ultra::evolution_strategy< E >
using	evaluator_type = E
using	fitness_t = evaluator_fitness_t<E>
using	individual_t = evaluator_individual_t<E>
Protected Member Functions inherited from ultra::evolution_strategy< E >
	evolution_strategy (const problem &, E &)
Static Protected Member Functions inherited from ultra::evolution_strategy< E >
template<LayeredPopulation P>
static bool	valid_layer (P &, typename P::layer_iter)
Protected Attributes inherited from ultra::evolution_strategy< E >
E &	eva_
const problem &	prob_

Detailed Description

template<Evaluator E>
class ultra::alps_es< E >

Basic ALPS strategy.

With ALPS, several instances of a search algorithm are run in parallel, each in its own age-layer, and the age of solutions is kept track of. The key properties of ALPS are:

each age-layer has its own sub-population of one or more candidate solutions (individuals);
each age-layer has a maximum age and it may not contain individuals older than that maximum age;
the age of individuals is based on when the original genetic material was created from random;
the search algorithm in a given age-layer can look at individuals in its own sub-population and at the sub-populations in younger age layers but it can only replace individuals in its own population;
at regular intervals, the search algorithm in the first age-layer is restarted.

Age is a measure of how long an individual's family of genotypic material has been in the population. Randomly generated individuals, such as those that are created when the search algorithm are started, start with an age of 0. Each generation that an individual stays in the population its age is increased by one. Individuals that are created through mutation or recombination take the age of their oldest parent and add one to it. This differs from conventional measures of age, in which individuals created through applying some type of variation to an existing individual (e.g. mutation or recombination) start with an age of 0.

The search algorithm in a given layer acts somewhat independently of the others, with an exception being that it can use individuals from both its layer and the layer below to generated new candidate solutions. Also, each age layer has an upper limit on the age of solutions it can contain. When an individual is too old for its current layer, it cannot be used to generate new individuals for that layer and eventually is removed from that layer. Optionally, an attempt can be made to move this individual up to the next layer – in which case it replaces some individual there that it's better than. Finally, at regular intervals the bottom layer is replaced with a new sub-population of randomly generated individuals, each with an age of 0.

See also: https://github.com/ghornby/alps

Constructor & Destructor Documentation

◆ alps_es()

template<Evaluator E>

alps_es::alps_es	(	const problem &	prob,
		E &	eva )

Constructs an ALPS evolution strategy.

Parameters

[in]	prob	the optimisation problem
[in]	eva	the evaluator used to assess individuals

Initialises ALPS-specific operators:

age-layered selection;
recombination;
age-aware replacement.

Member Function Documentation

◆ after_generation() [1/2]

template<Evaluator E>

template<LayeredPopulation P>

void ultra::alps_es< E >::after_generation	(	P &	pop,
		const summary< individual_t, fitness_t > &	sum )

Performs ALPS-specific post-generation updates.

Parameters

[in,out]	pop	the population after evolution
[in]	sum	summary statistics of the current generation

Responsibilities include:

incrementing individual ages;
merging equivalent layers;
shrinking converged layers;
restoring layer sizes when diversity returns;
adding new layers at age gaps;
moving individuals up when maximum layer count is reached.

Remarks: Structural changes occur only at generation boundaries.

◆ after_generation() [2/2]

template<Evaluator E>

template<LayeredPopulation P>

void ultra::alps_es< E >::after_generation	(	P &	pop,
		const summary< individual_t, fitness_t > &	sum )

Performs ALPS-specific post-generation updates.

Parameters

[in,out]	pop	the population after evolution
[in]	sum	summary statistics of the current generation

Responsibilities include:

incrementing individual ages;
merging equivalent layers;
shrinking converged layers;
restoring layer sizes when diversity returns;
adding new layers at age gaps;
moving individuals up when maximum layer count is reached.

Remarks: Structural changes occur only at generation boundaries.

◆ init() [1/2]

template<Evaluator E>

template<LayeredPopulation P>

void ultra::alps_es< E >::init ( P & pop ) const

Initialises individual ages for ALPS.

Parameters

[in,out] pop the population to initialise

Sets the initial age of all individuals in the population according to ALPS rules.

◆ init() [2/2]

template<Evaluator E>

template<LayeredPopulation P>

void ultra::alps_es< E >::init ( P & pop ) const

Initialises individual ages for ALPS.

Parameters

[in,out] pop the population to initialise

Sets the initial age of all individuals in the population according to ALPS rules.

◆ max_parallelism() [1/2]

template<Evaluator E>

template<LayeredPopulation P>

std::size_t ultra::alps_es< E >::max_parallelism ( const P & ) const

nodiscardnoexcept

Returns the maximum useful parallelism for ALPS.

Returns: maximum number of worker threads useful for ALPS

ALPS can add or remove layers at generation boundaries. Therefore the initial number of layers is not a stable upper bound for the whole run. Returning the hardware concurrency lets the evolution driver keep enough workers available for layers introduced later during evolution.

◆ max_parallelism() [2/2]

template<Evaluator E>

template<LayeredPopulation P>

std::size_t ultra::alps_es< E >::max_parallelism ( const P & ) const

noexcept

Returns the maximum useful parallelism for ALPS.

Returns: maximum number of worker threads useful for ALPS

ALPS can add or remove layers at generation boundaries. Therefore the initial number of layers is not a stable upper bound for the whole run. Returning the hardware concurrency lets the evolution driver keep enough workers available for layers introduced later during evolution.

◆ operations() [1/2]

template<Evaluator E>

template<LayeredPopulation P>

auto ultra::alps_es< E >::operations	(	P &	pop,
		typename P::layer_iter	iter,
		const evolution_status< individual_t, fitness_t > &	starting_status ) const

nodiscard

Assembles one ALPS evolutionary step.

Template Parameters

P	population type

Parameters

[in]	pop	a population. Operations are performed on sub-populations of pop
[in]	iter	iterator to the active age layer
[in]	starting_status	evolutionary status snapshot

Returns: a callable performing one ALPS evolutionary step

Builds a callable object encapsulating one iteration of the ALPS evolutionary process for a specific layer.

The returned callable performs:

selection from the current layer and all younger layers;
offspring generation via recombination;
replacement restricted to the current layer.

Note: Executing the callable mutates the population.

◆ operations() [2/2]

template<Evaluator E>

template<LayeredPopulation P>

auto ultra::alps_es< E >::operations	(	P &	pop,
		typename P::layer_iter	iter,
		const evolution_status< individual_t, fitness_t > &	starting_status ) const

Assembles one ALPS evolutionary step.

Template Parameters

P	population type

Parameters

[in]	pop	a population. Operations are performed on sub-populations of pop
[in]	iter	iterator to the active age layer
[in]	starting_status	evolutionary status snapshot

Returns: a callable performing one ALPS evolutionary step

Builds a callable object encapsulating one iteration of the ALPS evolutionary process for a specific layer.

The returned callable performs:

selection from the current layer and all younger layers;
offspring generation via recombination;
replacement restricted to the current layer.

Note: Executing the callable mutates the population.

◆ refinement_subgroup() [1/2]

template<Evaluator E>

template<LayeredPopulation P>

auto * ultra::alps_es< E >::refinement_subgroup ( P & pop ) const

nodiscardnoexcept

Returns the ALPS layer eligible for refinement.

Parameters

[in,out] pop layered population managed by ALPS

Returns: pointer to the last layer, or nullptr when refinement should be skipped

Refinement is deliberately disabled while the population has fewer than three layers. In that phase ALPS is still dominated by young layers, whose main purpose is exploration and periodic injection of fresh genetic material.

◆ refinement_subgroup() [2/2]

template<Evaluator E>

template<LayeredPopulation P>

auto * ultra::alps_es< E >::refinement_subgroup ( P & pop ) const

noexcept

Returns the ALPS layer eligible for refinement.

Parameters

[in,out] pop layered population managed by ALPS

Returns: pointer to the last layer, or nullptr when refinement should be skipped

Refinement is deliberately disabled while the population has fewer than three layers. In that phase ALPS is still dominated by young layers, whose main purpose is exploration and periodic injection of fresh genetic material.

◆ shape()

template<Evaluator E>

parameters alps_es::shape ( parameters params )

staticnodiscard

Returns strategy defaults derived from an initialised parameter profile.

Parameters

[out] params generic evolution parameters

Returns: parameters adjusted for ALPS

Transforms a fully initialised default profile into strategy-specific defaults.

Remarks: This function builds a default profile for the strategy. It does not merge those defaults with user constraints; search::tune_parameters() performs that merge.

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

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ alps_es()

Member Function Documentation

◆ after_generation() [1/2]

◆ after_generation() [2/2]

◆ init() [1/2]

◆ init() [2/2]

◆ max_parallelism() [1/2]

◆ max_parallelism() [2/2]

◆ operations() [1/2]

◆ operations() [2/2]

◆ refinement_subgroup() [1/2]

◆ refinement_subgroup() [2/2]

◆ shape()