Genetic Algorithm

Genetic Algorithms (GA) were among the first evolutionary algorithms and were originally conceived not for optimization but as a tool to study adaptive systems (Simon, 2013, p. 35).

History

Several individuals contributed to the development of GAs:

Nils Barricelli, an Italian-Norwegian mathematician, was not interested in biology or optimization but aimed to create artificial life in computers using natural processes like mutation and reproduction (Barricelli, 1954).
Alexander Fraser and James Barker, as biologists, were interested in biological evolution, which they could not observe directly and thus sought to simulate using computers (Fraser, 1957a, 1957b; Barker, 1958; Fraser, 1960).

Binary Genetic Algorithm

Recall the Hill-Climbing Algorithm: we sought to minimize a function \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) by finding a vector \(x \in \mathbb{R}^n\) such that \(f(x)\) is minimized.

Note

TODO Hill Climbing

Continuous Genetic Algorithm

The basic structure of a Genetic Algorithm can be expressed in pseudocode (Simon, 2013, p. 50):

Require: p_m (mutation rate)
Population ← {NP random individuals x_i}
while not termination criterion do
    Determine fitness f(x_i) for each individual in Population
    Children ← ∅
    while |Children| < |Population| do
        Select pair x_j, x_k from Population for reproduction
        Generate children v_1, v_2 from x_j, x_k
        Children ← Children ∪ (v_1, v_2)
    end while
    Mutate Children randomly with probability p_m
    Population ← Children
end while

Key Components of the Algorithm:

Initialization (Line 1): The random initialization of the population determines the search space of the algorithm, significantly influencing its runtime. A search space that is too large may slow convergence, while one that is too small may limit the algorithm’s potential to find solutions.
Termination Criterion (Line 2): Typically, this is either a maximum number of generations or an error threshold that the best solution must meet.
Fitness Evaluation (Line 3): The fitness function evaluates the suitability of a solution candidate and returns a corresponding fitness value. For minimization problems, the term cost function is often used instead of fitness function. Both are types of objective functions (Simon, 2013, p. 13):

\[ \begin{align}\begin{aligned}\min_x f(x) \Rightarrow f(x) \text{ is a cost function or objective function}\\\max_x f(x) \Rightarrow f(x) \text{ is a fitness function or objective function}\end{aligned}\end{align} \]
Selection (Line 6): The selection of parent pairs for reproduction is often proportional to their fitness. Individuals closer to an optimal solution have a higher probability of being selected. The number of parents can also vary (Simon, 2013, pp. 128ff).
Reproduction (Line 7): Children are generated by combining the vectors of two parents, often element-wise and randomly (Simon, 2013, pp. 209ff).
Mutation (Line 10): Each child is mutated with a probability \(p_m\). If selected, a random position in the genome is altered. The mutation can be constrained to a small range or span the entire permissible range of the vector element (Simon, 2013, pp. 214ff).
Elitism: In Line 11, the new population consists entirely of children. However, the concept of elitism ensures that the fittest individuals from the parent generation are carried over to the next generation unchanged. This prevents the loss of high-quality solutions and ensures convergence. Without elitism, GAs may behave like a random walk (Rudolph, 1994).

The algorithms described here use direct encoding, meaning the encoded “genome” is the solution itself. In nature, genes (genotype) are translated by RNA into proteins (phenotype). This principle is also applied in GAs, such as when evolving artificial neural networks (ANNs), as demonstrated later with the NEAT algorithm.

Note

TODO NEAT