Optimization in Engineering

• Decision-making is central to engineering design (sizing, dimensioning,

planning).
• Examples: aircraft wing material/structure, civil engineering roof design.
• Goal: maximize or minimize an objective function.
• Formal definition:
• Minimization → find 𝑋0 ∈ 𝐴 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝐹 𝑋0 ≤ 𝐹 𝑋 .
• Maximization → find 𝑋0 ∈ 𝐴 𝑠𝑢𝑐ℎ 𝑡ℎ𝑎𝑡 𝐹 𝑋0 ≥ 𝐹 𝑋 .
Key Questions in Optimization
• Does an optimal solution exist?
• Is it unique?
• What procedure finds it?
• How sensitive is the solution?
• How does it behave under parameter changes?
Classical Optimization Problems
• Since 1940, tackled by traditional methods:
• Linear programming
• Transportation & assignment problems
• Nonlinear programming
• Dynamic programming
• Inventory control
• Queuing theory
• Replacement problems
• Scheduling
Search Techniques
• Deterministic search: uses gradient-based methods (e.g., steepest descent).
• Stochastic search: introduces randomness (probabilistic exploration).
• Both aim to improve reliability of reaching near-optimal solutions.
• Transition rules guide movement toward better solutions.
Nontraditional Search Methods
• Popular in recent engineering optimization:
• Simulated annealing (Kirkpatrick, 1983)
• Ant colony optimization (Dorigo & Caro, 1999)
• Random cost method (Kost & Baumann, 1999)
• Evolution strategy (Kost, 1995)
• Genetic algorithms (Holland, 1975)
• Cellular automata (Wolfram, 1994)
Inspirations Behind Methods
• Simulated annealing: mimics cooling of molten metals.
• Genetic algorithms & evolution strategies: mimic natural genetics and
selection.
• Swarm intelligence: inspired by collective behavior of ants, bees, termites.
• Example: Ant colony optimization for network traffic routing.
• Random cost: stochastic uphill/downhill moves, escapes dead ends.
Genetic Algorithms (GA)
• Developed by John Holland (1975).
• Mimic natural selection and genetic evolution.
• Operate on a population of candidate solutions.
• Use operators: selection, crossover, mutation.
• Aim: evolve better solutions over successive generations.
History of Genetic Algorithms
• 1960s: Evolutionary computing introduced by I. Rechenberg
(Evolutionary Strategies).
• 1975: Prof. John Holland (University of Michigan) published
seminal GA work.
• Key references: Holland (1975), Goldberg (1989), Davis (1991),
Michalewicz (1992), Deb (1995).
• First engineering applications:
• Goldberg & Samtani (1986) → optimization of a 10-member plane
truss.
• Jenkins (1991) → trussed beam structure.
• Deb (1991), Rajeev & Krishnamoorthy (1992) → structural engineering.
• Other fields: biology, computer science, image processing,
pattern recognition, physical sciences, social sciences, neural
networks.
Basic Concepts of GA
• GA = computerized search & optimization based on natural
genetics & selection.
• Effective for large, complex search spaces.
• Key differences from traditional optimization:
• Works with coded variables (genetic space).
• Uses a population of solutions (not single point).
• Employs randomized operators (vs deterministic transition rules).
• Three essentials for GA design:
• Define objective function.
• Define genetic representation (chromosomes).
• Define genetic operators (selection, crossover, mutation)
Biological Background
• Organisms → cells → chromosomes → DNA → genes.
• Gene: encodes a trait (e.g., eye color).
• Alleles: possible settings of a trait (e.g., blue, brown
eyes).
• Locus: position of a gene on chromosome.
• Genome: complete set of genetic material.
• Genotype: specific set of genes in genome.
• Phenotype: physical/mental characteristics
expressed (e.g., eye color, intelligence).
Why GA Works
• Population-based search → explores multiple
solutions simultaneously.
• Randomized operators → adaptive exploration of
search space.
• Coding of variables → discretizes continuous
functions for easier manipulation.
• Can be extended for:
• Multiple optima (species).
• Parallelization for faster search.
• Performance improvements via operator variations.
8.3 Creation of Offspring (Genetic Algorithm)
• Offspring are created through recombination (crossover)
• Crossover combines genes from both parents to form a new chromosome
• Newly created offspring may undergo mutation
• Mutation: small random changes in DNA caused by copying errors
• Mutation helps in maintaining diversity in the population
• Fitness of an organism is measured by its success in solving the problem

8.3.1 Search Space

• Search space: set of all possible feasible solutions to a problem
• Each solution in the search space has a fitness value
• Finding a solution means searching for an optimal point
• Maximum (best fitness) or Minimum (least cost)
• Search space can be:
• Known at the beginning
• Explored gradually as the algorithm progresses
• Challenges of Search Space
• Search space is often large and complex
• Difficult to know:
• Where to start
• Where the optimal solution lies
• Traditional methods may get stuck in local optima

• Role of Genetic Algorithm (GA)

• Genetic Algorithms are inspired by Darwin’s theory of survival of the fittest
• GA starts with a population of solutions (chromosomes)
• New populations are generated from existing ones
• Solutions are selected based on fitness
• Fitter solutions have a higher chance of reproduction
• Process continues until:
• Desired solution quality is achieved
• Maximum number of generations is reached
• Genetic Algorithm – Example
Problem: Maximize
• 𝑓 𝑥 = 𝑥 2, 𝑥 ∈ 0 7
• Search Space:
• 01234567
• Each solution has a fitness value 𝑓 𝑥
• Initial Population:
• 2463
• Binary Encoding:
• 2 → 010
• 4 → 100
• 6 → 110
• 3 → 011
• Selection:
• Fitter chromosomes have higher chance to reproduce
• Selected parents: 6 (110) and 4 (100)
• Single-Point Crossover:
• Parent 1: 1 | 1 0
Parent 2: 1 | 0 0
• Offspring after crossover:
• 100 (4)
• 110 (6)
• Mutation & Result
• Mutation: Small random gene change
• 110 → 111
• New Population:
• {7,4,6}
• Best Solution Found:
• 𝑥 = 7, 𝑓 𝑥 = 49
8.4 Working Principle of Genetic Algorithm (GA)

• Unconstrained Optimization Problem

• Genetic Algorithm can be used to solve optimization problems
• Consider a general maximization problem:
• Maximize 𝑓 𝑋

• Handling Minimization Using GA

• GA is naturally suited for maximization
• A minimization problem can be converted into a maximization problem:
• If 𝑓 𝑋 > 0:
1
• Minimize 𝑓 𝑋 ⇒ Maximize 𝑓 𝑋
• If 𝑓 𝑋 < 0:
• Minimize 𝑓 𝑋 ⇒ Maximize −𝑓 𝑋
• Hence, both minimization and maximization problems can be solved using GA
• Comparison with Regression Analysis
• In multiple regression analysis:
• For 𝑘 independent variables
• Number of possible subsets:
• 2 𝑘+1 −1
(including intercept)
• As number of variables increases:
• Number of subsets grows exponentially
• Computational complexity becomes very high

Number of Variables Number of Subsets

2 7
3 15
9 1023
19 10,48,578
• Advantage of Genetic Algorithm
• GA does not evaluate all subsets
• Variables are coded as chromosomes
• GA searches the solution space using:
• Selection
• Crossover
• Mutation
• Efficiently finds near-optimal solutions with less
computation
8.5 Encoding in Genetic Algorithm
• What is Encoding?
• In Genetic Algorithm (GA), encoding is the process of representing problem
variables as chromosomes so that genetic operators like:
• selection
• crossover
• mutation
• Each chromosome is made up of genes, and each gene represents part of a solution.
• Different Ways of Encoding
• According to John Holland (1975):
• Genes can be represented in many forms:
• Bit strings
• Arrays
• Trees
• Lists
• However, the most commonly used and simplest method is binary encoding, which is
discussed here.
• 8.5.1 Binary Encoding
What is Binary Encoding?
• Each gene is represented using 0 or 1
• A chromosome is a string of bits
• Meaning of bits depends on the problem

• Example: Knapsack Problem

• Problem idea:
• There are several items, each with a value and size
• Knapsack has a fixed capacity
• Select items without exceeding capacity
• Binary Encoding rule:
• 1 → item is selected
• 0 → item is not selected
• Example chromosome:
• 101101100011
• Each bit corresponds to one item
• This chromosome represents one possible solution
• Encoding Variables in Optimization Problems
• In GA, unknown variables 𝑋𝑖 are coded into binary strings
• Though GA can work directly on variables, binary encoding is most common
• Length of the binary string decides solution accuracy

• 4-bit Binary Encoding Example

• A 4-bit binary string can represent:
• 24 = 16 values 0 to 15
• Example:
• 0000 → 0
• 0111 → 7
• 1111 → 15
• So, more bits ⇒ higher precision
• Binary to Decimal (Decoding)
• Binary string:
• 0111
• Decoded value:
• 0 × 23 + 1 × 22 + 1 × 21 + 1 × 20 = 7
• This process is called decoding.
• Encoding Multiple Variables
• If a problem has two variables 𝑋1 , 𝑋2 and each uses 4 bits:
• X₁ = 1011
X₂ = 0110
• Combined chromosome:
• 10110110
• Each substring represents one variable
• Minimum value → 0000
• Maximum value → 1111
• Mapping Binary Value to Actual Variable
• Since variables have upper and lower limits, binary values are mapped
linearly:
decoded value
• 𝑋𝑖 = 𝑋𝑚𝑖𝑛 + 𝑋𝑚𝑎𝑥 − 𝑋𝑚𝑖𝑛
2𝑛 −1
• This converts binary code into a real-world value.

• Accuracy of Encoding
1
• With 4 bits → accuracy = of search space
16
1
• With 5 bits → accuracy =
32
• Given
• Formula:
𝑋𝑖𝑈 −𝑋𝑖𝐿
• 𝑋𝑖 = 𝑋𝑖𝐿 + × decoded value
2𝑛 −1
• Where:
• 𝑋𝑖𝐿 =lower limit
• 𝑋𝑖𝑈 =upper limit
• 𝑛= number of bits
• decoded value = decimal value of binary string

• From the Problem

• Binary string: 1010 in range Xi ∈ [2,17]
• Number of bits 𝑛 = 4
• Lower limit 𝑋𝑖𝐿 = 2
• Upper limit 𝑋𝑖𝑈 = 17
• Step 1: Decode Binary Value
• Binary: 1010
1 × 23 + 0 × 22 + 1 × 21 + 0 × 20
=8+0+2+0
= 10
• Decoded value = 10

• Step 2: Substitute in Formula

17−2
• 𝑋𝑖 = 2 + × 10
24 −1
• Step 3: Simplify
24 = 16
24 − 1 = 15
17 − 2 = 15
So:
15
𝑋𝑖 = 2 + × 10
15
• Step 4: Final Calculation
𝑋𝑖 = 2 + 10
𝑋𝑖 = 12
• Meaning
The 4-bit binary string (1010) represents the real value 12 in the
search space [2, 17].
Encode the following values using the concept of binary encoding and
represent the output in GA format. (i) 542 (ii) 492

• Final GA Representation
Chromosome A : 1000011110 (542)
Chromosome B : 0111101100 (492)
8.5.2 Octal Encoding (0–7)
• What is Octal Encoding?
• In octal encoding, numbers are represented using base-8 digits.
• Allowed digits:
• 01234567
• Each position represents a power of 8.
• Example positional values:
• 83 , 82 , 81 , 80

• Step 1: Encoding (Decimal → Octal)

• To convert a decimal number to octal:
• Divide the number by 8 repeatedly
• Record the remainders
• Read remainders from bottom to top
Step 1: Encoding (Decimal → Octal)
1. To convert a decimal number to octal:
2. Divide the number by 8 repeatedly
3. Record the remainders
4. Read remainders from bottom to top
Example: Encode 542
Division Quotient Remainder
542 ÷ 8 67 6
67 ÷ 8 8 3
8÷8 1 0
1÷8 0 1

Read bottom → top

54210 = 10368
GA Representation
Chromosome = 1036
• Step 2: Decoding (Octal → Decimal)
• To decode an octal number, multiply digits by powers of 8.
• Example:
1036
1 × 83 + 0 × 82 + 3 × 81 + 6 × 80
= 512 + 0 + 24 + 6
= 542
So,
10368 = 54210
• Range of Octal Encoding
If we use n octal digits, the number of values is:
8𝑛
Example:

Octal digits Maximum Value

1 digit 7
2 digits 63
3 digits 511
4 digits 4095

So a 4-digit octal string can represent:

0 to 4095
Example limits:
0000 → minimum
7777 → maximum
• Accuracy in Octal Encoding
Accuracy depends on the number of octal digits.
For n octal digits:
1
Accuracy =
8𝑛
Example:

Digits Accuracy
1 1/8
2 1/64
3 1/512
4 1/4096

Increasing the number of digits improves precision.

8.5.3 Hexadecimal Encoding (Base-16)
What is Hexadecimal Encoding?
• Hexadecimal encoding uses base-16 digits.
• Allowed symbols:
0123456789ABCDEF
• Where:
Symbol Value
A 10
B 11
C 12
D 13
E 14
F 15

Each position represents a power of 16.

163 , 162 , 161 , 160
Step 1: Encoding (Decimal → Hexadecimal)
• To convert a decimal number to hexadecimal:
• Divide the number by 16 repeatedly
• Record remainders
• Convert remainder values 10–15 → A–F
• Read remainders from bottom to top

Example: Encode 67897

Division Quotient Remainder

67897 ÷ 16 4243 9
4243 ÷ 16 265 3
265 ÷ 16 16 9
16 ÷ 16 1 0
1 ÷ 16 0 1

Read bottom → top

6789710 = 1093916
GA Representation
Chromosome = 10939
• Step 2: Decoding (Hexadecimal → Decimal)
Example given in the text:
B079E6
Convert using powers of 16.
Values:
B = 11
11 × 165 + 0 × 164 + 7 × 163 + 9 × 162 + 14 × 161 + 6 × 160
= 11565542
So,
𝐵079𝐸616 = 1156554210
Range of Hexadecimal Encoding
If we use n hexadecimal digits, total values:
16𝑛
Example:

Digits Maximum Value

1 15
2 255
3 4095
4 65535

So 4-digit hexadecimal represents:

0 to 65535
Minimum and maximum chromosome:
0000 → minimum
FFFF → maximum
Accuracy in Hexadecimal Encoding
Accuracy depends on number of digits.
For n digits:
1
Accuracy =
16𝑛
Example:

Digits Accuracy
1 1/16
2 1/256
3 1/4096
4 1/65536

Increasing digits → better precision

8.5.4 Permutation Encoding
• What is Permutation Encoding?
• Used for ordering problems
• A chromosome is a sequence of numbers
• Each number appears exactly once
• The order of numbers represents a solution

• Example Chromosomes
• Chromosome A: 1 5 3 2 4 7 9 8 6
Chromosome B: 8 5 6 7 2 3 1 4 9
• Each chromosome is a permutation (arrangement) of numbers
• No number is repeated, none is missing
• Where is it Used?
• Permutation encoding is used in problems where:
• Order matters
• Each item must appear once
• Examples:
• Travelling Salesman Problem (TSP)
• Task scheduling
• Job sequencing

• Example: Travelling Salesman Problem (TSP)

• Problem
• A salesman must visit all cities once
• Return to the starting point
• Goal: Minimize total distance
• Encoding in GA • Important Property
• Suppose cities are numbered: • Each city appears only once
• 1, 2, 3, 4, 5
Order defines the route
• A chromosome: • Problem with Genetic Operators
• 13524 • After applying:
• Means: • Crossover
• Start at city 1 • Mutation
• Go to 3 → 5 → 2 → 4 • We may get invalid solutions like:
• 13352
• We may get invalid solutions like:
Repeated city (3)
• 13352 Missing city (4)
• Repeated city (3)
Missing city (4)
• Solution
• Apply correction/repair methods
• Ensure chromosome remains a valid permutation

• Why Not Binary Encoding Here?

• Binary encoding cannot easily represent order
• Permutation encoding directly represents sequence problems
8.5.5 Value Encoding
• What is Value Encoding?
• In value encoding, a chromosome is a sequence of actual values
• These values can be:
• Real numbers
• Characters
• Strings
• Symbols
• Each value directly represents a solution parameter
• Examples of Chromosomes
• Chromosome A: 1.234 5.3243 0.4556 2.0253
• Chromosome B: a b d j e t i j d h j
• Chromosome C: (Back, Right, Forward, Left)
• Values are problem-specific, not restricted to 0/1 or numbers like
permutation.
• Where is it Used? • Each chromosome:
• Value encoding is used when: • [0.5, -1.2, 0.8, 2.1]
• Binary or permutation encoding is not • Each value represents a weight of a
suitable connection
• Problem involves real or complex data • Input → Hidden layer weights
• Hidden → Output layer weights
• Examples:
• Neural networks (weights) • Advantages
• Control systems • Direct representation of real values
• Path planning • No need for decoding
• More natural for many real-world problems
• Strategy representation

• Disadvantages
• Example: Neural Network Weights
• Standard crossover/mutation may not work
• Problem properly
• Need custom genetic operators
• Find the weights of connections in a • More problem-specific design required
neural network
• Encoding
Key Difference from Other Encodings
Encoding Representation
Binary 0s and 1s
Permutation Order of numbers
Value Actual real/complex values
8.5.6 Tree Encoding
• What is Tree Encoding?
• In tree encoding, a chromosome is represented as a tree structure
• Nodes of the tree contain:
• Functions (e.g., +, −, ×, ÷)
• Operands/variables (e.g., X, numbers)
• Each chromosome represents a mathematical expression or program

• Structure of Tree Encoding

• Example expression:
• 𝑋+3 ×5
• Tree form:
• *
/\
+ 5
/\
X 3
• This tree is the chromosome
• Where is it Used?
• Tree encoding is mainly used in:
• Genetic Programming (GP)
• Evolving mathematical expressions
• Automatic program generation

• Why Tree Encoding is Useful

• Naturally represents programs and expressions
• Easy to apply operations on subtrees
• Flexible for complex problems

• Role of LISP
• LISP programming language is often used
• Because:
• Programs are already in tree-like structure
• Easy to manipulate and apply genetic operators
• Example Problem
• Given input-output data
• Find a function that best fits the data

• Encoding
• Chromosome = Function as a tree
• Example:
• +
/\
* 2
/\
X X
• This represents:
• 𝑋×𝑋 +2
• Genetic Operations in Tree Encoding
• Crossover → swap subtrees
• Mutation → change a node or subtree
• Advantages
• Can represent complex formulas/programs
• No need for predefined structure
• Very powerful for symbolic problems

• Disadvantages
• Complex to implement
• Trees can become very large (bloat problem)
• Requires special operators
• Fitness Function in Genetic Algorithm
• Fitness function evaluates quality of a solution
• Derived from objective function
• Used to:
• Compare solutions
• Select best individuals
• Higher fitness = better solution

• Objective vs Fitness Function

• GA works naturally with maximization
• Maximization:
• 𝐹 𝑋 =𝑓 𝑋
• Minimization:
1
• 𝐹 𝑋 = or 𝐹 𝑋 = −𝑓 𝑋
𝑓 𝑋
• Convert minimization → maximization
• Important Condition
• Fitness function should be non-negative
• Sometimes constants are added to ensure this
• Example:
• 𝐹 = −𝑓 𝑋 − 𝐶

• Selection Based on Fitness

• Probability of selection:
𝐹𝑖
• 𝑃𝑖 =
෍𝐹𝑗
• Higher fitness → higher chance to reproduce
• Two-Bar Pendulum Problem Example
• Two rods connected at joints A and B
• External force applied at point C
• Given:
• 𝑃=2
• 𝑊1 = 2, 𝑊2 = 2
• 𝑙1 = 𝑙2 = 2

• Objective of the Problem

• Find angles:
• 𝜃1 , 𝜃2
• Such that:
Π 𝜃1 𝜃2
is minimum (equilibrium condition)
• Objective Function
• Π = −4 sin 𝜃1 − 6 cos 𝜃1 − 4 sin 𝜃2 − 2 cos 𝜃2
• Represents total potential energy

• Convert to Fitness Function

• Since GA uses maximization:
• 𝐹 = −Π − 7
• Converts minimization → maximization
• Constant ensures positive fitness values
• Encoding of Variables
• Two variables: 𝜃1 , 𝜃2
• Each represented using 4 bits
• Chromosome = [θ₁ | θ₂] = 8 bits
• Example:
• 0010 0001

• Binary to Angle Mapping

Binary Angle
0000 0°
0001 6°
... ...
1111 90°
• Fitness Evaluation Process
• Decode chromosome
• Obtain 𝜃1 , 𝜃2
• Substitute into equation
• Compute fitness 𝐹
• Example Results
θ₁ θ₂ Fitness
0° 0° 1
12° 6° 2.10
36° 60° 4.60
42° 72° 4.55

• Higher fitness = better configuration

• GA Working on Pendulum
• Start with random population
• Evaluate fitness
• Select best solutions
• Apply crossover & mutation
• Repeat until optimal solution

• Final Result
• Optimal angles:
• 𝜃1 = 33.7∘ , 𝜃2 = 63.43∘
• Corresponds to minimum potential energy

• Conclusion
• Fitness function guides GA toward optimal solution
• Pendulum problem solved by:
• Encoding variables
• Evaluating fitness
• Iterative improvement
• Reproduction in Genetic Algorithm
• Reproduction = selection of chromosomes
• First operator applied in GA
• Based on Darwin’s survival of the fittest
• Better solutions are selected to create offspring

• Purpose of Reproduction
• Select parent chromosomes
• Form pool
• Increase copies of good solutions
• Above-average solutions get higher chance
• Types of Selection Methods
• Roulette Wheel Selection
• Tournament Selection
• Rank Selection
• Boltzmann Selection
• Steady-State Selection

• Roulette Wheel Selection

• Most commonly used method
• Selection probability depends on fitness
𝐹𝑖
• 𝑝𝑖 =
෍𝐹𝑗

• Higher fitness → higher probability

• Steps in Roulette Wheel Selection
• Calculate fitness of all individuals
• Compute probability 𝑝𝑖
• Compute cumulative probability 𝑃𝑖
• Generate random numbers (0–1)
• Select individuals based on range
• Probability Example
Individual Fitness Probability
1 1 0.0429
5 4.66 0.200
8 4.55 0.1955
• Expected Count
• Expected count = 𝑛 × 𝑝𝑖
• 𝑛 =population size
• Shows how many copies expected

• Cumulative Probability
• Add probabilities sequentially
• Example:
• P5 = P1 + P2 + P3 + P4 + P5
• Final value = 1
• Selection Using Random Numbers
• Generate random numbers (0–1)
• Match with cumulative ranges
• Example:
• Random = 0.428 → selects 4th individual

• Key Observation
• High fitness → more copies
• Low fitness → fewer or no copies
• Weak solutions are eliminated gradually

• Important Note
• Selection is probabilistic, not exact
• Sometimes weaker solution may be selected
• Sometimes stronger solution may be skipped
• Selection Using Random Numbers
• Generate random numbers (0–1)
• Match with cumulative ranges
• Example:
• Random = 0.428 → selects 4th individual

• Key Observation
• High fitness → more copies
• Low fitness → fewer or no copies
• Weak solutions are eliminated gradually

• Important Note
• Selection is probabilistic, not exact
• Sometimes weaker solution may be selected
• Sometimes stronger solution may be skipped
• Limitation of Roulette Wheel
• Noisy selection
• May not always match expected counts

• Improved Method
• Stochastic Remainder Selection
• Uses:
• Integer part (fixed copies)
• Decimal part (probabilistic selection)
• More stable and less noisy
• Example: Roulette Wheel Selection
• Step 1: Given Population
Chromosome Fitness (F)
C1 10
C2 20
C3 30
C4 40

• Step 2: Total Fitness

• σ 𝐹 = 10 + 20 + 30 + 40 = 100
• Step 3: Calculate Probability
𝐹𝑖
𝑝𝑖 =
σ𝐹
Chromosome Fitness Probability (p_i)
C1 10 0.10
C2 20 0.20
C3 30 0.30
C4 40 0.40

• Step 4: Cumulative Probability

Chromosome Range
C1 0.00 – 0.10
C2 0.10 – 0.30
C3 0.30 – 0.60
C4 0.60 – 1.00
• Step 5: Generate Random Numbers
• Assume:
• 0.05, 0.25, 0.50, 0.80

• Step 6: Selection

Random No. Selected Chromosome

0.05 C1
0.25 C2
0.50 C3
0.80 C4

• Final Pool
• C1, C2, C3, C4
• Boltzmann Selection in GA
• Inspired by Simulated Annealing
• Based on temperature control
• Uses Boltzmann probability distribution
• Helps balance exploration and exploitation

• Basic Idea
• At high temperature (T):
• All solutions have almost equal chance
• More exploration
• At low temperature (T):
• Better solutions are preferred
• More exploitation
• Boltzmann Probability
𝐸
−
• 𝑃 𝐸 =𝑒 𝑘𝑇

• Where:
• 𝐸= energy (objective value)
• 𝑇= temperature
• 𝑘= constant
• Lower energy → higher probability

• Concept in GA
• Replace fitness-based selection with:
• Temperature-based probability
• Selection changes over time:
• Early stage → random search
• Later stage → focused search
• Simple Example
• Given Fitness (converted to energy)
Chromosome Energy (E)
C1 2
C2 4
C3 6
C4 8
• Case 1: High Temperature (T = 100)
• 𝑃 𝐸 ≈ 𝑒 −𝐸/100
Chromosome Probability
C1 ~0.98
C2 ~0.96
C3 ~0.94
C4 ~0.92
• Tournament Selection in GA
• Selection method based on competition
• A group of individuals compete
• Best among them is selected
• Ensures better solutions are chosen

• Key Concepts
• Population Diversity
• Maintains variety of solutions
• Helps explore new search space
• Selective Pressure
• Favors better individuals
• Controls speed of convergence
• Selective Pressure Effect
• High pressure → fast convergence but risk of local optimum
• Low pressure → slow convergence
• Need balance between:
• Exploration
• Exploitation

• Why Not Roulette Wheel?

• Problems:
• Low selection pressure → slow improvement
• High chance of premature convergence
• Tournament selection solves this
• Tournament Selection Process
• Randomly select k individuals (usually k = 2)
• Compare their fitness
• Select the best (winner)
• Add winner to pool
• Repeat until pool is filled
• Given Example
Individual Fitness
1 1
2 2.10
3 3.11
4 4.01
5 4.66
6 1.91
7 1.93
8 4.55
• Step-by-Step Selection
• Step 1:
• Compare: 2 vs 4
• Winner: 4
• Step 2:
• Compare: 3 vs 8
• Winner: 8
• Step 3:
• Compare: 1 vs 3
• Winner: 3

• More Selections
• 4 vs 5 → 5
• 1 vs 6 → 6
• 1 vs 2 → 2
• 4 vs 2 → 4
• 8 vs 3 → 8
• Final Pool
• 4, 8, 3, 5, 6, 2, 4, 8
• Observations:
• Best individuals selected more times
• Weak individuals may be removed

• Key Observation
• Individuals 4 & 8 → selected twice
• Individuals 1 & 7 → not selected
• Strong solutions dominate
• Advantages
• Simple and fast
• Good control over selection pressure
• Avoids issues of roulette wheel

• Disadvantages
• May lose some useful solutions
• Needs proper tournament size

• Conclusion
• Tournament selection uses competition-based selection
• Provides better balance of:
• Diversity
• Selection pressure
• Widely used in modern GA
Rank Selection in GA
• Selection method based on ranking of individuals
• Instead of using actual fitness values
• Uses rank (position)

• Why Rank Selection?

• Problem in Roulette Wheel:
• If one fitness is very high → dominates selection
• Other solutions get very low chance
• Rank selection solves this issue
• Basic Idea
• Sort individuals based on fitness
• Assign ranks:
• Worst → Rank 1
• Best → Rank N
• Use ranks instead of fitness
• Example
• Given Fitness:

Chromosome Fitness
C1 10
C2 20
C3 30
C4 90
Assign Ranks
Chromosome Fitness Rank
C1 10 1
C2 20 2
C3 30 3
C4 90 4

Notice: Large fitness difference is reduced

• Probability Using Rank
Rank𝑖
𝑝𝑖 =
σ Ranks
෍ Ranks = 1 + 2 + 3 + 4 = 10
 Chromosome Rank Probability
C1 1 0.1
C2 2 0.2
C3 3 0.3
C4 4 0.4

Key Observation
•Best chromosome no longer dominates excessively
•All individuals get fair chance

Comparison Insight
•Roulette Wheel → based on actual fitness
•Rank Selection → based on relative position
• Advantages
• Prevents domination by one solution
• Maintains population diversity
• More stable selection

• Disadvantages
• Slower convergence
• Best solution not strongly favored

• Conclusion
• Rank selection avoids bias due to large fitness differences
• Uses ranking to control selection pressure
• Provides balanced and stable evolution
• Steady-State Selection in GA
• Not a specific selection method
• Focuses on population replacement strategy
• Only a few individuals change per generation

• Basic Idea
• Most of the population is kept unchanged
• Only a few:
• Best individuals are selected
• Worst individuals are removed
• New offspring replace weak solutions
• Working Process
• Select a few good individuals (parents)
• Generate offspring using crossover & mutation
• Remove a few worst individuals
• Insert new offspring into population
• Remaining population stays same

• Example
• Initial Population:
• A, B, C, D, E, F
• Fitness:
• A, B → high
• E, F → low
• Step:
• Select A, B → produce offspring X
• Remove E
• Insert X

• New Population:
• A, B, C, D, X, F
• Key Characteristics
• Small changes per generation
• Population evolves gradually
• Maintains good solutions

• Advantages
• Faster convergence
• Preserves good individuals
• Less disruption in population

• Disadvantages
• May reduce diversity
• Risk of getting stuck in local optimum