HW12. TSP, Project (10th of Dec, 23.59)
Take a look at the "cities" on a map - 2018.zip. Our goal is to find the shortest route through all cities (solve the TSP). There exists a direct road between any pair of cities (Euclidean distance; two points p1=(100,100), p2=(103,104) will have distance (p1, p2)=5 ).
EX1: Run the Nearest Neighbour (NN) route through all cities starting from node 1. If distances tie, choose the smallest number first. Perform this for three tasks (20, 100, 1000 cities). For receiving the "points" you can do it also "on paper" for 20-cities task. Implementation is preferred, of course, for all problem sizes and feeding to the next problems.
EX2 & EX3: Choose some (one) optimization method (e.g. simulated annealing, genetic algorithm, Ant Colony Optimisation...) and attempt a full optimization of the provided TSP tasks. For speed you may benefit from calculating all distances first, once and also ensuring some clever coding of the problem that supports the operations on the current TSP path.
It is recommended to work on small size problems (16, 20 nodes) first. These you can also attempt solving manually on paper as well.
Use the generated SWOG templates (in the archive 2018.zip) to highlight the TSP routes discovered...
EX4 & EX5: The course ends with the project to be completed usually by a small team of 2-3 people. Your task is to come up with one project proposal all by yourself - taking ideas from project proposal titles (file), from the course past homeworks, etc. E.g. you may well develop some of the past exercises into a more thorough setting with the goal to get more final version out of it. Note - this is a proposal that you may use to attract other students to join; and this is at the same time a proposal that you do not need to start executing necessarily. So. it's more a planning exercise, not execution exercise.
Project proposal has to consist of the following parts:
- Title
- 2-5 sentences of short description
- Briefly state the motivation and the main challenge of this project
- Division of tasks, estimated number of work hours per task, and deadline (aim at our poster session!)
- Allocation of the 2-3 people to tasks and hours.
- Recommended: create a GANTT chart to cover previous two points.
- Description of the envisioned end results that would go to the project report/poster.
EX6. (Bonus 2p): - Run your TSP finding algorithms on the 1000-city case. Report best solutions to the Piazza in a public thread, to initialize the competition. In the post describe your approach, report the calculation time, obtained path length and the visualization of the resulting path. The ones who can beat past best solutions will get points (even if someone will outcompete your solution next). To get points make sure to post new best solution to corresponding Piazza thread. NB! For the solution to beat previous solutions, it should have shorter resulting path or if lengths are comparable the new solution should be considerably faster.
Also, very good descriptions of the approach and convergence rates - may get awarded with points upon TA decision.
EX7. (Bonus 1p): Provide feedback for the course and homework topics so far
- which topics were most useful?
- what needs to be covered better in the course?
- are there some topics that would need more practical implementation assignments?
- are there some topics that got too much attention (e.g. too boring or otherwise already well known)