leap_ec.multiobjective package

Submodules

leap_ec.multiobjective.asynchronous module

leap_ec.multiobjective.nsga2 module

Implementation of Non-dominated sorted genetic algorithm II (NSGA-II).

  • Deb, Kalyanmoy, Amrit Pratap, Sameer Agarwal, and T. A. M. T. Meyarivan. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

leap_ec.multiobjective.nsga2.generalized_nsga_2(max_generations: int, pop_size: int, problem: ~leap_ec.multiobjective.problems.MultiObjectiveProblem, representation, pipeline, rank_func=<function rank_ordinal_sort>, stop=<function <lambda>>, init_evaluate=<bound method Individual.evaluate_population of <class 'leap_ec.individual.Individual'>>, start_generation: int = 0, context={'leap': {'distrib': {'non_viable': 0}}})

NSGA-II multi-objective evolutionary algorithm.

  • Deb, Kalyanmoy, Amrit Pratap, Sameer Agarwal, and T. A. M. T. Meyarivan.

    “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

  • Bogdan Burlacu. 2022. Rank-based Non-dominated Sorting. arXiv.

    DOI:https://doi.org/10.48550/ARXIV.2203.13654

This classic algorithm relies on the idea of “non-dominated sorting” and de-crowding to evolve a diverse Pareto front. The “generalized” NSGA-II we implement here differs slightly from the canonical algorithm, in that we default to a faster sorting algorithm devised by Burlacu (2022).

If you wish the algorithm to use the original NSGA-II behavior instead (which runs much slower), you can select the original operator by passing in rank_func=fast_nondominated_sort.

>>> from leap_ec.representation import Representation
>>> from leap_ec.ops import random_selection, clone, evaluate, pool
>>> from leap_ec.real_rep.initializers import create_real_vector
>>> from leap_ec.real_rep.ops import mutate_gaussian
>>> from leap_ec.multiobjective.nsga2 import generalized_nsga_2
>>> from leap_ec.multiobjective.problems import SCHProblem
>>> pop_size = 10
>>> max_generations = 5
>>> final_pop = generalized_nsga_2(
...     max_generations=max_generations, pop_size=pop_size,
...
...     problem=SCHProblem(),
...
...     representation=Representation(
...         initialize=create_real_vector(bounds=[(-10, 10)])
...     ),
...
...     pipeline=[
...         random_selection,
...         clone,
...         mutate_gaussian(std=0.5, expected_num_mutations=1),
...         evaluate,
...         pool(size=pop_size),
...     ]
... )

[Individual(…), Individual(…), Individual(…), … Individual(…)]

Note

You will need a selection as first operator in pipeline. This will use Deb’s multiobjective criteria for comparing individuals as dictated in MultiobjectiveProblem.

Parameters
  • max_generations (int) – The max number of generations to run the algorithm for. Can pass in float(‘Inf’) to run forever or until the stop condition is reached.

  • pop_size (int) – Size of the initial population

  • rank_func – the function used to calculate non-domination rankings for the individuals of the population.

  • stop (int) – A function that accepts a population and returns True iff it’s time to stop evolving.

  • problem (Problem) – the Problem that should be used to evaluate individuals’ fitness

  • representation – How the problem is represented in individuals

  • pipeline (list) – a list of operators that are applied (in order) to create the offspring population at each generation

  • init_evaluate – a function used to evaluate the initial population, before the main pipeline is run. The default of Individual.evaluate_population is suitable for many cases, but you may wish to pass a different operator in for distributed evaluation or other purposes.

  • start_generation – index of the first generation to count from (defaults to 0). You might want to change this, for example, in experiments that involve stopping and restarting an algorithm.

Returns

a list of the final population

leap_ec.multiobjective.ops module

LEAP pipeline operators for multiobjective optimization.

For now this just implements NSGA-II, but other multiobjective approaches will eventually be included.

leap_ec.multiobjective.ops.crowding_distance_calc(population: list = '__no__default__') list

This implements the NSGA-II crowding-distance-assignment()

Note that this assumes that all the individuals have had their ranks computed since we do crowding distance calculations within ranks.

  • Deb, Kalyanmoy, Amrit Pratap, Sameer Agarwal, and T. A. M. T. Meyarivan. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

Parameters

population – population to calculate crowding distances

Returns

individuals with crowding distance calculated

leap_ec.multiobjective.ops.fast_nondominated_sort(population: list = '__no__default__', parents: list = None) list

This implements the NSGA-II fast-non-dominated-sort()

This is really binning the population by ranks. In any case, the returned population will have an attribute, rank, that will denote the corresponding rank in which it is a member.

  • Deb, Kalyanmoy, Amrit Pratap, Sameer Agarwal, and T. A. M. T. Meyarivan. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

Parameters
  • population – population to be ranked

  • parents – optional parents population to be included with the ranking process

Returns

individuals binned by ranks

leap_ec.multiobjective.ops.per_rank_crowding_calc(ranked_population: list, is_maximizing) list

Calculate crowding distance within rank :param ranked_population: A population of entirely one rank :returns: population with crowding distance calculate for one rank

leap_ec.multiobjective.ops.rank_ordinal_sort(population: list = '__no__default__', parents: list = None) list

This implements Rank Ordinal Sort from Rank-based Non-dominated Sorting

Produces identical rank values to fast_nondominated_sort from the original NSGA-II implementation, however performs much faster.

  • Bogdan Burlacu. 2022. Rank-based Non-dominated Sorting. arXiv. DOI:https://doi.org/10.48550/ARXIV.2203.13654

Parameters
  • population – population to be ranked

  • parents – optional parents population to be included with the ranking process

Returns

individuals binned by ranks

leap_ec.multiobjective.ops.sort_by_dominance(population: list = '__no__default__') list

Sort population by rank and distance

This presumes that fast_nondominated_sort() and crowding_distance_calc have been used on all individuals in population.

Parameters

population – to be sorted

Returns

sorted population

leap_ec.multiobjective.probe module

leap_ec.multiobjective.problems module

LEAP Problem classes for multiobjective optimization.

class leap_ec.multiobjective.problems.MultiObjectiveProblem(maximize: Sequence[bool])

Bases: Problem

A problem that compares individuals based on Pareto dominance.

Inherit from this class and implement the evaluate() method to implement an objective function that returns a list of real-value fitness values.

In Pareto-dominance, an individual A is only considered “better than” an individual B if A is unambiguously better than B: i.e. it is at least as good as B on all objectives, and it is strictly better than B on at least one objective.

(Source code, png, hires.png, pdf)

_images/leap_ec-multiobjective-1.png
equivalent(first_fitnesses, second_fitnesses)

Return true if first_fitness and second_fitness are mutually Pareto non-dominating.

\[a \not \succ b \text{ and } b \not \succ a\]
Parameters
  • first_fitnesses – a np array of real-valued fitnesses for an individual, where each element corresponds to a single objective

  • second_fitnesses – same as first_fitnesses, but for a different individual

worse_than(first_fitnesses, second_fitnesses)

Return true if first_fitnesses is Pareto-dominated by second_fitnesses.

In the case of maximization over all objectives, a solution \(b\) dominates \(a\), written \(b \succ a\), if and only if

\[\begin{split}\begin{array}{ll} f_i(b) \ge f_i(a) & \forall i, \text{ and} \\ f_i(b) > f_j(a) & \text{ for some } j. \end{array}\end{split}\]

Here we may maximize over some objectives, and minimize over others, depending on the values in the self.maximize list.

Parameters
  • first_fitnesses – a np array of real-valued fitnesses for an individual, where each element corresponds to a single objective

  • second_fitnesses – same as first_fitnesses, but for a different individual

class leap_ec.multiobjective.problems.SCHProblem

Bases: MultiObjectiveProblem

SCH problem from Deb et al’s benchmarks

This expects a numpy scalar (zero dimensional) for a phenome.

\[\begin{split}\begin{align} f_1(x) &= x^2 \\ f_2(x) &= (x-2)^2 \\ -10^3 \le x &\le 10^3 \end{align}\end{split}\]
  • Deb, Kalyanmoy, Amrit Pratap, Sameer Agarwal, and T. A. M. T. Meyarivan. “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.” IEEE transactions on evolutionary computation 6, no. 2 (2002): 182-197.

evaluate(phenome)
Parameters

phenome – argument for objective functions

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDT1Problem(n=30, check_phenome=True)

Bases: ZDTBenchmarkProblem

The first problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. It’s meant to provide a simple multi-objective problem with a convex Pareto-optimal front.

\[\begin{split}\begin{align} f_1(x_1) &= x_1 \\ g(x_2, \ldots, x_n) &= 1 + 9\cdot {\sum_{i=2}^n x_i} / (n - 1) \\ h(f_1, g) &= 1 - \sqrt{f_1/g}\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_i &\in [0,1] \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 30\) dimensions in the solution space.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – contains x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDT2Problem(n=30, check_phenome=True)

Bases: ZDTBenchmarkProblem

The second problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. This is similar to leap_ec.problem.ZDT1Problem, except that it has a non-convex Pareto front.

\[\begin{split}\begin{align} f_1(x_1) &= x_1 \\ g(x_2, \ldots, x_n) &= 1 + 9\cdot {\sum_{i=2}^n x_i} / (n - 1) \\ h(f_1, g) &= 1 - (f_1/g)^2\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_i &\in [0,1] \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 30\) dimensions in the solution space.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – contains x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDT3Problem(n=10, check_phenome=True)

Bases: ZDTBenchmarkProblem

The third problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. This function differs from leap_ec.problem.ZDT1Problem and leap_ec.problem.ZDT1Problem in that the pareto-optimal front has discontinuity.

\[\begin{split}\begin{align} f_1(x_1) &= x_1 \\ g(x_2, \ldots, x_n) &= 1 + 9\cdot {\sum_{i=2}^n x_i} / (n - 1) \\ h(f_1, g) &= 1 - \sqrt{f_1/g} - (f_1/g)\sin(10\pi f_1)\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_i &\in [0,1] \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 10\) dimensions in the solution space.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – contains x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDT4Problem(n=30, check_phenome=True)

Bases: ZDTBenchmarkProblem

The fourth problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. ZDT4 contains 21^9 local pareto-optimal front for the default parameters, allowing it to test for the EA’s ability to handle multimodality.

\[\begin{split}\begin{align} f_1(x_1) &= x_1 \\ g(x_2, \ldots, x_n) &= 1 + 10(n-1) + \sum_{i=2}^n (x_i^2 - 10\cos(4\pi x_i)) \\ h(f_1, g) &= 1 - \sqrt{f_1/g}\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_1 &\in [0,1] \quad x_2, \ldots, x_n \in [-5,5] \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 30\) dimensions in the solution space.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – contains x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDT5Problem(n=11, check_phenome=True)

Bases: ZDTBenchmarkProblem

The fifth problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. In contrast to the other ZDT problems, ZDT5 takes a binary string as input.

Unlike the other ZDT problems, ZDT5Problem additionally provides a phenome_length property, denoting the length of the flattened binary sequence x. This property is intended to ease the creation of binary sequence phenomes for input into the problem.

\[\begin{split}\begin{align} u(x_i) &= \textrm{unitation}(x_i)\\ v(u(x_i)) &= \left\{ \begin{array}{lc} 2+u(x_i) & if u(x_i) < 5 \\ 1 & if u(x_i) = 5 \\ \end{array} \right\}\\ \\\\ f_1(x_1) &= 1 + u(x_1) \\ g(x_2, \ldots, x_n) &= \sum_{i=2}^n v(u(x_i)) \\ h(f_1, g) &= 1 / f_1\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_1 &\in \{0,1\}^30 \quad x_2, \ldots, x_n \in \{0,1\}^5 \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 11\) dimensions in the solution space. This translates to a flattened binary sequence of \(|phenome_x| = 80\).

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – the flattened binary sequence x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

property phenome_length
Returns

the length of the flattened binary sequence x

class leap_ec.multiobjective.problems.ZDT6Problem(n=10, check_phenome=True)

Bases: ZDTBenchmarkProblem

The sixth problem from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite. This function exhibits a nonuniformly distributed pareto front, as well as a lower density of solutions nearer to the pareto front.

\[\begin{split}\begin{align} f_1(x_1) &= 1-\textrm{exp}(-4x_1)\sin^6(6\pi x_1) \\ g(x_2, \ldots, x_n) &= 1 + 9\cdot (({\sum_{i=2}^n x_i}) / (n - 1))^{0.25} \\ h(f_1, g) &= 1 - (f_1/g)^2\\ f_2(x) &= g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \\\\ x_i &\in [0,1] \end{align}\end{split}\]

Traditionally the problem is used with \(|x| = 10\) dimensions in the solution space.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

property bounds
Returns

the bounds of the phenome

evaluate(phenome)
Parameters

phenome – contains x

Returns

two fitnesses, one for \(f_1(x)\) and \(f_2(x)\)

class leap_ec.multiobjective.problems.ZDTBenchmarkProblem(n, check_phenome=True)

Bases: MultiObjectiveProblem

The base class for problems from the classic Zitzler, Deb, and Thiele (ZDT) benchmark suite.

Each problem is of the form:

\[\begin{split}\begin{align} \textrm{Minimize} \quad& \mathcal{T}(x) &=&\quad (f_1(x_1), f_2(x)) \\ \textrm{subject to} \quad& f_2(x) &=&\quad g(x_2, \ldots, x_n)h(f_1(x_1), g(x_2, \ldots, x_n))\\ \textrm{where} \quad& x &=&\quad (x_1,\ldots,x_m)\\ \end{align}\end{split}\]

For reliability when testing, each problem has been provided with a check_phenome parameter to ensure that phenomes match the expected form and bounds of the problem.

  • Zitzler, Eckart, Kalyanmoy Deb, and Lothar Thiele. “Comparison of multiobjective evolutionary algorithms: Empirical results.” Evolutionary computation 8.2 (2000): 173-195.

abstract property bounds
Returns

the bounds of the phenome

Module contents