Evolutionary Algorithms: A Gentle Introduction to Problem Solving, Inspired by Nature

marcel blattner | May, 2025

Motivation for this blog post

DeepMind's recent system, AlphaEvolve, demonstrates a sophisticated approach to autonomous algorithm discovery and optimization. A core component of AlphaEvolve's methodology is its strategic use of Evolutionary Algorithms. This application highlights the continued significance of EAs and serves as the impetus for this blog post exploring their principles and capabilities.

Introduction

Evolutionary Algorithms (EAs) represent a fascinating branch of artificial intelligence and computer science, drawing their core inspiration from the processes of biological evolution to tackle complex problems. Rather than depending on precisely defined instructions to reach a solution, EAs employ a simulated version of "survival of the fittest." Through this mechanism, they iteratively refine a collection of potential solutions, gradually guiding them towards a satisfactory outcome. This introduction offers an accessible overview of how EAs function, particularly for those curious about their inner workings, and will be supported by simple illustrative program examples.

You can download example code to play with evolutionary algorithm here https://github.com/marcelbtec/evolvalgo

Historical Notes

The field of Evolutionary Algorithms (EAs) emerged from pioneering work in the mid-20th century, with several key threads developing independently before coalescing. Early conceptual work, such as Alan Turing's unpublished ideas on "genetical or evolutionary search" in 1948, hinted at the potential, but the field truly began to take shape in the 1950s and 1960s.

During this period, Evolutionary Programming was introduced by Lawrence J. Fogel in the U.S. (circa 1960-1966), initially focusing on evolving finite state machines for prediction and control tasks. Almost concurrently in Germany, Ingo Rechenberg and Hans-Paul Schwefel developed Evolution Strategies (circa 1964-1965), which used mutation and selection on vectors of real numbers, initially for engineering optimization problems like fluid dynamics, even before widespread computer use.

John Holland's work in the U.S. during the 1960s and formalized in his 1975 book, "Adaptation in Natural and Artificial Systems," established Genetic Algorithms, emphasizing binary string representations, crossover as a key operator, and the theoretical underpinnings of schema processing. For a period, these approaches evolved largely in parallel. It wasn't until the early 1990s that Genetic Programming, championed by John Koza (around 1992), emerged as a distinct branch focused on evolving computer programs, often represented as tree structures.

By the 1990s, the similarities between these different streams became more apparent, leading to the unifying term "Evolutionary Computation" and fostering greater cross-pollination of ideas, including the development of more sophisticated techniques for handling constraints, multi-objective optimization, and parameter self-adaptation (like the Covariance Matrix Adaptation Evolution Strategy, CMA-ES, developed by Hansen and Ostermeier starting in the mid-1990s), which significantly advanced the field's capabilities and practical applications.

The Core Idea: Mimicking Natural Selection

At its heart, biological evolution operates on a few fundamental principles. Firstly, individuals within any population exhibit variation in their traits. Secondly, these traits are heritable, meaning they can be passed down from parents to their offspring. Thirdly, the principle of selection dictates that individuals possessing traits more advantageous for their environment have a higher likelihood of surviving and reproducing, thereby passing on those beneficial traits. Finally, given sufficient time, this iterative process can lead to profound changes within a population, effectively adapting it to its prevailing environmental conditions.

Evolutionary Algorithms ingeniously adapt these natural principles to the domain of computation. In this context, instead of dealing with biological organisms, we work with candidate solutions to a given problem. These solutions are encoded in a specific format that allows them to be metaphorically "bred" and "mutated." A crucial component is the fitness function, which acts as the computational equivalent of the environment; it evaluates and quantifies how effective or "good" each candidate solution is.

The Main Components and Workflow of an Evolutionary Algorithm

Understanding an Evolutionary Algorithm involves familiarizing oneself with its key components and the typical sequence of operations. The entire process is iterative, with each cycle, or generation, aiming to produce better solutions.

Representation (or Encoding)

The first critical step is Representation (or Encoding). This defines how a potential solution to the problem is structured in a way that a computer can manipulate. The choice of representation is fundamental, as it directly influences how genetic operators like crossover and mutation will be applied. Common representations include strings of numbers (which can be binary, integer, or real-valued), tree structures (often used in genetic programming to represent programs or expressions), or more complex data structures tailored to specific problem domains. This encoded form of a solution is often metaphorically termed a "chromosome" or "genotype." For instance, if we aimed to find the maximum value of a simple mathematical function, such as $f(x)=−(x−5)^2+100$ for integer values of $x$ between 0 and 15, we could represent a candidate solution (an 'x' value) as a 4-bit binary string. The string $0101$ would represent $x=5$, and $1111$ would correspond to $x=15$.

Once a suitable representation is chosen, the algorithm proceeds with Initialization. This involves creating an initial population of candidate solutions. Typically, this first generation of solutions is generated randomly to ensure a diverse starting point for the evolutionary search. The size of this population is an important parameter that can affect the algorithm's performance and its ability to explore the solution space.

Fitness Evaluation

Following initialization, each individual in the current population undergoes Fitness Evaluation. A fitness function is applied to every candidate solution to quantify its quality or effectiveness in solving the problem at hand. This function is problem-specific and encapsulates the goal of the optimization. The general objective is usually to find individuals that maximize this fitness value, although in some problem formulations, minimization might be the target. The fitness score guides the selection process. Continuing with our example function $f(x)=−(x−5)^2+100$

In this scenario, an individual representing $x=5$ (e.g., [0,1,0,1]) would achieve the maximum fitness of $100$, while an individual representing $x=0$ (e.g., [0,0,0,0]) would have a fitness of $−(0−5)^2 +100=−25+100=75$.

Selection

The next crucial step in the cycle is Selection. Based on their calculated fitness values, individuals are chosen from the current population to act as "parents" for the subsequent generation. The core idea is that individuals with higher fitness scores have a greater probability of being selected, thus propagating their desirable traits. Various selection methods exist, each with different characteristics. Common examples include Roulette Wheel Selection, where each individual is allocated a portion of a metaphorical roulette wheel proportional to its fitness, and the "spin" of the wheel determines a parent. Another widely used method is Tournament Selection, where a small subset of individuals is randomly chosen from the population, and the fittest among this subset is selected as a parent. This process is typically repeated until enough parents are determined to create the next generation.

Once parents are selected, Reproduction occurs to create "offspring" that will form the basis of the new generation. This usually involves two primary genetic operators: Crossover (or Recombination) and Mutation. Crossover aims to combine the genetic material from two parent individuals to generate one or more offspring. The idea is that by combining parts of good solutions, even better solutions might be formed. For solutions represented as binary strings, a common technique is one-point crossover: a random point is selected within the string, and the segments of the parent strings beyond this point are swapped to create two new offspring. Other crossover methods like two-point or uniform crossover also exist.

Mutation, on the other hand, introduces small, random alterations to an offspring's genetic material after crossover (or sometimes directly to a selected parent if no crossover occurs). In the case of binary strings, mutation might involve flipping a randomly chosen bit (changing a 0 to a 1, or vice versa). For real-valued representations, mutation might involve adding a small random number to a gene. Mutation plays a vital role in maintaining genetic diversity within the population and provides the means to introduce new genetic material, which helps prevent the algorithm from converging prematurely to a suboptimal solution and allows exploration of new areas of the search space.

The crossover_rate parameter governs the probability that two selected parents will indeed undergo crossover, while the mutation_rate controls how often mutations occur per gene or per individual. Fine-tuning these rates, often empirically, is important for the algorithm's effective performance.

The newly created offspring then contribute to the Replacement strategy, which determines how the population for the next iteration (or generation) is formed. Various replacement schemes exist. For example, in a generational EA, the new offspring might replace the entire old population. Alternatively, steady-state EAs replace only a few members of the population at a time. A common and often beneficial strategy incorporated into replacement is elitism. With elitism, the best-performing individual (or a small number of top individuals) from the current generation are guaranteed to be carried over, unchanged, into the next generation. This ensures that the best solutions found so far are not lost due to the stochastic nature of selection, crossover, or mutation.

Finally, the cycle of evaluation, selection, reproduction, and replacement continues until a predefined Termination criterion is met. This criterion signals the end of the evolutionary search. Common termination conditions include reaching a maximum number of generations, or the algorithm might stop if a solution of sufficient quality (i.e., a fitness value exceeding a certain threshold) has been found. Another approach is to monitor the population's diversity or the improvement in fitness; if the best fitness score has not shown significant improvement over a certain number of consecutive generations, the algorithm might terminate, assuming it has converged or is unlikely to find better solutions with further computation.

The Evolutionary Cycle - A Simplified Flowchart

START
 |
Initialize Population (random solutions)
 |
LOOP (for a number of generations OR until termination condition is met)
 |
 |--> Evaluate Fitness of each individual
 |       |
 |
 |     Select Parents (based on fitness)
 |       |
 |      
 |     Perform Crossover and Mutation (to create offspring)
 |       |
 |      
 |     Replace old population with new generation (possibly with elitism)
 |
END LOOP
 |
 
Output: Best solution found

A Very Simple "Full" (Conceptual) Example

To see how these components might interlock, let's outline a conceptual EA for our ongoing problem of maximizing $f(x)=−(x−5)^2+100$.

(Note on the full example): This is a highly simplified EA. Practical EAs frequently employ more sophisticated selection mechanisms, crossover and mutation operators, and often require more intricate parameter tuning. For the straightforward problem used here, an EA is arguably an overly complex tool, but it effectively illustrates the fundamental process. One might observe it rapidly converging towards [0,1,0,1] (which represents $x=5$).

You can find the solution to this simple problem here: https://github.com/marcelbtec/evolvalgo

Why Opt for Evolutionary Algorithms?

Evolutionary Algorithms demonstrate particular strength and utility in several kinds of situations. They are especially well-suited when the problem at hand is characterized by high complexity, meaning the space of all possible solutions is so vast that searching through it exhaustively is computationally infeasible.

EAs are also valuable when the fitness landscape is rugged, containing numerous local optima, which are good solutions but not the absolute best global optimum. The population-based nature of EAs, coupled with the exploratory effect of mutation, often allows them to escape these local traps and continue searching for better solutions.

Furthermore, EAs can be a good choice when a clear deterministic algorithm to find the solution is unknown or difficult to formulate. They also tend to find robust solutions, which are solutions not overly sensitive to minor alterations in the problem's parameters. Additionally, EAs can be effectively adapted to tackle problems with multiple conflicting objectives, where the goal is to find a set of solutions that represent good trade-offs among these objectives.

Diverse Forms of Evolutionary Algorithms

While the underlying principles of variation, selection, and inheritance remain consistent, several distinct "flavors" of Evolutionary Algorithms have been developed over time. These variants are often tailored to specific types of problems or particular ways of representing solutions.

Genetic Algorithms (GAs), for example, typically use binary string representations for solutions and strongly emphasize crossover and mutation operators; this is often the type that first comes to mind when people hear the term "evolutionary algorithms." In contrast, Evolution Strategies (ES) frequently work with vectors of real-valued numbers and tend to emphasize mutation as the primary search operator, often incorporating mechanisms for self-adapting mutation rates.

Genetic Programming (GP) takes a unique approach by evolving actual programs, which are commonly represented as tree structures, to have these programs perform a specific desired task. Lastly, Evolutionary Programming (EP) shares similarities with Evolution Strategies. Still, it focuses on evolving individuals based on their expressed behavior rather than directly manipulating their genetic makeup, typically without employing a crossover operator. Each of these, and other specialized EAs, offers different strengths for different problem domains.

Considering Strengths and Limitations

Evolutionary Algorithms present a compelling set of advantages. Their wide applicability allows them to be used for a broad spectrum of problems across various fields. They are particularly good at global search, meaning they are generally less likely to become permanently stuck in local optima compared to some other optimization techniques. EAs can also effectively handle situations involving noisy or incomplete information, and their inherent parallelism is a significant benefit, as the fitness of many individuals in a population can often be evaluated independently and simultaneously, speeding up the process on multi-core processors or distributed systems. Perhaps one of their most intriguing strengths is their ability to discover novel and creative solutions that human designers might not have readily conceived.

However, it is also important to acknowledge their limitations. EAs can be computationally intensive, often requiring many fitness evaluations, which can translate to significant processing time, especially for complex fitness functions. Their performance can also be quite sensitive to the choice of various parameters, such as population size, mutation rate, and crossover rate; finding the optimal set of parameters for a given problem often requires careful tuning and experimentation. There is generally no guarantee that an EA will find the absolute optimal solution within a finite timeframe, although they very often succeed in finding very high-quality and practically useful solutions. Furthermore, the task of designing an effective representation for the solutions and an appropriate fitness function can itself be a challenging endeavor for certain types of problems. Finally, the "No Free Lunch" theorem in optimization reminds us that no single optimization algorithm is universally superior for all possible problems; an EA that is well-suited for one specific problem might perform poorly on another.

‍

References

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. (Reprinted by MIT Press, 1992).

Mitchell, M. (1996). An Introduction to Genetic Algorithms. MIT Press.

Eiben, A. E., & Smith, J. E. (2015). Introduction to Evolutionary Computing (2nd ed.). Springer.

De Jong, K. A. (2006). Evolutionary Computation: A Unified Approach. MIT Press.

Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press.

Luke, S. (2013). Essentials of Metaheuristics (Online, freely available).