Overview
Evolutionary Algorithms (EAs) are a family of population-based metaheuristic optimization methods that draw inspiration from mechanisms of biological evolution, such as selection, mutation, recombination, and fitness-based survival. They have been applied to a wide variety of scientific and engineering problems across numerous disciplines over several decades, and are widely recognized for their flexibility and versatility.
Characteristics
- Population-based search: EAs operate on a population of candidate solutions rather than a single point, exploring the search space in parallel.
- Evaluation-driven: Progress is guided by a fitness function that evaluates each candidate solution.
- Evaluation cost: EAs typically require a large number of solution evaluations to converge. This can make them slow and expensive when individual evaluations are costly (e.g., for complex software engineering models).
- Stochastic operators: Mutation and crossover/recombination introduce variability into the population over successive generations.
Applications
Search-Based Software Engineering (SBSE)
In search-based software engineering, EAs are commonly used to optimize software-related artifacts (models, configurations, test suites, etc.). Because traditional EAs can require many evaluations to converge on complex SE models, alternative approaches have been explored. For example, research has shown that, by building a very large initial population and then culling it using a recursive bi-clustering chop approach, comparable results to state-of-the-art EAs can be obtained using just a few evaluations (under 100) on multiple SE models, both unconstrained and constrained. The takeaway from this line of work is that practitioners undertaking search-based SE optimization tasks using traditional EAs should consider trying other techniques that may yield equivalent results with fewer evaluations.
Automated Theorem Proving
EAs have been investigated as a means of automatically generating formal proofs, leveraging their role as program generators combined with proof assistants as proof verifiers. Drawing on the BHK interpretation and the Curry–Howard isomorphism (under which proofs correspond to programs), researchers have used EAs to evolve proof terms and have them checked by proof assistants such as Coq. In one reported study, ten simple theorems from various branches of mathematics were proved using this approach, most of which could not be proved using the auto tactic alone in Coq. The work was released as open source along with the obtained experimental results.
Program Generation and Embedded Systems
The proGenesys tool applies a genetic-systems-based approach — a form of evolutionary algorithm — to program generation, with applications including embedded systems design techniques. The underlying paper, proGenesys — Program Generation Tool Based on Genetic Systems (Vili Podgorelec, International Conference on Artificial Intelligence, 1999), is categorized under the topics of Evolutionary Algorithms and Applications, Embedded Systems Design Techniques, and programming language.
Relation to Genetic Algorithms
Genetic Algorithms (GAs) are a well-known subclass of evolutionary algorithms that specifically use genetic-inspired operators (selection, crossover, mutation) on chromosome-like representations. The proGenesys tool is explicitly described as being "based on genetic systems," placing it within this GA-flavored branch of the EA family.