COMP2024 Spring 2025
Tutorial 3 - Metaheuristics
1. Define metaheuristics and explain their significance in optimization problems.
Metaheuristics are high-level problem-independent algorithmic frameworks designed
to guide heuristic optimization methods. They are crucial in solving complex
optimization problems where exact methods are computationally infeasible.
Metaheuristics balance exploration (searching new areas) and exploitation (refining
known good solutions).
2. What are the main characteristics of metaheuristics?
General Applicability: Can be applied across different problems.
Approximate Solutions: Do not guarantee optimal solutions but find near-
optimal ones.
Stochastic Elements: Often involve randomness.
Hybridizable: Can be combined with other methods.
3. Explain the difference between exploration and exploitation in metaheuristic
search strategies.
Exploration: Broadly searches the solution space to find diverse candidates,
preventing premature convergence.
Exploitation: Focuses on refining the best solutions found to improve their
quality.
4. What are the main components of a metaheuristic search method?
Solution Representation: Defines how candidate solutions are structured.
Evaluation Function: Measures solution quality.
Initialization Strategy: Generates the initial candidate solutions.
Neighborhood Relation: Defines how solutions transition.
Search Process: Guides exploration and exploitation.
Stopping Condition: Determines when to end the search.
Escape Mechanisms: Helps avoid local optima.
5. Describe two mechanisms for escaping local optima.
Prepared by Simon Lau Boung Yew Page 1 of 4
COMP2024 Spring 2025
Random Restart: Restarts the search with a new random solution (e.g., Iterated
Local Search, GRASP).
Changing the Search Landscape: Modifies the objective function or applies
variable neighbourhood search to explore new areas.
6. What is the main idea behind Iterated Local Search (ILS)?
ILS improves upon local search by:
1. Performing local search from an initial solution.
2. Applying a perturbation to escape local optima.
3. Restarting the local search from the perturbed solution.
4. Using an acceptance criterion to decide whether to keep the new solution.
7. What is Tabu Search, and how does it use memory structures?
Tabu Search is a metaheuristic that enhances local search by using memory to
prevent revisiting previous solutions. It employs:
Tabu List: Stores recently visited solutions or moves to avoid cycling.
Aspiration Criteria: Allows overriding tabu status if a move significantly
improves the solution.
Short-Term Memory: Helps avoid immediate reversals.
Long-Term Memory: Guides the search towards unexplored areas.
8. Compare Tabu Search and Iterated Local Search in handling local optima. Which
method would you recommend if vehicle routing problem (VRP) problem has a
rugged search space with many local optima? Justify your answer.
Feature Tabu Search Iterated Local Search
Memory Uses memory to track Memoryless, only tracks the best
Usage forbidden moves solution
Escape Uses tabu list and aspiration Uses perturbation and acceptance
Strategy criteria criteria
Structured problems with Problems where small changes yield
Best for
repetitive patterns improvements
Prepared by Simon Lau Boung Yew Page 2 of 4
COMP2024 Spring 2025
If the vehicle routing problem (VRP) has many local optima, Tabu Search is
preferable due to structured memory use.
9. Describe the steps on how you may apply Iterated Local Search (ILS) to solve
the following MAX-SAT problem. Use Iterated Local Search (ILS) to find an
improved assignment starting from the initial solution (a, b, c, d, e, f) =
(0,0,0,0,0,0).
(a∨b) ∧ (¬d∨f) ∧ (¬a∨c) ∧ (b∨¬f) ∧ (¬b∨c) ∧ (c∨e)
1. Initial Evaluation: Calculate the number of satisfied clauses for the initial
assignment.
2. Perturbation: Apply a random bit flip to escape local optima.
3. Local Search: Use Steepest Descent Hill Climbing (SDHC) to improve the
solution.
4. Move Acceptance: Accept if the new solution is equal or better.
5. Repeat until no further improvements can be made.
6. Final Solution: Report the best assignment and the number of satisfied
clauses.
10. You are designing a metaheuristic algorithm for exam timetabling at a university.
Exams must be scheduled in available rooms and non-overlapping time slots.
Conflicting exams (students appearing in both) cannot be scheduled
simultaneously.
Objective: Minimize total student exam clashes and maximize room utilization.
i) Which metaheuristic (Tabu Search or ILS) would you choose and why?
ii) Design the representation of candidate solutions.
iii) Define a neighbourhood move for improving the schedule.
iv) Suggest an escape mechanism for local optima.
i) Choice of Metaheuristic:
Tabu Search: Good for structured scheduling problems due to memory-based
learning.
ILS: Effective if small changes in schedules improve results.
ii) Solution Representation:
A timetable is represented as a matrix where rows are timeslots, and
columns are rooms.
Prepared by Simon Lau Boung Yew Page 3 of 4
COMP2024 Spring 2025
iii) Neighborhood Move:
Swap two exams in different time slots or move an exam to a different room.
iv) Escape Mechanism:
Tabu List:
o Short-term memory: Store recently swapped exams in a tabu list to
prevent reversing moves immediately.
Example: If Exam A was moved from Slot 1 to Slot 3, it cannot
be moved back for the next few iterations, encouraging
alternative placements.
o Long-Term Memory for Exam Placement Patterns: Track successful
exam placements and encourage revisiting patterns that historically led
to good solutions.
Example: If a previous solution with fewer student conflicts
grouped large exams earlier, prioritize similar assignments in
future iterations.
ILS:
o Perturbation by Swapping Multiple Exams at Once: Instead of
swapping only one exam at a time, swap multiple exams across time
slots to create significant changes.
Example: Swap two exams with different student groups instead
of just one, ensuring a more disruptive and exploratory move.
o Acceptance of Worse Solutions for Diversity: Occasionally accept a
worse exam schedule if it increases diversity and avoids being stuck in
a poor local solution.
Example: If shifting Exam C to Slot 4 increases conflicts slightly
but introduces new room combinations, accept the move
temporarily.
Prepared by Simon Lau Boung Yew Page 4 of 4
