COMP2024 Spring 2025
Tutorial 6 – Evolutionary Algorithms II
1. What is the Travelling Salesman Problem (TSP) and why is it challenging for
Genetic Algorithms (GAs)?
The TSP is an optimization problem where a salesman must visit a set of cities
exactly once and return to the original city while minimizing the travel distance. It is
challenging for GAs because:
Binary representation is unsuitable due to permutation constraints.
Traditional crossover/mutation operators can create invalid tours (e.g.,
duplicate/missing cities).
The search space is large, making it computationally difficult to find an optimal
solution.
2. Explain why binary encoding is unsuitable for the Traveling Salesman Problem
(TSP) in Genetic Algorithms.
Binary encoding causes:
Illegal tours where cities are repeated or missing.
Undefined city codes, leading to infeasible solutions.
Requirement for repair algorithms, increasing computational overhead.
Violation of permutation constraints, making traditional crossover/mutation
operators ineffective.
Permutation-based encoding is preferable as it preserves valid sequences.
3. What are permutation-preserving crossover operators? Provide examples.
These crossover operators maintain valid permutations:
Partially Mapped Crossover (PMX): Ensures valid offspring by mapping genes
between parents.
Order Crossover (OX): Preserves the order of elements in one parent while
filling missing elements from the other.
Cycle Crossover (CX): Swaps cycles of genes to maintain order integrity.
4. Explain how Partially Mapped Crossover (PMX) works.
Prepared by Simon Lau Boung Yew Page 1 of 6
COMP2024 Spring 2025
PMX follows these steps:
1. Select two parents with valid permutations.
2. Choose two random crossover points and swap the segment between them.
3. Map conflicting elements to ensure unique cities in offspring.
4. Fill remaining positions from the second parent while resolving conflicts.
Example: Parent 1: (1 2 3 | 4 5 6 7 | 8 9) Parent 2: (4 5 2 | 1 8 7 6 | 9 3) Offspring
after PMX: (4 2 3 | 1 8 7 6 | 5 9)
5. Describe swap, inversion, and scramble mutation in the context of permutation-
based encoding.
Swap Mutation: Two cities in the sequence are swapped.
Inversion Mutation: A segment of the tour is reversed.
Scramble Mutation: A subset of cities is randomly shuffled.
6. Compare Order Crossover (OX) and Cycle Crossover (CX) for TSP.
7. Define memetic algorithms.
Memetic Algorithms (MAs) are an extension of Genetic Algorithms (GAs) that
integrate local search techniques to refine solutions. While GAs rely on crossover
and mutation for exploration, MAs introduce exploitation through problem-specific
heuristics, improving convergence to high-quality solutions.
8. Explain the concept of multimeme memetic algorithms.
Prepared by Simon Lau Boung Yew Page 2 of 6
COMP2024 Spring 2025
Multimeme Memetic Algorithms (MMA) extend standard MAs by allowing individuals
within the population to evolve their own local search strategies (memes) alongside
their genetic material.
In MMA, each individual is assigned a meme, which represents a local search
strategy or mutation rule that adapts dynamically over generations. These memes
co-evolve with the solutions, leading to a self-adaptive evolutionary process.
9. You are tasked with solving the Traveling Salesman Problem (TSP) using a
Multimeme Memetic Algorithm (MMA). Given a TSP instance with six cities (A, B,
C, D, E, F), describe how you would design the algorithm by specifying how you
can encode the solution and memes of the TSP problem, and the steps of the
algorithm.
Consider solving the Traveling Salesman Problem (TSP) using Multimeme MAs.
i) Encoding Representation: Represent a candidate solution as a
permutation of cities (e.g., A → C → B → E → D → F → A).
ii) Memetic Operators: Implement the following local search strategies
(memes):
2-opt: Swap two cities to improve the tour.
3-opt: Remove and reinsert cities differently.
Swap mutation: Randomly swap two cities.
Insertion mutation: Move a city to a new position.
iii) Meme Evolution:
1. Assign a random meme to each individual in the population.
2. Apply crossover (e.g. PMX, OX or CX) and ensure offspring inherit
parent memes.
3. Each tour applies its meme for local optimization.
4. If 2-opt fails to improve, the meme mutates to 3-opt.
5. The best-performing memes propagate to future generations.
10. Apply PMX, OX and CX crossover respectively on the following parent
permutations:
P1: (1 2 3 4 5 6 7 8 9)
P2: (4 5 2 1 8 7 6 9 3)
Prepared by Simon Lau Boung Yew Page 3 of 6
COMP2024 Spring 2025
Prepared by Simon Lau Boung Yew Page 4 of 6
COMP2024 Spring 2025
11. Solve a small TSP instance using insertion mutation and evaluate its
effectiveness.
Problem:
Consider a Traveling Salesman Problem (TSP) instance with 6 cities labelled as A,
B, C, D, E, F and the following distance matrix:
Given the initial tour (A → B → C → D → E → F → A), apply insertion mutation by
removing city C and reinserting it after city E. Then, compute the new tour cost and
compare it with the original.
Step 1: Compute Initial Tour Cost
Initial tour: A → B → C → D → E → F → A
A→B=2
Prepared by Simon Lau Boung Yew Page 5 of 6
COMP2024 Spring 2025
B→C=4
C→D=3
D→E=2
E→F=4
F→A=3
Total cost: 18
Step 2: Apply Insertion Mutation
Remove city C and insert it after city E.
New tour: A → B → D → E → C → F → A
Step 3: Compute New Tour Cost
A→B=2
B→D=8
D→E=2
E→C=7
C→F=6
F→A=3
New total cost: 28
Step 4: Evaluate Effectiveness
The new tour cost increased from 18 to 28, making it less optimal.
Conclusion: In this case, insertion mutation did not improve the solution.
However, in other scenarios, it may help explore new regions of the search
space and escape local optima.
Final Answer:
Original Tour Cost: 18
New Tour Cost after Insertion Mutation: 28
Effectiveness: Less effective in this case, but useful for diversifying solutions
in larger search spaces.
Prepared by Simon Lau Boung Yew Page 6 of 6