Nondominated sorting genetic algorithm III (NSGA-III)

Nondominated sorting genetic algorithm III (NSGA-III)#

class nsga3#

Nondominated Sorting genetic algorithm III (NSGA-III).

NSGA-III is a many-objective evolutionary algorithm. It keeps the non-dominated sorting of NSGA-II but replaces the crowding distance, whose ability to discriminate degrades quickly as the number of objectives grows, with a set of structured reference directions. At every generation the objectives are adaptively normalized, each individual is associated with the reference direction whose ray it lies closest to, and the individuals which fill the least crowded directions are preferred. Diversity is therefore maintained explicitly rather than as a by-product of a density estimate, which is what allows the algorithm to scale to a large number of objectives.

The version implemented in pagmo can be applied to box-bounded, unconstrained, deterministic multiple-objective optimization. Like nsga2 it also deals with integer chromosomes, treating the last nix entries of the decision vector as integers.

Reference directions. The directions are placed on the unit simplex by the systematic approach of Das and Dennis: with divisions divisions along each objective, an \(M\)-objective problem receives \(H = \binom{M + p - 1}{p}\) directions. That count grows quickly with \(M\), so Deb and Jain add a second, inner layer for many-objective problems: a Das and Dennis layer built with divisions_inner divisions whose every coordinate is then mapped through

\[ c \rightarrow \frac{c + 1/M}{2}, \]
which shrinks it by one half about the centroid of the simplex while keeping it on that simplex. Setting divisions_inner to zero uses the outer layer alone. The two layers are concatenated deterministically, outer first, and a direction of the inner layer coinciding with one already present is dropped. The settings of Table I of the original paper are reproduced by:

Objectives

divisions

divisions_inner

Directions

Population

3

12

0

91

92

5

6

0

210

212

8

3

2

156

156

10

3

2

275

276

15

2

1

135

136

A configuration whose direction count is too large to be built is rejected before anything is allocated, rather than exhausting memory: eight objectives with divisions set to 8, for instance, would already need 5040 directions, which is the situation the inner layer exists to avoid.

Population requirements. The population size must be at least 5, as for nsga2, and it must be at least as large as the number of reference directions. Equality is explicitly permitted: the eight-objective row of Table I above uses a population of exactly 156 for 156 directions.

Memory. Section IV-C of the original paper takes the ideal point over the selected sets of every generation so far, and builds the normalizing hyperplane from the extreme points ever found since the start of the run, while Algorithm 2 is written in terms of the current generation alone. Both behaviours are available: with use_memory set to true the ideal point and the extreme points are retained across generations, and with it left false they are recomputed from scratch every generation. The retained extreme points are stored in the original objective coordinates, so that they remain meaningful as the ideal point moves.

Deviations from Deb and Jain. The following are deliberate and are the only ones:

  • Mating selection is selectable through random_mating. The default, true, is the behaviour of the original paper, whose Section IV-F states that no explicit selection operator is used and that parents are picked at random. Setting it to false instead holds the binary tournament on non-domination rank and crowding distance which is the pagmo convention established by nsga2; that is a materially different mechanism and is not what the paper describes. The tournament can help noticeably on multimodal problems, where the absence of any selection pressure at mating slows convergence: on DTLZ1 with three objectives it reached a p-distance below 0.08 across four seeds, against up to 1.08 for the random pairing. On the unimodal DTLZ2 the two are indistinguishable.

  • use_memory defaults to false, which follows Algorithm 2 literally rather than the running quantities of Section IV-C.

  • The default mutation probability is a constant, whereas Table II of the paper recommends \(1/n\) for a chromosome of length \(n\); that value depends on the problem and so cannot be a default. Passing it explicitly is advisable.

This implementation is based on the work of Paul Slavin in pagmo2 pull request #569.

See: Deb, K., & Jain, H. (2014). An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation, 18(4), 577-601. https://doi.org/10.1109/TEVC.2013.2281535

Public Types

typedef std::tuple<unsigned, unsigned long long, vector_double> log_line_type#

Single entry of the log (gen, fevals, ideal_point).

typedef std::vector<log_line_type> log_type#

The log.

Public Functions

nsga3(unsigned gen = 1u, double cr = 1.0, double eta_c = 30.0, double mut = 0.10, double eta_mut = 20.0, std::size_t divisions = 12u, std::size_t divisions_inner = 0u, bool random_mating = true, unsigned seed = pagmo::random_device::next(), bool use_memory = false)#

Constructor.

Constructs the NSGA-III user defined algorithm. The defaults for the genetic operators are those of Table II of Deb and Jain, and the default reference direction set is the single layer with 12 divisions of their Table I, which gives 91 directions for a three-objective problem.

Parameters:

  • gen – number of generations to evolve.

  • cr – crossover probability.

  • eta_c – distribution index for crossover.

  • mut – mutation probability.

  • eta_mut – distribution index for mutation.

  • divisions – number of divisions of the outer layer of reference directions along each objective.

  • divisions_inner – number of divisions of the inner layer of reference directions; zero disables the inner layer.

  • random_mating – if true, mating parents are picked at random as in Section IV-F of the original paper; if false, they are picked by binary tournament on non-domination rank and crowding distance, as in nsga2.

  • seed – seed used by the internal random number generator (default is random).

  • use_memory – if true, the ideal point and the extreme points are retained across generations, as described in Section IV-C of the original paper.

Throws:

std::invalid_argument – if cr or mut is not finite or not in \([0,1]\), if eta_c or eta_mut is not finite or not in \([1,100]\), if divisions is zero, or if divisions_inner exceeds divisions.

population evolve(population) const#

Algorithm evolve method.

Evolves the population for the requested number of generations.

Parameters:

pop – population to be evolved

Throws:

  • std::invalid_argument – if the problem is stochastic, constrained, single objective or has equal lower and upper bounds; if the population size is smaller than 5 or is smaller than the number of reference directions; or if a configured batch fitness evaluator returns a fitness vector of unexpected size.

  • unspecified – any exception thrown by the reference direction construction, in particular if the requested number of directions is too large to be built.

Returns:

evolved population

inline void set_seed(unsigned seed)#

Sets the seed.

Parameters:

seed – the seed controlling the algorithm stochastic behaviour

inline unsigned get_seed() const#

Gets the seed.

Returns:

the seed controlling the algorithm stochastic behaviour

inline void set_verbosity(unsigned level)#

Sets the algorithm verbosity.

Sets the verbosity level of the screen output and of the log returned by get_log(). level can be:

  • 0: no verbosity

  • >0: will print and log one line each level generations.

Example (verbosity 1): 

Gen:        Fevals:        ideal1:        ideal2:        ideal3:
  1              0       0.113086       0.153994      0.0682423
  2             92       0.113086       0.153994      0.0682423
  3            184      0.0866138       0.107934      0.0682423
  4            276      0.0866138      0.0917604      0.0682423
  5            368      0.0361252      0.0917604      0.0577711
Gen is the generation number, Fevals the number of function evaluations used. The ideal point of the current population follows, cropped to its 5th component.

Parameters:

level – verbosity level

inline unsigned get_verbosity() const#

Gets the verbosity level.

Returns:

the verbosity level

void set_bfe(const bfe &b)#

Sets the batch function evaluation scheme.

Parameters:

b – batch function evaluation object

inline std::string get_name() const#

Algorithm name.

Returns the name of the algorithm.

Returns:

std::string containing the algorithm name

std::string get_extra_info() const#

Extra info.

Returns extra information on the algorithm.

Returns:

an std::string containing extra info on the algorithm

inline const log_type &get_log() const#

Get log.

A log containing relevant quantities monitoring the last call to evolve. Each element of the returned std::vector is a nsga3::log_line_type containing: Gen, Fevals, ideal_point as described in nsga3::set_verbosity

Returns:

an std::vector of nsga3::log_line_type containing the logged values Gen, Fevals, ideal_point