Scribd
Upload
7 views2 pages

TSP Solutions with Genetic Algorithms

The document discusses the Travelling Salesman Problem (TSP) and its challenges for Genetic Algorithms, particularly focusing on encoding methods and crossover operators. It covers various mutation techniques and compares different crossover methods like Order Crossover and Cycle Crossover. Additionally, it outlines the design of a Multimeme Memetic Algorithm for solving TSP and includes a practical example of applying insertion mutation to a TSP instance.

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 DOCX, PDF, TXT or read online on Scribd
7 views2 pages

TSP Solutions with Genetic Algorithms

The document discusses the Travelling Salesman Problem (TSP) and its challenges for Genetic Algorithms, particularly focusing on encoding methods and crossover operators. It covers various mutation techniques and compares different crossover methods like Order Crossover and Cycle Crossover. Additionally, it outlines the design of a Multimeme Memetic Algorithm for solving TSP and includes a practical example of applying insertion mutation to a TSP instance.

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 DOCX, 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