A firm grasp of the core vocabulary of Genetic Algorithms is essential for understanding both their mechanics and the broader academic literature on the subject. This section provides the foundational lexicon that underpins the entire GA process.

Basic Terminology

• Population: A set of candidate solutions to the given problem. Its role is to serve as the pool of genetic material from which the GA evolves better solutions over time.
• Chromosome: A single candidate solution. Its role is to represent one complete, potential answer to the problem being solved.
• Gene: A single element or position within a chromosome. Its role is to correspond to a specific component or parameter of the overall solution.
• Allele: The specific value a gene holds for a particular chromosome. Its role is to represent the specific setting or choice for a given solution component.
• Genotype: The solution’s representation in the computational space (e.g., as a binary string). Its role is to provide an encoded format that the computer can manipulate through genetic operators.
• Phenotype: The solution’s representation in the real-world problem space. Its role is to provide the actual, decoded solution that can be applied to the problem and evaluated.

The Genotype-Phenotype Relationship

The relationship between the genotype and phenotype is crucial. Encoding is the process of transforming a solution from its real-world phenotype into its computational genotype. Conversely, Decoding transforms the genotype back into the phenotype so its quality can be evaluated.

Consider the 0/1 Knapsack Problem, where the goal is to select a subset of items to maximize total profit without exceeding a weight capacity.

• The phenotype is the list of items to be picked.
• The genotype can be a binary string where each bit corresponds to an item. A 1 at a position means the item is picked, and a 0 means it is not.

The decoding process must be computationally fast, as it is executed for every individual in every generation during fitness calculation.

Key Algorithmic Components

• Fitness Function: A function that takes a solution as input and produces a quantitative measure of its suitability or quality as output. It is the mechanism that guides the GA’s search.
• Genetic Operators: The core mechanisms that alter the genetic composition of the population. These include selection, crossover, and mutation.

Basic Structure of a GA

The lifecycle of a Genetic Algorithm follows a clear, iterative structure that mimics the process of evolution:

1. Initialize Population: Create an initial set of candidate solutions, often randomly.
2. Calculate Fitness: Evaluate the fitness of each individual in the population.
3. Loop until termination criteria are met: a. Parent Selection: Select individuals from the current population to be parents for the next generation. b. Crossover: Apply the crossover operator with probability pc to the selected parents to create new offspring. c. Mutation: Apply the mutation operator with probability pm to the new offspring. d. Decode and Fitness Calculation: Decode the new offspring and calculate their fitness values. e. Survivor Selection: Replace individuals in the old population with the new offspring to form the next generation’s population.
4. Find Best: Identify the best solution found during the run.
5. Return Best: Output the best solution.

This process—initialization, selection, reproduction, and replacement—works in a continuous loop. Over many generations, the interplay of these steps guides the population toward progressively better solutions, effectively “evolving” an answer to the problem.

We have now defined the core architecture of a GA. The next logical step is to explore one of the most critical design decisions: how to represent a solution as a chromosome.