Part - A
1. Define Genetic Algorithm (GA).
A Genetic Algorithm (GA) is a population-based optimization technique inspired by natural
selection and genetics. It works by generating a set of possible solutions and improving them
through selection, crossover, and mutation to find the best solution.
2. What is a fitness function?
A fitness function is a mathematical function used to evaluate how good a candidate solution
is. It assigns a fitness value to each individual, and solutions with higher fitness have a better
chance of being selected for reproduction.
3. Why is diversity important in population initialization?
Diversity in the initial population ensures different possible solutions are explored. It helps
avoid premature convergence to a local optimum and increases the chances of finding the
global optimum.
4. Explain roulette wheel selection.
Roulette wheel selection is a probabilistic selection method where each individual gets a
chance of selection proportional to its fitness value. Individuals with higher fitness have a
larger probability of being chosen for the next generation.
5. Define crossover operator.
Crossover is a genetic operator that combines genetic material from two parent chromosomes
to produce offspring. It helps create new solutions by exchanging parts of the parents’ genes,
increasing variation in the population.
6. What are advantages of Genetic Algorithms?
Suitable for complex and nonlinear optimization problems.
Does not require derivative or gradient information.
Can handle large search spaces efficiently.
Less likely to get stuck in local optima due to population-based search.
Part – B :
1. Explain Genetic Algorithms with biological inspiration, terminology, and working
principle.
Genetic Algorithm (GA) – Biological Inspiration, Terminology and Working Principle
(15 Marks)
Introduction
A Genetic Algorithm (GA) is a search and optimization technique inspired by the process of
natural evolution. It is based on the idea of “survival of the fittest” proposed by Charles
Darwin. GA is used to find approximate solutions for complex problems where traditional
methods are difficult to apply.
It belongs to the field of Artificial Intelligence and Evolutionary Computing.
1. Biological Inspiration of Genetic Algorithm
Genetic Algorithms are inspired by the way living organisms evolve over generations.
Concepts from Biology:
1. Natural Selection
In nature, organisms that are better adapted to the environment survive and reproduce.
Weak organisms gradually disappear.
2. Genes and Chromosomes
o A gene is a unit of heredity.
o A chromosome is a set of genes.
In GA, a solution is represented as a chromosome.
3. Reproduction
Organisms reproduce and pass their genes to the next generation.
4. Crossover (Recombination)
During reproduction, genes from two parents mix to form offspring.
5. Mutation
Sometimes small random changes occur in genes. This introduces variation.
6. Survival of the Fittest
Only the fittest individuals survive and pass their genes to the next generation.
Important Terms Explained:
1. Population
A set of candidate solutions at a given time.
2. Chromosome Representation
A solution can be represented as:
o Binary string (e.g., 101010)
o Real numbers
o Permutations
3. Fitness Function
A function used to evaluate how good a solution is.
4. Selection
Process of selecting good solutions for reproduction.
5. Crossover
Combining two parent solutions to produce new offspring.
6. Mutation
Randomly changing some genes to maintain diversity.
3. Working Principle of Genetic Algorithm
The Genetic Algorithm works in the following steps:
Step 1: Initialize Population
Randomly generate an initial population of solutions.
Each solution is called a chromosome.
Step 2: Evaluate Fitness
Calculate the fitness value of each chromosome using a fitness function.
Higher fitness means better solution.
Step 3: Selection
Select the best individuals based on fitness.
Methods: Roulette wheel selection, Tournament selection, etc.
Step 4: Crossover
Select two parents.
Exchange parts of their chromosomes.
Create new offspring.
Example:
Parent 1: 110010
Parent 2: 101111
After crossover:
Child 1: 110111
Child 2: 101010
Step 5: Mutation
Randomly change some genes.
Example: 110111 → 110101
Mutation prevents premature convergence.
Step 6: Create New Generation
Replace old population with new offspring.
Repeat the process.
Step 7: Termination Condition
The algorithm stops when:
Maximum number of generations reached, OR
Desired fitness achieved.
4. Flow of Genetic Algorithm
1. Start
2. Generate Initial Population
3. Evaluate Fitness
4. Selection
5. Crossover
6. Mutation
7. Form New Population
8. Check Termination Condition
9. Stop
5. Advantages of Genetic Algorithm
Can solve complex and nonlinear problems.
Works well for large search spaces.
Does not require gradient information.
Provides global search capability.
Easy to implement.
6. Applications of Genetic Algorithm
Optimization problems
Scheduling problems
Machine Learning
Feature selection
Traveling Salesman Problem
Engineering design optimization
2. Describe roulette wheel, tournament, rank selection, and elitism in detail.
Selection Methods in Genetic Algorithm (15 Marks)
In a Genetic Algorithm (GA), selection is the process of choosing the best individuals
(solutions) from the population to produce the next generation. The main aim of selection is
to give more chance to better solutions so that the overall quality improves.
The common selection methods are:
1. Roulette Wheel Selection
2. Tournament Selection
3. Rank Selection
4. Elitism
1. Roulette Wheel Selection
Meaning
Roulette wheel selection is a probability-based selection method. Each individual gets a
chance of being selected based on its fitness value.
It is called “roulette wheel” because it works like a casino roulette wheel where bigger fitness
means a bigger portion of the wheel.
How it Works
1. Calculate the fitness of all individuals.
2. Find total fitness of the population.
3. Calculate selection probability:
Probability=Individual FitnessTotal FitnessProbability = \frac{Individual\ Fitness}{Total\
Fitness}Probability=Total FitnessIndividual Fitness
4. Spin the wheel.
5. The individual where the wheel stops is selected.
Example
Suppose we have 4 individuals:
Individual Fitness
A 40
B 30
C 20
D 10
Total fitness = 100
Probability of selection:
A = 40%
B = 30%
C = 20%
D = 10%
So, A has the highest chance of being selected.
Advantages
Simple and easy to implement.
Fitter individuals get higher probability.
Disadvantages
If one individual has very high fitness, it may dominate.
Can lead to premature convergence.
2. Tournament Selection
Meaning
Tournament selection selects the best individual from a small randomly chosen group of
individuals.
How it Works
1. Randomly select a small group (for example, 2 or 3 individuals).
2. Compare their fitness.
3. Choose the one with highest fitness.
4. Repeat the process until required parents are selected.
Example
Suppose we randomly select B and C:
B fitness = 30
C fitness = 20
Winner = B
If we select A and D:
A fitness = 40
D fitness = 10
Winner = A
Advantages
Easy to implement.
Works well even when fitness values vary a lot.
No need to calculate total fitness.
Disadvantages
If tournament size is large, diversity reduces.
Strong individuals may dominate quickly.
3. Rank Selection
Meaning
In rank selection, individuals are selected based on their rank (position) instead of actual
fitness value.
Why Needed?
Sometimes fitness values are very close or very different. Rank selection avoids giving too
much importance to very high fitness individuals.
How it Works
1. Sort individuals based on fitness.
2. Assign ranks (1, 2, 3, …).
3. Selection probability is based on rank, not actual fitness.
Individual Fitness Rank
A 40 1
B 30 2
C 20 3
D 10 4
Higher rank means higher selection chance.
Advantages
Prevents domination by very strong individuals.
Maintains population diversity.
Disadvantages
Slightly slower because sorting is required.
4. Elitism
Meaning
Elitism is a method where the best individual(s) from the current generation are directly
copied to the next generation without any change.
Why It Is Used
Sometimes, good solutions may be lost due to crossover or mutation. Elitism ensures that the
best solution is always preserved.
How it Works
1. Find the best individual in the population.
2. Copy it directly to the next generation.
3. Perform selection, crossover, and mutation for the rest.
Example
If the best fitness in generation 1 is 95, elitism ensures that this solution is carried to
generation 2.
Advantages
Guarantees best solution is not lost.
Improves convergence speed.
Disadvantages
If used excessively, it may reduce diversity.
Can lead to premature convergence.
3. Explain mutation operator, types, and significance in GA.
Mutation Operator in Genetic Algorithm (15 Marks)
Introduction
In a Genetic Algorithm (GA), mutation is a genetic operator used to introduce small random
changes in chromosomes (solutions). It is inspired by biological mutation, where small
changes occur in genes naturally.
Mutation helps maintain diversity in the population and prevents the algorithm from getting
stuck in local optimum solutions.
1. What is Mutation Operator?
Mutation is the process of randomly changing one or more genes in a chromosome after
crossover.
In simple words:
👉 Mutation slightly modifies a solution to create variation.
It is usually applied with a small probability (called mutation rate), such as 0.01 or 1%.
2. Why Mutation is Needed?
Without mutation:
All individuals may become similar.
Population diversity reduces.
The algorithm may get stuck in a local optimum.
No new information is introduced.
Mutation:
Introduces new genetic material.
Maintains diversity.
Helps explore new search areas.
Improves global search ability.
3. Working of Mutation Operator
The mutation process occurs after crossover.
Steps:
1. Select a chromosome.
2. Choose a gene randomly.
3. Change its value randomly.
4. Insert mutated chromosome into new generation.
Mutation probability is usually small because:
Large mutation may destroy good solutions.
Small mutation maintains stability.
4. Types of Mutation in Genetic Algorithm
Mutation types depend on chromosome representation.
A. Bit Flip Mutation (Binary Representation)
Used when chromosome is a binary string (0 and 1).
How it Works:
Change 0 to 1 or 1 to 0 randomly.
Example:
Before mutation:
110010
After mutation (flip 3rd bit):
111010
Advantage:
Simple and easy.
Commonly used in binary GA.
B. Random Resetting Mutation (Integer Representation)
Used when genes contain integer values.
How it Works:
Replace a gene value with a random value within allowed range.
Example:
Before mutation:
[5, 3, 9, 2]
After mutation:
[5, 7, 9, 2]
(3 replaced by 7)
C. Swap Mutation (Permutation Representation)
Used in problems like Traveling Salesman Problem.
How it Works:
Two positions are selected randomly.
Their values are swapped.
Example:
Before mutation:
[1, 2, 3, 4, 5]
After mutation:
[1, 4, 3, 2, 5]
(2 and 4 swapped)
D. Inversion Mutation
Used for ordering problems.
How it Works:
Select a subset of genes.
Reverse their order.
Example:
Before mutation:
[1, 2, 3, 4, 5]
Select (2,3,4)
After mutation:
[1, 4, 3, 2, 5]
E. Gaussian Mutation (Real-Valued Representation)
Used when genes are real numbers.
How it Works:
Add small random value (Gaussian noise) to gene.
Example:
Before mutation:
2.5
After mutation:
2.5 + 0.1 = 2.6
5. Mutation Rate
Mutation rate is the probability of mutation occurring.
Too High → Random search (destroys good solutions)
Too Low → No diversity
Usually:
0.001 to 0.05 (very small value)
6. Significance of Mutation in GA
Mutation plays an important role in GA.
1. Maintains Diversity
Prevents population from becoming identical.
2. Avoids Premature Convergence
Helps escape local optimum solutions.
3. Introduces New Genetic Material
Adds new characteristics not present in parents.
4. Supports Exploration
Helps search unexplored areas in solution space.
5. Improves Global Search Capability
Makes GA powerful for complex optimization problems.
Difference Between Crossover and Mutation
Crossover Mutation
Combines two parents Modifies one individual
Main source of variation Secondary source of variation
Large changes Small random changes
High probability Low probability
8. Advantages of Mutation
Simple to implement.
Increases search space exploration.
Helps find better global solutions.
Essential for maintaining healthy population.