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

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

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


LLM大模型相关文章

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

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构建查询助手

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

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

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

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

GPT实战系列-ChatGLM2部署Ubuntu+Cuda11+显存24G实战方案

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

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

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/314910.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

1045 - Access denied for user ‘root @223.98.184.126‘ (using password: YES)

Mysql 1045错误 1 知识小课堂1.1 Mysql 1045错误1.2 mysql 常见的错误代码 2 问题呈现3 问题解决3.1 开始前的准备3.1.1 防火墙开端口3.1.2 宝塔管理控制 3.2 问题解决步骤 Navicat 连接数据库的时候报错&#xff0c;本文就是解决此问题。 1 知识小课堂 1.1 Mysql 1045错误 …

sectigo通配符dv证书400元买一年送1月实际签发13个月

Sectigo就是众多颁发数字证书的CA认证机构之一&#xff0c;旗下的DV通配符SSL证书作为一种加密通信工具&#xff0c;广泛应用于保护网站数据的安全。其中&#xff0c;SectigoDV通配符SSL证书是一种受欢迎的产品&#xff0c;它不仅能够提供强大的加密功能&#xff0c;还可以提高…

OpenGl L6坐标系统

一.标准化设备坐标 我们在L5谈到了对顶点着色器中的点进行变换&#xff0c;而变换的范围必须在 -1.0到1.0 之间&#xff0c;否者将不可见。只有将所有的点转换为标准化设备坐标后&#xff0c;才能全部传入光栅器&#xff0c;再转换为屏幕上的像素。 将坐标变换为标准化设备坐标…

【C语言小游戏】贪吃蛇

文章目录 1.引言2.运行图2.涉及知识3 Windows API3.1 控制台3.2 控制台屏幕坐标3.3 操作句柄3.4 控制台屏幕光标3.5 监视按键 4. 设计说明5. 完整代码 1.引言 使⽤C语⾔在Windows环境的控制台中模拟实现经典⼩游戏贪吃蛇 实现基本的功能&#xff1a; 贪吃蛇地图绘制蛇吃⻝物的…

基于SpringBoot的洗衣店管理系统

基于SpringBoot的洗衣店管理系统的设计与实现~ 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBootMyBatis工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 登录界面 可视化展示 用户界面 管理员界面 摘要 洗衣店管理系统基于Spring Boot框…

LeetCode 38 外观数列

题目描述 外观数列 给定一个正整数 n &#xff0c;输出外观数列的第 n 项。 「外观数列」是一个整数序列&#xff0c;从数字 1 开始&#xff0c;序列中的每一项都是对前一项的描述。 你可以将其视作是由递归公式定义的数字字符串序列&#xff1a; countAndSay(1) "1…

09Bean的生命周期/作用域不同管理方式不同/自己new的对象纳入Spring容器管理

Spring其实就是一个管理Bean对象的工厂。它负责对象的创建&#xff0c;对象的销毁等。 所谓的生命周期就是&#xff1a;对象从创建开始到最终销毁的整个过程。 Bean的生命周期之5步 ● 第一步&#xff1a;实例化Bean(无参构造方法执行) ● 第二步&#xff1a;Bean属性赋值(注…

Swin Transformer 学习笔记(附代码)

论文地址&#xff1a;https://arxiv.org/pdf/2103.14030.pdf 代码地址&#xff1a; GitHub - microsoft/Swin-Transformer: This is an official implementation for "Swin Transformer: Hierarchical Vision Transformer using Shifted Windows". 1.是什么&#x…

Unity——VContainer的依赖注入

一、IOC控制反转和DI依赖倒置 1、IOC框架核心原理是依赖倒置原则 C#设计模式的六大原则 使用这种思想方式&#xff0c;可以让我们无需关心对象的生成方式&#xff0c;只需要告诉容器我需要的对象即可&#xff0c;而告诉容器我需要对象的方式就叫做DI&#xff08;依赖注入&…

SqlAlchemy使用教程(一) 原理与环境搭建

一、SqlAlchemy 原理及环境搭建 SqlAlchemy是1个支持连接各种不同数据库的Python库&#xff0c;提供DBAPI与ORM&#xff08;object relation mapper&#xff09;两种方式使用数据库。 DBAPI方式&#xff0c;即使用SQL方式访问数据库 ORM, 对象关系模型&#xff0c;是用 Python…

js 实现拖动按钮添加布局

效果&#xff1a; h布局生成左右布局&#xff0c; v布局生成上下布局 代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, ini…

Python笔记08-面向对象

文章目录 类和对象构造方法内置方法封装继承类型注解多态 类只是一种程序内的“设计图纸”&#xff0c;需要基于图纸生产实体&#xff08;对象&#xff09;&#xff0c;才能正常工作 这种套路&#xff0c;称之为&#xff1a;面向对象编程 类和对象 定义类的语法如下&#xff…

vue v-for循环拖拽排序,实现数组选中的数据拖拽后对应的子数据也进行重新排序

如下图所有&#xff0c;有个需求更新&#xff0c; 实现拖拽。 1&#xff0c;当新增了测点类型的时候每个对应的回路子数据都会新增对应的测点类型。 2&#xff0c;当拖动测点类型结束的时候对应的回路里面的内容也会跟着测点类型的排序自动排序 其实很简单&#xff0c;只要会了…

el-tree多个树进行节点同步联动(完整版)

2024.1.11今天我学习了如何对多个el-tree树进行相同节点的联动效果&#xff0c;如图&#xff1a; 这边有两棵树&#xff0c;我们发现第一个树和第二个树之间会有重复的指标&#xff0c;当我们选中第一个树的指标&#xff0c;我们希望第二个树如果也有重复的指标也能进行勾选上&…

鸿蒙实战基础(ArkTS)-窗口管理

基于窗口能力&#xff0c;实现验证码登录的场景&#xff0c;主要完成以下功能&#xff1a; 登录页面主窗口实现沉浸式。输入用户名和密码后&#xff0c;拉起验证码校验子窗口。验证码校验成功后&#xff0c;主窗口跳转到应用首页。 登录界面实现沉浸式 完成登录界面布局的编…

全面解析微服务

导读 微服务是企业应用及数据变革升级的利器&#xff0c;也是数字化转型及运营不可或缺的助产工具&#xff0c;企业云原生更离不开微服务&#xff0c;同时云原生的既要最大化发挥微服务的价值&#xff0c;也要最大化弥补微服务的缺陷。本文梳理了微服务基础设施组件、服务网格、…

企业数据中台整体介绍及建设方案:文件全文51页,附下载

关键词&#xff1a;数据中台解决方案&#xff0c;数据治理&#xff0c;数据中台技术架构&#xff0c;数据中台建设内容&#xff0c;数据中台核心价值 一、什么是数据中台&#xff1f; 数据中台是指通过数据技术&#xff0c;对海量数据进行采集、计算、存储、加工&#xff0c;…

富唯智能新研发的复合机器人,轻松破解汽车底盘零配件生产中的难题

随着汽车工业的快速发展&#xff0c;对于底盘零配件的需求也日益增长。为了满足市场需求&#xff0c;智能物流解决方案在汽车底盘零配件生产中扮演着越来越重要的角色。如何实现高效、准确的生产和物流管理&#xff0c;以满足市场快速变化的需求&#xff0c;成为了汽车生产商亟…

在加载第三方库过程中,无法加载到库的问题(使用readelf, patchelf命令)

无法加载到库问题 问题及分析过程readelf 命令patchelf命令 问题及分析过程 在开发一个程序过程中&#xff0c;需要加载第三方库iTapTradeAPI, 在CMakeList.txt中已经设置了CMAKE_INSTALL_RPATH&#xff0c;但是发布到生产之后由于目录问题无法加载到libiTapTradeAPI库了 下面…

Vue过滤器详解

聚沙成塔每天进步一点点 本文内容 ⭐ 专栏简介基本用法多个过滤器的串联过滤器在指令中的应用全局过滤器 ⭐ 本期推荐 ⭐ 专栏简介 Vue学习之旅的奇妙世界 欢迎大家来到 Vue 技能树参考资料专栏&#xff01;创建这个专栏的初衷是为了帮助大家更好地应对 Vue.js 技能树的学习。每…