经典算法-模拟退火算法求解旅行商问题TSP

发布时间：2024年01月12日

经典算法-模拟退火算法求解旅行商问题TSP

旅行商问题（Traveling Salesman Problem, TSP）是组合优化中的经典问题。简单地说，一个旅行商需要访问N个城市，并返回到出发城市，问题是找到最短的可能路线，使得每个城市只被访问一次。由于TSP是一个NP-hard问题，找到其精确解决方案是非常计算密集型的，特别是对于大规模的城市集。因此，我们需要一种可以在合理的时间内得到近似解的方法。

GPT实战系列-Baichuan2本地化部署实战方案

GPT实战系列-如何用自己数据微调ChatGLM2模型训练

GPT实战系列-大话LLM大模型训练

GPT实战系列-ChatGLM2模型的微调训练参数解读

GPT实战系列-探究GPT等大模型的文本生成

GPT实战系列-Baichuan2等大模型的计算精度与量化

GPT实战系列-GPT训练的Pretraining，SFT，Reward Modeling，RLHF

GPT实战系列-P-Tuning本地化训练ChatGLM2等LLM模型，到底做了什么？(二)

GPT实战系列-P-Tuning本地化训练ChatGLM2等LLM模型，到底做了什么？(一)

模拟退火算法（Simulated Annealing, SA）是一个非常受欢迎的随机搜索技术，用于求解优化问题。模拟退火是受固体退火过程启发的一种算法，通过不断比较当前解和新解来找到问题的近似解。

在本文中，我们将介绍如何使用模拟退火算法解决TSP问题，并提供Python代码的实现。

问题描述

TSP问题描述的是以14个城市为例，假定14个城市的位置坐标如表所示，寻找一条最短的遍历14个城市的路径。

城市坐标

算法流程

计算城市距离

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

def total_distance(tour, cities):
    """计算给定路线的总距离"""
    n = len(tour)
    return sum(distance(cities[tour[i]], cities[tour[(i+1) % n]]) for i in range(n))

初始化退火算法参数

    # 初始解为城市的顺序
    current_solution = list(range(len(cities)))
    current_distance = total_distance(current_solution, cities)
    
    best_solution = current_solution[:]
    best_distance = current_distance
    
    temperature = initial_temperature

Metropolis准则函数

    # Metropolis准则
    if delta_distance < 0 or random.random() < np.exp(-delta_distance / temperature):
        current_solution = new_solution
        current_distance = new_distance
        
        if current_distance < best_distance:
            best_solution = current_solution[:]
            best_distance = current_distance

更新解

    # 随机选择两个城市进行交换，得到新的解
    i, j = random.sample(range(len(cities)), 2)
    new_solution = current_solution[:]
    new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
    
    new_distance = total_distance(new_solution, cities)
            
            delta_distance = new_distance - current_distance

主函数

def simulated_annealing(cities, initial_temperature, cooling_rate, num_iterations_per_temperature):
    """模拟退火算法求解TSP问题"""
    
    # 初始解为城市的顺序
    current_solution = list(range(len(cities)))
    current_distance = total_distance(current_solution, cities)
    
    best_solution = current_solution[:]
    best_distance = current_distance
    
    temperature = initial_temperature

    while temperature > 1e-3:  # 设置一个最低温度
        for _ in range(num_iterations_per_temperature):
            # 随机选择两个城市进行交换，得到新的解
            i, j = random.sample(range(len(cities)), 2)
            new_solution = current_solution[:]
            new_solution[i], new_solution[j] = new_solution[j], new_solution[i]
            
            new_distance = total_distance(new_solution, cities)
            
            delta_distance = new_distance - current_distance
            
            # Metropolis准则
            if delta_distance < 0 or random.random() < np.exp(-delta_distance / temperature):
                current_solution = new_solution
                current_distance = new_distance
                
                if current_distance < best_distance:
                    best_solution = current_solution[:]
                    best_distance = current_distance
        
        temperature *= cooling_rate  # 降低温度
    
    return best_solution, best_distance

cities = np.array([(16.47, 96.10),
                            (16.47, 94.44),
                            (20.09, 92.54),
                            (22.39, 93.37),
                            (25.23, 97.24),
                            (22.00, 96.05),
                            (20.47, 97.02),
                            (17.20, 96.29),
                            (16.30, 97.38),
                            (14.05, 98.12),
                            (16.53, 97.38),
                            (21.52, 95.59),
                            (19.41, 97.13),
                            (20.09, 92.55),])
initial_temperature = 1000
cooling_rate = 0.995
num_iterations_per_temperature = 1000

best_tour, best_distance = simulated_annealing(cities, initial_temperature, cooling_rate, num_iterations_per_temperature)
print("Best tour:", best_tour)
print("Best distance:", best_distance)

优化计算结果：

Best tour: [8, 9, 0, 1, 13, 2, 3, 4, 5, 11, 6, 12, 7, 10]
Best distance: 29.340520066994223

觉得有用 收藏收藏收藏

点个赞点个赞点个赞

End

GPT专栏文章：

GPT实战系列-ChatGLM3本地部署CUDA11+1080Ti+显卡24G实战方案

GPT实战系列-LangChain + ChatGLM3构建天气查询助手

大模型查询工具助手之股票免费查询接口

GPT实战系列-简单聊聊LangChain

GPT实战系列-大模型为我所用之借用ChatGLM3构建查询助手