Scribd
Upload
9 views2 pages

TSP Solutions with Genetic Algorithms

The document discusses the Traveling Salesman Problem (TSP) and its challenges for Genetic Algorithms, particularly the unsuitability of binary encoding. It covers various crossover methods like Partially Mapped Crossover (PMX), Order Crossover (OX), and Cycle Crossover (CX), as well as mutation techniques for permutation-based encoding. Additionally, it introduces memetic algorithms and outlines a design for solving TSP using a Multimeme Memetic Algorithm (MMA), including a practical exercise involving insertion mutation.

Uploaded by

Simon Lau Boung Yew
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

TSP Solutions with Genetic Algorithms

The document discusses the Traveling Salesman Problem (TSP) and its challenges for Genetic Algorithms, particularly the unsuitability of binary encoding. It covers various crossover methods like Partially Mapped Crossover (PMX), Order Crossover (OX), and Cycle Crossover (CX), as well as mutation techniques for permutation-based encoding. Additionally, it introduces memetic algorithms and outlines a design for solving TSP using a Multimeme Memetic Algorithm (MMA), including a practical exercise involving insertion mutation.

Uploaded by

Simon Lau Boung Yew
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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)?

2. Explain why binary encoding is unsuitable for the Traveling Salesman Problem
(TSP) in Genetic Algorithms.

3. What are permutation-preserving crossover operators? Provide examples.

4. Explain how Partially Mapped Crossover (PMX) works.

5. Describe swap, inversion, and scramble mutation in the context of permutation-


based encoding.

6. Compare Order Crossover (OX) and Cycle Crossover (CX) for TSP.

7. Define memetic algorithms.

8. Explain the concept of multimeme memetic algorithms.

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.

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)
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:

Prepared by Simon Lau Boung Yew Page 1 of 2


COMP2024 Spring 2025

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.

Prepared by Simon Lau Boung Yew Page 2 of 2

You might also like