Genetic Algorithms (GA)

The GeneticAlgorithm class provides a skeleton for the implementation of custom GAs, and the BinaryGeneticAlgorithm is the standard implementation of it.

For a good explanation of how Genetic Algorithms work, read this from MathWorks.

class sigmaepsilon.math.optimize.ga.Genom(*, phenotype: List[float] = None, genotype: List[int] = None, fittness: float, age: int = 0, index: int = -1)

A data class for members of a population.

model_config: ClassVar[ConfigDict] = {}

Configuration for the model, should be a dictionary conforming to [ConfigDict][pydantic.config.ConfigDict].

model_fields: ClassVar[dict[str, FieldInfo]] = {'age': FieldInfo(annotation=int, required=False, default=0), 'fittness': FieldInfo(annotation=float, required=True), 'genotype': FieldInfo(annotation=List[int], required=False, default_factory=list), 'index': FieldInfo(annotation=int, required=False, default=-1), 'phenotype': FieldInfo(annotation=List[float], required=False, default_factory=list)}

Metadata about the fields defined on the model, mapping of field names to [FieldInfo][pydantic.fields.FieldInfo].

This replaces Model.__fields__ from Pydantic V1.

class sigmaepsilon.math.optimize.ga.GeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, maxiter: int = 200, miniter: int = 100, elitism: int = 1, maxage: int = 5)

Base class for Genetic Algorithms (GA). Use this as a base class to your custom implementation of a GA.

The class has 4 abstract methods wich upon being implemented, yield a working genetic algorithm. These are populate(), decode(), crossover(), mutate() and select(). It is also possible to use a custom stopping criteria by implementing stopping_criteria(). See BinaryGeneticAlgorithm for an example.

Parameters:

• fnc (Callable) – The function to evaluate. It is assumed, that the function expects and N number of scalar arguments as a 1d iterable.

• ranges (Iterable) – Ranges for each scalar argument to the objective function.

• length (int, Optional) – Chromosome length. The higher the value, the more precision. Default is 5.

• p_c (float, Optional) – Probability of crossover. Default is 1.

• p_m (float, Optional) – Probability of mutation. Default is 0.2.

• nPop (int, Optional) – The size of the population. Default is 100.

• maxiter (int, Optional) – The maximum number of iterations. Default is 200.

• miniter (int, Optional) – The minimum number of iterations. Default is 100.

• elitism (float or int, Optional) – Default is 1

• ftol (float, Optional) – Torelance for floating point operations. Default is 1e-12.

Note

Be cautious what you use a genetic algorithm for. Like all metahauristic methods, a genetic algorithm can be wery demanding on the computational side. If the objective unction takes a lot of time to evaluate, it is probably not a good idea to use a heuristic approach, unless you have a dedicated solver that is able to run efficiently for a large number of problems.

See also

BinaryGeneticAlgorithm

abstract crossover(parent1: ndarray | None = None, parent2: ndarray | None = None) → Tuple[ndarray]

Takes in two parents, returns two offspring. You’d probably want to use it inside the populator.

abstract decode(genotypes: ndarray | None = None) → ndarray

Turns genotypes into phenotypes.

abstract mutate(child: ndarray | None = None) → ndarray

Takes a child in, returns a mutant.

abstract populate(genotypes: ndarray | None = None)

Ought to produce a pool of phenotypes.

abstract select(genotypes: ndarray | None = None, phenotypes: ndarray | None = None)

Ought to implement dome kind of selection mechanism, eg. a roulette wheel, tournament or other.

solve(recycle: bool = False, **kwargs) → Genom

Solves the problem and returns the best phenotype.

Parameters:

recycle (bool, Optional) – If True, the leftover resources of the previous calculation are the starting point of the new solution.

Returns:

The best candidate.

Return type:

Genom

class sigmaepsilon.math.optimize.bga.BinaryGeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, maxiter: int = 200, miniter: int = 100, elitism: int = 1, maxage: int = 5)

An implementation of a Binary Genetic Algorithm (BGA) for finding minimums of real valued unconstrained problems of continuous variables in n-dimensional vector spaces.

In other words, it solves the following problem:

\begin{eqnarray} & minimize& \quad f(\mathbf{x}) \quad in \quad \mathbf{x} \in \mathbf{R}^n. \end{eqnarray}

Parameters:

• fnc (Callable) – The fittness function.

• ranges (Iterable) – sequence of pairs of limits for each variable

• length (int, Optional) – Chromosome length (string length). Default is 5.

• p_c (float, Optional) – Probability of crossover, 0 <= p_c <= 1. Default is 1.

• p_m (float, Optional) – Probability of mutation, 0 <= p_m <= 1. Default is 0.2.

• nPop (int, Optional) – Number of members in the population. Default is 100.

• elitism (float or int, Optional) – Value to control elitism. Default is 1.

Examples

Find the minimizer of the Rosenbrock function. The exact value of the solution is x = [1.0, 1.0].

>>> from sigmaepsilon.math.optimize import BinaryGeneticAlgorithm
>>> def Rosenbrock(x):
...     a, b = 1, 100
...     return (a-x[0])**2 + b*(x[1]-x[0]**2)**2
>>> ranges = [[-10, 10], [-10, 10]]
>>> BGA = BinaryGeneticAlgorithm(Rosenbrock, ranges, length=12, nPop=200)
>>> _ = BGA.solve()
>>> x = BGA.best_phenotype()
>>> fx = Rosenbrock(x)
...

The following code prints the history using the evolve generator of the object

>>> from sigmaepsilon.math.optimize import BinaryGeneticAlgorithm
>>> import matplotlib.pyplot as plt
>>> def Rosenbrock(x):
...     a, b = 1, 100
...     return (a-x[0])**2 + b*(x[1]-x[0]**2)**2
>>> ranges = [[-10, 10], [-10, 10]]
>>> BGA = BinaryGeneticAlgorithm(Rosenbrock, ranges, length=12, nPop=200)
>>> _ = [BGA.evolve(1) for _ in range(100)]
>>> x = BGA.best_phenotype()
>>> fx = Rosenbrock(x)
...

crossover(parent1: ndarray | None = None, parent2: ndarray | None = None, nCut: int | None = None) → Tuple[ndarray]

Performs crossover on the parents parent1 and parent2, using an nCut number of cuts and returns two childs.

decode(genotypes: ndarray | None = None) → ndarray

Decodes the genotypes to phenotypes and returns them as an array.

mutate(child: ndarray | None = None) → ndarray

Returns a mutated genotype. Children come in, mutants go out.

populate(genotypes: ndarray | None = None) → ndarray

Populates the model and returns the array of genotypes.

select(genotypes: ndarray | None = None, phenotypes: ndarray | None = None) → ndarray

Organizes a tournament and returns the genotypes of the winners.