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 neumann.optimize.GeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, **kwargs)[source]#

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(). 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

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][source]#

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

abstract decode(genotypes: ndarray | None = None)[source]#

Turns genotypes into phenotypes.

abstract mutate(child: ndarray | None = None) → ndarray[source]#

Takes a child in, returns a mutant.

abstract populate(genotypes: ndarray | None = None)[source]#

Ought to produce a pool of phenotypes.

abstract select(genotypes: ndarray | None = None, phenotypes: ndarray | None = None)[source]#

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

solve(reset: bool = False, returnlast: bool = False, **kwargs)[source]#

Solves the problem and returns the best phenotype.

class neumann.optimize.BinaryGeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, **kwargs)[source]#

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 integer, 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 neumann.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 neumann.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][source]#

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

decode(genotypes: ndarray | None = None) → ndarray[source]#

Decodes the genotypes to phenotypes.

mutate(child: ndarray | None = None) → ndarray[source]#

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

populate(genotypes: ndarray | None = None)[source]#

Populates the model from a list of genotypes as seeds.

select(genotypes: ndarray | None = None, phenotypes: ndarray | None = None) → ndarray[source]#

Organizes a tournament and returns the genotypes of the winners.