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)
- 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
andleap_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