HW10. TSP, SA, Genetic Algorithm, NN (18th of Nov, 23.59)
EX1. (1P) In the file hw10_TSP_data.zip there are generated data sets for the TSP problem. Code that generated them are in Google Colab.
Data:
https://drive.google.com/file/d/1XWwn7j4p2Ymp0C8R2p6EXEHlg8OPqv1P/view?usp=drive_link
Here is the code that generated it, after that the file writing was commented out. You can uncomment file creation; for comparison let’s use however the same data from above.
https://colab.research.google.com/drive/1Jw8l1T57YF8M389S7AHqKs3zg9WJEVRK#scrollTo=xH_3ryEAiks0
There is also one NN method implemented; and code for visualising the results.
Look at the smallest data set (30 points) - Find the optimal solution - by analysing the NN method and modifying that result by hand (or using some other method). Report the result - drawing and total cost.
There is also a web tool to visualize resulting paths https://abercus.github.io/tspvis/
EX2. (1P) Implement a Simulated Annealing procedure for finding hopefully a better TSP solution than the greedy Nearest Neighbour method (NN) would.
In the report insert results (images) for all 4 data sizes, and the compute time you spent to acquire the result.
Is it better to start from the original random order or from the NN heuristic solution?
EX3. (1P) Attempt to solve the largest examples of TSP and compete for the best solution. See also the bonus points that you can receive by announcing your best solutions (distance and visual “proof”) in our course Slack.
In your report discuss what method(s) worked the best for you, the time of calculations and the obtained score. Visualize how the score improved over the compute time.
EX4. (1P) Let’s unscramble some images. The following code exposes how the four images were randomly generated by shuffling rows. You can test it with your own examples (the first cell):
https://colab.research.google.com/drive/1xuPt_nqf-LrrmHR9_xs9YNvYN5ZOTqsw#scrollTo=-oApPPQHZS1X
In here are your scrambled data sets -
https://drive.google.com/file/d/1jCM3sVa70ld1LI8Ln7DCusUDSNAGSGxt/view?usp=drive_link
The second cell provides an example code by “unscrambling” by simply reordering these scrambled files by sorting rows by their color intensity. The result is not perfect.
Can you figure out what was in the original images by TSP or NN methods?
EX5. (1P) Discuss which methods (TSP, Nearest-neighbour, two-way nearest neigbour, …) would work the best and why?
What are the properties of the data that would work better in the sense that makes images easier to unscramble.
Why some images could and some could not be reconstructed? Provide examples (recommended is to create illustrating examples by yourself).
EX6. (2P) Bonus point (1p; max 2p per person ) for improving the so far best 1000-city TSP score as reported in the Slack homework channel.