模拟退火解决旅行商问题 python

旅行商问题是一个经典的组合优化问题，它的目标是找到一条路径，使得旅行商从起点出发，经过所有城市恰好一次，最终回到起点的路径长度最短。模拟退火算法是一种基于概率的全局优化算法，可以用来解决旅行商问题。

下面是一个基于 python 的模拟退火算法解决旅行商问题的代码实现：

import math
import random

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

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

# 模拟退火算法求解旅行商问题
def simulated_annealing(cities, T=10000, alpha=0.99, stopping_T=1e-8, stopping_iter=1000):
    # 初始化路径
    path = list(range(len(cities)))
    random.shuffle(path)
    # 初始化温度
    t = T
    # 迭代次数
    i = 0
    # 记录最优解和对应的路径
    best_path = path[:]
    best_length = path_length(best_path, cities)
    while t > stopping_T and i < stopping_iter:
        # 产生新解
        new_path = path[:]
        # 交换两个随机城市的位置
        pos1, pos2 = sorted(random.sample(range(len(new_path)), 2))
        new_path[pos1:pos2+1] = reversed(new_path[pos1:pos2+1])
        # 计算新解路径长度
        new_length = path_length(new_path, cities)
        # 判断是否接受新解
        if new_length < best_length:
            best_path = new_path[:]
            best_length = new_length
            path = new_path[:]
        else:
            delta = new_length - path_length(path, cities)
            p = math.exp(-delta/t)
            if random.random() < p:
                path = new_path[:]
        # 降温
        t *= alpha
        i += 1
    return best_path, best_length

这个代码实现中，`cities` 是一个城市列表，每个城市由经度和纬度构成。`distance` 函数计算两个城市之间的欧几里得距离，`path_length` 函数计算给定路径的长度。`simulated_annealing` 函数使用模拟退火算法求解旅行商问题，其中 `T` 是初始温度，`alpha` 是降温因子，`stopping_T` 是停止降温的温度阈值，`stopping_iter` 是停止迭代的迭代次数阈值。该函数返回最优路径和对应的路径长度。

下面是一个使用该函数求解旅行商问题并可视化结果的示例：

import matplotlib.pyplot as plt
from mpl_toolkits.basemap import Basemap

# 生成随机城市
def generate_cities(n):
    cities = []
    for i in range(n):
        lat = random.uniform(-90, 90)
        lon = random.uniform(-180, 180)
        cities.append((lat, lon))
    return cities

# 可视化结果
def plot_path(path, cities):
    # 创建地图
    m = Basemap(projection='merc', llcrnrlat=-80, urcrnrlat=80, llcrnrlon=-180, urcrnrlon=180)
    # 绘制海岸线、国家边界线和州边界线
    m.drawcoastlines()
    m.drawcountries()
    m.drawstates()
    # 绘制城市位置
    lats = [city[0] for city in cities]
    lons = [city[1] for city in cities]
    x, y = m(lons, lats)
    m.plot(x, y, 'ro', markersize=5)
    # 绘制路径
    lats = [cities[path[i]][0] for i in range(len(path))]
    lons = [cities[path[i]][1] for i in range(len(path))]
    x, y = m(lons, lats)
    m.plot(x, y, 'b-', linewidth=2)
    # 显示图形
    plt.show()

# 生成随机城市
cities = generate_cities(50)
# 求解旅行商问题
path, length = simulated_annealing(cities)
print(f'路径长度：{length:.2f}')
# 可视化结果
plot_path(path, cities)

这个示例代码生成了 50 个随机城市，并使用模拟退火算法求解旅行商问题，最后将结果可视化展示出来。