anatomy
This document is a work in progress.
Abstract: this paper presents an extended specification for the Ultra evolutionary framework. Architectural choices will be detailed and their conceptual significance underlined. Implementation details will be discussed.
Ultra implements an object-oriented layered architecture, built on the base of five classes:
-
basic_searchandevolution; -
problem; -
layered_population; -
parameters.
The goal of a layered architecture is to neatly divide base concepts, such as the internal structure of individuals, from higher level concepts, more directly relating to the evolutionary method.
This is the skeleton of a program using the Ultra framework:
ultra::basic_search<a_given_evolutionary_strategy> s(a_problem_instance, a_fitness_function);
s.run();The basic_search class allows the selection of the evolutionary strategy to be used during evolution and offers a similar interface for all type of searches. Often, users can take up the ultra::search, the instantiation of ultra::basic_search, which provides a good, general evolutionary strategy:
ultra::search s(a_problem_instance, a_fitness_function);
s.run();There are various specializations of the ultra::basic_search for different tasks (de::search for Differential Evolution, ga::search for Genetic Algorithms and src::search for Symbolic Regression and Classification).
Whatever the search class, it uses ultra::problem to access the parameters and constraints of the problem to be tackled.
Being an evolutionary framework, Ultra performs its work with the help of the ultra::evolution and ultra::population classes.
Fitness is a scalar/vector value assigned to an individual which reflects how well the individual solves the task.
In the literature there are (at least) four measures of fitness:
- raw fitness
- standardized fitness
- adjusted fitness
- normalized fitness
but we are mostly interested in the first two.
The raw fitness is the measurement of fitness that is stated in the natural terminology of the problem itself, so the better value may be either smaller or larger.
For example in an optimal control problem, one may be trying to minimize some cost measure, so a lesser value of raw fitness is better.
Because raw fitness is so loosely-defined, what is calculated and used in Ultra is the standardized fitness. The only requirement for standardized fitness is that bigger values represent better individuals (this may differ in other frameworks).
Many of the fitness functions available in Ultra (see class src::evaluator and the many specializations) define the optimal fitness as scalar value 0 / vector (0, ... 0) and use negative values for sub-optimal solutions but this is not mandatory.
Often, excluding the simplest cases, fitness alone is not enough to understand goodness and flaws of the candidate solution.
The default population is organized in multiple subgroups or layers. In the picture, each subgroup is represented as a torus to mark the fact that many evolutionary strategies may use a Trivial Geography scheme, where individuals are viewed as having a 1-dimensional spatial structure, essentially a circle, considering the first and last locations to be adjacent. The production of an individual for location i is permitted to involve only parents from i's local neighborhood.
This is not fixed and can be turned off by setting the parameter parameters::population::mate_zone to a large enough value. Each layer is implemented in the linear_population class.
The global population is implemented in the layered_population class. The first and the last layer are highlighted in different colors because some algorithms handle them in a specific manner. Notably, the ALPS algorithm segregates individuals based on their ages:
- the first layer contains the youngest individuals;
- upper layers contain progressively older individuals;
- the last layer contains the oldest individual (without an age limit).
In contrast, the standard evolutionary strategy treats each layer in the same way.
Regardless of the evolutionary strategy, layers or subgroups are evolved in parallel. Possible interactions among layers depend on the strategy. For example, using the standard evolutionary strategy and the differential evolutionary strategy, there is no direct interaction; with ALPS the i-th layer may sometimes access the i-1-th layer for selection / recombination and upper layers for replacement.
The linear_population class contains a mutex ([[nodiscard]] auto &mutex() const) that the user must use to coordinate accesses in a multi-threaded environment.
