COMP2024 Spring 2025
Tutorial 5 – Evolutionary Algorithms I
1. What are Evolutionary Algorithms (EAs), and why are they useful?
Evolutionary Algorithms (EAs) are optimization techniques inspired by natural
evolution. They are useful because:
They explore large search spaces efficiently.
They avoid local optima through genetic diversity.
They are adaptable to different problem domains, including scheduling, routing,
and optimization.
2. Explain the core components of a Genetic Algorithm (GA).
The core components include:
1. Representation (Encoding): Solutions are encoded as chromosomes (e.g.,
binary strings, permutations, or real-valued vectors).
2. Fitness Function: Evaluates how good a solution is.
3. Selection: Selects parents for reproduction (e.g., roulette wheel, tournament
selection).
4. Crossover (Recombination): Combines parents to create offspring.
5. Mutation: Introduces small random changes for diversity.
6. Replacement: Decides which individuals move to the next generation.
3. What are the key selection methods used in GAs?
Roulette Wheel Selection: Probability of selection proportional to fitness.
Tournament Selection: A subset competes, and the best is chosen.
Rank Selection: Individuals ranked, and selection is based on rank.
4. Explain the role of crossover in Genetic Algorithms and describe its types.
Single-Point Crossover: Splits chromosomes at one point.
Two-Point Crossover: Splits at two points and swaps middle segments.
Uniform Crossover: Each gene is randomly selected from either parent.
5. What is the role of mutation in Genetic Algorithms?
Prepared by Simon Lau Boung Yew Page 1 of 8
COMP2024 Spring 2025
Mutation helps in:
Maintaining genetic diversity by introducing random changes.
Escaping local optima to explore new areas.
Preventing premature convergence by avoiding dominance of a single solution.
6. What is a replacement strategy in GAs, and what are the main types?
Generational Replacement: Entire population is replaced.
Steady-State Replacement: Only a few individuals are replaced per iteration.
Elitism: Best individuals are preserved across generations.
7. Define Memetic Algorithms and explain how they differ from Genetic Algorithms.
Memetic Algorithms (MAs) extend Genetic Algorithms by incorporating local search
techniques. Unlike GAs, which rely solely on evolutionary operators, MAs refine
solutions through hill climbing or other local search methods to enhance solution
quality.
8. Compare Genetic Algorithms (GAs) and Memetic Algorithms (MAs).
9. Apply a Genetic Algorithm to solve a MAX-SAT problem.
Problem:
Given a MAX-SAT formula with 6 variables {a, b, c, d, e, f}, initialize a population
of 4 individuals, evaluate fitness, and apply Roulette Wheel Selection to choose
two parents for crossover.
Sample Answer:
Prepared by Simon Lau Boung Yew Page 2 of 8
COMP2024 Spring 2025
Prepared by Simon Lau Boung Yew Page 3 of 8
COMP2024 Spring 2025
Prepared by Simon Lau Boung Yew Page 4 of 8
COMP2024 Spring 2025
10. Implement a Genetic Algorithm for function optimization.
Prepared by Simon Lau Boung Yew Page 5 of 8
COMP2024 Spring 2025
Sample Answer:
Prepared by Simon Lau Boung Yew Page 6 of 8
COMP2024 Spring 2025
Prepared by Simon Lau Boung Yew Page 7 of 8
COMP2024 Spring 2025
Prepared by Simon Lau Boung Yew Page 8 of 8
