Here is the complete content for your PDF.
It contains all explanations based on your transcripts with
structured headings and subheadings.
GENETIC ALGORITHM NOTES
This document contains comprehensive explanations of genetic algorithm concepts, encoding techniques,
and crossover operators based on the video transcripts provided.
1. Encoding Techniques in Genetic Algorithm
Introduction
Encoding is the first stage of a genetic algorithm (GA), where chromosomes are represented in a particular
format for computation. Solutions of a problem, called potential or candidate solutions, need to be encoded
before applying GA.
Example Problem
Maximize f(x) = x³, x ∈ [0, 15]. Candidate solutions: 0 to 15.
1. Binary Encoding Technique
• Most common method.
• Chromosomes represented as strings of 0s and 1s.
• Example: 4 chromosomes with 3 genes each:
◦ Chromosome 1: 100
◦ Chromosome 2: 110
• 0-1 Knapsack Problem Example:
◦ Items: A, B, C
◦ Capacity: 25
◦ Encode selection with binary genes: 1 = selected, 0 = not selected.
• Function Example: f(x) = x²/2 + 125/x, x ∈ [0,15]
◦ Binary representation uses 4 bits for each value.
2. Value Encoding Technique
• Genes have real values instead of 0 or 1.
• No need for encoding/decoding.
• Example: Chromosomes for f(x) = x²/2 + 125/x:
◦ Chromosome 1: 5
◦ Chromosome 2: 8
◦ Chromosome 3: 10
◦ Chromosome 4: 13
1
3. Permutation or Order Encoding Technique
• Useful for order-sensitive problems (e.g., Traveling Salesman Problem).
• Chromosome represents the order of processing.
• Example: 5 cities: A, B, C, D, E
◦ Chromosome 1: A → D → C → B → E → A
◦ Chromosome 2: A → B → C → D → E → A
4. Tree Encoding Technique
• Solutions represented as binary trees.
• Can encode equations or looping constructs.
• Example: Chromosome A and B represented as binary trees.
2. Binary Coded Crossover Operators in Genetic Algorithm
Introduction
Binary crossover operators combine two parent chromosomes to create new offspring. Selection of parents
is based on fitness scores.
1. Single Point Crossover
• Select two parents (P1, P2).
• Randomly select one crossover point.
• Swap bits to the right of the crossover point.
• Result: Two new offspring.
2. Two Point Crossover
• Select two crossover points.
• Swap bits between these points.
• Result: New offspring with swapped segments.
3. Multi Point Crossover
• Select more than two crossover points.
• Swap bits at alternate segments.
• Result: New offspring with mixed gene segments.
4. Uniform Crossover
• Toss a coin for each gene to decide swap.
• Head → 1 (swap), Tail → 0 (do not swap).
• Swap genes according to coin toss.
• Result: Two new offspring.
2
5. Half-Uniform Crossover
• Compare corresponding bits of parents.
• Toss coin only for non-matching genes.
• Swap bits where coin toss = 1.
• Result: New offspring.
6. Uniform Crossover with Crossover Mask (CM)
• Create a random mask of 0s and 1s.
• For O1:
◦ Mask = 0 → take bit from P1
◦ Mask = 1 → take bit from P2
• For O2, reverse selection.
• Result: Two new offspring.
7. Shuffle Crossover
• Randomly shuffle genes of both parents.
• Select single point crossover.
• Swap genes after crossover point.
• Result: New offspring.
8. Three Parent Crossover
• Select three parents (P1, P2, P3).
• Offspring O1, O2, O3 generated:
◦ O1: if P1 bit = P2 bit → take P1, else take P3
◦ O2: combination P1, P3, P2
◦ O3: combination P2, P3, P1
• Result: Three offspring with mixed parental bits.
3. Real-Coded Crossover Operators in Genetic Algorithm
Introduction
• Chromosomes contain real numbers.
• Useful for continuous optimization problems.
• Parent selection based on fitness scores.
• Gene selection and parameter alpha or alpha-beta used.
1. Single Arithmetic Crossover
• Select kth gene.
• Alpha parameter (0 ≤ α ≤ 1).
• Offspring formulas: o1_k = (1 - α) * P1_k + α * P2_k o2_k = (1 - α) * P2_k + α * P1_k
3
• Example:
◦ P1_k = 12.76, P2_k = 19.41, α = 0.5
◦ O1_k = O2_k = 16.08
2. Linear Crossover
• Can generate 3 offspring.
• Uses αᵢ and βᵢ for each offspring.
• Formula: O_i = α_i * P1_k + β_i * P2_k
• Example:
◦ P1_k = 12.76, P2_k = 19.41
◦ O1 = 16.08, O2 = 9.43, O3 = 22.73
Key Notes
• Linear crossover increases population diversity.
• Real-coded operators maintain continuity of search space.
4. Summary of Encoding and Crossover Techniques
Encoding / Crossover Type Purpose Example / Notes
Knapsack problem, function
Binary Encoding Represent genes as 0s & 1s
optimization
Value Encoding Genes are direct values f(x) = x²/2 + 125/x
Permutation/Order
Order-sensitive problems TSP: A→D→C→B→E→A
Encoding
Tree Encoding Equations / loops as trees Binary tree representations
Single Point Crossover Swap bits after one point Binary GA
Two Point Crossover Swap bits between two points Binary GA
Multi Point Crossover Swap bits at multiple points Binary GA
Uniform Crossover Coin toss for each gene Binary GA
Swap only non-matching
Half-Uniform Crossover Binary GA
genes
Uniform with Mask Mask decides bit selection Binary GA
Shuffle + single-point
Shuffle Crossover Binary GA
crossover
Three Parent Crossover Mix bits from 3 parents Binary GA
Single Arithmetic Crossover Real gene arithmetic mix Real-coded GA
4
Encoding / Crossover Type Purpose Example / Notes
Linear Crossover Linear combinations α, β Real-coded GA
End of Document
This content is now ready to be converted to a PDF.