brkga_mp_ipr.algorithm module

class brkga_mp_ipr.algorithm.BrkgaMpIpr(decoder: object, sense: brkga_mp_ipr.enums.Sense, seed: int, chromosome_size: int, params: brkga_mp_ipr.types.BrkgaParams, evolutionary_mechanism_on: bool = True, chrmosome_type: type = <class 'brkga_mp_ipr.types.BaseChromosome'>)

Bases: object

This class represents a Multi-Parent Biased Random-key Genetic Algorithm with Implicit Path Relinking (BRKGA-MP-IPR).

Main capabilities

Evolutionary process

In the BRKGA-MP-IPR, we keep a population of chromosomes divided between the elite and the non-elite group. During the mating, multiple parents are chosen from the elite group and the non-elite group. They are sorted either on no-decreasing order for minimization or non-increasing order to maximization problems. Given this order, a bias function is applied to the rank of each chromosome, resulting in weight for each one. Using a roulette method based on the weights, the chromosomes are combined using a biased crossover.

This code also implements the island model, where multiple populations can be evolved in parallel, and migration between individuals between the islands are performed using exchange_elite() method.

This code requires a Decoder object capable to map a chromosome to a solution for the specific problem, and return a value to be used as fitness to the decoded chromosome. The decoder must have the method

def decode(self, chromosome: BaseChromosome, rewrite: bool) -> float:

where chromosome is an BaseChromosome object of representing a solution and rewrite is a boolean indicating that if the decode should rewrite the chromosome in case it implements local searches and modifies the initial solution decoded from the chromosome.

Note that BaseChromosome is a simple list of floats and can be manipulated as so. However, wrapping such a list into a new class allows the user to customize the chromosome, adding new functionalities as needed. Please, see BaseChromosome for more details.

Attributes:

params (BrkgaParams): The BRKGA and IPR hyper-parameters.

opt_sense (Sense): Indicates whether we are maximizing or minimizing.

chromosome_size (positive int): Number of genes in the chromosome.

elite_size (positive int): Number of elite items in the population.

num_mutants (positive int): Number of mutants introduced at each

generation into the population.

evolutionary_mechanism_on (bool): If false, no evolution is performed

but only chromosome decoding. Very useful to emulate a multi-start algorithm.

evolve(num_generations: int = 1) → None

Evolves all populations for generations.

Args:

num_generations (positive int): the number of generations to be

evolved.

Raises:

RuntimeError: If the algorith has been initialized before.

ValueError: either if population_index < 0 or

population_index >= num_independent_populations.

evolve_population(population_index: int) → None

Evolves the population population_index to the next generation.

Note:

Although this method allows us to evolve populations independently, and therefore, provide nice flexibility, the generation of each population can be unsyched. We must proceed with care when using this function instead of evolve().

Args:

population_index (positive int): the index for the population to

be evolved.

Raises:

RuntimeError: If the algorith has been initialized before.

ValueError: either if population_index < 0 or

population_index >= num_independent_populations.

exchange_elite(num_immigrants: int) → None

Todo

to be implemented.

fill_chromosome(chromosome: brkga_mp_ipr.types.BaseChromosome) → None

Fills a given chromosome with random keys, using the pre-allocated memory.

Args:

chromosome (BaseChromosome): The chromosome to be filled.

generate_chromosome(chromosome_size: int) → brkga_mp_ipr.types.BaseChromosome

Generates a new chromosome with the given size. The new chromosome is an object of class self._ChromosomeType (which should be a BaseChromosome derivative), given in the constructor. If the chromosome type is not given in the constructor, BaseChromosome is used instead. Please, see the documentation of both the BaseChromosome and the constructor for more details.

Args:

chromosome_size (positive int): The size of the chromosome.

get_best_chromosome() → brkga_mp_ipr.types.BaseChromosome

Returns a deep copy of the best individual found so far among all populations.

Raises:

RuntimeError: If the algorith has been initialized before.

get_best_fitness() → float

Returns the fitness/value of the best individual found so far among all populations.

Raises:

RuntimeError: If the algorith has been initialized before.

get_chromosome(population_index: int, position: int) → brkga_mp_ipr.types.BaseChromosome

Returns a deep copy of the chromosome ranked at position in the population population_index.

Args:

population_index (positive int): the population from where

fetch the chromosome.

position (positive int): position the chromosome position,

ordered by fitness. The best chromosome is located in position 0.

Raises:

RuntimeError: If the algorith has been initialized before.

ValueError: either if population_index < 0 or

population_index >= num_independent_populations.

ValueError: either if when position < 0 or

position >= population_size.

get_current_population(population_index: int = 0) → None

Returns a reference for population population_index.

Warning:

IT IS NOT ADIVISED TO CHANGE THE POPULATION DIRECTLY, since such changes can result in undefined behavior.

Args:

population_index (positive int): the index for the population.

Raises:

RuntimeError: If the algorith has been initialized before.

ValueError: either if population_index < 0 or

population_index >= num_independent_populations.

initialize() → None

Initializes the populations and others data structures of the BRKGA. If an initial population is supplied, this method completes the remaining individuals, if they do not exist.

Warning:

THIS METHOD MUST BE CALLED BEFORE ANY OPTIMIZATION METHODS.

This method also performs the initial decoding of the chromosomes. Therefore, depending on the decoder implementation, this can take a while, and the user may want to time such procedure in his/her experiments.

Raises:

RuntimeError: If the algorith has been initialized before

and it is not a reset() call.

ValueError: If the bias functions is not set.

inject_chromosome(chromosome: brkga_mp_ipr.types.BaseChromosome, population_index: int, position: int, fitness: float = inf) → None

Todo

to be implemented.

path_relink(pr_type: brkga_mp_ipr.enums.PathRelinkingType, pr_selection: brkga_mp_ipr.enums.PathRelinkingSelection, dist: callable, number_pairs: int, minimum_distance: float, block_size: int = 1, max_time: int = 0, percentage: int = 1.0) → brkga_mp_ipr.enums.PathRelinkingResult

Todo

to be implemented.

reset() → None

Resets all populations with brand new keys. All warm-start solutions provided by set_initial_population() are discarded. You may use inject_chromosome() to insert those solutions again.

Raises:

RuntimeError: If the algorith has been initialized before.

set_bias_custom_function(bias_function: Callable[[int], float]) → None

Sets a new bias function to be used to rank the chromosomes during the mating. It must be a positive non-increasing function returning a float, i.e., \(f : \mathbb{N}^+ \to \mathbb{R}^+\) such that \(f(i) \ge 0\) and \(f(i) \ge f(i+1)\) for \(i \in [1..total\_parents]\). For instance, the following sets an inverse quadratic function:

brkga = BRKGA_MP_IPR(...)
brkga.set_bias_custom_function(lambda x : 1.0 / (x * x))

Args:

bias_function: A positive non-increasing function.

Raises:

ValueError: In case the function is not a non-increasing

positive function.

set_initial_population(chromosomes: List[brkga_mp_ipr.types.BaseChromosome]) → None

Sets initial individuals into the poulation to work as warm-starters. Such individuals can be obtained from solutions of external procedures such as fast heuristics, other methaheuristics, or even relaxations from a mixed integer programming model that models the problem.

All given solutions are assigned to one population only. Therefore, the maximum number of solutions is the size of the populations.

Args:

chromosomes (list of BaseChromosome): a set of individuals or

solutions encoded as BaseChromosomes.

Raises:

ValueError: if the number of given chromosomes is larger than

the population size; if the sizes of the given chromosomes do not match with the required chromosome size.

shake(intensity: int, shaking_type: brkga_mp_ipr.enums.ShakingType, population_index: int = inf) → None

Todo

to be implemented.