Genetic Algorithm

[Link]
October 2025

1 Intuition and Concept of Genetic Algorithms

Genetic Algorithms (GAs) belong to the family of evolutionary algorithms, inspired by Charles
Darwin’s theory of natural selection: “Survival of the fittest.” The fundamental idea is to mimic
the process of biological evolution to evolve better and better solutions to complex optimization
problems.
1.1 1. Motivation
In nature, organisms evolve over generations, adapting to their environment. The traits that
enhance survival or reproduction become more common. Similarly, in optimization, candidate
solutions can be thought of as organisms. Through selective reproduction, recombination, and
random variation, a population of solutions gradually evolves toward higher quality.
GAs are particularly useful for problems where:
• The objective function is non-linear, discontinuous, or noisy.
• Gradient-based methods fail due to lack of differentiability.
• The search space is large, discrete, or multi-modal (many local optima).

1.2 2. Core Intuition: Evolution as Optimization

Each iteration of a GA (called a generation) is analogous to one generation in a biological
population. The main biological processes and their computational counterparts are shown
below:

Natural Process Computational Analogy

Gene / Chromosome Representation of solution

Population of individuals Set of candidate solutions
Fitness (survival strength) Objective function value
Reproduction / Mating Selection of good parents
Crossover (recombination) Exchange of features between parents
Mutation Small random change to maintain diversity
Natural Selection Replacement of weaker individuals

Thus, a GA evolves a population of solutions toward better fitness over time.

1
1.3 3. Why a Population-Based Search?
Unlike deterministic algorithms (e.g., gradient descent or hill climbing) that track a single point
in the search space, a GA maintains a population of solutions. This provides two major benefits:
1. Exploration: Multiple areas of the search space are sampled simultaneously, reducing the
risk of getting trapped in local minima.

2. Information Exchange: Crossover allows good partial solutions (building blocks) to

combine and form better global solutions.
This population-based nature makes GAs powerful in dealing with complex or deceptive
landscapes.

1.4 4. Intuition Behind Major Steps

(a) Initialization
The process begins with a diverse population of randomly generated candidate solutions. This
diversity is crucial to ensure broad exploration of the search space from the beginning. If the
population is too similar, the algorithm may converge prematurely to a poor solution.

(b) Fitness Evaluation

Each candidate solution is evaluated using a fitness function, which measures its quality or
suitability for the problem. Fitness acts as a measure of “survival ability” in the evolutionary
analogy. Better fitness means higher chances of reproduction.

(c) Selection
The selection phase decides which individuals (parents) will reproduce. It applies evolutionary
pressure by giving fitter individuals higher chances to pass their traits to the next generation.
However, some weaker individuals are also allowed occasionally to maintain diversity (explo-
ration). Analogy: The fittest individuals get to reproduce more often.

(d) Crossover (Recombination)

Crossover combines genetic material from two parents to create offspring. The hope is that good
traits from both parents will combine to yield even better children. Analogy: Offspring inherit
mixed characteristics from both parents.
For example, if one parent encodes “short travel distance between cities A and B” and
another encodes “short distance between C and D,” the child may inherit both, resulting in an
overall shorter tour.

(e) Mutation
Crossover alone cannot introduce new genetic material; it only rearranges what already exists.
Mutation ensures occasional random alterations in the offspring — flipping a bit, swapping
cities, or perturbing a numeric value. This prevents stagnation and allows exploration of unseen
parts of the search space. Analogy: Random genetic mutations that lead to new traits in nature.

2
(f) Replacement (Survival of the Fittest)
Once offspring are created, they compete with the current population to form the next generation.
The fittest individuals are preserved (elitism), ensuring steady improvement in population quality.

(g) Termination
The process continues until a stopping condition is met — such as reaching a maximum number
of generations or achieving a desired fitness threshold.

1.5 5. Conceptual Illustration

Figure below (to be inserted) conceptually shows how a population evolves across generations,
gradually moving toward the global optimum:

ga_evolution_diagram.png

A good reference visualization: [Link]

d/d7/Genetic_algorithm_flowchart.svg

1.6 6. Importance of Each Step

• Initialization: Ensures coverage and diversity in search space.

• Selection: Drives exploitation of promising regions.

• Crossover: Facilitates recombination of useful patterns.

• Mutation: Maintains diversity and prevents premature convergence.

• Replacement: Preserves the best individuals and controls convergence rate.

3
Together, these steps create a self-adaptive search process balancing exploration and exploitation
— where exploration discovers new promising areas and exploitation refines good solutions.

2 Genetic Algorithms (In-depth)

2.1 Overview and Motivation
A Genetic Algorithm (GA) is a population-based stochastic optimization method inspired by
natural evolution. A GA maintains a population of candidate solutions (chromosomes) and
evolves them using selection, crossover (recombination), and mutation operators. GAs are
well-suited for multimodal, nonlinear, and combinatorial problems where gradient methods fail.

When to Use Genetic Algorithms (GAs)

Genetic Algorithms are particularly useful when traditional optimization methods (like gradient
descent or linear programming) fail due to the nature of the search space or the objective function.
They shine in problems that are complex, discrete, or have multiple local optima.
Typical scenarios include:

• Non-convex or multi-modal objective functions: GAs do not require convexity or smooth-

ness, and can escape local minima. Example: Optimizing a complex function such as

f (x) = sin(10x) + x2 , x ∈ [−1, 1]

which has many local minima. A GA can explore globally and find the true minimum.

• Non-differentiable or discontinuous functions: When gradients are undefined or noisy

(e.g., simulation-based or empirical models), GAs can still optimize effectively. Example:
Tuning hyperparameters of a machine learning model or optimizing black-box system
outputs.

• Discrete or combinatorial problems: GAs handle permutations, combinations, or binary

strings directly without relaxation. Example: Traveling Salesman Problem (TSP), job
scheduling, or knapsack optimization.

• Complex constraints or irregular feasible spaces: If constraints make the feasible region
non-convex or discontinuous, GAs can be adapted by encoding only feasible solutions or
using penalty functions. Example: Layout design, path planning with obstacle avoidance.

• Robust, global search requirements: When approximate but global solutions are accept-
able, and function evaluation is parallelizable. Example: Engineering design optimization,
neural architecture search, or economic modeling.

In summary: Use Genetic Algorithms when:

• The search space is large, rugged, or discontinuous.

• Objective and constraint functions are black-box or simulation-based.

• A near-global solution is more valuable than a fast but local one.

Use Genetic Algorithms when:

[Link] problem has too many options or a bumpy/jumpy solution space.

[Link] can test solutions but don’t have a formula (black-box or simulation).
[Link] want a really good (near-best) answer,4 even if it takes time.

Simple rule: Big, messy, or unknown problems try Genetic Algorithms.

3 Designing GA Components for Different Problem Types
The performance of a Genetic Algorithm depends critically on how its components — represen-
tation, selection, crossover, and mutation — are designed for a given problem type. Although the
basic flow remains the same, each component must respect the problem’s structure, constraints,
and objective landscape.
We discuss three major problem categories and the design of GA operators for each:

3.1 1. Binary Optimization Problems

Binary GAs are the earliest and simplest form, suitable for problems where variables take
discrete values (0 or 1).

Encoding
Each variable or decision is represented as a bit:

S = [b1 , b2 , . . . , bn ], bi ∈ {0, 1}

For example, in the Knapsack Problem, each gene represents whether an item is included (1)
or excluded (0).

Fitness Function
The total profit is maximized under a capacity constraint:
(
∑i pi bi if ∑i wi bi ≤ Wmax
Fitness(S) =
0 otherwise

Crossover
Binary crossover mimics bit exchange between two parents.
• Single-point crossover: Choose a random crossover point k and swap the tail parts.

Parent1 = [1, 0, 1, |1, 0, 0], Parent2 = [0, 1, 0, |1, 1, 1]

Offspring1 = [1, 0, 1, 1, 1, 1]

• Uniform crossover: Each bit has probability p = 0.5 to be inherited from either parent.

Mutation
Flip each bit with a small probability pm :
(
1 − bi , with probability pm
b′i =
bi , otherwise
This ensures new regions of the search space are explored.

5
Illustration
A helpful schematic of bit-level crossover and mutation can be found here: [Link]
[Link]/wikipedia/commons/1/1d/Genetic_algorithm_operations.svg

3.2 2. Permutation-Based Problems

These problems involve ordering or arrangement, such as the Travelling Salesman Problem
(TSP) or job scheduling.

Encoding
Each chromosome is a permutation of city indices:

S = [C1 ,C2 , . . . ,Cn ]

For example: S = [1, 4, 3, 2, 5] represents visiting cities in that order.

Fitness Function
The objective is to minimize total travel cost:
n−1
E(S) = ∑ d(Ci,Ci+1) + d(Cn,C1)
i=1

where d(Ci ,C j ) is the distance between cities i and j.

Crossover (Order-Preserving)
Traditional crossover may destroy valid permutations, so specialized operators are used:
• Order Crossover (OX): Copy a random segment from parent 1 and preserve the order of
remaining cities from parent 2. Example:

P1 = [1, 2, 3, 4, 5, 6, 7], P2 = [4, 1, 2, 7, 3, 6, 5]

Select segment [3,4,5] from P1 . Fill remaining positions from P2 in order ⇒ [7, 3, 4, 5, 6, 1, 2].
Correct Child[7, 6, 3, 4, 5, 1, 2]
• Partially Mapped Crossover (PMX): Maintains absolute position mappings between
parent genes.

Mutation
Permutation-specific mutation maintains feasibility:
• Swap Mutation: Exchange two cities randomly.

• Inversion Mutation: Reverse a random subsequence of the tour.

Tabu-Aided Mutation (optional)

In some hybrid GAs, recently explored permutations can be stored in a short-term tabu list to
avoid revisiting them, similar to Tabu Search.

6
Illustration
Good crossover examples: [Link]
Crossover_example_TSP.svg

3.3 3. Continuous or Real-Valued Optimization Problems

Used for engineering design, parameter tuning, or function optimization.

Encoding
Chromosomes are represented as vectors of real numbers:

S = [x1 , x2 , . . . , xn ], xi ∈ [ximin , ximax ]

Fitness Function
Defined directly from the objective function, e.g.:

f (S) = −(x12 + x22 ) (to minimize sphere function)

Crossover
Recombination is done via arithmetic operations:
• Arithmetic Crossover:

Child = α · P1 + (1 − α) · P2 , α ∈ [0, 1]

• Blend Crossover (BLX-α): Each gene is sampled uniformly between:

[min(x1 , x2 ) − αd, max(x1 , x2 ) + αd], d = |x1 − x2 |

Mutation
• Gaussian Mutation: Add normally distributed noise.

xi′ = xi + N (0, σ 2 )

• Boundary Mutation: Replace xi by its upper or lower bound with small probability.

Constraint Handling
For constrained continuous problems:
• Penalize infeasible solutions:

f ′ (S) = f (S) − λ · Penalty(S)

• Or repair infeasible chromosomes using normalization.

7
Illustration
Continuous crossover/mutation visualization: [Link]
commons/b/bb/Genetic_algorithm_crossover_and_mutation.svg

3.4 4. Common Design Guidelines

• Choose representation that naturally encodes feasibility.

• Tune pc (crossover rate) and pm (mutation rate) based on exploration vs exploitation balance.

• Use elitism to retain the best individuals.

• Maintain population diversity to prevent premature convergence.

The next section demonstrates these design principles through a complete step-by-step example
of applying GA to the Travelling Salesman Problem.

3.5 Key Concepts and Notation

(t) (t)
• Population at generation t: P(t) = {S1 , . . . , SN }

• Fitness (to maximize) or cost/energy (to minimize). We often map cost → fitness by
f (S) = 1/(1 + E(S)) or f (S) = 1/E(S) if E > 0.

• Selection probability (roulette wheel):

f (Si )
pi =
∑Nj=1 f (S j )

3.6 Step-by-step detailed GA procedure (with reasoning)

1. Representation / Encoding Design choices depend on problem type — encoding deter-
mines which crossover/mutation operators are valid.

• Binary encoding: fixed-length bitstrings (classic GA). Good for subset selection, combina-
torial encodings.

• Permutation encoding: for ordering problems (TSP, scheduling). Chromosome is a

permutation of elements.

• Real-valued (vector) encoding: continuous optimization; chromosome is a vector of reals.

• Tree/Graph encodings: for program synthesis / symbolic regression (Genetic Program-

ming).

Design tip: choose an encoding that naturally preserves feasibility under your primary
operators, or provide a robust repair operator.

2. Initialization Methods:
• Random initialization: uniformly random across feasible set — gives maximum diversity.

• Heuristic seeding: include one or more good solutions from a greedy heuristic to speed
convergence.

8
 • Stratified initialization: ensure coverage of various regions (useful when search space is
structured).
Design guideline: For TSP/permutation problems, mix random permutations with a nearest-
neighbor heuristic seed(s) for early good individuals.

3. Fitness Evaluation Map objectives to a scalar fitness for selection. For minimization
problems (e.g., cost E), common mappings:
1 1
f (S) = , or f (S) =
1 + E(S) E(S)
If fitness differences are too large / small, use scaling (linear or sigma scaling) or rank-based
selection to avoid premature takeover.

4. Selection Common selection operators:

• Roulette-wheel (fitness-proportionate): probability pi above.

Pros: Simple. Cons: Sensitive to fitness scaling; can be dominated by a few very-fit
individuals.

• Tournament selection: pick k uniformly at random, select best.

Pros: Easy, robust, tunable via k (selection pressure).

• Rank selection: sort by fitness and assign selection probability based on rank. Reduces
sensitivity to scale.

Design tip: Use tournament (k = 2 or 3) for robust classroom implementations.

5. Crossover (Recombination) Purpose: create offspring by combining genetic material of

two parents. Many designs depend on encoding.
Binary (bitstring) operators:
• Single-point crossover: choose cut position, swap tails.

• Two-point crossover: choose two cuts, swap middle segment.

• Uniform crossover: each bit taken from either parent with fixed probability (e.g., 0.5).
Permutation operators (TSP-like — must preserve permutation):
• Partially Mapped Crossover (PMX): choose two cut points; swap middle segments and
map remaining items to preserve permutation (example diagram).

• Order Crossover (OX): copy a segment from parent1, then fill remaining positions in order
from parent2. (Use for TSP)

• Cycle Crossover (CX): preserves absolute position cycles between parents.

Real-coded crossover:
• BLX-α: offspring gene xo uniformly from interval [min(x1p , x2p ) − αδ , max(x1p , x2p ) + αδ ]
where δ is gap.

9
 • Simulated Binary Crossover (SBX): probabilistic operator approximating single-point
crossover in real domain.
Design tip: choose a crossover that preserves feasibility or include a reliable repair routine.

6. Mutation Purpose: introduce new genetic material; helps escape premature convergence.

• Binary: bit-flip with probability pm .

• Permutation: swap two positions; inversion (reverse subsequence); scramble (random

shuffle a subsequence).

• Real-valued: add Gaussian noise x ← x + N (0, σ 2 ) or polynomial mutation.

Design tip: set mutation probability low (binary: 0.01 per bit; permutations: 0.1 per
chromosome), but adaptive schemes that increase mutation when diversity drops are powerful.

7. Repair and Constraint Handling If operators produce infeasible individuals, handle via:
• Repair functions: deterministically fix infeasible chromosomes (e.g., for permutation
duplicates).

• Penalty methods: penalize infeasible individuals in fitness (e.g., f ← f − λ · violation).

• Feasible-preserving operators: design operators that always maintain feasibility.

8. Replacement / Survivorship How to form the next generation:

• Generational replacement: offspring replace all parents.

• Steady-state / (+) replacement: combine parents and offspring, select best N.

• Elitism: carry forward the top e individuals untouched to next generation (prevents degen-
eration).

9. Termination Conditions Common choices:

• Max generations reached.

• No improvement over g generations.

• Time budget exhausted.

• Achieved acceptable fitness.

3.7 Diversity and Convergence Control

Monitor diversity (e.g., average pairwise Hamming distance or permutation distance). If diversity
drops quickly:
• Increase mutation rate adaptively,

• Reintroduce random individuals,

• Use niching techniques or crowding to maintain multimodal exploration.

10
3.8 Parameter Guidelines (starting points)
• Population size N: 20–200 (small problems 20–50; larger problems 100+).

• Crossover probability pc : 0.6–0.9.

• Mutation probability pm : binary 0.001–0.01 per bit; permutation 0.05–0.2 per chromosome.

• Tournament size k: 2–5.

• Elitism: keep top 1–5% individuals.

3.9 Worked Toy Example (TSP with 5 cities) — detailed generation walk-
through
We will illustrate a single-generation GA on the same 5-city TSP used previously. Distance
matrix:

A B C D E
A 0 2 9 10 7
B 2 0 6 4 3
C 9 6 0 8 5
D 10 4 8 0 6
E 7 3 5 6 0
Encoding: permutation of cities. We use PMX or OX for crossover (PMX illustrated).
GA settings:

N = 4, pc = 0.9, pm = 0.2 (mutation per offspring), tournament k = 2, elitism e = 1.

Initial population (random + heuristic seed):

S1 = [A, B,C, D, E], E(S1 ) = 29

S2 = [B, D,C, E, A], E(S2 ) = 31
S3 = [C, E, A, D, B], E(S3 ) = 26
S4 = [A, E,C, B, D], E(S4 ) = 30

(Compute each total cost via the matrix — arithmetic shown in class.)

Compute fitness (minimization → fitness): Use f (S) = 1/E(S).

f = {1/29, 1/31, 1/26, 1/30} ≈ {0.0345, 0.0323, 0.0385, 0.0333}

Selection (tournament k=2 for each parent): - To pick Parent A: randomly sample two
individuals, choose one with higher fitness. - Suppose tournament picks S2 and S3 → selects S3
(fitness 0.0385). - To pick Parent B: picks S1 and S4 → selects S1 (0.0345).
Thus Parent Pair 1: S3 and S1 .
Repeat for Parent Pair 2: suppose picks S4 and S2 → selects S4 and S3 -> Parent Pair 2:
S4 , S 3 .

11
Crossover (apply PMX with cut points at positions 2 and 4 — 1-based): Parent1 S3 =
[C, E, A, D, B] Parent2 S1 = [A, B,C, D, E]
PMX steps (pair 1):
1. Cut between positions 2 and 4. Middle segments:

P1mid = [E, A, D], P2mid = [B,C, D]

2. Child1: copy middle segment from P1 at same positions:

Child1 = [_, E, A, D, _]

3. Map relationships from the swapped segment: E ↔ B, A ↔ C, D ↔ D.

4. Fill remaining positions from P2 in order, applying mapping if conflict: - P2 order: [A, B,
C, D, E]. - Position1 for child: try A — but A maps to C (since AC) and C is not present in
middle -> after mapping we resolve conflicts as per PMX rules. (Work through mapping
carefully on board.)

5. Final Child1 (after mapping conflict resolution) might be: [A, E, A, D,C] — invalid (dupli-
cate A) — repair via PMX mapping yields proper permutation. Show mapping table and
final offspring:
Child1 = [A, E,C, D, B]

6. Similarly create Child2.

(In class, show step-by-step PMX mapping table and how duplicates are resolved — use
PMX diagram.)

Mutation (swap mutation with probability 0.2) Apply mutation to each child with prob-
ability 0.2: - Suppose Child1 mutated: swap positions 4 and 5 → convert [A, E,C, D, B] to
[A, E,C, B, D]. - Child2 unchanged.

Repair: For PMX this step generally ensures children are valid permutations; validate and
repair if necessary.

Evaluation: compute E(child) and fitness. Suppose after evaluation:

E(child1) = 27, E(child2) = 28

Fitnesss accordingly.

Replacement with elitism (e=1): Keep best of previous generation (say S3 with E=26)
automatically into next generation. Fill remaining 3 spots with best offspring and remaining
parents as per (+) or generational replacement policy. Suppose new population becomes:

{S3 (elite), child1, child2, S1 }

12
Observe: After one generation:
• Best improved from 26 (original) — perhaps unchanged or better if child1 had 25.

• Diversity should be measured; if collapse occurs, increase mutation.

(Detailed arithmetic for every distance addition, mapping tables, and mutation steps
should be shown on the board or in slides — provide printed table for students.)

3.10 Operator Design Recommendations for Different Problem Types

Binary (feature-selection / subset problems)
• Encoding: bitstring where bit=1 means include feature.

• Crossover: single/two-point or uniform.

• Mutation: bit-flip.

• Constraint handling: use penalty on number of selected features or repair to meet cardinality
constraints.

Permutation (TSP, sequencing)

• Encoding: permutation of items.

• Crossover: PMX, OX, CX (designed to produce valid permutations).

• Mutation: swap, inversion, scramble.

• Repair: use mapping-based repair for invalid offspring or prefer permutation-preserving

operators.

Real-valued (continuous optimization)

• Encoding: vector of reals.

• Crossover: BLX-α, SBX, arithmetic crossover.

• Mutation: Gaussian perturbation, polynomial mutation.

• Constraint handling: project into feasible set or use penalized fitness.

3.11 Constraint Handling Approaches (summary)

1. Feasible-preserving operators when possible.

2. Repair functions (e.g., mapping duplicates in permutations).

3. Penalty functions: static, dynamic, or adaptive penalties.

4. Specialized decoders: encode genotype that decodes to feasible phenotype.

13
3.12 Advanced Topics / Variants (brief)
• Adaptive GAs: self-adaptive mutation/crossover rates based on diversity or success rates.

• Island models / distributed GAs: multiple subpopulations with migration (good for
parallelism).

• Memetic algorithms: combine GA with local search (apply hill-climb or tabu locally to
offspring).

• Multi-objective GAs (NSGA-II, SPEA2): maintain Pareto front for multi-objective prob-
lems.

3.13 Practical classroom/lab projects

• Implement GA for 10-city TSP and plot best/average fitness vs generation.

• Experiment: vary mutation rate and population size, observe premature convergence vs
exploration.

• Hybrid experiment: GA + local search (2-opt) and compare convergence speed solution
quality.

3.14 References and useful diagrams

• GA flowchart and operator diagrams (use in slides): see flowcharts.

• PMX / OX crossover diagrams (permutation crossover examples).

• Ordered crossover animation / explanation (useful video):

Instructor notes: show one full generation on the board with mapping tables for PMX,
compute costs exactly, and print the intermediate offspring. Encourage students to implement
the same toy instance in Python to observe GA dynamics.

14