Implementing Simulated Annealing for the Traveling Salesperson Problem

Simulated annealing is a probabilistic technique for approximating the global optimum of a given function. It is inspired by the annealing process in metallurgy, where a material is heated and then slowly cooled to reduce defects and achieve a more stable crystalline structure. This challenge asks you to implement simulated annealing to find a near-optimal solution to the classic Traveling Salesperson Problem (TSP).

Problem Description

The Traveling Salesperson Problem (TSP) is a famous optimization problem where a salesperson must visit a set of cities exactly once and return to their starting city, minimizing the total distance traveled. You will implement a simulated annealing algorithm to find a good, though not necessarily perfect, solution to this problem for a given set of cities.

What needs to be achieved: Implement a simulated annealing algorithm that takes a list of cities (represented by their coordinates) and returns a permutation of these cities representing a tour that aims to minimize the total distance.

Key requirements:

1. Representing the problem:
   • Cities will be represented as tuples of (x, y) coordinates.
   • A "tour" will be a list of city indices in the order they are visited.
   • You need a function to calculate the Euclidean distance between two cities.
   • You need a function to calculate the total distance of a given tour.
2. Simulated Annealing Core:
   • Implement a function that performs the simulated annealing process.
   • This function should accept the list of cities, initial temperature, cooling rate, and number of iterations per temperature step.
   • It should start with an initial random tour.
   • In each iteration, it should generate a "neighboring" tour by making a small change (e.g., swapping two cities).
   • It should decide whether to accept the neighboring tour based on the Metropolis criterion (which considers the energy difference and temperature).
   • The temperature should gradually decrease over time according to the cooling rate.
3. Neighbor Generation: Implement a simple neighbor generation strategy, such as the "2-opt" swap (reversing a sub-segment of the tour).
4. Output: The function should return the best tour found and its total distance.

Expected behavior: The algorithm should iteratively explore the solution space, initially accepting more "costly" moves to escape local optima, and then becoming more selective as the temperature decreases, converging towards a good solution.

Edge cases to consider:

• A very small number of cities (e.g., 2 or 3).
• Cities with identical coordinates.

Examples

Example 1: Input:

cities = [(0, 0), (1, 5), (4, 2), (6, 4)]
initial_temp = 1000
cooling_rate = 0.995
iterations_per_temp = 100

Output:

(Tour: [0, 1, 3, 2], Distance: 16.40312423743285)

Explanation: The algorithm starts with a random tour, e.g., [0, 1, 2, 3]. It then explores neighboring tours by making swaps. As the temperature cools, it becomes less likely to accept tours that increase the total distance. The output shows one possible near-optimal tour found by the algorithm and its calculated total Euclidean distance. The exact tour might vary due to the random nature of the algorithm.

Example 2: Input:

cities = [(0, 0), (10, 0), (5, 8.66)] # Equilateral triangle
initial_temp = 500
cooling_rate = 0.99
iterations_per_temp = 50

Output:

(Tour: [0, 1, 2], Distance: 30.0)

Explanation: For a small, symmetric problem like an equilateral triangle, the algorithm should ideally find the optimal solution, where each side is traveled once. The total distance is the sum of the lengths of the three sides.

Example 3: (Edge Case - Two Cities) Input:

cities = [(0, 0), (3, 4)]
initial_temp = 100
cooling_rate = 0.95
iterations_per_temp = 10

Output:

(Tour: [0, 1], Distance: 10.0)

Explanation: With only two cities, there's only one possible tour (going from city A to B and back to A, or vice versa, which is the same path length). The distance is twice the distance between the two points.

Constraints

• The number of cities will be between 2 and 50, inclusive.
• City coordinates will be integers or floats between -1000 and 1000.
• initial_temp will be a positive float.
• cooling_rate will be a float between 0 and 1 (exclusive of 0, inclusive of values close to 1, e.g., 0.9 to 0.999).
• iterations_per_temp will be a positive integer.
• The algorithm should run within a reasonable time limit (e.g., a few seconds for up to 50 cities).

Notes

• Euclidean Distance: The distance between two points (x1, y1) and (x2, y2) is sqrt((x2 - x1)^2 + (y2 - y1)^2).
• Initial Tour: A good starting point is a random permutation of the city indices.
• Neighbor Generation (2-opt): A simple and effective way to generate a neighbor is to pick two random indices i and j in the tour, and reverse the segment of the tour between i and j (inclusive of i, exclusive of j, or vice-versa, ensuring a valid swap). For example, if the tour is [A, B, C, D, E] and i=1, j=3, swapping indices 1 and 2 would give [A, C, B, D, E]. A 2-opt swap would be to reverse the segment between two indices, e.g., [A, B, C, D, E] with indices i=1 and j=3 could become [A, D, C, B, E] by reversing [B, C, D].
• Metropolis Criterion: Given an current state with energy E_current and a neighboring state with energy E_neighbor, the probability of accepting the neighbor is:
  • If E_neighbor < E_current, accept.
  • If E_neighbor >= E_current, accept with probability exp(-(E_neighbor - E_current) / Temperature).
• Experiment with initial_temp, cooling_rate, and iterations_per_temp to see how they affect the solution quality and runtime. Higher initial temperatures and slower cooling rates generally lead to better solutions but take longer.