退火与启发式退火求解att48.tsp数据集最优路径并绘图python代码

下面是使用模拟退火算法和启发式退火算法求解att48.tsp数据集最优路径并绘图的Python代码：

import math
import random
import matplotlib.pyplot as plt

# 读取数据集
def read_data(filename):
    with open(filename) as f:
        lines = f.readlines()
        data = []
        for line in lines:
            if line.strip():
                data.append(list(map(float, line.strip().split())))
        return data

# 计算两个城市之间的距离
def distance(city1, city2):
    return math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)

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

# 随机生成初始路径
def random_path(n):
    path = list(range(n))
    random.shuffle(path)
    return path

# 模拟退火算法求解最优路径
def sa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter):
    n = len(data)
    path = random_path(n)
    length = path_length(path, data)
    temp = init_temp
    i = 0
    while temp >= stopping_temp and i < stopping_iter:
        new_path = list(path)
        # 交换两个随机城市的位置
        index1, index2 = random.sample(range(n), 2)
        new_path[index1], new_path[index2] = new_path[index2], new_path[index1]
        new_length = path_length(new_path, data)
        delta = new_length - length
        if delta < 0 or math.exp(-delta / temp) > random.random():
            path, length = new_path, new_length
        temp *= alpha
        i += 1
    return path, length

# 启发式退火算法求解最优路径
def hsa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter):
    n = len(data)
    path = random_path(n)
    length = path_length(path, data)
    temp = init_temp
    i = 0
    while temp >= stopping_temp and i < stopping_iter:
        for j in range(n):
            new_path = list(path)
            # 取出第j个城市
            city = new_path.pop(j)
            # 计算剩下城市到第j个城市的距离
            distances = []
            for k in range(n - 1):
                distances.append(distance(data[new_path[k]], data[city]))
            # 找到最近的城市插入到第j个位置
            index = distances.index(min(distances))
            new_path.insert(index, city)
            new_length = path_length(new_path, data)
            delta = new_length - length
            if delta < 0 or math.exp(-delta / temp) > random.random():
                path, length = new_path, new_length
        temp *= alpha
        i += 1
    return path, length

# 绘制路径图
def plot_path(path, data):
    x = [data[path[i]][0] for i in range(len(path))]
    y = [data[path[i]][1] for i in range(len(path))]
    plt.plot(x, y, 'o-')
    plt.show()

if __name__ == '__main__':
    data = read_data('att48.tsp')
    init_temp = 10000
    alpha = 0.99
    stopping_temp = 1e-8
    stopping_iter = 10000
    path, length = sa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter)
    print('SA TSP:', length)
    plot_path(path, data)
    path, length = hsa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter)
    print('HSA TSP:', length)
    plot_path(path, data)

其中，`read_data`函数用于读取数据集，`distance`函数用于计算两个城市之间的距离，`path_length`函数用于计算路径长度，`random_path`函数用于随机生成初始路径，`sa_tsp`函数用于使用模拟退火算法求解最优路径，`hsa_tsp`函数用于使用启发式退火算法求解最优路径，`plot_path`函数用于绘制路径图。

使用以下代码运行程序：

if __name__ == '__main__':
    data = read_data('att48.tsp')
    init_temp = 10000
    alpha = 0.99
    stopping_temp = 1e-8
    stopping_iter = 10000
    path, length = sa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter)
    print('SA TSP:', length)
    plot_path(path, data)
    path, length = hsa_tsp(data, init_temp, alpha, stopping_temp, stopping_iter)
    print('HSA TSP:', length)
    plot_path(path, data)

其中，`init_temp`为初始温度，`alpha`为温度下降速度，`stopping_temp`为终止温度，`stopping_iter`为终止迭代次数。运行程序后，会先使用模拟退火算法求解最优路径，然后绘制路径图；然后使用启发式退火算法求解最优路径，然后绘制路径图。