Chapter: 11 Genetic Algorithms:
Q) Describe working principle of Genetic Algorithm. – S21, W24 (4M)
To solve any problem, a genetic algorithm begins with a set of solutions
(represented by chromosomes) called the population.
Solutions from a particular population are taken and used to form a new
population. The new population describes what we call the next generation.
It is hoped that the next generation will be better than the previous one.
Solutions are selected according to their fitness to form new solutions. Fitness is
the ability of a solution to survive and pass on to the next generation. The more
their fitness, the higher is their chance to reproduce.
The next generation (their offspring) are created by exchanging individual genes
of parents selected and also by changing genes randomly in individual
chromosomes.
This is repeated until some condition (e.g., number of generations or improvement
in the best solution) is satisfied.
Q) List out the genetic operators. Describe them briefly. – S21, W22, W23 (4M)
1. Selection Operator
o Purpose: Chooses individuals from the current population to
become parents of the next generation, favoring those with higher
fitness.
2. Crossover (Recombination) Operator
o Purpose: Combines the genetic material of two parent individuals
to produce offspring, allowing the exchange and recombination of
genetic traits.
3. Mutation Operator
o Purpose: Introduces random changes to individual genes within a
chromosome, promoting diversity in the population and helping to
prevent premature convergence to suboptimal solutions.
4. Replacement Operator
o Purpose: Determines which individuals from the current
population and the offspring should survive into the next
generation.
Q) Explain Roulette-Wheel selection method of genetic algorithm. – S22(7M)
In this selection scheme, parents are selected according to their fitness
values.
The higher the fitness value of a chromosome, the more is the chance that
it will be selected.
Conceptually, each chromosome of the population is allocated a section
of an imaginary roulette wheel.
Unlike a real roulette wheel, the sections are of different sizes,
proportional to the chromosome’s fitness, such that the fittest candidate
has the biggest slice of the wheel and the weakest chromosome has the
smallest.
The wheel is then spun and the chromosome associated with the winning
section is selected. This process is repeated as many times as necessary to
select the entire set of parents for the next generation.
Fig. 11.2.7: Roulette Wheel Selection
Fig. 11.2.7 shows the Roulette–Wheel for 4 chromosomes according to their
fitness. Since the 3rd chromosome has a higher fitness than any other
chromosome, it is expected that the roulette-wheel selection will choose it more
than any other chromosome.
If
𝑛
1
𝐹ˉ = ∑ 𝐹𝑗
𝑛
𝑗=1
is the average fitness of the population, then the Roulette-wheel selection is
expected to make 𝐹𝑗 /𝐹ˉ copies of the jᵗʰ string in the population. Where 𝐹𝑗 is the
fitness value of jᵗʰ chromosome and ‘n’ is the number of chromosomes in a
chosen population.
Q) Describe the phases of genetic algorithm. – S22 (7M)
A Genetic Algorithm (GA) is an optimization technique inspired by the process of natural
selection and evolution. It is used to find approximate solutions to complex problems by
evolving a population of candidate solutions. The phases of a Genetic Algorithm are as
follows:
1. Initialization
Population Generation: Create an initial population of candidate solutions (often
called chromosomes or individuals). These are usually generated randomly.
2. Selection
Fitness Evaluation: Evaluate each individual’s performance using a fitness function,
which quantifies how well the candidate solution solves the problem.
3. Crossover (Recombination)
Crossover Operation: Combine pairs of parents to produce offspring (new candidate
solutions). This mimics biological reproduction and allows for the mixing of genetic
information.
4. Mutation
Mutation Operation: Introduce random changes to individual genes in offspring. This
adds diversity to the population and helps explore the search space, preventing
premature convergence.
5. Replacement
Population Update: Replace some or all of the old population with the new generation
of individuals. This can be done by entirely replacing the old population or by
keeping the best individuals (elitism).
6. Termination
Stopping Criteria: The algorithm repeats the selection, crossover, and mutation phases
for multiple generations until a stopping criterion is met, such as:
o A maximum number of generations.
o A solution with an acceptable fitness level is found.
o Convergence of the population.
Q) Explain Various Types of Cross Over Operators in Genetic Algorithm. –S23
(7M)
2. Two-Point Crossover
Mechanism: Two crossover points are selected, and the segment of the
chromosome between these two points is swapped between the two
parents.
Example:
o Parent 1: 101**^1|100|^**101
o Parent 2: 011**^0|001|^**010
o Offspring 1: 1010000101
o Offspring 2: 0111111010
Use Case: Provides more diversity than single-point crossover by
allowing for more complex mixing of parental genes.
3. Uniform Crossover
Mechanism: Each gene is independently chosen from either parent with
a fixed probability (typically 50%). Instead of selecting a contiguous
segment, genes are chosen based on a uniform random process.
Example:
o Parent 1: 1011100
o Parent 2: 0110011
o Offspring: 1111110 (genes chosen randomly from Parent 1 or 2)
Use Case: Useful when maintaining the overall genetic diversity of the
population is important.
4. Arithmetic Crossover
Mechanism: Commonly used with real-number encoded chromosomes,
where offspring are generated by performing arithmetic operations (like
averaging) on the parent genes.
Example:
o Parent 1: (5, 7)
o Parent 2: (2, 8)
o Offspring: (3.5, 7.5) (e.g., averaging the corresponding genes)
Use Case: Suitable for problems with real-valued chromosomes, such as
in optimization problems.
Q) Discuss the termination parameters used in genetic algorithms in detail. –
S25 (7M)
In a Genetic Algorithm (GA), the termination parameters (or stopping criteria) determine
when the algorithm should stop evolving further generations.
The goal is to stop the algorithm when a satisfactory or optimal solution has been found, or
when further improvement is unlikely.
Common Termination Parameters:
1. Fixed Number of Generations
The algorithm stops after a predefined number of generations have been produced.
Simple and commonly used when the computational budget or time is limited.
Example:
Stop after 100 generations, regardless of whether the best solution has improved or not.
Use Case: When approximate solutions are acceptable and execution time is important.
2. Convergence of Population
The algorithm stops when most individuals in the population become similar (no
diversity), indicating that evolution has converged.
This means no significant change in solutions is observed across generations.
Example:
If 95% of the population has identical chromosomes, the GA is considered converged.
Use Case: When continued evolution is unlikely to produce better results.
3. Fitness Threshold (Acceptable Solution Found)
The algorithm terminates when the best individual’s fitness value reaches or exceeds a
predefined threshold.
Example:
If the fitness value ≥ 0.98 (or within 1% of the target value), stop the algorithm.
Use Case: When an acceptable or optimal solution is known in advance.
4. No Improvement Over Generations
The GA stops when the best fitness value remains unchanged for a certain number of
consecutive generations.
Example:
If there’s no improvement in the best fitness for 20 generations, terminate the algorithm.
Use Case: Prevents wasting time on unnecessary iterations once the search stagnates.
5. Time Limit or Computational Budget
The algorithm is terminated when the maximum allowed computation time or number
of evaluations is reached.
Use Case: Real-time systems or when computational resources are limited.