The actual part you need to submit is the Metaheuristics section. The rest is meant to introduce you to the basics.
- You can use
Template.ipynb
to start writing the part you need to submit (about meta-heuristics). - I propose you work as follows (You don't have to follow this though!):
- Ensure the whole group members are familiar with the TSP problem, 2-opt and 3-opt local search techniques. (see Wikipedia article link below.)
- Implement 2-opt or/and 3-opt.
- Decide which meta-heuristics you want to try. Watch the guest lecture videos on Aula and check the literature related to TSP and the meta-heuristics you are thinking of.
- Split the group into 2 sub-groups, each to work on one meta-heuristic.
- One group member will oversee both groups' work and will be reponsible for merging the 2 notebooks into one coherent notebook.
- You may try Google Colab and/or Microsoft Azure if that helps you work better, but please be aware that I am not sure about their GDPR compliance.
I should emphasise here that "exhaustive search" and "greedy" are *not meta-heuristics, nor are 2-opt and 3-opt. Ensure this is clear to you.
-
Ensure you have Jupyter.
-
Familiarise yourself with Jupyter functionaility. Consider taking LinkedIn Learning courses (free through the university) or any suitable alternatives. Here is a recommended set (e.g. each member of the group takes one):
-
Load and study
Investigating TSP.ipynb
.- Can you improve any of the functions to make them more efficient?
- See how large you can make n while testing
exhaustive_search()
. - Check that
greedy_nearest_neighbours()
is correct. If not then fix it!
-
Read the Wikipedia article on TSP. Pay attention to th Computing a solution section, and especially to the
2-opt
and3-opt
techniques for defining neighbourhoods. -
Experiment with generating your own graph families. For example:
- Euclidean graphs: generate points using (x,y) coordinates, then generate the adjacency matrix by calculating all the required distances. Recall that the distance between two points (x1,y1) and (x2,y2) is sqrt[(x1-x2)2+(y1-y2)2].
- Graphs with obvious shortest cycle: think of a graph where all the distances are 2 except for the edges on a predefined cycle, where the distance is 1. Such a graph would be useful for testing/debugging the nearest neighbours greedy search.
- Applegate, DL, Bixby, RE, Chvátal, V, Cook, WJ, 2007, The Traveling Salesman Problem: A Computational Study, Princeton University Press, Princeton.
- Cook, WJ 2012, In Pursuit of the Traveling Salesman: Mathematics at the Limit of Computation, Princeton University Press, Princeton.
- Glover, F, & Kochenberger, GA (eds) 2002, Handbook of Metaheuristics, Kluwer Academic Publishers, Secaucus.
- Gutin, G, & Punnen, AP (eds) 2002, The Traveling Salesman Problem and Its Variations, Springer, New York, NY.
- Pintea, C.-M., 2014. Advances in Bio-inspired Computing for Combinatorial Optimization Problems. 1st ed. 2014.
- Steven, SS 2008, The Algorithm Design Manual, Springer, England.
- You may also find its companion website useful.
- Talbi, E.-G., 2009. Metaheuristics from design to implementation, Hoboken, NJ: John Wiley & Sons.