fairdo.optimize.operators package#

This package contains numerous methods for different genetic operators. The methods are implemented in respective submodules: initialization, selection, crossover, and mutation.

Notes

To change the default settings of the genetic method, use the built-in function functools.partial to set different parameters.

Example

>>> from functools import partial
>>> from fairdo.optimize.single import genetic_algorithm
>>> from fairdo.optimize.operators import onepoint_crossover,\
fractional_flip_mutation, elitist_selection
>>> # Specify your mutation function with customized parameters
>>> my_mutation_function = partial(fractional_flip_mutation, mutation_rate=0.10)
>>> # Define f, d, n, pop_size, num_generations...
>>> f = lambda x: 1 if x[0] == 1 and x[1] == 1 else 0
>>> d = 2
>>> n = 0 # no constraints
>>> pop_size = 100
>>> num_generations = 100
>>> # Now you can use my_mutation_function as an argument to genetic_algorithm
>>> result = genetic_algorithm(f, d, pop_size, num_generations,
>>>                            selection=elitist_selection,
>>>                            crossover=onepoint_crossover,
>>>                            mutation=my_mutation_function, maximize=False)

Submodules#

fairdo.optimize.operators.crossover module#

This module implements various crossover methods used in genetic algorithms. Crossover is a genetic operator to combine two individuals to produce offspring.

Each function in this module takes a pair of parents and produces a user-given amount of offsprings by combining the genes of the parents. The way in which the genes (individuals’ features) are combined depends on the specific crossover method.

These crossover methods are based on the works of the following references:

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

fairdo.optimize.operators.crossover.kpoint_crossover(parents, num_offspring, k=2)[source]#

Perform the crossover operation with K-point crossover on the parents to create the offspring.

Parameters:

parents (numpy array) – Parents of the offspring with shape (2, d).
num_offspring (int) – Number of offsprings.
k (int) – number of crossover points, default is 2

Returns:

offspring

Return type:

ndarray, shape (num_offspring, d)

fairdo.optimize.operators.crossover.no_crossover(parents, num_offspring)[source]#

Perform the crossover operation with no crossover on the parents to create the offspring.

Parameters:

parents (numpy array) – Parents of the offspring with shape (2, d).
num_offspring (int) – Number of offsprings.

Returns:

offspring

Return type:

ndarray, shape (num_offspring, d)

fairdo.optimize.operators.crossover.onepoint_crossover(parents, num_offspring)[source]#

Perform the crossover operation with One-point crossover on the parents to create the offspring.

Parameters:

parents (numpy array) – Parents of the offspring with shape (2, d).
num_offspring (int) – Number of offsprings.

Returns:

offspring

Return type:

ndarray, shape (num_offspring, d)

fairdo.optimize.operators.crossover.simulated_binary_crossover(parents, num_offspring, eta=15)[source]#

Perform the crossover operation with Simulated Binary Crossover (SBX) on the parents to create the offspring.

Parameters:

parents (numpy array) – Parents of the offspring with shape (2, d).
num_offspring (int) – Number of offsprings.

Returns:

offspring

Return type:

ndarray, shape (num_offspring, d)

References

Kalyanmoy Deb, Karthik Sindhya, and Tatsuya Okabe. Self-adaptive simulated binary crossover for real-parameter optimization. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO ‘07, pages 1187–1194, New York, NY, USA, 2007. Association for Computing Machinery.

fairdo.optimize.operators.crossover.uniform_crossover(parents, num_offspring, p=0.5)[source]#

Perform the crossover operation with Uniform crossover on the parents to create the offspring.

Parameters:

parents (numpy array) – Parents of the offspring with shape (2, d).
num_offspring (int) – Number of offsprings.
p (float) – Probability of selecting a gene from the first parent, default is 0.5.

Returns:

offspring

Return type:

ndarray, shape (num_offspring, d)

fairdo.optimize.operators.initialization module#

fairdo.optimize.operators.initialization.biased_random_initialization(pop_size, d, selection_probability=0.8)[source]#

Initialize the population with a bias towards selecting more items.

Parameters:

pop_size (int) – Size of the population.
d (int) – Dimensionality of the problem (number of items).
selection_probability (float) – Probability of initializing a bit as 1.
Returns – np.ndarray: Initialized population with shape (pop_size, d).

fairdo.optimize.operators.initialization.random_initialization(pop_size, d)[source]#

Generate a random population of binary vectors. Each vector has a length of d. The values of the vectors are either 0 or 1. The population is generated randomly.

Parameters:

pop_size (int) – The size of the population to generate.
d (int) – The dimension of the binary vectors.

Returns:

population – The generated population of binary vectors.

Return type:

ndarray, shape (pop_size, d)

fairdo.optimize.operators.initialization.variable_initialization(pop_size, d, min_p=0.5, max_p=0.99)[source]#

Initialize the population with a variable probability of selecting items.

Parameters:

pop_size (int) – Size of the population.
d (int) – Dimensionality of the problem (number of items).
min_p (float) – Minimum probability of selecting an item.
max_p (float) – Maximum probability of selecting an item.
Returns – np.ndarray: Initialized population with shape (pop_size, d).

fairdo.optimize.operators.mutation module#

This module implements various mutation methods used in genetic algorithms. These methods are used to introduce diversity in the population by randomly altering the genes of the individuals. Each function in this module takes a population of individuals as input and returns a mutated population. The mutation happens outplace, meaning that the original population is not modified. The rate of mutation can be specified by the user.

These mutation methods are based on the works of the following references:

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

Bäck, T. (1993). Optimal Mutation Rates in Genetic Search. Proceedings of the 5th International Conference on Genetic Algorithms.

fairdo.optimize.operators.mutation.adaptive_mutation(offspring, mutation_rate=0.05, diversity_threshold=0.1)[source]#

Mutates the given offspring with an adaptive mutation rate based on population diversity.

Parameters:

offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
mutation_rate (float, optional) – The initial probability of flipping each bit for each offspring. Default is 0.05.
diversity_threshold (float, optional) – The threshold for population diversity. If diversity falls below this threshold, increase mutation rate. Default is 0.1.

Returns:

offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.

Return type:

ndarray, shape (n, d)

fairdo.optimize.operators.mutation.bit_flip_mutation(offspring, mutation_rate=0.05)[source]#

Mutates the given offspring by flipping each bit with a certain probability. Some offspring may not be mutated at all, and some may be mutated more than expected.

Parameters:

offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
mutation_rate (float, optional) – The probability of flipping each bit. Default is 0.05.

Returns:

offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.

Return type:

ndarray, shape (n, d)

fairdo.optimize.operators.mutation.diverse_mutation(offspring, mutation_rate=0.05)[source]#

Mutates the given offspring in a diverse manner to prevent convergence towards 50% selection rate. Using the uniform mutation rate, the mutation rate is adjusted based on the proportion of 1s in each offspring. This means that the mutation rate is higher for offspring with a higher proportion of 1s.

Parameters:

offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
mutation_rate (float, optional) – The base mutation rate for each bit. Default is 0.05.

Returns:

offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.

Return type:

ndarray, shape (n, d)

fairdo.optimize.operators.mutation.fractional_flip_mutation(offspring, mutation_rate=0.05)[source]#

Mutates the given offspring by flipping a percentage of random bits for each offspring. A fixed amount of bits is flipped for each offspring.

Parameters:

offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
mutation_rate (float, optional (default=0.05)) – The percentage of random bits to flip for each offspring. Default is 0.05.

Returns:

offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.

Return type:

ndarray, shape (n, d)

fairdo.optimize.operators.mutation.shuffle_mutation(offspring, **kwargs)[source]#

Mutates the given offspring by shuffling the bits of each offspring.

Parameters:

offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
kwargs (dict) – Additional keyword arguments. Ignored.

Returns:

offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.

Return type:

ndarray, shape (n, d)

fairdo.optimize.operators.mutation.swap_mutation(offspring)[source]#

Mutates the given offspring by randomly selecting two bits and swapping their values.

Parameters:: offspring (ndarray, shape (n, d)) – The offspring to be mutated. Each row represents an offspring, and each column represents a bit.
Returns:: offspring – The mutated offspring. Each row represents an offspring, and each column represents a bit.
Return type:: ndarray, shape (n, d)

fairdo.optimize.operators.selection module#

This module implements various selection methods used in genetic algorithms. In multi objective optimization, the selection methods are used to select the parents based on the Pareto front and it is assumed that the fitness values are to be minimized. In single objective optimization, the selection methods are used to select the parents based on the fitness values and it is assumed that the fitness values are to be maximized.

These methods are used to select the individuals from the current generation that will be used to produce the offspring for the next generation. Each function in this module takes a population of individuals and their fitness values as input, and returns a subset of the population to be used as parents for the next generation and the parents’ fitness. The number of parents to select can be specified by the user.

These selection methods are based on the works of the following references:

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.

Baker, J. E. (1985). Adaptive selection methods for genetic algorithms. Proceedings of an International Conference on Genetic Algorithms and their Applications.

Whitley, D. (1989). The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. Proceedings of the Third International Conference on Genetic Algorithms.

fairdo.optimize.operators.selection.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.operators.selection.elitist_selection(population, fitness, num_parents=2)[source]#

This function selects the fittest (max fitness) parents from the population.

Parameters:

population (ndarray, shape (n, d)) – population of individuals
fitness (ndarray, shape (n,)) – fitness of each individual
num_parents (int) – number of parents to select

Returns:

parents (ndarray, shape (num_parents, d))
fitness (ndarray, shape (num_parents,))

fairdo.optimize.operators.selection.elitist_selection_multi(population, fitness_values, fronts_lengths, num_parents=2, tournament_size=3)[source]#

Randomly selects from the first front.

Parameters:

population (ndarray, shape (n, d)) – Population of individuals.
fitness_values (ndarray, shape (n, m)) – Fitness of each individual.
fronts_lengths (list of int) – Lengths of each front.
num_parents (int) – Number of parents to select.
tournament_size (int) – Number of individuals participating in each tournament.

Returns:

parents (ndarray, shape (num_parents, d)) – Selected parents.
fitness (ndarray, shape (num_parents,)) – Fitness of the selected parents.

fairdo.optimize.operators.selection.rank_selection(population, fitness, num_parents=2)[source]#

This function selects parents from the population based on their rank. The rank is determined by the fitness of the individual. The higher the fitness, the higher the rank. The probability of selecting an individual is proportional to its rank.

Parameters:

population (ndarray, shape (n, d)) – The population of individuals.
fitness (ndarray, shape (n,)) – The fitness of each individual.
num_parents (int) – The number of parents to select.

Returns:

parents (ndarray, shape (num_parents, d)) – The selected parents.
fitness (ndarray, shape (num_parents,)) – The fitness of the selected parents.

fairdo.optimize.operators.selection.roulette_wheel_selection(population, fitness, num_parents=2)[source]#

Select parents using Roulette Wheel Selection. The probability of selecting an individual is proportional to its fitness. The higher the fitness, the higher the chance of being selected. This function assumes that the fitness is non-negative.

Parameters:

population (ndarray, shape (n, d)) – Population of individuals.
fitness (ndarray, shape (n,)) – Fitness of each individual.
num_parents (int) – Number of parents to select.

Returns:

parents (ndarray, shape (num_parents, d)) – Selected parents.
fitness (ndarray, shape (num_parents,)) – Fitness of the selected parents.

Notes

This function normally assumes that the fitness is non-negative. However, if the fitness is negative, then the fitness values are shifted to be non-negative.

References

This function is based on the work: Holland, J. H. (1975). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. The Michigan Press.

fairdo.optimize.operators.selection.stochastic_universal_sampling(population, fitness, num_parents=2)[source]#

This function selects parents from the population using the Stochastic Universal Sampling (SUS) method.

Parameters:

population (ndarray, shape (n, d)) – The population of individuals.
fitness (ndarray, shape (n,)) – The fitness of each individual in the population.
num_parents (int) – The number of parents to select.

Returns:

parents (ndarray, shape (num_parents, d)) – The selected parents.
fitness (ndarray, shape (num_parents,)) – The fitness of the selected parents.

Notes

This function normally assumes that the fitness is non-negative. However, if the fitness is negative, then the fitness values are shifted to be non-negative.

References

This function is based on the work of Baker (1987) in the following paper: Baker, J. E. (1987). “Reducing Bias and Inefficiency in the Selection Algorithm”. Proceedings of the Second International Conference on Genetic Algorithms and Their Application.

fairdo.optimize.operators.selection.tournament_selection(population, fitness, num_parents=2, tournament_size=3)[source]#

Select parents using Tournament Selection. This method randomly selects a few individuals and chooses the best out of them to become a parent. The process is repeated until the desired number of parents are selected.

Parameters:

population (ndarray, shape (n, d)) – Population of individuals.
fitness (ndarray, shape (n,)) – Fitness of each individual.
num_parents (int) – Number of parents to select.
tournament_size (int) – Number of individuals participating in each tournament.

Returns:

parents (ndarray, shape (num_parents, d)) – Selected parents.
fitness (ndarray, shape (num_parents,)) – Fitness of the selected parents.

fairdo.optimize.operators.selection.tournament_selection_multi(population, fitness_values, fronts_lengths, num_parents=2, tournament_size=3)[source]#

Parameters:

population (ndarray, shape (n, d)) – Population of individuals.
fitness_values (ndarray, shape (n, m)) – Fitness of each individual.
fronts_lengths (list of int) – Lengths of each front.
num_parents (int) – Number of parents to select.
tournament_size (int) – Number of individuals participating in each tournament.

Returns:

parents (ndarray, shape (num_parents, d)) – Selected parents.
fitness (ndarray, shape (num_parents,)) – Fitness of the selected parents.