Genetic Algorithms#
Genetic algorithms (GAs) are a type of meteheuristic optimization algorithm inspired by the principles of natural selection and genetics. They are used to find approximate solutions to complex problems by mimicking the process of evolution. In a genetic algorithm, a population of potential solutions (individuals) is evolved over successive generations. Each individual is evaluated based on a fitness function, and the best-performing individuals are selected to create offspring through processes like crossover (recombination) and mutation. Over time, the population evolves toward better solutions. Genetic algorithms are particularly useful for solving problems with large, complex search spaces where traditional optimization methods might struggle. They are widely used in areas such as engineering, computer science, and artificial intelligence. The class is designed to align with the ‘survival of the fittest’ principle by default, prioritizing maximization.
Binary Genetic Algorithm (BGA)#
A widely used variation is the binary genetic algorithm (BinaryGeneticAlgorithm), in which each candidate solution is represented as a sequence of binary digits (0s and 1s). In this encoding, each bit (gene) represents a specific attribute or decision variable of the solution, and the entire set of genes for an individual within the population forms a genom (Genom).
We will demonstrate the efficiency of the BGA by minimizing the Rosenbrock function, a widely used benchmark problem for evaluating the performance of nonlinear programming methods.
from sigmaepsilon.math.optimize import BinaryGeneticAlgorithm as BGA
from typing import Iterable
from numbers import Number
def Rosenbrock(x: Iterable[Number], a: Number = 1, b: Number = 100) -> float:
return (a - x[0]) ** 2 + b * (x[1] - x[0] ** 2) ** 2
ranges = [[-2, 2], [-1, 3]]
bga = BGA(Rosenbrock, ranges, length=12, nPop=100, minimize=True, maxage=20)
To solve the problem, call the solve method, which returns an instance of Genom.
result = bga.solve()
type(result), result.phenotype, result.fitness
You can get a more detailed view about the actual state of the optimizer by accessing the state attribute of the instance.
bga.state
This has a to_scipy method, if you prefer to see an instance of scipy.optimize.OptimizeResult here.
bga.state.to_scipy()
If you want, you can have more control over the iterations using the evolve method, that runs a specified amount of evolutions:
import matplotlib.pyplot as plt
bga = BGA(Rosenbrock, ranges, length=12, nPop=100, minimize=True)
history = [Rosenbrock(bga.best_phenotype())]
for _ in range(100):
bga.evolve(1)
history.append(bga.champion.fitness)
plt.plot(history)
plt.title('History of the best solution')
plt.show()
x = bga.champion.phenotype
fx = bga.champion.fitness
print(f"The minimum value is f(x) = {fx} at x = {x}.")
import numpy as np
import matplotlib.pyplot as plt
# Generate grid data
x = np.linspace(-2, 2, 400)
y = np.linspace(-1, 3, 400)
X, Y = np.meshgrid(x, y)
Z = np.array([[Rosenbrock([xi, yi]) for xi, yi in zip(row_x, row_y)] for row_x, row_y in zip(X, Y)])
# Create the plot with contour lines
plt.figure(figsize=(8, 6))
levels = [0, 1, 5, 10, 20, 50, 100, 200, 500, 800]
contour = plt.contour(X, Y, Z, levels=levels, cmap='viridis')
plt.clabel(contour, inline=True, fontsize=8)
plt.title('Rosenbrock Function with Contour Lines')
plt.xlabel('x')
plt.ylabel('y')
x = result.phenotype
plt.scatter(x[0], x[1], color="red", s=100, marker='s', label="BGA")
plt.scatter(1, 1, color="green", s=100, marker='^', label="MIN")
plt.legend()
plt.show()
For reproducible runs, or to run several independent instances in the same process, pass a seed to the constructor; this seeds a per-instance random number generator used for every stochastic operation (population initialization, crossover, mutation, selection) instead of the global NumPy random state:
bga_1 = BGA(Rosenbrock, ranges, length=12, nPop=100, minimize=True, seed=0)
bga_2 = BGA(Rosenbrock, ranges, length=12, nPop=100, minimize=True, seed=0)
result_1 = bga_1.solve()
result_2 = bga_2.solve()
result_1.phenotype == result_2.phenotype