Bio-inspired Computing Assignment 1: Traveling salesman problem (TSP)
Bio-inspired Computing Assignment 1
2023/10/13
Traveling salesman problem (TSP) is a famous problem with lots of
applications. TSP aims at finding a Hamiltonian cycle with limited cost. A
formal definition of TSP is as follows. Given a complete graph 𝐺 =
(𝑉, 𝐸) with vertex set 𝑉 and edge set 𝐸, TSP aims to find a cycle of
length l with minimum cost:
l
𝜋∗ =argmin∑ 𝑑(𝜋𝑖,𝜋𝑖+1), 𝜋 𝑖=1
Note that the index is wrapping around to the beginning if it’s over l.
The cost is defined as the sum of Euclidean distance.
Considering TSP is an NP-complete problem, evolutionary algorithm can
be used to solve it efficiently. Write a program to solve TSP using genetic
algorithm.
Implementation
[Input] The problem can be described by a list of vertices. Each vertex in
𝑉 is expressed by its x and y coordinates. The information is stored in the
input_TSP.csv file.
[Output] Output the solution to output_TSP.csv file, including the tour
and its corresponding cost.
[Algorithm] Please implement different variations of GAs according to the following table:
Representation Crossover (𝑝𝑐 = 0.9)
Mutation (𝑝𝑚 = 0.9) Parent Selection Survivor Selection Population size n Termination
Analysis
Permutation
Order, Cycle, Edge crossover
Swap, Inversion
𝑘-tournament (𝑘 = 2)
μ + λ
100
500 Generations
Your report should compare the performance of above methods in terms of
-
tour length,
-
running time,
-
Different parameters, e.g., 𝑝𝑐, 𝑝𝑚, and n.
Each method should run 30 trials for performance comparisons.
Requirement
-
You have to turn in your source code and a report for the assignment. Do not turn in executable files. You will get zero score if the code cannot be compiled or cannot provide correct results.
-
Upload your files in a zip file in the format: TSP_StudentID.zip, where StudentID is your student ID.
-
The due date is 2023/10/27. Every delay takes a penalty of 20 scores per day.
-
Plagiarism is prohibited with no exception. Being identified as plagiarism will get zero score for the assignment. This includes using any nature language processing techniques such as ChatGPT.
