通过模拟退火解决旅行商问题

Question

我目前正在尝试实现一种算法，通过模拟退火来解决旅行商问题。根据我对该主题的阅读，这就是我所实现的：

一些补充功能：

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

主要算法功能：

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

实施：

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)

我正在使用 ATSP 文件 br17，其中包含 17 个“城市”。如下图所示，超过 1000 次迭代后的距离没有显示出最小化的迹象。

有人可以就我的实施中可能存在的问题提供建议吗？任何帮助是极大的赞赏！谢谢！

Answer 1

您不小心将比较换成了公式

math.exp(-(current_distance - new_distance) / temperature)

你应该有

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

来自 java 源（尽管语言并不重要）