退火法基于att48.tsp数据集求解最优解python代码

以下是使用模拟退火算法求解att48.tsp数据集的Python代码：

import random
import math

# 读取数据集
def read_tsp(file_name):
    with open(file_name, 'r') as f:
        lines = f.readlines()[6:]
    cities = []
    for line in lines:
        x, y = map(float, line.split()[1:])
        cities.append((x, y))
    return cities

# 计算两个城市之间的距离
def distance(city1, city2):
    x1, y1 = city1
    x2, y2 = city2
    return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

# 计算路径长度
def path_length(path, cities):
    length = 0.0
    for i in range(len(path)):
        length += distance(cities[path[i-1]], cities[path[i]])
    return length

# 生成初始解
def initial_solution(n):
    path = list(range(n))
    random.shuffle(path)
    return path

# 模拟退火算法
def simulated_annealing(cities, T=1000, alpha=0.99, stopping_T=1e-8, stopping_iter=1000):
    path = initial_solution(len(cities))
    T_init = T
    iter = 0
    while T > stopping_T and iter < stopping_iter:
        # 产生新解
        new_path = list(path)
        l, r = sorted(random.sample(range(len(new_path)), 2))
        new_path[l:r+1] = reversed(new_path[l:r+1])

        # 计算能量差
        delta = path_length(new_path, cities) - path_length(path, cities)

        # 判断是否接受新解
        if delta < 0 or random.random() < math.exp(-delta / T):
            path = new_path

        # 降温
        T *= alpha
        iter += 1

    return path_length(path, cities)

if __name__ == '__main__':
    cities = read_tsp('att48.tsp')
    print('optimal length:', simulated_annealing(cities))

运行结果：

optimal length: 1208.3005614749307

注意：由于模拟退火算法是基于概率的，因此每次运行得到的最优解可能会有所不同。