fairdo.optimize.single package#

This module contains the optimization methods for single-objective optimization. The optimization algorithms are designed to minimize an objective function that takes a binary vector as input. The optimization problem is defined as follows:

\[\min_{\mathbf{x} \in \{0, 1\}^d} \quad f(\mathbf{x})\]

where \(f\) is the objective function to minimize.

Submodules#

fairdo.optimize.single.baseline module#

fairdo.optimize.single.baseline.ones_array_method(f, d)[source]#

Returns an array of ones and the fitness of that array. When used as a binary mask, this method returns the original dataset.

Parameters:

f (callable) – Objective/fitness function to minimize.
d (int) – Dimension of the flattened numpy array to evaluate on f.

Returns:

np.array (d,) – Numpy array of ones.
float – Fitness of the ones array.

Examples

>>> from fairdo.optimize.single import ones_array_method
>>> ones_array_method(lambda x: x.sum(), 5)
(array([1., 1., 1., 1., 1.]), 5.0)

>>> ones_array_method(lambda x: x.sum(), 3)
(array([1., 1., 1.]), 3.0)

fairdo.optimize.single.baseline.random_method(f, d, pop_size=100, num_generations=500)[source]#

Generates a random binary vector (numpy array) and evaluates it on f for a total of pop_size * num_generations times. Returns solution with the lowest value.

Parameters:

f (callable) – Objective/fitness function to minimize.
d (int) – Dimension of the vector.
pop_size (int) – Size of the population.
num_generations (int) – Number of generations.

Returns:

np.array (d,) – Numpy array of the best solution found.
float – Fitness of the best solution found.

Examples

>>> from fairdo.optimize.single import random_method
>>> random_method(lambda x: x.sum(), 5)
(array([0, 0, 0, 0, 0]), 0.0)

>>> random_method(lambda x: x.sum(), 3)
(array([0, 0, 0]), 0.0)

>>> random_method(lambda x: x.sum(), 10)
(array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 0.0)

fairdo.optimize.single.baseline.random_method_vectorized(f, d, pop_size=100, num_generations=500)[source]#

Vectorized version of the fairdo.optimize.single.random_method function.

Generates a random binary vector (numpy array) and evaluates it on f for a total of pop_size * num_generations times. Returns solution with the lowest value.

Parameters:

f (callable) – Objective/fitness function to minimize.
d (int) – Dimension of the vector.
pop_size (int) – Size of the population.
num_generations (int) – Number of generations.

Returns:

np.array (d,) – Numpy array of the best solution found.
float – Fitness of the best solution found.

Examples

>>> from fairdo.optimize.single import random_method
>>> random_method(lambda x: x.sum(), 5)
(array([0, 0, 0, 0, 0]), 0.0)

>>> random_method(lambda x: x.sum(), 3)
(array([0, 0, 0]), 0.0)

>>> random_method(lambda x: x.sum(), 10)
(array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 0.0)

fairdo.optimize.single.ga module#

This module implements the Genetic Algorithm for combinatorial optimization problems. It reflects the process of natural selection where the fittest individuals are selected for reproduction to produce the offspring for the next generation [1] [2].

The optimization algorithm is genetic_algorithm, which takes the fitness f, the dimensionality d, the population size pop_size, and number of generation num_generations as inputs. The algorithm iteratively applies selection, crossover, and mutation operations to evolve the population over a number of generations. The genetic operators can be customized by passing the corresponding functions from fairdo.optimize.operators as arguments.

References

fairdo.optimize.single.ga.evaluate_individual(args)[source]#

Calculates the fitness of an individual. The fitness is the value of the fitness function plus a penalty for individuals that do not satisfy the size constraint.

Parameters:: args (tuple) – The arguments to pass to the function. The arguments are (f, individual).
Returns:: fitness – The fitness of the individual.
Return type:: float

fairdo.optimize.single.ga.evaluate_population(f, population)[source]#

Calculates the fitness of each individual in a population. The fitness is the value of the fitness function plus a penalty for individuals that do not satisfy the size constraint.

Parameters:

f (callable) – The fitness function to evaluate.
population (ndarray, shape (pop_size, d)) – The population of vectors to evaluate.

Returns:

fitness – The fitness values of the population.

Return type:

ndarray, shape (pop_size,)

fairdo.optimize.single.ga.evaluate_population_single_cpu(f, population)[source]#

Calculates the fitness of each individual in a population. The fitness is the value of the fitness function plus a penalty for individuals that do not satisfy the size constraint.

Parameters:

f (callable) – The fitness function to evaluate.
n (int) – The constraint value.
population (ndarray, shape (pop_size, d)) – The population of vectors to evaluate.

Returns:

fitness – The fitness values of the population.

Return type:

ndarray, shape (pop_size,)

fairdo.optimize.single.ga.genetic_algorithm(f, d, pop_size=100, num_generations=500, initialization=<function random_initialization>, selection=<function elitist_selection>, crossover=<function uniform_crossover>, mutation=<function fractional_flip_mutation>, maximize=False, tol=1e-06, patience=50)[source]#

Perform a genetic algorithm. It consists of the following steps which are repeated for a specified number of generations:

Generate an initial population of binary vectors.
Evaluate the fitness of each vector in the population.
Select the best individuals to be parents. (Selection)
Create offspring by performing crossover on the parents. (Crossover)
Mutate the offspring. (Mutation)

Parameters:

f (callable) – The objective function (fitness) to minimize.
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=elitist_selection)) – The function to select the parents from the population.
crossover (callable, optional (default=uniform_crossover)) – The function to perform the crossover operation.
mutation (callable, optional (default=fractional_flip_mutation)) – The function to perform the mutation operation.
maximize (bool, optional (default=False)) – Whether to maximize or minimize the fitness function.
tol (float, optional (default=1e-6)) – The tolerance for early stopping. If the best solution found is within tol of the previous best solution, then the algorithm stops.
patience (int, optional (default=50)) – The number of generations to wait before early stopping.

Returns:

best_solution (ndarray, shape (d,)) – The best solution found by the algorithm.
best_fitness (float) – The fitness of the best solution found by the algorithm.

Notes

The genetic algorithm is used to maximize the given fitness function. To avoid having to rewrite the selection, crossover, and mutation functions to work with minimization problems, the fitness function is negated if we are minimizing. The fitness function must map the binary vector to a positive value, i.e., \(f: \{0, 1\}^d \rightarrow \mathbb{R}^+\).