"Metaheuristics"

use python

Traveling salesman. The famous Travelling Salesman Problem (TSP) consists in finding a tour that passes through all cities with the shortest total distance. Some instances are on Moodle, each in a file in which we have a list of n cities ( n is the first number at the beginning of the file), each on a separate line that gives its identifier and coordinates, in the form: Id, x,y. The cities are always given in order of increasing identifiers from 1 to n. A solution of this problem is a sequence of n cities, it represents a tour starting from the point with coordinates (0,0) then passing through each of the cities of the sequence, then returning to the point (0,0). For simplicity, the distance between two cities will be their Euclidean distance : (x1x2)2+(y1y2)2 We want to find a tour that has minimum length. For the instance in file tsp5.txt, with 5 cities, the best tour visits the cities in the order it has a total length of 263.88 km.

Question 2.1. Write a function that returns a random vector of n cities, where n is the number of cities read as the first number in an instance file. For this function, you can either use a constructive method (create a chained list of cities and randomly draw the index of the first city from 1 to n, delete the corresponding city from the list then randomly draw between 1 and n1 the second city etc) or an iterative method (start from the solution X where the cities are in increasing order from 1 to n and for i=1 to n exchange X[i] and X[random(n)]).

Question 2.2. Write a function that calculates the value of this solution, i.e. the distance that the traveling salesman must travel from (0,0) through all the cities X[1]X[n] and back to (0,0).

Question 2.3. Program a function best_neighbour that returns the best neighbour of X, where a neighbour of X is any sequence obtained by swapping two cities in the sequence X.

Question 2.4. Use the Steepest Hill-Climbing method, with restards, on both the tsp5.txt and tsp101.txt. For each trial, you should be able to display the initial solution drawn at random, the solution reached and the number of moves made from the initial solution to the solution reached. Question 2.5. Use the tabu method to solve these instances, trying different sizes for the Tabu list and for the MAX_moves. Here again, you should be able to display the initial solution, the solution reached, the number of moves made to the solution reached, the best solution found, and the contents of the tabu list at the end of the search.