fairdo.optimize.multi package#

This module contains implementations of multi-objective optimization algorithms. All algorithms are designed to minimize objective functions which take a binary vector as input. The multi-objective optimization problem is defined as follows:

\[\min_{\mathbf{x} \in \{0, 1\}^d} \quad (f_1(\mathbf{x}), f_2(\mathbf{x}), \ldots, f_n(\mathbf{x}))\]

where $f_1, f_2, \ldots, f_n$ are objective functions.

Submodules#

fairdo.optimize.multi.nsga module#

Non-dominated Sorting Genetic Algorithm II (NSGA-II) for multi-objective optimization [1]. It maintains a population of solutions and uses non-dominated sorting and crowding distance to select the best solutions. Fitness functions are minimized by default. Returns the Pareto front of the population.

References

fairdo.optimize.multi.nsga.crowding_distance(fitness_values)[source]#

Calculate crowding distance for each individual in the population.

Parameters:: fitness_values (ndarray, shape (N, num_fitness_functions)) – Fitness values of the population.
Returns:: crowding_distances – Crowding distances for each individual.
Return type:: ndarray, shape (N,)

fairdo.optimize.multi.nsga.dom_counts_indices(fitness_values)[source]#

Calculates the number of individuals that dominate each individual and the indices of individuals that are dominated by each individual.

Parameters:

fitness_values (ndarray, shape (pop_size, num_fitness_functions)) – The fitness values of each individual in the population for each fitness function.

Returns:

dominating_counts (ndarray, shape (pop_size,)) – The number of individuals that dominate each individual. i-th element of the array is the number of individuals that dominate the i-th individual.
dominated_indices (list of ndarrays) – The indices of individuals that are dominated by each individual. i-th element of the list is an array containing the indices of individuals that are dominated by the i-th individual.

fairdo.optimize.multi.nsga.dom_counts_indices_fast(fitness_values)[source]#

Calculates the number of individuals that dominate each individual and the indices of individuals that are dominated by each individual. Faster implementation using broadcasting.

Parameters:

fitness_values (ndarray, shape (pop_size, num_fitness_functions)) – The fitness values of each individual in the population for each fitness function.

Returns:

dominating_counts (ndarray, shape (pop_size,)) – The number of individuals that dominate each individual.
dominated_indices (list of ndarrays) – The indices of individuals that are dominated by each individual.

Notes

This function uses broadcasting to compare all pairs of individuals in the population. The result is a significant speedup compared to the non-broadcasting implementation. dominating_counts differs from the original implementation. The original implementation counts equal fitness values as dominating, while this implementation does not.

fairdo.optimize.multi.nsga.evaluate_population(fitness_functions, population)[source]#

Evaluate the fitness of each individual in the population using the given fitness functions.

Parameters:

fitness_functions (list of callables) – The list of fitness functions to evaluate.
population (ndarray, shape (pop_size, d)) – The population of binary vectors.

Returns:

fitness_values – The fitness values of each individual in the population for each fitness function.

Return type:

ndarray, shape (pop_size, num_fitness_functions)

fairdo.optimize.multi.nsga.evaluate_population_parallel(fitness_functions, population)[source]#

Evaluate the fitness of each individual in the population using the given fitness functions.

Parameters:

fitness_functions (list of callables) – The list of fitness functions to evaluate.
population (ndarray, shape (pop_size, d)) – The population of binary vectors.

Returns:

fitness_values – The fitness values of each individual in the population for each fitness function.

Return type:

ndarray, shape (pop_size, num_fitness_functions)

fairdo.optimize.multi.nsga.non_dominated_sort(fitness_values)[source]#

Perform non-dominated sorting on the given fitness values.

Parameters:: fitness_values (ndarray, shape (pop_size, num_fitness_functions)) – The fitness values of each individual in the population for each fitness function.
Returns:: fronts – List of fronts, where each front contains the indices of individuals in that front.
Return type:: list of ndarrays

fairdo.optimize.multi.nsga.non_dominated_sort_fast(fitness_values)[source]#

Perform non-dominated sorting on the given fitness values. Faster implementation using broadcasting.

Parameters:: fitness_values (ndarray, shape (pop_size, num_fitness_functions)) – The fitness values of each individual in the population for each fitness function.
Returns:: fronts – List of fronts, where each front contains the indices of individuals in that front.
Return type:: list of ndarrays

Notes

This function uses broadcasting to compare all pairs of individuals in the population. The result is a significant speedup compared to the non-broadcasting implementation.

fairdo.optimize.multi.nsga.nsga2(fitness_functions, d, pop_size=100, num_generations=500, initialization=<function variable_initialization>, selection=<function elitist_selection_multi>, crossover=<function onepoint_crossover>, mutation=<function bit_flip_mutation>, return_all_fronts=False)[source]#

Perform NSGA-II (Non-dominated Sorting Genetic Algorithm II) for multi-objective optimization. NSGA-II maintains a population of solutions and uses non-dominated sorting and crowding distance to select the best solutions. Fitness functions are minimized by default.

Parameters:

fitness_functions (list of callables) – The list of objective functions to minimize. Each function should take a binary vector and return a scalar value.
d (int) – The number of dimensions.
pop_size (int) – The size of the population.
num_generations (int) – The number of generations.
initialization (callable, optional (default=random_initialization)) – The function to initialize the population.
selection (callable, optional (default=tournament_selection_multi)) – The function to perform selection.
crossover (callable, optional (default=uniform_crossover)) – The function to perform crossover.
mutation (callable, optional (default=shuffle_mutation)) – The function to perform mutation.
return_all_fronts (bool, optional (default=False)) – Whether to return all fronts. If False, only the first front is returned. If True, the combined_population and fitness_values are returned along with the fronts.

Returns:

population (ndarray, shape (pop_size, d)) – The best solution found by NSGA-II.
fitness_values (ndarray, shape (pop_size, num_fitness_functions)) – The fitness values of the best solution found by NSGA-II.
fronts (list of ndarrays) – List of fronts, where each front contains the indices of individuals in that front. Only returned if return_all_fronts is True`.)

Notes

The fitness functions must map the binary vector to a scalar value, i.e., $f: {0, 1}^d rightarrow mathbb{R}$. We used the same operators as the authors of NSGA-II in the original paper [1]. We only changed the selection operator. The original paper uses binary tournament selection, but we use elitist selection with multiple objectives.

References

[1] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002).: A fast and elitist multiobjective genetic algorithm: NSGA-II. https://ieeexplore.ieee.org/document/996017

fairdo.optimize.multi.nsga.selection_indices(combined_fitness_values, fronts, pop_size)[source]#

Select the best individuals from the combined population based on the non-dominated sorting results and crowding distance to maintain diversity.

Parameters:

combined_fitness_values (ndarray, shape (N, d)) – Combined population containing both original population and offspring.
fronts (list of ndarrays) – List of fronts, where each front contains the indices of individuals in that front.
pop_size (int) – The size of the population.

Returns:

selected_indices – Selected indices from the combined population.

Return type:

list