Evolutionary Computation and Genetic Algorithms

Introduction and Context

Evolutionary computation (EC) is a family of population-based optimization and learning methods inspired by biological evolution. Instead of constructing a solution directly from a mathematical model, an evolutionary algorithm maintains a population of candidate solutions and improves that population through variation and selection. The central idea is simple: candidate solutions that perform well are more likely to contribute to future solutions, while poorly performing candidates are gradually removed.

Evolutionary methods are particularly useful when the search space is large, discontinuous, noisy, multimodal, non-differentiable, or combinatorial. They are therefore important in artificial intelligence, engineering design, scheduling, feature selection, robotics, finance, bioinformatics, and machine learning. Their strength is broad applicability; their weakness is that they usually provide near-optimal rather than guaranteed optimal solutions within finite computational budgets.

A genetic algorithm (GA) is the most widely known EC method. It typically represents solutions as chromosomes, evaluates them using a fitness function, selects parents, applies crossover and mutation, and replaces some or all members of the population. Other major paradigms include evolutionary strategies (ES), evolutionary programming (EP), differential evolution (DE), and genetic programming (GP).

Learning Objectives

After studying this chapter, the reader should be able to:

1. Formulate an evolutionary search problem using representations, objective functions, fitness functions, and constraints.
2. Explain population initialization, selection, crossover, mutation, and replacement.
3. Design and analyse a genetic algorithm for discrete and continuous problems.
4. Distinguish genetic algorithms, genetic programming, and evolutionary strategies.
5. Explain convergence, diversity loss, premature convergence, and termination criteria.
6. Apply penalty, repair, feasibility-based, and multi-objective constraint-handling methods.
7. Critically evaluate the practical, ethical, and computational implications of evolutionary optimization.

1. Evolutionary Search as Optimization

An optimization problem can be written generally as:

Here, x is a candidate solution, S is the feasible search space, and f(x) is the objective function. For a maximization problem, larger objective values are preferred; for a minimization problem, smaller values are preferred.

The search space may be:

• Discrete, such as permutations of jobs or binary feature-selection vectors.
• Continuous, such as real-valued engineering design parameters.
• Mixed, containing both categorical and numerical variables.
• Structured, such as syntax trees in genetic programming.

In many real problems, the objective is subject to constraints:

where g_i are inequality constraints and h_j are equality constraints. A solution satisfying all constraints is feasible. Evolutionary algorithms can search unconstrained spaces effectively, but constraint handling must be designed explicitly when infeasible solutions are unacceptable.

Representation and Genotype–Phenotype Mapping

A chromosome, or genotype, is the data structure manipulated by the algorithm. The decoded candidate in the problem domain is the phenotype. A mapping may be written as:

where G is the genotype space, X is the phenotype space, and φ is the decoding function.

Examples include:

A good representation should be expressive, compact, and compatible with variation operators. If most randomly generated chromosomes decode to invalid solutions, the representation is poorly aligned with the problem.

Fitness Functions

The fitness function measures the quality of a candidate for selection. If the objective is maximized, fitness may be directly defined as:

For a minimization problem, a common transformation is:

provided that f(x) is non-negative. Another approach is rank-based fitness, which avoids dependence on the scale of the objective. Fitness transformation must preserve the intended preference ordering and should not create numerical instability.

Fitness is not necessarily identical to the business or scientific objective. For example, a machine-learning model may be evaluated using validation error but penalized for excessive complexity, latency, or energy use. A composite objective can be written as:

where E is predictive error, C is computational cost, L is latency, and α, β, and γ are non-negative weights. Units should be normalized before combining quantities with different units.

2. The Genetic Algorithm Cycle

A canonical generational GA follows this sequence:

1. Initialize a population.
2. Decode chromosomes and evaluate fitness.
3. Select parent chromosomes.
4. Generate offspring through crossover and mutation.
5. Evaluate offspring.
6. Select survivors for the next generation.
7. Repeat until a termination condition is reached.

Figure: The iterative cycle of a canonical genetic algorithm.

Initialization

The initial population may be generated randomly, heuristically, or through a hybrid method. Random initialization improves coverage, while heuristic seeding can provide high-quality starting points. Excessive seeding from one heuristic may reduce diversity and cause premature convergence. A population size must balance diversity against evaluation cost.

Selection

Selection determines which individuals become parents and, in some algorithms, which individuals survive.

Roulette-wheel selection assigns selection probability proportional to fitness:

where F_i is the fitness of individual i and N is population size. This method requires non-negative fitness values and can be overly sensitive to extreme fitness differences.

Tournament selection randomly samples a group of individuals and selects the best in that group. Tournament size controls selection pressure: larger tournaments favour the current best more strongly.

Rank selection orders individuals by fitness and assigns probability according to rank rather than raw values. It is more robust when objective values have very different scales.

Elitism copies a small number of the best individuals directly into the next generation. It prevents loss of the best-so-far solution but can reduce diversity if used excessively.

Crossover

Crossover combines information from two or more parents.

For binary strings, one-point crossover chooses a cut position and exchanges suffixes. Uniform crossover independently chooses each gene from either parent, usually with probability one-half.

For real-valued vectors, arithmetic crossover can produce:

where p₁ and p₂ are parent vectors and λ is a mixing coefficient. Crossover is useful when combining partial structures, but it can disrupt beneficial combinations or generate infeasible solutions.

Permutation problems require specialized operators. Ordinary one-point crossover may duplicate or omit items. Order crossover and partially matched crossover preserve permutation validity.

Mutation

Mutation introduces new genetic material and protects against loss of diversity. For a binary chromosome, bit-flip mutation changes a bit with probability p_m. For a chromosome of length L, the expected number of mutated bits is:

This expectation does not imply that exactly Lp_m bits change in every offspring. Mutation events are random and usually independent.

For continuous variables, Gaussian mutation is often written:

where σ_i controls mutation scale and z_i is a standard normal random variable. Mutation scales may be fixed, adapted during evolution, or self-adapted as strategy parameters.

For permutations, swap, insertion, and inversion mutations are common. For trees, mutation may replace a subtree with a newly generated subtree.

Replacement

In a generational GA, all or nearly all parents are replaced by offspring. In a steady-state GA, only a few offspring are created and inserted at a time. Common survivor policies include:

• Generational replacement: offspring form the next population.
• Generational replacement with elitism: the best parents are preserved.
• Comma selection: only offspring compete for survival.
• Plus selection: parents and offspring compete together.
• Crowding or niching: similar individuals compete to preserve multiple regions of the search space.

3. Worked Example: Binary Optimization

Consider maximizing the number of ones in a four-bit chromosome. The objective is:

where each x_i is either 0 or 1. Suppose two parents are:

• Parent 1: 1100, fitness 2
• Parent 2: 1011, fitness 3

Using one-point crossover after the second bit gives:

• Offspring 1: 1111, fitness 4
• Offspring 2: 1000, fitness 1

If mutation flips the third bit of Offspring 2, it becomes 1010, with fitness 2. The best offspring is therefore 1111. This example illustrates that crossover can combine useful partial patterns, while mutation can either improve or reduce fitness. Selection does not guarantee improvement in every individual; it increases the probability that high-quality genetic material contributes to future generations.

4. Genetic Programming

Genetic programming (GP) evolves executable computer programs rather than fixed-length strings. A program is commonly represented as a rooted syntax tree. Internal nodes are functions, such as arithmetic operators, and leaf nodes are terminals, such as variables or constants.

For symbolic regression, the target may be to approximate a function from observed data. A candidate program can be evaluated using mean squared error:

where y_i is the observed value, ŷ_i is the program prediction, and n is the number of observations. The units of MSE are the square of the target units.

GP uses subtree crossover: a randomly selected subtree from one parent is exchanged with a subtree from another. Subtree mutation replaces a selected subtree with a newly generated subtree. Important practical issues include:

• Bloat: programs grow unnecessarily without improving predictive performance.
• Closure: every operator must be defined for the values it receives.
• Parsimony: complexity penalties or size limits discourage unnecessarily large programs.
• Interpretability: evolved expressions can be more interpretable than black-box models, but large trees may be difficult to understand.

A complexity-aware objective may be:

where s is program size and λ controls the penalty. The two terms should be scaled appropriately before combination.

5. Evolutionary Strategies and Related Methods

Evolutionary strategies emphasize real-valued vectors, mutation, and adaptation of mutation parameters. A typical individual may contain both object variables and strategy parameters. The algorithm can adapt its search step sizes according to success in the current landscape.

In a (μ, λ) strategy, λ offspring are generated from μ parents, and only offspring form the next generation. In a (μ + λ) strategy, parents and offspring compete together. The comma strategy encourages turnover; the plus strategy preserves high-quality parents.

Differential evolution creates trial vectors by adding scaled differences between population vectors. A common mutation form is:

where x_a, x_b, and x_c are distinct population vectors and F is a scaling factor. Crossover then combines the trial vector with a target vector. Differential evolution is often effective for continuous black-box optimization.

Evolutionary programming historically emphasized mutation and selection, with representations adapted to the task. In modern usage, the distinctions among EC paradigms can overlap, and algorithm choice should be based on representation, evaluation cost, landscape structure, and constraints rather than labels alone.

6. Convergence, Diversity, and Termination

Convergence means that the population increasingly concentrates around particular regions of the search space. Convergence is desirable when the region is high quality, but dangerous when the population converges prematurely to a local optimum.

Useful monitoring measures include:

• Best fitness and mean fitness.
• Fitness variance.
• Genotypic diversity, such as average Hamming distance for binary strings.
• Phenotypic diversity, such as distance between decoded solutions.
• Number of unique individuals.
• Constraint violation statistics.

For binary chromosomes, the Hamming distance between two strings is the number of positions at which they differ. Low average Hamming distance indicates genetic convergence, although phenotypically different genotypes can sometimes decode to the same solution.

Typical termination rules include:

1. A fixed number of generations or evaluations.
2. A target fitness level.
3. No improvement in the best fitness for a specified patience period.
4. Population diversity falling below a threshold.
5. A computational or financial budget being exhausted.

A robust experiment usually uses multiple random seeds. Reporting only the best run can seriously exaggerate performance. Mean, median, standard deviation, and success rate provide a more reliable comparison.

Controlling Premature Convergence

Premature convergence may be reduced by:

• Increasing mutation or using adaptive mutation.
• Maintaining several subpopulations or islands.
• Using fitness sharing or crowding.
• Reducing selection pressure.
• Introducing random immigrants.
• Restarting when progress stagnates.
• Preserving elites carefully rather than copying too many.

No diversity method is universally superior. Diversity can preserve exploration but may also slow exploitation and increase evaluation cost.

7. Constraint Handling

Constraint handling is central to engineering and operational applications. Four major approaches are common.

Penalty Functions

An infeasible solution receives a penalty. For minimization, a static penalty may be:

where V(x) measures violation and ρ is a penalty coefficient. For inequality constraints, one possible violation measure is:

This formulation assumes constraints have been scaled comparably. Equality constraints may require a tolerance because exact equality is difficult under floating-point computation. An excessively large penalty makes the search ignore objective quality; a small penalty allows unacceptable solutions to dominate.

Repair Operators

A repair operator transforms an infeasible chromosome into a feasible one. For a schedule, repair may remove duplicated jobs and insert missing jobs. Repair is effective when a principled projection onto the feasible set exists, but arbitrary repair can introduce bias.

Feasibility Rules

A common comparison rule is:

1. Any feasible solution is preferred to any infeasible solution.
2. Between feasible solutions, prefer the better objective.
3. Between infeasible solutions, prefer the smaller total violation.

This avoids selecting a penalty coefficient but requires a meaningful violation measure.

Specialized Representations

The strongest method is often to encode only feasible solutions. For example, a permutation representation automatically ensures that each job appears once. Such representations reduce wasted evaluations and simplify interpretation.

8. Multi-Objective Evolutionary Optimization

Many real decisions involve competing objectives, such as minimizing cost and emissions while maximizing reliability. A solution x dominates solution y if it is no worse in every objective and strictly better in at least one. The set of non-dominated solutions forms the Pareto front.

Unlike a single-objective algorithm, a multi-objective algorithm seeks a diverse approximation to the Pareto front. NSGA-II, SPEA2, and decomposition-based methods are widely used. Important evaluation criteria include convergence toward the front and diversity along the front. A single weighted sum can miss non-convex parts of the Pareto front, so decision-makers should not assume that one weight setting represents all meaningful trade-offs.

9. Illustrative Case: Energy-Aware Neural Network Feature Selection

Background

A company wants to deploy a classifier on battery-powered industrial sensors. The available dataset contains 80 measured features. More features may improve predictive accuracy but increase sensing, storage, and inference energy.

Problem

The decision variable is a binary vector of length 80. A value of one means that a feature is selected. The optimization must balance validation error and energy consumption while enforcing a maximum of 20 selected features.

Approach

A GA is initialized with 100 binary chromosomes. Each chromosome is evaluated using stratified validation. A scalar objective for minimization is:

Here, E_val is validation error, C_norm is normalized energy cost, k(x) is the number of selected features, and α and β are policy weights. Because the feature-count violation is measured in feature units while the other terms are dimensionless, β must be calibrated rather than chosen arbitrarily.

Tournament selection, uniform crossover, and bit-flip mutation are used. Elitism preserves the best three feasible solutions. Five independent runs are performed, and the median validation error and feature count are reported. A final untouched test set is used only after the design has been selected.

Outcome

The resulting model uses 17 features and has slightly higher validation error than the full model but substantially lower estimated energy use. The appropriate conclusion is not that the GA found the globally optimal feature subset; rather, it found a competitive trade-off under the specified evaluation budget and objective design.

Learning Points

1. The representation naturally matches feature selection.
2. Validation data must not be confused with final test data.
3. Energy and accuracy should be measured consistently.
4. Repeated runs are necessary because evolutionary algorithms are stochastic.
5. The objective encodes organizational priorities and therefore requires stakeholder scrutiny.

10. Implementation and Best Practices

A professional implementation should:

• Define the representation before selecting operators.
• Use operators that preserve problem validity where possible.
• Normalize or otherwise calibrate heterogeneous objective terms.
• Cache expensive evaluations when identical solutions recur.
• Parallelize independent fitness evaluations when appropriate.
• Record random seeds, parameter settings, stopping rules, hardware, and software versions.
• Separate training, validation, and test data in machine-learning applications.
• Compare against simple baselines, local search, and problem-specific heuristics.
• Report distributions across repeated runs rather than a single result.
• Use statistical tests cautiously and account for multiple comparisons.

The no-free-lunch perspective is important: averaged over all possible problems, no optimizer is universally superior. Performance depends on landscape structure, representation, variation operators, evaluation noise, and computational budget.

11. Limitations, Governance, and Ethical Issues

Evolutionary algorithms can require thousands or millions of objective evaluations. If each evaluation involves a physical experiment, a simulation, or model training, cost may dominate algorithm design. Surrogate models, parallel evaluation, early stopping, and active-learning strategies can reduce this burden, but surrogate errors may mislead the search.

Optimization can also amplify undesirable objectives. If a hiring model is optimized only for predictive accuracy, it may reproduce historical discrimination. If a recommender is optimized solely for engagement, it may promote harmful or addictive content. Fitness functions should therefore include fairness, safety, sustainability, privacy, and regulatory requirements where relevant.

Important governance practices include:

• Documenting objectives, constraints, and data provenance.
• Auditing evolved solutions for bias and unsafe behaviour.
• Keeping human approval for high-impact decisions.
• Testing robustness under distribution shift and adversarial conditions.
• Preserving reproducibility and an audit trail.
• Avoiding claims of global optimality without a valid proof.

Contemporary Developments

Current research combines evolutionary search with deep learning, surrogate-assisted optimization, quality-diversity algorithms, automated machine learning, and neuroevolution. Quality-diversity methods seek both high performance and behavioural variety, which is valuable in robotics and design exploration. Neuroevolution can optimize neural architectures, weights, or learning rules, although gradient-based methods are often more efficient for large differentiable networks. Hybrid memetic algorithms combine global evolutionary exploration with local improvement, exploiting complementary strengths.

The research frontier also includes explainable evolutionary optimization, human-in-the-loop search, environmentally conscious computation, and algorithms for dynamic or changing objectives. These developments reinforce a central principle: evolutionary computation is not merely a biological metaphor but a flexible engineering framework whose effectiveness depends on careful modelling and evaluation.

Chapter Summary

Evolutionary computation formulates optimization as population-based search. A chromosome represents a candidate solution, a decoding function maps it to the problem domain, and a fitness function measures its quality. Genetic algorithms repeatedly initialize, evaluate, select, recombine, mutate, and replace individuals. Selection controls exploitation; mutation and population diversity support exploration; crossover recombines useful structures.

Representations and operators must match the problem type: binary operators suit feature selection, permutation operators suit scheduling, real-valued operators suit numerical design, and tree operators suit genetic programming. Evolutionary strategies and differential evolution are important alternatives, especially for continuous optimization. Convergence should be monitored through fitness and diversity, since premature convergence can produce poor solutions. Constraints may be managed through penalties, repair, feasibility rules, or specialized representations.

Evolutionary methods are powerful but stochastic, computationally demanding, and sensitive to objective design. Reliable practice requires repeated runs, meaningful baselines, transparent reporting, constraint awareness, and ethical governance. In AI and ML, evolutionary optimization is especially valuable when the search space is non-differentiable, discrete, expensive, or structurally complex.

Key Terms

Evolutionary computation: Population-based computation inspired by evolutionary processes.

Genetic algorithm: An evolutionary algorithm using chromosome representation, selection, crossover, mutation, and replacement.

Chromosome: Encoded representation of a candidate solution.

Genotype: Internal representation manipulated by evolutionary operators.

Phenotype: Decoded solution expressed in the problem domain.

Fitness function: Measure used to compare candidate quality.

Selection pressure: Degree to which better individuals are favoured.

Crossover: Combination of genetic material from parent solutions.

Mutation: Random variation introduced into a candidate solution.

Elitism: Direct preservation of high-quality individuals.

Population diversity: Variation among individuals in a population.

Premature convergence: Loss of diversity before a satisfactory solution is found.

Genetic programming: Evolution of executable programs, usually represented as trees.

Evolutionary strategy: Evolutionary method emphasizing real-valued mutation and parameter adaptation.

Differential evolution: Continuous optimizer using scaled differences between population vectors.

Penalty function: Constraint-handling method that worsens fitness according to violation.

Pareto dominance: Relation in which one solution is no worse in all objectives and better in at least one.

Pareto front: Set of non-dominated solutions.

Bloat: Uncontrolled growth of genetic-programming structures.

Quality diversity: Search for both high performance and diverse behaviours.

Review Questions

Short Answer Questions

1. What is the difference between genotype and phenotype?
2. Why is mutation important in a genetic algorithm?
3. Distinguish generational and steady-state replacement.
4. What is premature convergence?
5. State two methods for handling constraints.

Long Answer Questions

1. Explain the complete cycle of a canonical genetic algorithm, including representation, fitness, selection, crossover, mutation, and replacement.
2. Compare roulette-wheel, tournament, rank-based selection, and elitism.
3. Explain how genetic programming represents and evolves computer programs. Discuss bloat and parsimony.
4. Compare genetic algorithms, evolutionary strategies, and differential evolution for continuous optimization.
5. Discuss why repeated runs, diversity monitoring, and appropriate baselines are necessary when evaluating evolutionary algorithms.

Analytical / Application Questions

1. Design a genetic algorithm for university examination timetabling. Specify the representation, fitness components, variation operators, constraint-handling method, and termination criteria.
2. A feature-selection GA achieves excellent validation accuracy but selects nearly every feature. Diagnose the objective-design problem and propose a revised formulation.
3. An evolutionary run shows rapidly increasing best fitness, unchanged population diversity, and poor performance on independent test cases. Analyse the likely causes and recommend corrective actions.

Multiple Choice Questions with Answers

Question 1

Which component determines how well a candidate solution satisfies the optimization objective?

A. Mutation operator

B. Fitness function

C. Population size

D. Chromosome length

Correct Answer: B. Fitness function

Question 2

For a binary chromosome of length L with independent bit mutation probability p_m, what is the expected number of mutated bits?

A. L + p_m

B. L/p_m

C. Lp_m

D. p_m/L

Correct Answer: C. Lp_m

Question 3

Which crossover is specifically designed to preserve permutation validity in sequencing problems?

A. Bit-flip crossover

B. Order crossover

C. Gaussian crossover

D. Subtree mutation

Correct Answer: B. Order crossover

Question 4

What is the main purpose of elitism?

A. To guarantee random exploration

B. To preserve selected high-quality solutions

C. To eliminate all infeasible solutions

D. To increase chromosome length

Correct Answer: B. To preserve selected high-quality solutions

Question 5

In genetic programming, a candidate program is commonly represented as a:

A. Syntax tree

B. Probability table

C. Fixed histogram

D. Constraint matrix

Correct Answer: A. Syntax tree

Question 6

Which condition describes premature convergence?

A. The population maintains high diversity indefinitely

B. The algorithm stops before evaluating fitness

C. The population loses diversity around a poor solution

D. Every offspring is infeasible

Correct Answer: C. The population loses diversity around a poor solution

Question 7

For a minimization problem, which expression is a common penalty formulation?

A. f(x) − ρV(x)

B. f(x) + ρV(x)

C. f(x)V(x) − ρ

D. V(x)/f(x) only

Correct Answer: B. f(x) + ρV(x)

Question 8

A solution is Pareto-dominated when another solution is:

A. Worse in every objective

B. No worse in every objective and better in at least one

C. Equal in every objective only

D. Feasible while it is infeasible

Correct Answer: B. No worse in every objective and better in at least one

Question 9

Which evolutionary method commonly uses a scaled difference between population vectors?

A. Differential evolution

B. Genetic programming

C. Rank selection

D. Subtree mutation

Correct Answer: A. Differential evolution

Question 10

Why should evolutionary algorithms normally be run with multiple random seeds?

A. They are deterministic algorithms

B. Their stochastic results can vary across runs

C. Mutation is otherwise disabled

D. Fitness cannot be computed once

Correct Answer: B. Their stochastic results can vary across runs