1. Core Concepts and Principles
Definition and Inspiration
A Genetic Algorithm (GA) is a search and optimization method based on the concepts of natural selection and genetics. GAs are a subset of the broader field of Evolutionary Computation. The methodology was developed by John Holland and his colleagues at the University of Michigan, including David E. Goldberg.
The core principle involves maintaining a population of possible solutions to a problem. These solutions undergo processes analogous to biological evolution, such as recombination (crossover) and mutation, to produce new “children” or solutions. Each candidate solution is assigned a fitness value, and individuals with higher fitness are more likely to be selected to “mate,” propagating their characteristics to subsequent generations. This process embodies the Darwinian concept of “Survival of the Fittest,” evolving progressively better solutions over time. While randomized, GAs outperform simple random search by effectively exploiting historical information.
The Optimization Problem
Optimization is the process of finding the best possible outcome by adjusting a set of inputs to maximize or minimize one or more objective functions. The entire set of possible solutions constitutes the “search space.” The goal of an optimization algorithm is to efficiently search this space to find the point or set of points that yield the optimal solution. GAs are designed to navigate vast and complex search spaces to locate these optimal or near-optimal solutions.
Fundamental Process and Terminology
The basic structure of a GA operates through an iterative loop that mimics evolution. The process begins with an initial population of solutions and continues until a termination criterion is satisfied.
Generalized GA Pseudo-code:
GA()
initialize population
find fitness of population
while (termination criteria is not reached) do
parent selection
crossover with probability pc
mutation with probability pm
decode and fitness calculation
survivor selection
find best
return best
Basic Terminology:
| Term | Description |
| Population | A subset of all possible encoded solutions to the problem in the current generation. |
| Chromosome | A single candidate solution to the problem. |
| Gene | An individual element or position within a chromosome. |
| Allele | The specific value a gene takes for a particular chromosome. |
| Genotype | The representation of the population in the computational space, often in a format easily manipulated by a computer (e.g., a binary string). |
| Phenotype | The representation of the population in the actual real-world solution space. |
| Encoding/Decoding | The process of transforming a solution between the phenotype (real-world) and genotype (computational) spaces. Fast decoding is crucial as it is performed repeatedly. |
| Fitness Function | A function that takes a candidate solution as input and outputs a measure of its suitability or “fitness.” It quantifies how good a solution is. |
| Genetic Operators | The mechanisms that alter the genetic composition of offspring, such as crossover, mutation, and selection. |