Solving the Travelling Salesman Problem by Simulated Annealing

Question

I am currently attempting to implement an algorithm to solve the Travelling Salesman Problem by simulated annealing. Based on what I had read into the topic, this is what I had implemented:

Some supplementary functions:

def calculate_total_distance(route, distance_matrix):
total_distance = sum(distance_matrix[route[i]][route[i+1]] for i in range(len(route) - 1))
total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
return total_distance

def create_initial_route(number_of_cities):
    route = list(range(number_of_cities))
    random.shuffle(route)
    return route

def swap_two_cities(route):
    new_route = route.copy()
    city1, city2 = random.sample(range(len(route)), 2)
    new_route[city1], new_route[city2] = new_route[city2], new_route[city1]
    return new_route

Main algorithm function:

def simulated_annealing(distance_matrix, initial_temperature, cooling_rate, number_of_iterations):
    current_route = create_initial_route(len(distance_matrix))
    current_distance = calculate_total_distance(current_route, distance_matrix)
    temperature = initial_temperature

    for iteration in range(number_of_iterations):
        new_route = swap_two_cities(current_route)
        new_distance = calculate_total_distance(new_route, distance_matrix)

        if new_distance < current_distance or random.random() < math.exp(-(current_distance - new_distance) / temperature):
            current_route, current_distance = new_route, new_distance
        print(current_route, current_distance)
        temperature *= cooling_rate

    return current_route, current_distance

Implementation:

initial_temperature = 5000
cooling_rate = 0.995
number_of_iterations = 1000

optimal_route, optimal_distance = simulated_annealing(distance_matrix, initial_temperature, cooling_rate, number_of_iterations)
print("Optimal route:", optimal_route)
print("Total distance:", optimal_distance)

I am utilising the ATSP file br17, which holds 17 "cities". As you can see in the image below, the distance over 1000 iterations shows no sign of minimisation.

Is anyone able to help advise on what might be the problem in my implementation? Any help is greatly appreciated! Thank you!

Answer 1

you accidentally swapped comparison for the formula math.exp(-(current_distance - new_distance) / temperature)

you should have

if new_distance < current_distance or random.random() > math.exp(-(current_distance - new_distance) / temperature):

edit: no i'm stupid but you did miss a sign random.random() < math.exp((current_distance - new_distance) / temperature

also try playing around with your cooling rate( 0.99 seems to work a little better, ideally automatically calculate it)

from java source (though the language doesn't matter much)