Genetic Algorithm
Artificial Intelligence [SE 333]
Tamanna Rahaman
1
Backtracking Algorithm
A backtracking algorithm is a problem-solving technique that systematically
explores all possible options to build a solution incrementally, undoing
(backtracking) the previous choice as soon as it determines that the current
path cannot lead to a valid final solution.
try → check → undo → try another option
2
4 Queen Problem
The 4 Queens Problem consists in placing
four queens on a 4 x 4 chessboard so that no
two queens attack each other.
No two queens are allowed to be placed on:
→
The same row
→
The same column
→
The same diagonal
3
Q1 - - - Q1 - - - Q1 - - - Q1 - - -
- - - - Q2 - - - - Q2 - - - Q2
- - - - - - - - - - Q3 - -
- - - - - - - - - - -
- Q1 - - - Q1 - - - Q1 - - - Q1 - -
- - - Q2 - - - Q2 - - - Q2 - -
Q3 - - - Q3 - - - - - - - -
- - Q4 - - - - - - -
4
All possible solution
to 5 Queen Problem
5
Weaknesses of Backtracking Algorithm
1) Slow for large problems
2) May revisit many possibilities
3) High recursion depth
4) worst-case time complexity can be exponential
6
Genetic Algorithm
A Genetic Algorithm (GA) is a population-based evolutionary
optimization technique inspired by the principles of natural selection
and genetics.
First introduced by John Holland in 1975
It works by iteratively evolving a population of candidate solutions
using biologically motivated operators such as selection, crossover and
mutation to find optimal or near-optimal solutions to complex
problems
7
Core Terminology
Population: A set of all available candidate solutions currently being
evaluated.
Chromosome: A single candidate solution represented as a string of
data parameters.
Gene: The smallest building block of a chromosome, representing a
specific variable or trait.
Fitness Function: A problem-specific mathematical formula evaluating
how successfully an individual solves the problem
8
Algorithm Workflow
1) Initialization: The algorithm generates a random pool of
individual solutions to seed the starting population.
2) Fitness Evaluation: Every individual receives a fitness score
based on how well it solves the objective function.
3) Selection: Fitter individuals are stochastically chosen to
become "parents" based on their fitness scores.
4) Crossover: Pairs of parents swap genetic subsets to create
child solutions inheriting the best traits of both.
5) Mutation: Random modifications are introduced to single
genes within the children to maintain genetic diversity and
prevent stagnation.
6) Termination Check: The cycle repeats across multiple
generations until a termination criteria (e.g., target accuracy
or generation limit) is reached.
9
Example of Genetic Algorithm
Q3 Maximum Fitness = (8 X 7)/2 = 28
Fitness = 28 - Number of attacking pairs
Here, number of attacking pair is 5
Q4
So, fitness = 28 – 5 = 23
Q6
Q1
Q2 Q5
Q7 Q8
3 2 7 5 2 4 1 1
10
Example of Genetic Algorithm
11
Real-World Applications
●
Logistics & Scheduling: Optimizing ●
Finance & Trading: Selecting
complex distribution networks and assets, balancing investment
solving routing problems like the portfolios, and building
Traveling Salesperson Problem. programmatic trading rules.
●
Engineering Design: Conceptualizing ●
Healthcare and Treatment
complex structural frameworks, Planning: In oncology, genetic
aerodynamic shapes, and electronic algorithms optimize radiation
circuits. therapy for cancer patients.
●
Machine Learning: Tuning ●
Trajectory and Path Planning:
hyperparameters and conducting GAs calculate optimal routes for
automated feature selection for autonomous robots moving
multi-layered neural networks. through dynamic environments.
12