Multi-objective algorithms

Multi-objective algorithms#

namespace algorithm

Single- and multi-objective algorithms that can be used in the GAs.

class NSGA2#

#include <algorithm/nsga2.hpp>
class NSGA2 : public gapp::algorithm::Algorithm#

Non-dominated sorting genetic algorithm (NSGA-II), used for multi-objective optimization. This algorithm doesn’t work for single-objective problems.

The aim of the algorithm is to find a set of solutions which are well spread out along the entire pareto-front in the objective-space.

The algorithm uses a non-dominated sorting method to sort the candidates of the population into distinct pareto fronts, and then selects the candidates of the best fronts for the population of the next generation. Candidates that belong to the same front are ranked according to their crowding distances, which are their distances from the neigbouring solutions in the objective space.

The algorithm uses a selection operator that selects solutions for the crossovers based on these same criteria (their pareto ranks and crowding distances).

The algorithm assumes fitness maximization, and has no parameters.

See also

Deb, K., et al. “A fast and elitist multiobjective genetic algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

class NSGA3#

#include <algorithm/nsga3.hpp>
class NSGA3 : public gapp::algorithm::Algorithm#

NSGA-III algorithm, used for multi- and many-objective optimization. This algorithm doesn’t work for single-objective problems.

The aim of the algorithm is to find a set of solutions which are well spread out along the entire pareto-front in the objective-space.

The algorithm uses a non-dominated sorting method to sort the solutions into a set of distinct pareto fronts, and then selects the candidates of the best fronts for the population of the next generation. Candidates that belong to the same front are ranked using a set of reference directions in the objective space. The candidate solutions closest to a reference directions which has less candidates associated with it, and candidates closer to reference directions are considered better.

The algorithm uses a selection operator that selects candidates for the crossovers based on these same criteria (their pareto ranks and their distances from the reference directions).

The reference directions are generated at the start of the run, and don’t change throughout it. The method used for generating the reference directions can be specified in the constructor.

The algorithm assumes fitness maximization, and it has no parameters.

See also

Deb, K., and Jain, H. “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, no. 4 (2013): 577-601.

Public Types

using RefLineGenerator = std::function<FitnessMatrix(size_t, size_t)>#

The type of the reference line generator function.

Public Functions

NSGA3(RefLineGenerator gen = reflines::quasirandomSimplexPointsMirror)#

Create an NSGA-III algorithm.

Parameters:

gen – The method to use for generating the reference lines for the algorithm.

struct Impl#
struct CandidateInfo#

Reference line generation methods#

namespace reflines#

Methods for generating reference lines for the NSGA3 algorithm. 

#include <algorithm/reference_lines.hpp>
FitnessMatrix gapp::algorithm::reflines::quasirandomSimplexPointsMirror(
size_t dim,
size_t num_points,
)#

Generates a set of points on the unit simplex by mapping a set of quasirandom points generated in a unit hypercube onto the unit simplex.

Parameters:

  • dim – The dimension of the generated points.

  • num_points – The number of points to generate.

Returns:

The generated simplex points.

FitnessMatrix gapp::algorithm::reflines::quasirandomSimplexPointsSort(
size_t dim,
size_t num_points,
)#

Generates a set of points on the unit simplex by mapping a set of quasirandom points generated in a unit hypercube onto the unit simplex.

Parameters:

  • dim – The dimension of the generated points.

  • num_points – The number of points to generate.

Returns:

The generated simplex points.

FitnessMatrix gapp::algorithm::reflines::quasirandomSimplexPointsRoot(
size_t dim,
size_t num_points,
)#

Generates a set of points on the unit simplex by mapping a set of quasirandom points generated in a unit hypercube onto the unit simplex.

Parameters:

  • dim – The dimension of the generated points.

  • num_points – The number of points to generate.

Returns:

The generated simplex points.

FitnessMatrix gapp::algorithm::reflines::quasirandomSimplexPointsLog(
size_t dim,
size_t num_points,
)#

Generates a set of points on the unit simplex by mapping a set of quasirandom points generated in a unit hypercube onto the unit simplex.

Parameters:

  • dim – The dimension of the generated points.

  • num_points – The number of points to generate.

Returns:

The generated simplex points.

FitnessMatrix gapp::algorithm::reflines::pickSparseSubset(
size_t dim,
size_t num_points,
RefLineGenerator generator,
Positive<size_t> k,
)#

Generate a set of reference points by picking a subset of the points generated by another simplex point generator function.

Parameters:

  • dim – The dimension of the generated points.

  • num_points – The number of points to generate.

  • generator – The simplex point generator function used for creating the initial set of points.

  • k – The multiple of num_points to use for the size of the initial point set generated using the given generator function.

Returns:

The generated simplex points.