geneticalgs package¶
Submodules¶
geneticalgs.standard_ga module¶
-
class
geneticalgs.standard_ga.
IndividualGA
(chromosome, fitness_val)[source]¶ Bases:
object
The class represents an individual of population in GA.
-
chromosome
¶ float, list
A chromosome represented a solution. The solution may be binary encoded in chromosome or be a float or a list of floats in case of dealing with real value solutions. The list contains only positions of bit 1 (according to input data list) in case of binary encoded solution.
-
fitness_val
¶ float, int
Fitness value of the given chromosome.
-
-
class
geneticalgs.standard_ga.
StandardGA
(fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
object
This class implements the base functionality of genetic algorithms and must be inherited. In other words, the class doesn’t provide functionality of genetic algorithms by itself. This class is inherited by RealGA and BinaryGA classes in the current implementation.
-
fitness_func
¶ function
This function must compute fitness value of a single chromosome. Function parameters depend on the implemented subclasses of this class.
-
optim
¶ str
What this genetic algorithm must do with fitness value: maximize or minimize. May be ‘min’ or ‘max’. Default is “max”.
-
selection
¶ str
Parent selection type. May be “rank” (Rank Wheel Selection), “roulette” (Roulette Wheel Selection) or “tournament”. Default is “rank”.
-
tournament_size
¶ int
Defines the size of tournament in case of ‘selection’ == ‘tournament’. Default is None.
-
mut_prob
¶ float
Probability of mutation. Recommended values are 0.5-1%. Default is 0.5% (0.05).
-
mut_type
¶ int
This parameter defines how many chromosome bits will be mutated. Default is 1.
-
cross_prob
¶ float
Probability of crossover. Recommended values are 80-95%. Default is 95% (0.95).
-
cross_type
¶ int
This parameter defines crossover type. The following types are allowed: single point (1), two point (2) and multiple point (2 < cross_type). The extreme case of multiple point crossover is uniform one (cross_type == all_bits). The specified number of bits (cross_type) are crossed in case of multiple point crossover. Default is 1.
-
elitism
¶ True, False
Elitism on/off. Default is True.
-
_check_common_parameters
()[source]¶ This method verifies common input parameters of a genetic algorithm.
-
_check_init_random_population
(*args)[source]¶ TO BE REIMPLEMENTED IN SUBCLASSES.
This method verifies the input parameters of a random initialization.
-
_compute_fitness
(chromosome)[source]¶ TO BE REIMPLEMENTED IN SUBCLASSES.
This method computes fitness value of the given chromosome.
Parameters: chromosome (float, list) – A chromosome of genetic algorithm. Defined fitness function (self.fitness_func) must deal with such chromosomes. Returns: fitness value of the given chromosome
-
_compute_rank_wheel_sum
(population_size)[source]¶ The method returns sum of a wheel that is necessary in parent selection process in case of “rank” selection type.
Parameters: population_size (int) – Size of a population. Returns: sum of the wheel for the given population size
-
_conduct_tournament
(population, size)[source]¶ Conducts a tournament of the given size within the specified population. The population must be sorted by chromosome’s fitness value the following way: the last population elements are the best.
Parameters: Returns: winners – indices of a winner of the current tournament and the second best participant
Return type: int, int
-
_cross
(parent1, parent2)[source]¶ This method crosses over the two given chromosomes (parents). The first parent is a target chromosome that means its bits will be replaced with bits of the second parent (source chromosome) with the specified crossover probability.
Parameters: - parent1 (float, list) – Target chromosome. May be a float or a list of floats, or a binary encoded combination of the original data list (self.data) of the first parent.
- parent2 (float, list) – Source chromosome. May be a float or a list of floats, or a binary encoded combination of the original data list (self.data) of the second parent.
Returns: child – a chromosome (a binary representation, a float or a list of floats) created by the crossover of the two given parents
Return type: list, float
-
_generate_random_population
(*args)[source]¶ TO BE REIMPLEMENTED IN SUBCLASSES.
This method generates new random population by the given input parameters.
-
_invert_bit
(chromosome, bit_num)[source]¶ TO BE REIMPLEMENTED IN SUBCLASSES. This method mutates the appropriate bits of the chromosome from bit_num with the specified mutation probability.
Parameters: - chromosome (list, float) – A chromosome of population (chromosome without its fitness value).
- bit_num (list) – List of bits’ numbers to invert.
Returns: mutated chromosome
-
_mutate
(chromosome)[source]¶ This method mutates (inverses bits) the given chromosome.
Parameters: chromosome (float, list) – a float or a list of floats, or a binary encoded combination of the original data list (it contains positions of bit 1 according to self.data). Returns: mutated chromosome as float, list of floats or binary representation (any of the mentioned representations with inverted bits depending on subclass)
-
_random_diff
(stop, n, start=0)[source]¶ Creates a list of ‘n’ different random integer numbers within the interval (start, stop) (‘start’ included).
Parameters: Returns: list of different random integer values from the given interval (‘start’ included)
-
_replace_bits
(source, target, start, stop)[source]¶ TO BE REIMPLEMENTED IN SUBCLASSES. Replace target bits with source bits in interval (start, stop) (both included) with the specified crossover probability. This interval represents positions of bits to replace (minimum start point is 0 and maximum end point is self._bin_length - 1).
Parameters: Returns: target with replaced bits with source one in the interval (start, stop) (both included)
-
_select_parents
(population, wheel_sum=None)[source]¶ Selects parents from the given population.
Parameters: Returns: parents – selected parents
Return type: IndividualGA, IndividualGA
-
_sort_population
()[source]¶ Sorts self.population according to self.optim (“min” or “max”) in such way that the last element of the population in both cases is the chromosome with the best fitness value.
-
_update_solution
(chromosome, fitness_val)[source]¶ Updates current best solution if the given one is better.
Parameters: - chromosome (float, list) – Chromosome of a population (binary encoded, float or list of floats).
- fitness_val (float, int) – Fitness value of the given chromosome.
-
best_solution
¶ Returns tuple in the following form: (best chromosome, its fitness value).
Returns: tuple with the currently best found chromosome and its fitness value.
-
extend_population
(elem_list)[source]¶ DOES NOT WORK WITH DIFFUSION GENETIC ALGORITHM.
Extends a current population with the new elements. Be careful with type of elements in elem_list: they must have the same type as elements of a current population, e.g. IndividualGA objects with the appropriate chromosome representation (binary encoded for BinaryGA, a float or a list of floats for RealGA).
Parameters: elem_list (list) – New elements of the same type (including chromosome representation) as in the current population.
-
init_population
(chromosomes, interval=None)[source]¶ Initializes a population with the given chromosomes (binary encoded, float or a list of floats). The fitness values of these chromosomes will be computed by a specified fitness function.
It is recommended to have an amount of chromosomes equal to some squared number (9, 16, 100, 625 etc.) in case of diffusion model of GA. Otherwise some last chromosomes will be lost as the current implementation supports only square arrays of diffusion model.
Parameters: - chromosomes (list) – Chromosomes of a new population. A single chromosome in case of binary GA is represented as a list of bits’ positions with value 1 in the following way: LSB (least significant bit) has position (len(self.data) - 1) and MSB (most significant bit) has position 0. If it is a GA on real values, a chromosome is represented as a float or a list of floats in case of multiple dimensions. Size of chromosomes list must be at least 4.
- interval (tuple) – An interval in which we are searching the best solution. Must be specified in case of RealGA.
-
run
(max_generation)[source]¶ Starts a standard GA (RealGA or BinaryGA). The algorithm performs max_generation generations and then stops. Old population is completely replaced with a new computed one at the end of each generation.
Parameters: max_generation (int) – Maximum number of GA generations. Returns: fitness_progress – List of average fitness values for each generation (including original population) Return type: list
-
geneticalgs.real_ga module¶
-
class
geneticalgs.real_ga.
RealGA
(fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
geneticalgs.standard_ga.StandardGA
This class realizes GA over the real values. In other words, it tries to find global minimum or global maximum (depends on the settings) of a given fitness function.
-
fitness_func
¶ function
This function must compute fitness value of a single chromosome. Function parameters depend on the implemented subclasses of this class.
-
optim
¶ str
What this genetic algorithm must do with fitness value: maximize or minimize. May be ‘min’ or ‘max’. Default is “max”.
-
selection
¶ str
Parent selection type. May be “rank” (Rank Wheel Selection), “roulette” (Roulette Wheel Selection) or “tournament”. Default is “rank”.
-
tournament_size
¶ int
Defines the size of tournament in case of ‘selection’ == ‘tournament’. Default is None.
-
mut_prob
¶ float
Probability of mutation. Recommended values are 0.5-1%. Default is 0.5% (0.05).
-
mut_type
¶ int
This parameter defines how many chromosome bits will be mutated. Default is 1.
-
cross_prob
¶ float
Probability of crossover. Recommended values are 80-95%. Default is 95% (0.95).
-
cross_type
¶ int
This parameter defines crossover type. The following types are allowed: single point (1), two point (2) and multiple point (2 < cross_type). The extreme case of multiple point crossover is uniform one (cross_type == all_bits). The specified number of bits (cross_type) are crossed in case of multiple point crossover. Default is 1.
-
elitism
¶ True, False
Elitism on/off. Default is True.
You may initialize instance of this class the following way
from geneticalgs import RealGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize standard real GA with fitness maximization by default gen_alg = RealGA(fitness_function) # initialize random one-dimensional population of size 20 within interval (0, 1000) gen_alg.init_random_population(20, 1, (0, 1000))
Then you may start computation by gen_alg.run(number_of_generations) and obtain the currently best found solution by gen_alg.best_solution.
-
_adjust_to_interval
(var)[source]¶ This method replaces NaN, inf, -inf in var by numpy.nan_to_num() and then returns var if it is within the specified interval. Otherwise returns lower bound of the interval if (var < lower bound) or upper bound of the interval if (var > upper bound).
Parameters: var (list, float) – A float or a list of floats to adjust to the specified interval. Returns: adjusted input parameter
-
_check_init_random_population
(size, dim, interval)[source]¶ This method verifies the input parameters of a random initialization.
Parameters:
-
_compute_fitness
(chromosome)[source]¶ This method computes fitness value of the given chromosome.
Parameters: chromosome (float, list) – A chromosome of genetic algorithm. May be a single float or a list of floats in case of multiple dimensions. Defined fitness function (self.fitness_func) must deal with this chromosome representation. Returns: fitness value of the given chromosome
-
_generate_random_population
(size, dim, interval)[source]¶ This method generates a new random population by the given input parameters.
Parameters: Returns: array – Array rows represent chromosomes. Number of columns is specified with dim parameter.
Return type: numpy.array
-
_get_chromosome_return_value
(chromosome)[source]¶ This method returns a vector (chromosome as a list of floats) or a single float depending on number of elements in the given chromosome.
Parameters: chromosome (list) – This list contains a single float or represents a vector of floats in case of multiple dimensions. Returns: chromosome[0] iff there is only 1 element in the list, otherwise chromosome
-
_get_mut_bit_offset
()[source]¶ Returns bit number (from left (index 0) to the right) in 32- or 64-bit big-endian floating point binary representation (IEEE 754) from which a mantissa begins. It is necessary because this real GA implementation mutates only mantissa bits (mutation of exponent changes a float number the undesired fast and unexpected way).
-
_invert_bit
(chromosome, bit_num)[source]¶ This method mutates the appropriate bits of the chromosome from bit_num with the specified mutation probability. The method mutates bit_num’s bits of all floats in a list represented chromosome in case of multiple dimensions.
Parameters: - chromosome (float, list) – A single float or a list of floats in case of multiple dimensions.
- bit_num (list) – List of bits’ numbers to invert.
Returns: mutated chromosome (float, list)
-
_is_chromosome_list
(chromosome)[source]¶ This method returns True iff chromosome is a list (even list of just 1 element), otherwise False.
Parameters: chromosome (float, list) – A chromosome of GA population. May be float or a list of floats in case of multiple dimensions. Returns: True iff the given chromosome is a list (even a list of just 1 element), otherwise False.
-
_replace_bits
(source, target, start, stop)[source]¶ Replaces target bits with source bits in interval (start, stop) (both included) with the specified crossover probability. This interval represents positions of bits to replace (minimum start point is 0 and maximum end point is self._bin_length - 1).
Parameters: - source (float, list) – Values in source are used as replacement for target. May be a float or a list of floats in case of multiple dimensions.
- target (float, list) – Values in target are replaced with values in source. May be a float or a list of floats in case of multiple dimensions.
- start (int) – Start point of interval (included).
- stop (int) – End point of interval (included).
Returns: target – Target with replaced bits with source one in the interval (start, stop) (both included).
Return type: float, list
-
geneticalgs.binary_ga module¶
-
class
geneticalgs.binary_ga.
BinaryGA
(data=None, fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
geneticalgs.standard_ga.StandardGA
This class realizes GA over a binary encoded input data. In other words, the algorithm tries to find a combination of the input data with the best fitness value.
You may initialize instance of this class the following way
from geneticalgs import BinaryGA # define data whose best combination we are searching for input_data = [1,2,3,7,-1,-20] # define a simple fitness function def fitness_function(chromosome, data): # this function searches for the greatest sum of numbers in data # chromosome contains positions (from left 0 to right *len(data)-1) of bits 1 sum = 0 for bit in chromosome: sum += data[bit] return sum # initialize standard binary GA gen_alg = BinaryGA(input_data, fitness_function) # initialize random population of size 6 gen_alg.init_random_population(6)
Then you may start computation by gen_alg.run(number_of_generations) and obtain the currently best found solution by gen_alg.best_solution.
-
_check_init_random_population
(size)[source]¶ This method verifies the input parameter of a random initialization.
Parameters: size (int) – Size of a new population to check. Returns: max_num – Maximum amount of the input data combinations. Return type: int
-
_compute_fitness
(chromosome)[source]¶ This method computes fitness value of the given chromosome.
Parameters: chromosome (list) – A binary encoded chromosome of genetic algorithm. Defined fitness function (self.fitness_func) must deal with this chromosome representation. Returns: fitness value of the given chromosome
-
_generate_random_population
(max_num, size)[source]¶ This method generates a new random population by the given input parameters.
Parameters: Returns: population – list if integers in interval [1, maxnum) that represents a binary encoded combination.
Return type:
-
_get_bit_positions
(number)[source]¶ This method receives a positive decimal integer number and returns positions of bit 1 in its binary representation. However, these positions are transformed the following way: they are mapped on the data list (self.data) “as is”. It means that LSB (least significant bit) is mapped on the last position of the data list (e.g. self._bin_length - 1), MSB is mapped on the first position of the data list (e.g. 0) and so on.
Parameters: number (int) – This decimal number represents binary encoded combination of the input data (self.data). Returns: list of positions with bit 1 (these positions are mapped on the input data list “as is” and thus, LSB is equal to index (self._bin_length - 1) of the input data list).
-
_invert_bit
(chromosome, bit_num)[source]¶ This method mutates the appropriate bits of the given chromosome from bit_num with the specified mutation probability.
Parameters: Returns: mutant – mutated chromosome as binary representation of self.data (it contains positions of bit 1)
Return type:
-
_replace_bits
(source, target, start, stop)[source]¶ Replaces target bits with source bits in interval (start, stop) (both included) with the specified crossover probability and returns target. This interval represents positions of bits to replace (minimum start point is 0 and maximum end point is self._bin_length - 1).
Parameters: Returns: target with replaced bits in the interval (start, stop) (both included)
-
geneticalgs.diffusion_ga module¶
-
class
geneticalgs.diffusion_ga.
DiffusionGA
(instance)[source]¶ Bases:
object
This class implements diffusion model of genetic algorithms. The current implementation supports four neighbours (up, down, left, right) of a currently processed cell. Supports the standard selection types (e.g. “rank”, “roulette”, “tournament”). It’s evident that the maximum tournament size is 4 in this case.
You may initialize instance of this class the following way
from geneticalgs import RealGA, DiffusionGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize standard real GA with fitness maximization by default gen_alg = RealGA(fitness_function) # then initialize diffusion GA using the already initialized real GA instance dga = DiffusionGA(gen_alg) # initialize random one-dimensional population of size 20 within interval (0, 1000) dga.init_random_population(20, 1, (0, 1000))
BinaryGA is used the same way. You may start computation by dga.run(number_of_generations) and obtain the currently best found solution by dga.best_solution.
-
_compute_diffusion_generation
(chrom_arr)[source]¶ This method computes a new generation of a diffusion model of GA.
Parameters: chrom_arr (numpy.array) – Diffusion array of chromosomes (binary encoded, float or a list of floats) of the current generation. Returns: new_chrom_array, new_fitness_arr – New diffusion arrays of chromosomes and their fitness values of the next generation. Return type: numpy.array, numpy.array
-
_construct_diffusion_model
(population)[source]¶ Constructs two arrays: first for chromosomes of GA, second for their fitness values. The current implementation supports construction of only 2D square arrays. Thus, an array side is a square root of the given population length. If the calculated square root is a fractional number, it will be truncated that means the last chromosomes in population may not be presented in the constructed arrays.
Parameters: population (list) – List of GA chromosomes. Same as in self.init_population(new_population).
-
_find_critical_values
(fitness_arr)[source]¶ Finds 1D or 2D array coordinates of the best and the worst fitness values in the given array. Returns coordinates of the first occurrence of these critical values.
Parameters: fitness_arr (numpy.array) – Array of fitness values. Returns: coords_best, coords_worst – Coordinates of the best and the worst fitness values as (index_best, index_worst) in 1D or ((row, column), (row, column)) in 2D. Return type: tuple
-
_get_neighbour
(row, column)[source]¶ The method returns a chromosome selected from the four neighbours (up, down, left, right) of the currently processed cell (specified with the given row and column) according to the selection type (“rank”, “roulette” or “tournament”).
Parameters: Returns: chromosome – A chromosome selected from neighbours according to the specified selection type (“rank”, “roulette”, “tournament”).
Return type: binary encoded, float, list of floats
-
_init_diffusion_model
(population)[source]¶ This method constructs diffusion model from the given population and then updates the currently best found solution.
Parameters: population (list) – List of GA chromosomes.
-
best_solution
¶ Returns tuple in the following form: (best chromosome, its fitness value).
Returns: tuple with the currently best found chromosome and its fitness value.
-
init_population
(new_population)[source]¶ Initializes population with the given chromosomes (binary encoded, float or a list of floats) in new_population. The fitness values of these chromosomes will be computed by a specified fitness function.
It is recommended to have new_population size equal to some squared number (9, 16, 100, 625 etc.) in case of diffusion model of GA. Otherwise some last chromosomes in the given population will be lost as the current implementation supports only square arrays of diffusion model.
Parameters: new_population (list) – A new population of chromosomes of size at least 4. A single chromosome in case of binary GA is represented as a list of bits’ positions with value 1 in the following way: LSB (least significant bit) has position (len(self.data) - 1) and MSB (most significant bit) has position 0. If it is a GA on real values, an individual is represented as a float or a list of floats in case of multiple dimensions.
-
init_random_population
(size, dim=None, interval=None)[source]¶ Initializes a new random population with the given parameters.
Parameters: - size (int) – A size of new generated population. Must be at least 2 in case of RealGA and at least 4 in case of BinaryGA.
- dim (int, None) – Amount of space dimensions in case of RealGA.
- interval (tuple, None) – The generated numbers of each dimension will be within this interval (start point included, end point excluded). Must be specified in case of RealGA.
-
population
¶ Returns the following tuple: (array of chromosomes, array of their fitness values).
Returns: array of chromosomes, array of fitness values – Array of chromosomes and another array with their fitness values. Return type: tuple
-
run
(max_generation)[source]¶ Starts a diffusion GA. The algorithm performs max_generation generations and then stops. Old population is completely replaced with a new computed one at the end of each generation.
Parameters: max_generation (int) – Maximum number of GA generations. Returns: fitness_progress – List of average fitness values for each generation (including original population). Return type: list
-
geneticalgs.migration_ga module¶
-
class
geneticalgs.migration_ga.
MigrationGA
(type='binary')[source]¶ Bases:
object
This class implements migration model of GA, namely island model (not stepping-stone). It works with binary or real GA.
-
type
¶ str
Type of used genetic algorithms: may be ‘binary’ or ‘real’.
You may initialize instance of this class the following way
from geneticalgs import RealGA, MigrationGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize two or more standard real GAs with fitness maximization by default gen_alg1 = RealGA(fitness_function) gen_alg2 = RealGA(fitness_function) # initialize random one-dimensional populations of size 10 and 15 within interval (0, 1000) gen_alg1.init_random_population(10, 1, (0, 1000)) gen_alg2.init_random_population(15, 1, (0, 1000)) # then initialize migration GA using the already initialized standard GA instances mga = MigrationGA(type='real') # set type of used instances mga.init_populations([gen_alg1, gen_alg2])
Migration model with BinaryGA is used the same way. You may start computation by mga.run(*args).
-
_compare_solutions
()[source]¶ Compares best solutions of the specified GA instances and returns the best solution.
Returns: best_solution – Best solution across all GA instances as (best chromosome, its fitness value). Return type: tuple
-
init_populations
(ga_list)[source]¶ This method initializes migration model of GA. Type of optimization (‘min’ or ‘max’) will be set to the same value of the first given GA instance. Valid GA instances are RealGA and BinaryGA.
Parameters: ga_list (list) – List of BinaryGA (or RealGA) instances with already initialized populations.
-
run
(max_generation, period=1, migrant_num=1, cloning=True, migrate=True)[source]¶ Runs a migration model of GA.
Parameters: - max_generation (int) – Maximum number of GA generations.
- period (int) – How often migration must be performed. Must be less than or equal to max_generation.
- migrant_num (int) – How many best migrants will travel to all another populations.
- cloning (True, False) – Can migrants clone? If False, an original population will not have its migrants after a migration. Otherwise, clones of migrants will remain in their original population after the migration of originals.
- migrate (True, False) – Turns on/off migration process. It is useful in case of running GA by only one generation so period must be also set to 1, but you want to perform migration with period greater than 1 and thus, set migrate initially to False and set it to True when you actually want the algorithm to perform migration. This was used in benchmarking by COCO BBOB platform.
Returns: fitness_progress, best_solution – fitness_progress contains lists of average fitness value of each generation for each specified GA instance. best_solution is the best solution across all GA instances as in form (best chromosome, its fitness value).
Return type: You may use this method the standard way
avg_fitness_progress, best_solution = mga.run(50, 10, 2)
or in more unusual way if you want to get the best found solution for each generation
max_generation = 10 for i in range(max_generation): # perform migration every four generations if i > 0 and i % 3 == 0: migrate = True else: migrate = False _, best_solution = mga.run(1, 1, 2, cloning=True, migrate=migrate)
-
Module contents¶
-
class
geneticalgs.
StandardGA
(fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
object
This class implements the base functionality of genetic algorithms and must be inherited. In other words, the class doesn’t provide functionality of genetic algorithms by itself. This class is inherited by RealGA and BinaryGA classes in the current implementation.
-
fitness_func
¶ function
This function must compute fitness value of a single chromosome. Function parameters depend on the implemented subclasses of this class.
-
optim
¶ str
What this genetic algorithm must do with fitness value: maximize or minimize. May be ‘min’ or ‘max’. Default is “max”.
-
selection
¶ str
Parent selection type. May be “rank” (Rank Wheel Selection), “roulette” (Roulette Wheel Selection) or “tournament”. Default is “rank”.
-
tournament_size
¶ int
Defines the size of tournament in case of ‘selection’ == ‘tournament’. Default is None.
-
mut_prob
¶ float
Probability of mutation. Recommended values are 0.5-1%. Default is 0.5% (0.05).
-
mut_type
¶ int
This parameter defines how many chromosome bits will be mutated. Default is 1.
-
cross_prob
¶ float
Probability of crossover. Recommended values are 80-95%. Default is 95% (0.95).
-
cross_type
¶ int
This parameter defines crossover type. The following types are allowed: single point (1), two point (2) and multiple point (2 < cross_type). The extreme case of multiple point crossover is uniform one (cross_type == all_bits). The specified number of bits (cross_type) are crossed in case of multiple point crossover. Default is 1.
-
elitism
¶ True, False
Elitism on/off. Default is True.
-
best_solution
¶ Returns tuple in the following form: (best chromosome, its fitness value).
Returns: tuple with the currently best found chromosome and its fitness value.
-
extend_population
(elem_list)[source]¶ DOES NOT WORK WITH DIFFUSION GENETIC ALGORITHM.
Extends a current population with the new elements. Be careful with type of elements in elem_list: they must have the same type as elements of a current population, e.g. IndividualGA objects with the appropriate chromosome representation (binary encoded for BinaryGA, a float or a list of floats for RealGA).
Parameters: elem_list (list) – New elements of the same type (including chromosome representation) as in the current population.
-
init_population
(chromosomes, interval=None)[source]¶ Initializes a population with the given chromosomes (binary encoded, float or a list of floats). The fitness values of these chromosomes will be computed by a specified fitness function.
It is recommended to have an amount of chromosomes equal to some squared number (9, 16, 100, 625 etc.) in case of diffusion model of GA. Otherwise some last chromosomes will be lost as the current implementation supports only square arrays of diffusion model.
Parameters: - chromosomes (list) – Chromosomes of a new population. A single chromosome in case of binary GA is represented as a list of bits’ positions with value 1 in the following way: LSB (least significant bit) has position (len(self.data) - 1) and MSB (most significant bit) has position 0. If it is a GA on real values, a chromosome is represented as a float or a list of floats in case of multiple dimensions. Size of chromosomes list must be at least 4.
- interval (tuple) – An interval in which we are searching the best solution. Must be specified in case of RealGA.
-
run
(max_generation)[source]¶ Starts a standard GA (RealGA or BinaryGA). The algorithm performs max_generation generations and then stops. Old population is completely replaced with a new computed one at the end of each generation.
Parameters: max_generation (int) – Maximum number of GA generations. Returns: fitness_progress – List of average fitness values for each generation (including original population) Return type: list
-
-
class
geneticalgs.
IndividualGA
(chromosome, fitness_val)[source]¶ Bases:
object
The class represents an individual of population in GA.
-
chromosome
¶ float, list
A chromosome represented a solution. The solution may be binary encoded in chromosome or be a float or a list of floats in case of dealing with real value solutions. The list contains only positions of bit 1 (according to input data list) in case of binary encoded solution.
-
fitness_val
¶ float, int
Fitness value of the given chromosome.
-
-
class
geneticalgs.
BinaryGA
(data=None, fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
geneticalgs.standard_ga.StandardGA
This class realizes GA over a binary encoded input data. In other words, the algorithm tries to find a combination of the input data with the best fitness value.
You may initialize instance of this class the following way
from geneticalgs import BinaryGA # define data whose best combination we are searching for input_data = [1,2,3,7,-1,-20] # define a simple fitness function def fitness_function(chromosome, data): # this function searches for the greatest sum of numbers in data # chromosome contains positions (from left 0 to right *len(data)-1) of bits 1 sum = 0 for bit in chromosome: sum += data[bit] return sum # initialize standard binary GA gen_alg = BinaryGA(input_data, fitness_function) # initialize random population of size 6 gen_alg.init_random_population(6)
Then you may start computation by gen_alg.run(number_of_generations) and obtain the currently best found solution by gen_alg.best_solution.
-
class
geneticalgs.
RealGA
(fitness_func=None, optim='max', selection='rank', mut_prob=0.05, mut_type=1, cross_prob=0.95, cross_type=1, elitism=True, tournament_size=None)[source]¶ Bases:
geneticalgs.standard_ga.StandardGA
This class realizes GA over the real values. In other words, it tries to find global minimum or global maximum (depends on the settings) of a given fitness function.
-
fitness_func
¶ function
This function must compute fitness value of a single chromosome. Function parameters depend on the implemented subclasses of this class.
-
optim
¶ str
What this genetic algorithm must do with fitness value: maximize or minimize. May be ‘min’ or ‘max’. Default is “max”.
-
selection
¶ str
Parent selection type. May be “rank” (Rank Wheel Selection), “roulette” (Roulette Wheel Selection) or “tournament”. Default is “rank”.
-
tournament_size
¶ int
Defines the size of tournament in case of ‘selection’ == ‘tournament’. Default is None.
-
mut_prob
¶ float
Probability of mutation. Recommended values are 0.5-1%. Default is 0.5% (0.05).
-
mut_type
¶ int
This parameter defines how many chromosome bits will be mutated. Default is 1.
-
cross_prob
¶ float
Probability of crossover. Recommended values are 80-95%. Default is 95% (0.95).
-
cross_type
¶ int
This parameter defines crossover type. The following types are allowed: single point (1), two point (2) and multiple point (2 < cross_type). The extreme case of multiple point crossover is uniform one (cross_type == all_bits). The specified number of bits (cross_type) are crossed in case of multiple point crossover. Default is 1.
-
elitism
¶ True, False
Elitism on/off. Default is True.
You may initialize instance of this class the following way
from geneticalgs import RealGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize standard real GA with fitness maximization by default gen_alg = RealGA(fitness_function) # initialize random one-dimensional population of size 20 within interval (0, 1000) gen_alg.init_random_population(20, 1, (0, 1000))
Then you may start computation by gen_alg.run(number_of_generations) and obtain the currently best found solution by gen_alg.best_solution.
-
-
class
geneticalgs.
DiffusionGA
(instance)[source]¶ Bases:
object
This class implements diffusion model of genetic algorithms. The current implementation supports four neighbours (up, down, left, right) of a currently processed cell. Supports the standard selection types (e.g. “rank”, “roulette”, “tournament”). It’s evident that the maximum tournament size is 4 in this case.
You may initialize instance of this class the following way
from geneticalgs import RealGA, DiffusionGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize standard real GA with fitness maximization by default gen_alg = RealGA(fitness_function) # then initialize diffusion GA using the already initialized real GA instance dga = DiffusionGA(gen_alg) # initialize random one-dimensional population of size 20 within interval (0, 1000) dga.init_random_population(20, 1, (0, 1000))
BinaryGA is used the same way. You may start computation by dga.run(number_of_generations) and obtain the currently best found solution by dga.best_solution.
-
best_solution
¶ Returns tuple in the following form: (best chromosome, its fitness value).
Returns: tuple with the currently best found chromosome and its fitness value.
-
init_population
(new_population)[source]¶ Initializes population with the given chromosomes (binary encoded, float or a list of floats) in new_population. The fitness values of these chromosomes will be computed by a specified fitness function.
It is recommended to have new_population size equal to some squared number (9, 16, 100, 625 etc.) in case of diffusion model of GA. Otherwise some last chromosomes in the given population will be lost as the current implementation supports only square arrays of diffusion model.
Parameters: new_population (list) – A new population of chromosomes of size at least 4. A single chromosome in case of binary GA is represented as a list of bits’ positions with value 1 in the following way: LSB (least significant bit) has position (len(self.data) - 1) and MSB (most significant bit) has position 0. If it is a GA on real values, an individual is represented as a float or a list of floats in case of multiple dimensions.
-
init_random_population
(size, dim=None, interval=None)[source]¶ Initializes a new random population with the given parameters.
Parameters: - size (int) – A size of new generated population. Must be at least 2 in case of RealGA and at least 4 in case of BinaryGA.
- dim (int, None) – Amount of space dimensions in case of RealGA.
- interval (tuple, None) – The generated numbers of each dimension will be within this interval (start point included, end point excluded). Must be specified in case of RealGA.
-
population
¶ Returns the following tuple: (array of chromosomes, array of their fitness values).
Returns: array of chromosomes, array of fitness values – Array of chromosomes and another array with their fitness values. Return type: tuple
-
run
(max_generation)[source]¶ Starts a diffusion GA. The algorithm performs max_generation generations and then stops. Old population is completely replaced with a new computed one at the end of each generation.
Parameters: max_generation (int) – Maximum number of GA generations. Returns: fitness_progress – List of average fitness values for each generation (including original population). Return type: list
-
-
class
geneticalgs.
MigrationGA
(type='binary')[source]¶ Bases:
object
This class implements migration model of GA, namely island model (not stepping-stone). It works with binary or real GA.
-
type
¶ str
Type of used genetic algorithms: may be ‘binary’ or ‘real’.
You may initialize instance of this class the following way
from geneticalgs import RealGA, MigrationGA import math # define some function whose global minimum or maximum we are searching for # this function takes as input one-dimensional number def fitness_function(x): # the same function is used in examples return abs(x*(math.sin(x/11)/5 + math.sin(x/110))) # initialize two or more standard real GAs with fitness maximization by default gen_alg1 = RealGA(fitness_function) gen_alg2 = RealGA(fitness_function) # initialize random one-dimensional populations of size 10 and 15 within interval (0, 1000) gen_alg1.init_random_population(10, 1, (0, 1000)) gen_alg2.init_random_population(15, 1, (0, 1000)) # then initialize migration GA using the already initialized standard GA instances mga = MigrationGA(type='real') # set type of used instances mga.init_populations([gen_alg1, gen_alg2])
Migration model with BinaryGA is used the same way. You may start computation by mga.run(*args).
-
init_populations
(ga_list)[source]¶ This method initializes migration model of GA. Type of optimization (‘min’ or ‘max’) will be set to the same value of the first given GA instance. Valid GA instances are RealGA and BinaryGA.
Parameters: ga_list (list) – List of BinaryGA (or RealGA) instances with already initialized populations.
-
run
(max_generation, period=1, migrant_num=1, cloning=True, migrate=True)[source]¶ Runs a migration model of GA.
Parameters: - max_generation (int) – Maximum number of GA generations.
- period (int) – How often migration must be performed. Must be less than or equal to max_generation.
- migrant_num (int) – How many best migrants will travel to all another populations.
- cloning (True, False) – Can migrants clone? If False, an original population will not have its migrants after a migration. Otherwise, clones of migrants will remain in their original population after the migration of originals.
- migrate (True, False) – Turns on/off migration process. It is useful in case of running GA by only one generation so period must be also set to 1, but you want to perform migration with period greater than 1 and thus, set migrate initially to False and set it to True when you actually want the algorithm to perform migration. This was used in benchmarking by COCO BBOB platform.
Returns: fitness_progress, best_solution – fitness_progress contains lists of average fitness value of each generation for each specified GA instance. best_solution is the best solution across all GA instances as in form (best chromosome, its fitness value).
Return type: You may use this method the standard way
avg_fitness_progress, best_solution = mga.run(50, 10, 2)
or in more unusual way if you want to get the best found solution for each generation
max_generation = 10 for i in range(max_generation): # perform migration every four generations if i > 0 and i % 3 == 0: migrate = True else: migrate = False _, best_solution = mga.run(1, 1, 2, cloning=True, migrate=migrate)
-