7 Genetic Algorithm

This chapter introduces genetic algorithms as a central member of population-based metaheuristics, contrasting their multi-agent, exploration-oriented search with single-trajectory, exploitation-heavy methods. It classifies population metaheuristics into evolutionary computation and swarm intelligence, focusing on the former as the conceptual foundation of GAs. A strong emphasis is placed on how the diversity and quality of the initial population shape performance, surveying practical sampling strategies—pseudo- and quasi-random sequences, Sobol and Latin hypercube designs, and Gaussian-inspired methods—to balance exploration and exploitation from the outset.

Building on biological evolution, the chapter distills evolutionary computation into five core components: a population of candidate solutions, a fitness function, parent selection, genetic operators (crossover and mutation), and survival strategies. It surveys major EC paradigms (GA, DE, GP, EP, ES, CA, and co-evolution) and discusses advantages (domain-agnostic flexibility, interpretability, multiple alternatives, and natural parallelism) alongside limitations (computational cost, tuning needs, and lack of optimality guarantees). Practical GA design choices are covered in depth: encoding schemes (binary, real, permutation), transforming minimization to maximization, and selection with calibrated selective pressure (elitism, fitness-proportionate/roulette, rank-based linear and non-linear, stochastic universal sampling, tournament, and random). Survivor selection and population update models (generational vs steady-state) complete the algorithmic picture.

The chapter then operationalizes GA: initialize a population, evaluate fitness, select parents, recombine via 1-point, n-point, or uniform crossover, inject diversity with mutation, repair infeasible offspring when needed, and terminate on common criteria (evaluation budget, threshold attainment, stagnation, or resource limits). A binary-coded case study (ticket pricing) demonstrates end-to-end design—from bit-length determination and sampling to selection, reproduction, and survivor choice—showing GA converging to the same solution as a classical optimizer. Implementation is presented both from scratch in Python and with a modern framework (pymoo), highlighting practical elements such as sampling operators, crossover/mutation choices, feasibility repair, duplicate elimination, and parameterization (population size, probabilities). The result is a clear, hands-on blueprint for applying GAs to discrete and continuous optimization problems.

Metaheuristics algorithms

Sampling methods to generate initial population

Generate random initial routes

Genotype, phenotype and taxonomic classification

EC Paradigms

Genetic Algorithm versus Natural Evolution

GA Steps

Equation 7.1

Equation 7.2

Binary Encoding

Selection methods with their selective pressure

Equation 7.4

Roulette wheel of ticket pricing example

Equation 7.5

Equation 7.6

Stochastic Universal Sampling (SUS) strategy

Tournament Selection

1-point crossover

n-point crossover

Uniform Crossover

Mutation

GA generational and steady-state models

• Metaheuristic algorithms that are population-based, often referred to as P-metaheuristics, employ multiple agents to find an optimal or near-optimal global solution. These algorithms can be divided into two main categories, depending on their source of inspiration: evolutionary computation algorithms and swarm intelligence algorithms.
• Evolutionary computation algorithms draw inspiration from the process of biological evolution. Examples of evolutionary computation algorithms include Genetic Algorithm (GA), Differential Evolution (DE), Genetic Programming (GP), Evolutionary Programming (EP), Evolutionary Strategies (ES), Cultural Algorithms (CA), and Co-evolution (CoE).
• The genetic algorithm is the most widely used form of evolutionary computation. It is an adaptive heuristic search method designed to mimic the natural system’s processes required for evolution, as outlined in Charles Darwin's theory of evolution.
• Pseudo-random, Quasi-random, Sequential diversification, Parallel diversification, and heuristics represent various initialization strategies for P-metaheuristics like genetic algorithms. Each strategy offers distinct levels of diversity, computational cost, and initial solution quality.
• In genetic algorithms, the crossover and mutation operators play essential roles in searching the solution space and maintaining diversity within the population. The primary purpose of these operators is to handle the search dilemma by balancing exploration/diversification (searching new areas of the solution space) and exploitation/intensification (refining the existing solutions).
• High crossover rate and a low mutation rate are recommended to balance exploration and exploitation. The high crossover rate facilitates the sharing of good traits between individuals, while the low mutation rate introduces small random changes to maintain diversity and prevent premature convergence. This combination allows the algorithm to efficiently search the solution space and find high-quality solutions.
• In the generational model of genetic algorithms, the entire population is replaced while in the steady-state model of genetic algorithms, a small fraction of the population is replaced. The steady-state model has lower computation cost compared to the generational model in genetic algorithms but generational models improves diversity preservation compared to the steady-state models.
• A wide range of open-source Python libraries exist for working with genetic algorithms. One such library, pymoo (Multi-objective Optimization in Python), includes popular algorithms such as genetic algorithms, differential evolution, evolutionary strategies, Non-dominated Sorting Genetic Algorithm (NSGA-II), NSGA-III, and Particle Swarm Optimization (PSO).

FAQ