Skip to content
STIMSMITH

Genetic Algorithms

Technique WIKI v1 · 6/27/2026

Genetic Algorithms (GAs) are a class of optimization and search heuristics inspired by the principle of natural selection. They are particularly useful for combinatorial problems with large search spaces where no tractable algorithm is available, and they have been applied across software testing, default reasoning, and automated program generation.

Overview

Genetic Algorithms (GAs) are a family of population-based search and optimization techniques inspired by the biological process of natural selection. They operate by evolving a population of candidate solutions through selection, crossover, and mutation operators, favoring individuals with higher fitness over successive generations. GAs are especially suited to problems characterized by huge search spaces and the absence of tractable exact algorithms.

Characteristics

  • Stochastic by nature: GAs incorporate randomness in population initialization, selection, crossover, and mutation, which means that outputs for the same input may differ between runs.
  • Unknown ground-truth outputs: Because of this stochasticity, it is often difficult to specify known expected outputs for test cases.
  • Generalizability: Some design principles and metamorphic relations transfer across different types of evolutionary algorithms.

Applications

Combinatorial Optimization and Default Reasoning

GAs have been successfully applied to combinatorial problems. In the context of Default Logic — whose extension-finding problem is Σ₂ᴾ-complete and thus intractable for non-trivial knowledge bases — GA-based techniques have been used to build efficient default reasoning systems. A formal description of the components required for an extension search based on GA principles has been proposed, along with supporting experimental results.

Software Testing

Although GAs themselves are widely used to aid software testing (for example, in test data generation), testing GA implementations poses unique challenges due to stochasticity and the lack of known outputs. Statistical metamorphic testing has been proposed as a solution, identifying 17 metamorphic relations for testing GAs. Mutation testing has shown these relations to be more effective at finding defects than traditional unit tests based on known outputs. Three of the system-level relations were observed to fail excessively across fitness functions and were subsequently refined to reduce their failure rates.

Automated Program Generation

GAs have also served as the foundation for program generation tools. The proGenesys system, presented at the 1999 International Conference on Artificial Intelligence, applies genetic-system principles to program generation, with applications that include embedded systems design.

Testing Considerations

When testing a GA implementation, the following practical considerations have been identified:

  • Use of metamorphic relations rather than known-output assertions, since outputs are not deterministic.
  • Statistical evaluation of results is required to distinguish genuine defects from acceptable stochastic variation.
  • Cross-implementation comparison of mutation scores can be used to validate that the metamorphic relations generalize across different GA implementations.

Related Algorithmic Family

GAs are a specific instance of evolutionary algorithms, a broader family of population-based metaheuristics that share the same high-level structure of iterated selection and variation.

LINKED ENTITIES

2 links
Evolutionary Algorithms is_a
proGenesys instantiated_by

CITATIONS

7 sources
7 citations
[1] Genetic Algorithms are inspired by the principle of natural selection and have been applied to combinatorial problems with huge search spaces where no tractable algorithm is available. Genetic Algorithms for Extension Search in Default Logic
[2] Statistical metamorphic testing has been applied to Genetic Algorithms by identifying 17 metamorphic relations, which are more effective at finding defects than traditional unit tests based on known outputs. Systematic Testing of Genetic Algorithms: A Metamorphic Testing based Approach
[3] Three system-level metamorphic relations for GAs were found to fail excessively across fitness functions and were subsequently modified to reduce their failure rates. Systematic Testing of Genetic Algorithms: A Metamorphic Testing based Approach
[4] Some metamorphic relations identified for Genetic Algorithms are generalizable across different types of evolutionary algorithms, and produced similar mutation scores between two implementations. Systematic Testing of Genetic Algorithms: A Metamorphic Testing based Approach
[5] GAs have been used to build an efficient default reasoning system, with a formal description of the components required for an extension search based on GA principles and supporting experimental results. Genetic Algorithms for Extension Search in Default Logic
[6] proGenesys is a program generation tool based on genetic-system principles, presented at the 1999 International Conference on Artificial Intelligence, with applications including embedded systems design. proGenesys-Program Generation Tool Based on Genetic Systems
[7] GAs are inherently stochastic in initialization, selection, crossover, and mutation, leading to non-deterministic outputs for the same input. Systematic Testing of Genetic Algorithms: A Metamorphic Testing based Approach