Skip to content

Genetic Algorithm

Introduction

A genetic algorithm mimics natural selection by evolving a population of candidate solutions through processes akin to biological reproduction and mutation. Each candidate is evaluated using a fitness function, and the best-performing solutions are selected to create new candidates through crossover and mutation. This iterative process enables the algorithm to explore and exploit the solution space, making it particularly useful for complex or discontinuous landscapes where gradient-based methods fail.

Example

from gradient_free_optimizers import GeneticAlgorithmOptimizer

...

opt = GeneticAlgorithmOptimizer(search_space, mutation_rate=0.4, n_parents=3)
opt.search(objective_function, n_iter=100)

About the implementation

The genetic algorithm optimizer works similar to the evolution strategy, in that both do an mutation or crossover step in each iteration. The probability of doing each is determined by the mutation and crossover rate.

Parameters

population

Size of the population for population-based optimization algorithms. A member of the population is called single optimizer, individual or particle depending on the type of algorithm. Each member of the population is a separate optimizer class with information about the positions and scores of the optimizer and all methods to perform the iteration and evaluation steps.

All population based optimizers in this package calculate the new positions one member at a time. So if the optimizer performs 10 iterations and has a population size of 10, then each member of the population would move once to a new position.

  • type: int
  • default: 10
  • typical range: 4 ... 25

mutation_rate

The mutation rate is a parameter in genetic algorithms that specifies the probability of randomly altering the value of a gene in a chromosome. Mutation helps in maintaining genetic diversity within the population and prevents the algorithm from getting stuck in local optima.

\[ x'_i = \begin{cases} x_i & \text{if } \text{rand} > p_m \\ 1 - x_i & \text{if } \text{rand} \leq p_m \end{cases} \]
  • type: float
  • default: 0.5
  • typical range: 0.0 ... 1.0

crossover_rate

The crossover rate is a parameter in genetic algorithms that determines the probability with which crossover (recombination) occurs between pairs of parent chromosomes. It controls how often parts of the parent chromosomes are exchanged to produce offspring. A higher crossover rate increases the diversity of the offspring, which can help in exploring the solution space more effectively.

\[ u_{i,j}^{(g)} = \begin{cases} v_{i,j}^{(g)} & \text{if } \text{rand}_j \leq C_r \text{ or } j = j_{\text{rand}} \\ x_{i,j}^{(g)} & \text{otherwise} \end{cases} \]
  • type: float
  • default: 0.5
  • typical range: 0.0 ... 1.0

n_parents

The number of parents in a genetic algorithm refers to the number of chromosomes selected from the current population to participate in the crossover process. Usually, pairs of parents are selected to generate new offspring. If the population size is 𝑁N, typically 𝑁/2 N/2 pairs of parents are chosen in each generation.

  • type: int
  • default: 2
  • typical range: 2 ... 5

offspring

The number of offspring refers to the number of new chromosomes generated in each generation through the processes of crossover and mutation. Typically, the number of offspring is equal to the population size, ensuring that the population size remains constant over generations.

  • type: int
  • default: 10
  • typical range: 10 ... 20