Nonlinear Programming (NLP)#

Nonlinear programming (NLP) is a subset of optimization where the objective function or constraints are nonlinear. Unlike linear programming, where relationships between variables are linear, NLP deals with more complex systems where variables may interact in intricate ways, resulting in non-straightforward solutions. NLP is used in a variety of fields such as economics, engineering, machine learning, and operations research, where real-world problems often exhibit nonlinear behaviors. The goal of NLP is to find the best possible solution (such as maximum profit or minimum cost) subject to given constraints.

Genetic Algorithms (GA)#

Genetic algorithms (GAs) are a type of optimization algorithm inspired by the principles of natural selection and genetics. GAs work by iteratively evolving a population of potential solutions to a problem through processes like selection, crossover (recombination), and mutation. Each individual solution is represented as a “chromosome,” and better solutions are evolved over generations by selecting and breeding the fittest individuals. GAs are particularly useful for solving complex, nonlinear, or discrete optimization problems where traditional methods may struggle. They are widely applied in fields such as artificial intelligence, engineering, and economics.

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

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 = 0, elitism: int | float | None = 1, maxage: int = 5, minimize: bool = False, seed: int | SeedSequence | Generator | None = None, selection_strategy: SelectionStrategy | None = None, vectorized: bool = False, n_jobs: int = 1)[source]#

Base class for Genetic Algorithms (GA).

Use this as a base class to your custom implementation of a GA.

The class has 3 representation-specific extension points that a subclass must implement to yield a working genetic algorithm: populate(), crossover() and mutate() (their base implementations raise NotImplementedError). encode()/decode() default to the identity mapping (suitable for representations where genotype and phenotype coincide, e.g. real-valued encodings) and select() already comes with a working, pluggable default (see selection_strategy / SelectionStrategy); override them only if you need representation-specific behavior. It is also possible to use a custom stopping criteria by overriding stopping_criteria(). See the BitChromosomeGeneticAlgorithm (shared bit-chromosome machinery, with BinaryGeneticAlgorithm and IntegerGeneticAlgorithm as its concrete, continuous/integer subclasses) and RealValuedGeneticAlgorithm classes for examples.

Note

This class is designed for maximizing the objective function. To minimize it, either negate the objective function or pass minimize=True when instantiating the class.

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 | int | None, Optional) – Determines the portion of the population designated as elite, which automatically survives to the next generation. If less than or equal to 1, it specifies a fraction of the population. If greater than 1, it indicates the exact number of individuals to be selected as elite. The default value of 1 assures that the reigning champion is always preserved. To turn this off, det the value to None. Default is 1.
ftol (float, Optional) – Torelance for floating point operations. Default is 1e-12.
maxage (int, Optional) – The age is the maximum number of generations a candidate spends at the top (being the best candidate). Default is 5.
minimize (bool, Optional) – If True, the objective function is minimized. Default is False.
seed (int | numpy.random.SeedSequence | numpy.random.Generator | None, Optional) – A seed for a per-instance numpy.random.default_rng(), used for every stochastic operation instead of the global numpy.random state. Passing the same seed makes runs reproducible, and lets multiple instances draw independent random streams in the same process. Default is None (nondeterministic).
selection_strategy (SelectionStrategy, Optional) – The strategy used by the default select() implementation to pick the survivors of a generation. Default is TournamentSelection.
vectorized (bool, Optional) – If True, evaluate() calls the objective function once with the whole (nPop, dim) array of phenotypes and expects it to return one fitness value per row, instead of calling it once per individual. Default is False.
n_jobs (int, Optional) – If different from 1 and vectorized is False, evaluate() calls the objective function once per individual in parallel worker processes (using concurrent.futures.ProcessPoolExecutor); -1 means “use all available CPUs”. The objective function must be picklable (e.g. a module-level function, not a lambda or a closure). Default is 1 (sequential evaluation).

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 function takes a lot of time to evaluate, it is probably not a good idea to use a heuristic approach, unless you have a dedicated evaluator that is able to run efficiently for a large number of problems or if the long running time is not an issue. If you want to customize the way the objective is evaluated, override the evaluate() method.

class sigmaepsilon.math.optimize.ga.Genom(*, phenotype: list[float] = <factory>, genotype: list[int | float] = <factory>, fitness: float, age: int = 0, index: int = -1)[source]#

A data class for members of a population.

property fittness: float#: Return the fitness value (deprecated alias for fitness).

model_config: ClassVar[ConfigDict] = {}#: Configuration for the model, should be a dictionary conforming to [ConfigDict][pydantic.config.ConfigDict].

Selection strategies#

The winners of each generation (beyond the automatically-surviving elite) are picked by a pluggable SelectionStrategy, injected via the selection_strategy constructor argument of GeneticAlgorithm and its subclasses.

class sigmaepsilon.math.optimize.selection.SelectionStrategy[source]#

Base class for pluggable selection strategies used by the default select() implementation.

abstract select(ga: GeneticAlgorithm, fitness: ndarray) → ndarray[source]#

Return an array of indices into fitness (repetition allowed) identifying the winners of the selection process.

The number of returned indices must be at least ga.nPop // 2, since the caller pairs them up to breed the rest of the next generation.

Parameters:

ga (GeneticAlgorithm) – The genetic algorithm instance, used to access elitism, nPop, _minimize, divide and the shared rng.
fitness (numpy.ndarray) – Fitness values of the current population.

class sigmaepsilon.math.optimize.selection.TournamentSelection(k: int = 3)[source]#

Classic k-way tournament selection: the elite (per ga.elitism) automatically survives, and the rest of the winners are picked by repeatedly drawing k random candidates from the non-elite pool and keeping the fittest of them.

Parameters:: k (int, Optional) – Tournament size. Default is 3.

select(ga: GeneticAlgorithm, fitness: ndarray) → ndarray[source]#: Select winners using k-way tournaments among the non-elite population.

class sigmaepsilon.math.optimize.selection.RouletteSelection[source]#

Fitness-proportionate (“roulette wheel”) selection: the probability of an individual being picked is proportional to its (shifted, non-negative) fitness.

select(ga: GeneticAlgorithm, fitness: ndarray) → ndarray[source]#: Select winners with probability proportional to their shifted fitness.

class sigmaepsilon.math.optimize.selection.RankSelection[source]#

Rank-based selection: the probability of an individual being picked depends on its rank within the population rather than the raw fitness value, which reduces the influence of outlier fitness values compared to RouletteSelection.

select(ga: GeneticAlgorithm, fitness: ndarray) → ndarray[source]#: Select winners with probability proportional to their fitness rank.

Binary Genetic Algorithm (BGA)#

Binary genetic algorithms (BGA) are a specific type of genetic algorithm where each solution is encoded as a string of binary digits (0s and 1s). These binary strings, known as genotypes (or chromosomes), represent the decision variables in the problem. Through genetic operations like selection, crossover, and mutation, BGAs evolve a population of solutions over time to find the best possible outcome. This approach is particularly well-suited for optimization problems where variables naturally lend themselves to binary encoding, such as combinatorial optimization and certain engineering design tasks.

BGA and IntegerGeneticAlgorithm (below) share the same underlying bit-chromosome machinery, provided by BitChromosomeGeneticAlgorithm; they only differ in whether the decoded value is kept as a continuous float (BGA) or rounded to the nearest integer (IGA).

class sigmaepsilon.math.optimize.bitchromosome.BitChromosomeGeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, maxiter: int = 200, miniter: int = 0, elitism: int | float | None = 1, maxage: int = 5, minimize: bool = False, seed: int | SeedSequence | Generator | None = None, selection_strategy: SelectionStrategy | None = None, vectorized: bool = False, n_jobs: int = 1)[source]#

Shared base for genetic algorithms whose genotype is a flat 0/1 bit chromosome.

The chromosome has length dim * length, decoded into dim scalar phenotypes by linearly scaling each variable’s length-bit segment into its ranges[d] bounds.

This class provides the representation-specific machinery (populate(), crossover(), mutate(), decode()) for any bit-chromosome GA. What varies between concrete subclasses is only how the linearly-decoded scalar is interpreted, which is controlled by the _postprocess_phenotypes() hook:

BinaryGeneticAlgorithm keeps the continuous, floating point value (suitable for real-valued, box-constrained optimization).
IntegerGeneticAlgorithm rounds it to the nearest integer (suitable for boolean or small-integer-domain decision variables).

Note

This class is not meant to be instantiated directly; use one of its concrete subclasses instead.

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 = 0, elitism: int | float | None = 1, maxage: int = 5, minimize: bool = False, seed: int | SeedSequence | Generator | None = None, selection_strategy: SelectionStrategy | None = None, vectorized: bool = False, n_jobs: int = 1)[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.

The class is able to solve unconstrained optimization problems of the form:

\[\begin{split}\\begin{eqnarray} & maximize& \\quad f(\\mathbf{x}) \\quad in \\quad \\mathbf{x} \\in \\mathbf{R}^n. \\end{eqnarray}\end{split}\]

Note

This class is designed for maximizing the objective function. To minimize it, either negate the objective function or pass minimize=True when instantiating the class.

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) – Determines the portion of the population designated as elite, which automatically survives to the next generation. If less than or equal to 1, it specifies a fraction of the population. If greater than 1, it indicates the exact number of individuals to be selected as elite. The default value of 1 assures that the reigning champion is always preserved. To turn this off, det the value to None. Default is 1.
ftol (float, Optional) – Torelance for floating point operations. Default is 1e-12.
maxage (int, Optional) – The age is the maximum number of generations a candidate spends at the top (being the best candidate) before termination. Default is 5.
minimize (bool, Optional) – If True, the objective function is minimized. Default is False.
seed (int | numpy.random.SeedSequence | numpy.random.Generator | None, Optional) – A seed for a per-instance random number generator. Default is None.
selection_strategy (SelectionStrategy, Optional) – The selection strategy used by select(). Default is TournamentSelection.
vectorized (bool, Optional) – See evaluate(). Default is False.
n_jobs (int, Optional) – See evaluate(). 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 as BGA
>>>
>>> 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 = BGA(rosenbrock, ranges, length=12, nPop=100, minimize=True)
>>> _ = bga.solve()
>>> champion = bga.champion
>>> x = champion.phenotype
>>> fx = champion.fitness

Integer Genetic Algorithm (IGA)#

Integer genetic algorithms (IGA) are for problems whose decision variables are natively boolean or small bounded integers (e.g. a 0/1 knapsack indicator vector, or a handful of discrete levels per variable), instead of continuous, box-constrained real numbers. IGA reuses BGA’s bit-chromosome representation and genetic operators, but rounds the decoded value to the nearest integer, which is both the semantically correct representation for discrete variables and cheaper than retaining unneeded floating-point precision.

class sigmaepsilon.math.optimize.iga.IntegerGeneticAlgorithm(fnc: Callable, ranges: Iterable, *, length: int = 5, p_c: float = 1, p_m: float = 0.2, nPop: int = 100, maxiter: int = 200, miniter: int = 0, elitism: int | float | None = 1, maxage: int = 5, minimize: bool = False, seed: int | SeedSequence | Generator | None = None, selection_strategy: SelectionStrategy | None = None, vectorized: bool = False, n_jobs: int = 1)[source]#

An implementation of a Genetic Algorithm (GA) for problems whose decision variables are natively boolean or small bounded integers, e.g. a 0/1 knapsack indicator vector, or a handful of discrete levels per variable.

Like BinaryGeneticAlgorithm, individuals are represented as flat 0/1 bit chromosomes and decoded with the same linear scaling into ranges. The only difference is that the decoded value is rounded to the nearest integer instead of kept as a continuous float, which is both the semantically correct representation for discrete decision variables and cheaper than retaining floating-point precision that the problem doesn’t need.

Note

This class is designed for maximizing the objective function. To minimize it, either negate the objective function or pass minimize=True when instantiating the class.

Note

Choose length so that 2 ** length - 1 comfortably covers the width of the widest range. For pure boolean variables (ranges=[[0, 1]] * dim), length=1 is enough and is the most efficient choice: each gene already encodes exactly the one bit of information that is needed. For a wider integer range, e.g. [0, 6] (7 distinct values), pick length so that 2 ** length - 1 >= 6, e.g. length=3 (8 raw levels, rounded down to the 7 needed).

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) – Integer bounds for each scalar argument to the objective function, e.g. [[0, 1], [0, 1]] for two boolean variables, or [[0, 6]] for a single 7-valued discrete variable.
length (int, Optional) – Chromosome length (bits) per variable. See the note above for sizing guidance. 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 0.
elitism (float or int, Optional) – Determines the portion of the population designated as elite, which automatically survives to the next generation. If less than or equal to 1, it specifies a fraction of the population. If greater than 1, it indicates the exact number of individuals to be selected as elite. The default value of 1 assures that the reigning champion is always preserved. To turn this off, set the value to None. Default is 1.
maxage (int, Optional) – The age is the maximum number of generations a candidate spends at the top (being the best candidate) before termination. Default is 5.
minimize (bool, Optional) – If True, the objective function is minimized. Default is False.
seed (int | numpy.random.SeedSequence | numpy.random.Generator | None, Optional) – A seed for a per-instance random number generator. Default is None.
selection_strategy (SelectionStrategy, Optional) – The selection strategy used by select(). Default is TournamentSelection.
vectorized (bool, Optional) – See evaluate(). Default is False.
n_jobs (int, Optional) – See evaluate(). Default is 1.

Examples

Solve a small 0/1 knapsack problem: pick a subset of items (each either included or excluded) to maximize total value without exceeding a weight budget.

>>> import numpy as np
>>> from sigmaepsilon.math.optimize import IntegerGeneticAlgorithm as IGA
>>>
>>> values = np.array([60, 100, 120, 80, 30])
>>> weights = np.array([10, 20, 30, 15, 5])
>>> capacity = 50
>>>
>>> def knapsack(x):
...     total_weight = np.dot(weights, x)
...     total_value = np.dot(values, x)
...     penalty = 1000 * max(0, total_weight - capacity)
...     return total_value - penalty
>>>
>>> ranges = [[0, 1]] * len(values)
>>> iga = IGA(knapsack, ranges, length=1, nPop=50, seed=0)
>>> champion = iga.solve()
>>> selection = champion.phenotype

Real-Valued Genetic Algorithm (RGA)#

Real-valued genetic algorithms (RGA) operate directly on continuous, real-valued chromosomes instead of a binary encoding, using arithmetic (blend) crossover and Gaussian mutation. This avoids the precision/chromosome-length trade-off of BGA, at the cost of a different exploration behavior.

class sigmaepsilon.math.optimize.rga.RealValuedGeneticAlgorithm(*args, mutation_scale: float = 0.1, **kwargs)[source]#

A real-valued (continuous) Genetic Algorithm (GA).

It finds minimums or maximums of unconstrained problems over box-ranges of continuous variables, without binary encoding.

Unlike BinaryGeneticAlgorithm, individuals are represented directly as real-valued vectors (genotype == phenotype), using arithmetic (blend) crossover and Gaussian mutation. This avoids the precision/length trade-off inherent to binary encoding, at the cost of the different exploration behavior of a continuous representation.

Note

This class is designed for maximizing the objective function. To minimize it, either negate the objective function or pass minimize=True when instantiating the class.

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.
p_c (float, Optional) – Probability of crossover. Default is 1.
p_m (float, Optional) – Probability of mutation (per gene). Default is 0.2.
mutation_scale (float, Optional) – Standard deviation of the Gaussian mutation noise, expressed as a fraction of each variable’s range. Default is 0.1.
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 0.
elitism (float or int, Optional) – Determines the portion of the population designated as elite, which automatically survives to the next generation. If less than or equal to 1, it specifies a fraction of the population. If greater than 1, it indicates the exact number of individuals to be selected as elite. The default value of 1 assures that the reigning champion is always preserved. To turn this off, set the value to None. Default is 1.
maxage (int, Optional) – The age is the maximum number of generations a candidate spends at the top (being the best candidate) before termination. Default is 5.
minimize (bool, Optional) – If True, the objective function is minimized. Default is False.
seed (int | numpy.random.SeedSequence | numpy.random.Generator | None, Optional) – A seed for a per-instance random number generator. Default is None.
selection_strategy (SelectionStrategy, Optional) – The selection strategy used by select(). Default is TournamentSelection.
vectorized (bool, Optional) – See evaluate(). Default is False.
n_jobs (int, Optional) – See evaluate(). 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.rga import RealValuedGeneticAlgorithm as RGA
>>>
>>> def rosenbrock(x):
...     a, b = 1, 100
...     return (a-x[0])**2 + b*(x[1]-x[0]**2)**2
>>>
>>>
>>> ranges = [[-10, 10], [-10, 10]]
>>> rga = RGA(rosenbrock, ranges, nPop=100, minimize=True)
>>> _ = rga.solve()
>>> champion = rga.champion
>>> x = champion.phenotype
>>> fx = champion.fitness