Homework: The travelling delivery drone problem ===================================================== * **Topic:** discrete optimization, simulated annealing * **Template:** `A3_salesman.py `_ * **Data:** - `A3_10_cities.txt `_ - `A3_20_cities.txt `_ * **Further reading:** - https://en.wikipedia.org/wiki/Travelling_salesman_problem - https://en.wikipedia.org/wiki/Simulated_annealing Theory ######### The travelling salesman problem is a famous, difficult optimization problem. The problem is this: You have a set of points on a map. We call these cities, but in a more general case they could be any kinds of points that have some measurable distance. Your task is to visit each point exactly once and then return to the starting point taking the shortest route possible. The problem is simple, but since the number of permutations (different ways to order the cities) grows as :math:`N!`, where :math:`N` is the number of cities, it is impossible to test all the possible routes when the number of cities goes past about 10. Since the problem is discrete, you also cannot calculate derivatives to help in the optimization task. Instead, your task is to find as good a solution as you can using the *simulated annealing* method. Simulated annealing uses the same algorithm as Metropolis Monte Carlo, which we used previously to sample states from the canonical ensemble. In the canonical ensemble, the total energy of the system is not constant because the system can exhange energy with its environment, and the probability of finding the system in a state with total energy :math:`E` is given by the Boltzmann factor .. math :: P(E) \propto e^{-\frac{E}{k_B T}}. On one hand, if the temperature is high, the system can have high energies and access many different states. On the other hand, if the temperature is low, the probability to find the system in a high energy state is very low. That means the system must end up in an energy minimum as temperature approaches zero. Now, we are obviously not interested in any real energy or temperature, but we can formulate the optimization problem using similar principles. Let us denote the total length of the salesman's route as :math:`L`. Let us also introduce a "temperature-like" quantity :math:`T`. If we now use the Metropolis algorithm to build a simulation that treats :math:`L` like energy and :math:`T` like temperature, it will sample the routes according to probabilities .. math :: P(L) \propto e^{-\frac{L}{T}}. When :math:`T` is large, the algorithm samples both long and short routes. But when :math:`T` approaches zero, the algorithm should only find short routes. There is no guarantee it will find the *shortest* route, but it should converge towards some local minimum. Running the algorithm several times will likely locate several short routes and possibly also the shortest one. The algorithm works by starting from some initial route (e.g., random), assigning a temperature and repeating the following: * Produce a new route by making a small random change to the current route. * Calculate the change in route length, :math:`\Delta L`. * If the new route is shorter than the old one, accept the new route. * If the new route is longer than the old one, accept the new route with probability .. math :: P = e^{- \frac{\Delta L}{T}}. Otherwise keep the old route. * Lower the temperature by a small amount. The efficiency of the algorithm depends *strongly* on how you produce new routes. Firstly, the changes you make must be small enough. Large changes will produce essentially random states and the algorithm will not converge. But it also matters *how*, you make these small changes. A bad choice can create lots of local minima where the algorithm gets easily stuck. I especially suggest you try to figure out a simple operation that can get rid of crossings, because the optimal route clearly cannot have any crossings, and getting rid of them is important. Also note that besides the 10 and 20 city cases, your program will be tested using a 40 city geography. It is not expected to solve the 40 city case exactly, but it should produce a somewhat reasonable solution. Task ######## To complete this assignment, you need to complete the following tasks, submit your code *as a plain .py file*, and answer the questions. In the computing tasks, you must implement the incomplete functions so that they operate *exactly* as described in the documentation. * **Computing task:** 1. Implement a function to calculate route length. 2. Implement a function to calculate the Boltzmann factor. 3. Come up with 1-3 good operations for making small changes to the route and implement them. 4. Implement a function to run simulated annealing. 5. Find the shortest routes for the provided 10 and 20 city geographies. 6. Adjust the simulation parameters so that your program always produces at least a reasonable result. * **Questions to answer:** 1. What kinds of operations did you end up using for generating the new routes? Why did you choose them? 2. How do you vary temperature in your simulation? Why did you end up with these parameters? 3. Are the best solutions you found reasonable? Include pictures of optimized routes and explain why do you believe them to be good (or bad) solutions. 4. How reliably do you think your program solves the problem with 20 cities or more? Is there a lot of variance in the end result? Include data in your explanation! What steps did you take to make your program more reliable? A3_salesman.py ################# .. automodule:: A3_salesman :members: :undoc-members: