Skip to content

Algorithms

Full class reference for every algorithm and variant. For a runnable example per algorithm, see the Multi-objective and Single-objective pages in the User Guide.

Multi-objective

gde3

hype

HYPE(problem, reference_point, population_size, offspring_population_size, mutation, crossover, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: GeneticAlgorithm[S, R]

This is an implementation of the Hypervolume Estimation Algorithm for Multi-objective Optimization proposed in:

  • J. Bader and E. Zitzler. HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. TIK Report 286, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, November 2008.

It uses the Exact Hypervolume-based indicator formulation, which once computed, guides both the environmental selection and the binary tournament selection operator

Please note that as per the publication above, the evaluator and replacement should not be changed anyhow. It also requires that Problem() has a reference_point with objective values defined, e.g.

problem = ZDT1() reference_point = FloatSolution(problem.number_of_variables,problem.number_of_objectives, [0], [1]) reference_point.objectives = [1., 1.]

Source code in src/jmetal/algorithm/multiobjective/hype.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def __init__(
    self,
    problem: Problem,
    reference_point: Solution,
    population_size: int,
    offspring_population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    """This is an implementation of the Hypervolume Estimation Algorithm for Multi-objective Optimization
    proposed in:

    * J. Bader and E. Zitzler. HypE: An Algorithm for Fast Hypervolume-Based Many-Objective
    Optimization. TIK Report 286, Computer Engineering and Networks Laboratory (TIK), ETH
    Zurich, November 2008.

    It uses the Exact Hypervolume-based indicator formulation, which once computed, guides both
    the environmental selection and the binary tournament selection operator

    Please note that as per the publication above, the evaluator and replacement should not be changed
    anyhow. It also requires that Problem() has a reference_point with objective values defined, e.g.

    problem = ZDT1()
    reference_point = FloatSolution(problem.number_of_variables,problem.number_of_objectives, [0], [1])
    reference_point.objectives = [1., 1.]
    """

    selection = BinaryTournamentSelection(
        comparator=SolutionAttributeComparator(key="fitness", lowest_is_best=False)
    )
    self.ranking_fitness = RankingAndFitnessSelection(
        population_size,
        dominance_comparator=dominance_comparator,
        reference_point=reference_point,
    )
    self.reference_point = reference_point
    self.dominance_comparator = dominance_comparator

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=offspring_population_size,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )

ibea

IBEA(problem, population_size, offspring_population_size, mutation, crossover, kappa, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), rng=None)

Bases: GeneticAlgorithm[S, R]

Epsilon IBEA implementation as described in

  • Zitzler, Eckart, and Simon Künzli. "Indicator-based selection in multiobjective search." In International Conference on Parallel Problem Solving from Nature, pp. 832-842. Springer, Berlin, Heidelberg, 2004.

https://link.springer.com/chapter/10.1007/978-3-540-30217-9_84

IBEA is a genetic algorithm (GA), i.e. it belongs to the evolutionary algorithms (EAs) family. The multi-objective search in IBEA is guided by a fitness associated to every solution, which is in turn controlled by a binary quality indicator. This implementation uses the so-called additive epsilon indicator, along with a binary tournament mating selector.

:param problem: The problem to solve. :param population_size: Size of the population. :param mutation: Mutation operator (see 🇵🇾mod:jmetal.operator.mutation). :param crossover: Crossover operator (see 🇵🇾mod:jmetal.operator.crossover). :param kappa: Weight in the fitness computation.

Source code in src/jmetal/algorithm/multiobjective/ibea.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def __init__(
    self,
    problem: Problem,
    population_size: int,
    offspring_population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    kappa: float,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    rng: np.random.Generator | None = None,
):
    """Epsilon IBEA implementation as described in

    * Zitzler, Eckart, and Simon Künzli. "Indicator-based selection in multiobjective search."
    In International Conference on Parallel Problem Solving from Nature, pp. 832-842. Springer,
    Berlin, Heidelberg, 2004.

    https://link.springer.com/chapter/10.1007/978-3-540-30217-9_84

    IBEA is a genetic algorithm (GA), i.e. it belongs to the evolutionary algorithms (EAs)
    family. The multi-objective search in IBEA is guided by a fitness associated to every solution,
    which is in turn controlled by a binary quality indicator. This implementation uses the so-called
    additive epsilon indicator, along with a binary tournament mating selector.

    :param problem: The problem to solve.
    :param population_size: Size of the population.
    :param mutation: Mutation operator (see :py:mod:`jmetal.operator.mutation`).
    :param crossover: Crossover operator (see :py:mod:`jmetal.operator.crossover`).
    :param kappa: Weight in the fitness computation.
    """

    selection = BinaryTournamentSelection(
        comparator=SolutionAttributeComparator(key="fitness", lowest_is_best=False)
    )
    self.kappa = kappa

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=offspring_population_size,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )

mocell

R = TypeVar('R') module-attribute

.. module:: MOCell :platform: Unix, Windows :synopsis: MOCell (Multi-Objective Cellular evolutionary algorithm) implementation .. moduleauthor:: Antonio J. Nebro antonio@lcc.uma.es

MOCell(problem, population_size, neighborhood, archive, mutation, crossover, selection=None, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: GeneticAlgorithm[S, R]

MOCEll implementation as described in:

:param problem: The problem to solve. :param population_size: Size of the population. :param mutation: Mutation operator (see 🇵🇾mod:jmetal.operator.mutation). :param crossover: Crossover operator (see 🇵🇾mod:jmetal.operator.crossover). :param selection: Selection operator (see 🇵🇾mod:jmetal.operator.selection).

Source code in src/jmetal/algorithm/multiobjective/mocell.py 
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def __init__(
    self,
    problem: Problem,
    population_size: int,
    neighborhood: Neighborhood,
    archive: BoundedArchive,
    mutation: Mutation,
    crossover: Crossover,
    selection: Selection | None = None,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    """
    MOCEll implementation as described in:

    :param problem: The problem to solve.
    :param population_size: Size of the population.
    :param mutation: Mutation operator (see :py:mod:`jmetal.operator.mutation`).
    :param crossover: Crossover operator (see :py:mod:`jmetal.operator.crossover`).
    :param selection: Selection operator (see :py:mod:`jmetal.operator.selection`).
    """
    if selection is None:
        selection = BinaryTournamentSelection(
            MultiComparator(
                [
                    FastNonDominatedRanking.get_comparator(),
                    CrowdingDistanceDensityEstimator.get_comparator(),
                ]
            )
        )

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=1,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )
    self.dominance_comparator = dominance_comparator
    self.neighborhood = neighborhood
    self.archive = archive
    self.current_individual = 0
    self.current_neighbors: list[S] = []

    self.comparator = MultiComparator(
        [
            FastNonDominatedRanking.get_comparator(),
            CrowdingDistanceDensityEstimator.get_comparator(),
        ]
    )

moead

MOEAD(problem, population_size, mutation, crossover, aggregation_function, neighbourhood_selection_probability, max_number_of_replaced_solutions, neighbor_size, weight_files_path, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), rng=None)

Bases: GeneticAlgorithm

:param max_number_of_replaced_solutions: (eta in Zhang & Li paper). :param neighbourhood_selection_probability: Probability of mating with a solution in the neighborhood rather than the entire population (Delta in Zhang & Li paper).

Source code in src/jmetal/algorithm/multiobjective/moead.py 
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
def __init__(
    self,
    problem: Problem,
    population_size: int,
    mutation: Mutation,
    crossover: DifferentialEvolutionCrossover,
    aggregation_function: AggregationFunction,
    neighbourhood_selection_probability: float,
    max_number_of_replaced_solutions: int,
    neighbor_size: int,
    weight_files_path: str,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    rng: np.random.Generator | None = None,
):
    """
    :param max_number_of_replaced_solutions: (eta in Zhang & Li paper).
    :param neighbourhood_selection_probability: Probability of mating with a solution in the neighborhood rather
           than the entire population (Delta in Zhang & Li paper).
    """
    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=1,
        mutation=mutation,
        crossover=crossover,
        selection=NaryRandomSolutionSelection(2),
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        termination_criterion=termination_criterion,
        rng=rng,
    )
    self.max_number_of_replaced_solutions = max_number_of_replaced_solutions
    self.fitness_function = aggregation_function
    self.neighbourhood = WeightVectorNeighborhood(
        number_of_weight_vectors=population_size,
        neighborhood_size=neighbor_size,
        weight_vector_size=problem.number_of_objectives(),
        weights_path=weight_files_path,
    )
    self.neighbourhood_selection_probability = neighbourhood_selection_probability
    self.permutation = None
    self.current_subproblem = 0
    self.neighbor_type = None

MOEADIEpsilon(problem, population_size, mutation, crossover, aggregation_function, neighbourhood_selection_probability, max_number_of_replaced_solutions, neighbor_size, weight_files_path, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), rng=None)

Bases: MOEAD

:param max_number_of_replaced_solutions: (eta in Zhang & Li paper). :param neighbourhood_selection_probability: Probability of mating with a solution in the neighborhood rather than the entire population (Delta in Zhang & Li paper).

Source code in src/jmetal/algorithm/multiobjective/moead.py 
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
def __init__(
    self,
    problem: Problem,
    population_size: int,
    mutation: Mutation,
    crossover: DifferentialEvolutionCrossover,
    aggregation_function: AggregationFunction,
    neighbourhood_selection_probability: float,
    max_number_of_replaced_solutions: int,
    neighbor_size: int,
    weight_files_path: str,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    rng: np.random.Generator | None = None,
):
    """
    :param max_number_of_replaced_solutions: (eta in Zhang & Li paper).
    :param neighbourhood_selection_probability: Probability of mating with a solution in the neighborhood rather
           than the entire population (Delta in Zhang & Li paper).
    """
    if termination_criterion is None:
        termination_criterion = StoppingByEvaluations(300000)

    super().__init__(
        problem=problem,
        population_size=population_size,
        mutation=mutation,
        crossover=crossover,
        aggregation_function=aggregation_function,
        neighbourhood_selection_probability=neighbourhood_selection_probability,
        max_number_of_replaced_solutions=max_number_of_replaced_solutions,
        neighbor_size=neighbor_size,
        weight_files_path=weight_files_path,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        termination_criterion=termination_criterion,
        rng=rng,
    )
    self.constraints: list[float] = []
    self.epsilon_k = 0
    self.phi_max = -1e30
    self.epsilon_zero = 0
    self.tc = 800
    self.tao = 0.05
    self.rk = 0
    self.generation_counter = 0
    self.archive: list[Solution] = []

nsgaii

R = TypeVar('R') module-attribute

.. module:: NSGA-II :platform: Unix, Windows :synopsis: NSGA-II (Non-dominance Sorting Genetic Algorithm II) implementation.

.. moduleauthor:: Antonio J. Nebro antonio@lcc.uma.es, Antonio Benítez-Hidalgo antonio.b@uma.es

NSGAII(problem, population_size, offspring_population_size, mutation, crossover, selection=None, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: GeneticAlgorithm[S, R]

NSGA-II implementation as described in

  • K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," in IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, Apr 2002. doi: 10.1109/4235.996017

NSGA-II is a genetic algorithm (GA), i.e. it belongs to the evolutionary algorithms (EAs) family. The implementation of NSGA-II provided in jMetalPy follows the evolutionary algorithm template described in the algorithm module (🇵🇾mod:jmetal.core.algorithm).

.. note:: A steady-state version of this algorithm can be run by setting the offspring size to 1.

:param problem: The problem to solve. :param population_size: Size of the population. :param mutation: Mutation operator (see 🇵🇾mod:jmetal.operator.mutation). :param crossover: Crossover operator (see 🇵🇾mod:jmetal.operator.crossover).

Source code in src/jmetal/algorithm/multiobjective/nsgaii.py 
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def __init__(
    self,
    problem: Problem,
    population_size: int,
    offspring_population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    selection: Selection | None = None,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    """
    NSGA-II implementation as described in

    * K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, "A fast and elitist
      multiobjective genetic algorithm: NSGA-II," in IEEE Transactions on Evolutionary Computation,
      vol. 6, no. 2, pp. 182-197, Apr 2002. doi: 10.1109/4235.996017

    NSGA-II is a genetic algorithm (GA), i.e. it belongs to the evolutionary algorithms (EAs)
    family. The implementation of NSGA-II provided in jMetalPy follows the evolutionary
    algorithm template described in the algorithm module (:py:mod:`jmetal.core.algorithm`).

    .. note:: A steady-state version of this algorithm can be run by setting the offspring size to 1.

    :param problem: The problem to solve.
    :param population_size: Size of the population.
    :param mutation: Mutation operator (see :py:mod:`jmetal.operator.mutation`).
    :param crossover: Crossover operator (see :py:mod:`jmetal.operator.crossover`).
    """
    if selection is None:
        selection = BinaryTournamentSelection(
            MultiComparator(
                [
                    FastNonDominatedRanking.get_comparator(),
                    CrowdingDistanceDensityEstimator.get_comparator(),
                ]
            )
        )

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=offspring_population_size,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )
    self.dominance_comparator = dominance_comparator

replacement(population, offspring_population)

This method joins the current and offspring populations to produce the population of the next generation by applying the ranking and crowding distance selection.

:param population: Parent population. :param offspring_population: Offspring population. :return: New population after ranking and crowding distance selection is applied.

Source code in src/jmetal/algorithm/multiobjective/nsgaii.py 
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
def replacement(self, population: list[S], offspring_population: list[S]) -> list[list[S]]:
    """This method joins the current and offspring populations to produce the population of the next generation
    by applying the ranking and crowding distance selection.

    :param population: Parent population.
    :param offspring_population: Offspring population.
    :return: New population after ranking and crowding distance selection is applied.
    """
    ranking: FastNonDominatedRanking[S] = FastNonDominatedRanking(self.dominance_comparator)
    density_estimator: CrowdingDistanceDensityEstimator[S] = CrowdingDistanceDensityEstimator()

    r = RankingAndDensityEstimatorReplacement(
        ranking, density_estimator, RemovalPolicyType.ONE_SHOT
    )
    solutions = r.replace(population, offspring_population)

    return solutions

DistributedNSGAII(problem, population_size, mutation, crossover, number_of_cores, client, selection=None, termination_criterion=None, dominance_comparator=DominanceComparator(), rng=None)

Bases: Algorithm[S, R]

Source code in src/jmetal/algorithm/multiobjective/nsgaii.py 
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
def __init__(
    self,
    problem: Problem,
    population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    number_of_cores: int,
    client,
    selection: Selection | None = None,
    termination_criterion: TerminationCriterion | None = None,
    dominance_comparator: DominanceComparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    if selection is None:
        selection = BinaryTournamentSelection(
            MultiComparator(
                [
                    FastNonDominatedRanking.get_comparator(),
                    CrowdingDistanceDensityEstimator.get_comparator(),
                ]
            )
        )
    if termination_criterion is None:
        termination_criterion = StoppingByEvaluations(max_evaluations=25000)

    super().__init__()
    self.problem = problem
    self.population_size = population_size
    self.mutation_operator = mutation
    self.crossover_operator = crossover
    self.selection_operator = selection
    self.dominance_comparator = dominance_comparator

    self.termination_criterion = termination_criterion
    self.observable.register(termination_criterion)

    self.number_of_cores = number_of_cores
    self.client = client

    self.rng = rng
    thread_rng_into_operators(
        self.rng, self.selection_operator, self.crossover_operator, self.mutation_operator
    )

run()

Execute the algorithm.

Source code in src/jmetal/algorithm/multiobjective/nsgaii.py 
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
def run(self):
    """Execute the algorithm."""
    self.start_computing_time = time.time()

    create_solution = dask.delayed(self.problem.create_solution)
    evaluate_solution = dask.delayed(self.problem.evaluate)

    task_pool = as_completed([], with_results=True)

    for _ in range(self.number_of_cores):
        new_solution = create_solution()
        new_evaluated_solution = evaluate_solution(new_solution)
        future = self.client.compute(new_evaluated_solution)

        task_pool.add(future)

    batches = task_pool.batches()

    auxiliar_population: list[S] = []
    while len(auxiliar_population) < self.population_size:
        batch = next(batches)
        for _, received_solution in batch:
            auxiliar_population.append(received_solution)

            if len(auxiliar_population) < self.population_size:
                break

        # submit as many new tasks as we collected
        for _ in batch:
            new_solution = create_solution()
            new_evaluated_solution = evaluate_solution(new_solution)
            future = self.client.compute(new_evaluated_solution)

            task_pool.add(future)

    self.init_progress()

    # perform an algorithm step to create a new solution to be evaluated
    while not self.stopping_condition_is_met():
        batch = next(batches)

        for _, received_solution in batch:
            offspring_population = [received_solution]

            # replacement
            ranking: FastNonDominatedRanking[S] = FastNonDominatedRanking(
                self.dominance_comparator
            )
            density_estimator: CrowdingDistanceDensityEstimator[S] = (
                CrowdingDistanceDensityEstimator()
            )

            r = RankingAndDensityEstimatorReplacement(
                ranking, density_estimator, RemovalPolicyType.ONE_SHOT
            )
            auxiliar_population = r.replace(auxiliar_population, offspring_population)

            # selection
            mating_population = []
            for _ in range(2):
                solution = self.selection_operator.execute(auxiliar_population)
                mating_population.append(solution)

            # Reproduction and evaluation
            new_task = self.client.submit(
                reproduction,
                mating_population,
                self.problem,
                self.crossover_operator,
                self.mutation_operator,
            )
            task_pool.add(new_task)

            # update progress
            self.evaluations += 1
            self.solutions = auxiliar_population

            self.update_progress()

            if self.stopping_condition_is_met():
                break

    self.total_computing_time = time.time() - self.start_computing_time

    # at this point, computation is done
    for future, _ in task_pool:
        future.cancel()

nsgaiii

R = TypeVar('R') module-attribute

.. module:: NSGA-III :platform: Unix, Windows :synopsis: NSGA-III (Non-dominance Sorting Genetic Algorithm III) implementation.

.. moduleauthor:: Antonio Benítez-Hidalgo antonio.b@uma.es, Julian Blank blankjul@egr.msu.edu

NSGAIII(reference_directions, problem, mutation, crossover, population_size=None, selection=None, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: NSGAII

Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
def __init__(
    self,
    reference_directions,
    problem: Problem,
    mutation: Mutation,
    crossover: Crossover,
    population_size: int = None,
    selection: Selection | None = None,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    self.reference_directions = reference_directions.compute()

    if not population_size:
        population_size = len(self.reference_directions)
    if self.reference_directions.shape[1] != problem.number_of_objectives():
        raise Exception(
            "Dimensionality of reference points must be equal to the number of objectives"
        )

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=population_size,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        dominance_comparator=dominance_comparator,
        rng=rng,
    )

    self.extreme_points = None
    self.ideal_point = np.full(self.problem.number_of_objectives(), np.inf)
    self.worst_point = np.full(self.problem.number_of_objectives(), -np.inf)

replacement(population, offspring_population)

Implements NSGA-III environmental selection based on reference points as described in:

  • 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. doi:10.1109/TEVC.2013.2281535.
Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
def replacement(self, population: list[S], offspring_population: list[S]) -> list[S]:
    """Implements NSGA-III environmental selection based on reference points as described in:

    * 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. doi:10.1109/TEVC.2013.2281535.
    """
    F = np.array([s.objectives for s in population])

    # find or usually update the new ideal point - from feasible solutions
    # note that we are assuming minimization here!
    self.ideal_point = np.min(np.vstack((self.ideal_point, F)), axis=0)
    self.worst_point = np.max(np.vstack((self.worst_point, F)), axis=0)

    # calculate the fronts of the population
    ranking: FastNonDominatedRanking = FastNonDominatedRanking(self.dominance_comparator)
    ranking.compute_ranking(population + offspring_population, k=self.population_size)

    fronts, non_dominated = ranking.ranked_sublists, ranking.get_subfront(0)

    # find the extreme points for normalization
    self.extreme_points = get_extreme_points(
        F=np.array([s.objectives for s in non_dominated]),
        n_objs=self.problem.number_of_objectives(),
        ideal_point=self.ideal_point,
        extreme_points=self.extreme_points,
    )

    # find the intercepts for normalization and do backup if gaussian elimination fails
    worst_of_population = np.max(F, axis=0)
    worst_of_front = np.max(np.array([s.objectives for s in non_dominated]), axis=0)

    nadir_point = get_nadir_point(
        extreme_points=self.extreme_points,
        ideal_point=self.ideal_point,
        worst_point=self.worst_point,
        worst_of_population=worst_of_population,
        worst_of_front=worst_of_front,
    )

    #  consider only the population until we come to the splitting front
    pop: np.ndarray = np.concatenate(ranking.ranked_sublists)
    F = np.array([s.objectives for s in pop])

    # update the front indices for the current population
    counter = 0
    for i in range(len(fronts)):
        for j in range(len(fronts[i])):
            fronts[i][j] = counter
            counter += 1
    last_front = np.array(fronts[-1])

    # associate individuals to niches
    niche_of_individuals, dist_to_niche = associate_to_niches(
        F=F,
        niches=self.reference_directions,
        ideal_point=self.ideal_point,
        nadir_point=nadir_point,
    )

    # if we need to select individuals to survive
    if len(pop) > self.population_size:
        # if there is only one front
        if len(fronts) == 1:
            until_last_front = np.array([], dtype=int)
            niche_count = np.zeros(len(self.reference_directions), dtype=int)
            n_remaining = self.population_size
        # if some individuals already survived
        else:
            until_last_front = np.concatenate(fronts[:-1])
            niche_count = compute_niche_count(
                len(self.reference_directions), niche_of_individuals[until_last_front]
            )
            n_remaining = self.population_size - len(until_last_front)

        S_idx = niching(
            pop=pop[last_front],
            n_remaining=n_remaining,
            niche_count=niche_count,
            niche_of_individuals=niche_of_individuals[last_front],
            dist_to_niche=dist_to_niche[last_front],
            rng=self.rng,
        )

        survivors_idx = np.concatenate((until_last_front, last_front[S_idx].tolist()))
        pop = pop[survivors_idx]

    return list(pop)

result()

Return only non dominated solutions.

Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
383
384
385
386
387
388
def result(self):
    """Return only non dominated solutions."""
    ranking: FastNonDominatedRanking = FastNonDominatedRanking(self.dominance_comparator)
    ranking.compute_ranking(self.solutions, k=self.population_size)

    return ranking.get_subfront(0)

get_extreme_points(F, n_objs, ideal_point, extreme_points=None)

Calculate the Achievement Scalarization Function which is used for the extreme point decomposition.

Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
def get_extreme_points(F, n_objs, ideal_point, extreme_points=None):
    """Calculate the Achievement Scalarization Function which is used for the extreme point decomposition."""
    asf = np.eye(n_objs)
    asf[asf == 0] = 1e6

    # add the old extreme points to never loose them for normalization
    _F = F
    if extreme_points is not None:
        _F = np.concatenate([extreme_points, _F], axis=0)

    # use __F because we substitute small values to be 0
    __F = _F - ideal_point
    __F[__F < 1e-3] = 0

    # update the extreme points for the normalization having the highest asf value each
    F_asf = np.max(__F * asf[:, None, :], axis=2)
    idx = np.argmin(F_asf, axis=1)
    extreme_points = _F[idx, :]

    return extreme_points

get_nadir_point(extreme_points, ideal_point, worst_point, worst_of_front, worst_of_population)

Calculate the axis intersects for a set of individuals and its extremes (construct hyperplane).

Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
def get_nadir_point(extreme_points, ideal_point, worst_point, worst_of_front, worst_of_population):
    """Calculate the axis intersects for a set of individuals and its extremes (construct hyperplane)."""
    try:
        # find the intercepts using gaussian elimination
        M = extreme_points - ideal_point
        b = np.ones(extreme_points.shape[1])
        plane = np.linalg.solve(M, b)
        intercepts = 1 / plane

        nadir_point = ideal_point + intercepts

        if (
            not np.allclose(np.dot(M, plane), b)
            or np.any(intercepts <= 1e-6)
            or np.any(nadir_point > worst_point)
        ):
            raise LinAlgError()
    except LinAlgError:
        nadir_point = worst_of_front

    b = nadir_point - ideal_point <= 1e-6
    nadir_point[b] = worst_of_population[b]

    return nadir_point

associate_to_niches(F, niches, ideal_point, nadir_point, utopian_epsilon=0.0)

Associate each solution to a reference point.

Source code in src/jmetal/algorithm/multiobjective/nsgaiii.py 
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
def associate_to_niches(F, niches, ideal_point, nadir_point, utopian_epsilon: float = 0.0):
    """Associate each solution to a reference point."""
    utopian_point = ideal_point - utopian_epsilon

    denom = nadir_point - utopian_point
    denom[denom == 0] = 1e-12

    # normalize by ideal point and intercepts
    N = (F - utopian_point) / denom

    def compute_perpendicular_distance(N, ref_dirs):
        u = np.tile(ref_dirs, (len(N), 1))
        v = np.repeat(N, len(ref_dirs), axis=0)

        norm_u = np.linalg.norm(u, axis=1)

        scalar_proj = np.sum(v * u, axis=1) / norm_u
        proj = scalar_proj[:, None] * u / norm_u[:, None]
        val = np.linalg.norm(proj - v, axis=1)
        matrix = np.reshape(val, (len(N), len(ref_dirs)))

        return matrix

    dist_matrix = compute_perpendicular_distance(N, niches)

    niche_of_individuals = np.argmin(dist_matrix, axis=1)
    dist_to_niche = dist_matrix[np.arange(F.shape[0]), niche_of_individuals]

    return niche_of_individuals, dist_to_niche

omopso

R = TypeVar('R') module-attribute

.. module:: OMOPSO :platform: Unix, Windows :synopsis: Implementation of SMPSO.

.. moduleauthor:: Antonio J. Nebro antonio@lcc.uma.es

OMOPSO(problem, swarm_size, uniform_mutation, non_uniform_mutation, leaders, epsilon, termination_criterion, swarm_generator=RandomGenerator(), swarm_evaluator=SequentialEvaluator(), rng=None)

Bases: ParticleSwarmOptimization

This class implements the OMOPSO algorithm as described in

todo Update this reference * SMPSO: A new PSO-based metaheuristic for multi-objective optimization

The implementation of OMOPSO provided in jMetalPy follows the algorithm template described in the algorithm templates section of the documentation.

:param problem: The problem to solve. :param swarm_size: Size of the swarm. :param leaders: Archive for leaders.

Source code in src/jmetal/algorithm/multiobjective/omopso.py 
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def __init__(
    self,
    problem: FloatProblem,
    swarm_size: int,
    uniform_mutation: UniformMutation,
    non_uniform_mutation: NonUniformMutation,
    leaders: BoundedArchive | None,
    epsilon: float,
    termination_criterion: TerminationCriterion,
    swarm_generator: Generator = RandomGenerator(),
    swarm_evaluator: Evaluator = SequentialEvaluator(),
    rng: numpy.random.Generator | None = None,
):
    """This class implements the OMOPSO algorithm as described in

    todo Update this reference
    * SMPSO: A new PSO-based metaheuristic for multi-objective optimization

    The implementation of OMOPSO provided in jMetalPy follows the algorithm template described in the algorithm
    templates section of the documentation.

    :param problem: The problem to solve.
    :param swarm_size: Size of the swarm.
    :param leaders: Archive for leaders.
    """
    super().__init__(problem=problem, swarm_size=swarm_size)
    self.swarm_generator = swarm_generator
    self.swarm_evaluator = swarm_evaluator

    self.termination_criterion = termination_criterion
    self.observable.register(termination_criterion)

    self.uniform_mutation = uniform_mutation
    self.non_uniform_mutation = non_uniform_mutation

    self.rng = rng
    thread_rng_into_operators(self.rng, self.uniform_mutation, self.non_uniform_mutation)

    self.leaders = leaders

    self.epsilon = epsilon
    self.epsilon_archive: NonDominatedSolutionsArchive[FloatSolution] = (
        NonDominatedSolutionsArchive(EpsilonDominanceComparator(epsilon))
    )

    self.c1_min = 1.5
    self.c1_max = 2.0
    self.c2_min = 1.5
    self.c2_max = 2.0
    self.r1_min = 0.0
    self.r1_max = 1.0
    self.r2_min = 0.0
    self.r2_max = 1.0
    self.weight_min = 0.1
    self.weight_max = 0.5
    self.change_velocity1 = -1
    self.change_velocity2 = -1

    self.dominance_comparator = DominanceComparator()

    self.speed = numpy.zeros((self.swarm_size, self.problem.number_of_variables()), dtype=float)

R = TypeVar('R') module-attribute

.. module:: RamdomSearch :platform: Unix, Windows :synopsis: Simple random_search search algorithms.

.. moduleauthor:: Antonio J. Nebro antonio@lcc.uma.es

smsemoa

R = TypeVar('R') module-attribute

.. module:: SMSEMOA :platform: Unix, Windows :synopsis: SMSEMOA (S-Metric Selection Evolutionary Multiobjective Algorithm) implementation.

.. moduleauthor:: Antonio J. Nebro ajnebro@uma.es

SMSEMOA(problem, population_size, mutation, crossover, selection=None, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: GeneticAlgorithm[S, R]

SMSEMOA implementation (template based on NSGA-II).

Source code in src/jmetal/algorithm/multiobjective/smsemoa.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def __init__(
    self,
    problem: Problem,
    population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    selection: Selection | None = None,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    """
    SMSEMOA implementation (template based on NSGA-II).
    """
    if selection is None:
        selection = RandomSelection()
    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=1,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )
    self.dominance_comparator = dominance_comparator

replacement(population, offspring_population)

SMS-EMOA replacement strategy.

Implements replacement according to SMS-EMOA algorithm: 1. Merge current population with offspring 2. Compute non-dominated ranking 3. Fill new population by fronts 4. In the last front, remove solution with smallest HV contribution

Parameters:

Name Type Description Default
population list[S]

Current population

 required
offspring_population list[S]

Offspring population (typically 1 solution)

 required

Returns:

Type Description
list[S]

New population of size self.population_size
Source code in src/jmetal/algorithm/multiobjective/smsemoa.py 
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
def replacement(self, population: list[S], offspring_population: list[S]) -> list[S]:
    """
    SMS-EMOA replacement strategy.

    Implements replacement according to SMS-EMOA algorithm:
    1. Merge current population with offspring
    2. Compute non-dominated ranking
    3. Fill new population by fronts
    4. In the last front, remove solution with smallest HV contribution

    Args:
        population: Current population
        offspring_population: Offspring population (typically 1 solution)

    Returns:
        New population of size self.population_size
    """
    # Merge populations
    merged_population = population + offspring_population

    # Compute non-dominated ranking
    ranking: FastNonDominatedRanking[S] = FastNonDominatedRanking(self.dominance_comparator)
    ranking.compute_ranking(merged_population)

    num_subfronts = ranking.get_number_of_subfronts()

    # Collect all subfronts except the last
    result_population: list[S] = []
    for i in range(num_subfronts - 1):
        result_population.extend(ranking.get_subfront(i))

    # Get the last subfront
    last_subfront = ranking.get_subfront(num_subfronts - 1)

    # If the entire last subfront fits, add it and return
    if len(result_population) + len(last_subfront) <= self.population_size:
        result_population.extend(last_subfront)
        return result_population

    # Otherwise, we need to truncate the last subfront using HV contribution
    # Calculate reference point in objective space (not normalized)
    # Use worst values from merged population
    objectives_array = np.array([s.objectives for s in merged_population])

    # Reference point should be worse than all solutions
    # For minimization: use maximum values + offset
    offset = 1.0  # Offset to ensure reference point is dominated by all solutions
    reference_point = np.max(objectives_array, axis=0) + offset

    # Compute HV contribution directly on last subfront (without normalization)
    hv_estimator: HypervolumeContributionDensityEstimator[S] = (
        HypervolumeContributionDensityEstimator(reference_point=reference_point.tolist())
    )
    hv_estimator.compute_density_estimator(last_subfront)

    # Sort by HV contribution (descending: largest contributions first)
    sorted_last_subfront = sorted(
        last_subfront, key=lambda s: s.attributes["hv_contribution"], reverse=True
    )

    # Add all but one from the last subfront (remove the worst)
    result_population.extend(sorted_last_subfront[: len(last_subfront) - 1])

    return result_population

spea2

R = TypeVar('R') module-attribute

.. module:: SPEA2 :platform: Unix, Windows :synopsis: SPEA2 implementation. Note that we do not follow the structure of the original SPEA2 code. We consider SPEA2 as a genetic algorithm with binary tournament selection, with a comparator based on the strength fitness and the KNN distance, and a sequential replacement strategy based in iteratively (sequentially) removing the worst solution of the population + offspring population. The worst solutions is selected again considering the strength fitness and KNN distance. Note that the implementation is exactly the same of NSGA-II, but using the fast nondominated sorting and the crowding distance density estimator, and the replacement follows a one-shot scheme (once the solutions are ordered, the best ones are selected without recomputing the ranking and density estimator).

.. moduleauthor:: Antonio J. Nebro antonio@lcc.uma.es

SPEA2(problem, population_size, offspring_population_size, mutation, crossover, termination_criterion=None, population_generator=RandomGenerator(), population_evaluator=SequentialEvaluator(), dominance_comparator=DominanceComparator(), rng=None)

Bases: GeneticAlgorithm[S, R]

:param problem: The problem to solve. :param population_size: Size of the population. :param mutation: Mutation operator (see 🇵🇾mod:jmetal.operator.mutation). :param crossover: Crossover operator (see 🇵🇾mod:jmetal.operator.crossover).

Source code in src/jmetal/algorithm/multiobjective/spea2.py 
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
def __init__(
    self,
    problem: Problem,
    population_size: int,
    offspring_population_size: int,
    mutation: Mutation,
    crossover: Crossover,
    termination_criterion: TerminationCriterion | None = None,
    population_generator: Generator = RandomGenerator(),
    population_evaluator: Evaluator = SequentialEvaluator(),
    dominance_comparator: Comparator = DominanceComparator(),
    rng: np.random.Generator | None = None,
):
    """
    :param problem: The problem to solve.
    :param population_size: Size of the population.
    :param mutation: Mutation operator (see :py:mod:`jmetal.operator.mutation`).
    :param crossover: Crossover operator (see :py:mod:`jmetal.operator.crossover`).
    """
    multi_comparator = MultiComparator(
        [StrengthRanking.get_comparator(), KNearestNeighborDensityEstimator.get_comparator()]
    )
    selection = BinaryTournamentSelection(comparator=multi_comparator)

    super().__init__(
        problem=problem,
        population_size=population_size,
        offspring_population_size=offspring_population_size,
        mutation=mutation,
        crossover=crossover,
        selection=selection,
        termination_criterion=termination_criterion,
        population_evaluator=population_evaluator,
        population_generator=population_generator,
        rng=rng,
    )
    self.dominance_comparator = dominance_comparator

replacement(population, offspring_population)

This method joins the current and offspring populations to produce the population of the next generation by applying the ranking and crowding distance selection.

:param population: Parent population. :param offspring_population: Offspring population. :return: New population after ranking and crowding distance selection is applied.

Source code in src/jmetal/algorithm/multiobjective/spea2.py 
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def replacement(self, population: list[S], offspring_population: list[S]) -> list[list[S]]:
    """This method joins the current and offspring populations to produce the population of the next generation
    by applying the ranking and crowding distance selection.

    :param population: Parent population.
    :param offspring_population: Offspring population.
    :return: New population after ranking and crowding distance selection is applied.
    """
    ranking: StrengthRanking[S] = StrengthRanking(self.dominance_comparator)
    density_estimator: KNearestNeighborDensityEstimator[S] = KNearestNeighborDensityEstimator()

    replacement = RankingAndDensityEstimatorReplacement(
        ranking, density_estimator, RemovalPolicyType.SEQUENTIAL
    )
    solutions = replacement.replace(population, offspring_population)

    return solutions

Single-objective

See Single-objective algorithms in the User Guide.