Genetic Algorithm
MTE 4105(a)
Machine Learning Algorithms
Md. Meraj Ahmed
Lecturer
Department of Mechatronics Engineering, RUET
Evolutionary Algorithms
Algorithms that simulate physical and/or biological behavior in nature to solve
optimization problems
Biological Behavior Algorithm Concept
Mimics natural evolution. A population of solutions
Genetic Algorithm
Genetics and Evolution evolves over generations using selection, crossover
(GA) (reproduction), and mutation to improve.
Mimics how neurons in the brain learn and process
Artificial Neural information. ANNs learn from data through adjusting
Human Nervous System
Network (ANN) weights in a structure inspired by biological neural
networks.
Ant Colony Mimics ants finding the shortest path by laying and
Behaviour of Ant Colony
Optimization (ACO) following virtual pheromone trails
Physical Behaviour Algorithm Concept
Mimics human thinking with shades of grey, using
Learning Fuzzy Logic (FL) degrees of truth to handle uncertainty and
approximate reasoning
Mimics bird flocking, where particles move by
Swarming/grouping of Particle Swarming
following the best and updating from their own and
particles Optimization (PSO)
neighbors’ experience
08/18/2025 MTE 4105(a) Machine Learning Algorithms 2
Genetic Algorithm
• Genetic Algorithms (GAs) are adaptive *heuristic search algorithms that belong
to the larger part of evolutionary algorithms.
• Based on the ideas/principles of natural selection and genetics.
• Genetic algorithm simulate the process of natural selection which means those
species who can adapt to changes in their environment are able to survive and
reproduce and go to next generation.
• In simple words, they simulate “survival of the fittest” among individual of
consecutive generation for solving problem.
*Heuristic search = Smart searching using
educated guesses to make solving problems faster
and more efficient, especially when exploring every
option would take too long.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 3
Genetic Algorithm
• It is frequently used to find optimal or near-optimal solutions to difficult
problems which otherwise would take a lifetime to solve.
• Use techniques inspired by evolutionary biology such as inheritance, mutation,
selection, and crossover.
• The evolution usually starts from a population of randomly generated individuals
and happens in generations.
• In each generation, the fitness of every individual in the population is evaluated,
multiple individuals are selected from the current population (based on their fitness)
and modified to form a new population.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 4
Basic Terminology
1. Population: A set of possible solutions (individuals) at each generation.
2. Chromosome (Individual): A single solution in the population. Often
represented as a string (like binary, real numbers, etc.).
3. Gene: A part of the chromosome that represents a specific feature or parameter
of the solution.
4. Allele: The value of a gene. For example, in binary encoding, an allele could be 0
or 1.
5. Genotype: Population in the computational space, usually encoded as a string
(e.g., binary, real numbers, or symbols).
6. Phenotype: The actual solution in the problem space that the genotype
represents.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 5
Basic Terminology
7. Encoding: Process of transforming from the phenotype to genotype space.
8. Decoding: Process of transforming a genotype to the phenotype space.
9. Fitness function: A fitness function simply defined is a function which takes the
solution as input and produces the suitability of the solution as the output. Evaluates
how good each individual (solution) is at solving the problem
10. Genetic operator: These alter the genetic composition of the offspring. These
include crossover, mutation, selection, etc.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 6
Genotype Representation
It has been observed that improper representation can lead to poor performance of
the GA. Therefore, choosing a proper representation, having a proper definition of
the mappings between the phenotype and genotype spaces is essential for the
success of a GA.
1. Binary
Representation
2. Real-valued
Representation
3. Integer
Representation
4. Permutation
Representation
08/18/2025 MTE 4105(a) Machine Learning Algorithms 7
Step-by-Step Process
1. Begin the algorithm.
2. Initialize a random population of candidate
solutions.
3. Calculate the fitness value for each
individual.
4. Select individuals based on their fitness.
5. Apply crossover to produce new offspring.
6. Apply mutation to introduce variation.
7. Check if the termination criteria are satisfied.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 8
Population Initialization
It involves creating a set of candidate solutions (called individuals or chromosomes)
that the algorithm will evolve over time.
2 Types:
1. Random Initialization (most common)
• Chromosomes are generated randomly within valid ranges
It has been experimentally
• Ensures genetic diversity
observed that the random
2. Heuristic Initialization solutions are the ones to
• Use prior knowledge or partial solutions drive the population to
• Can speed up convergence but may reduce diversity optimality.
• The diversity of the population should be maintained otherwise it might lead to
premature convergence.
• The population size should not be kept very large as it can cause a GA to slow
down, while a smaller population might not be enough for a good mating pool.
Therefore, an optimal population size needs to be decided by trial and error (Trade
off).
08/18/2025 MTE 4105(a) Machine Learning Algorithms 9
Selection
Selection is the process of choosing individuals (parents) from the current
population to form the mating pool, which is used to generate the next
generation. Ex: Roulette Wheel Selection, Tournament Selection, Rank Selection
etc.
Roulette Wheel Selection
In population with ‘n’ individuals,
for each chromosome ‘x’ with
fitness value fx, probability:
fx
P x= 𝑛
∑f i
𝑖=1
08/18/2025 MTE 4105(a) Machine Learning Algorithms 10
Crossover
Crossover is the process of combining the genes of two parent solutions to
create new offspring.
Types of
Crossover
1. Single-Point
Crossover
2. Two-Point
Crossover
3. Uniform
crossover (One bit
shifting)
08/18/2025 MTE 4105(a) Machine Learning Algorithms 11
Mutation
• Mutation is a genetic operator that randomly alters one or more genes in a
chromosome.
• Introduces small random changes to maintain diversity in the population and
avoid premature convergence.
Mutation
Techniques
1. Bit flip Mutation
2. Swap Mutation
3. Scramble
Mutation
4. Inversion
Mutation
08/18/2025 MTE 4105(a) Machine Learning Algorithms 12
Termination Criteria
Usually, we keep one of the following termination conditions:
1. When there has been no improvement in the population for X
iterations.
2. When we reach an absolute number of generations.
3. When the objective function value has reached a certain pre-
defined value.
08/18/2025 MTE 4105(a) Machine Learning Algorithms 13
Example Problem
Problem
Solution
08/18/2025 MTE 4105(a) Machine Learning Algorithms 14
Example Problem
08/18/2025 MTE 4105(a) Machine Learning Algorithms 15
Example Problem
08/18/2025 MTE 4105(a) Machine Learning Algorithms 16
Example Problem
08/18/2025 MTE 4105(a) Machine Learning Algorithms 17
Example Problem
Try Maximize f(x) = x3 – 60x2 + 900x + 100 (0x31)
yourself:
08/18/2025 MTE 4105(a) Machine Learning Algorithms 18
The End
08/18/2025 MTE 4105(a) Machine Learning Algorithms 19
