强化学习求解TSP(六):Qlearning求解旅行商问题TSP(提供Python代码)

一、Qlearning简介

Q-learning是一种强化学习算法,用于解决基于奖励的决策问题。它是一种无模型的学习方法,通过与环境的交互来学习最优策略。Q-learning的核心思想是通过学习一个Q值函数来指导决策,该函数表示在给定状态下采取某个动作所获得的累积奖励。

Q-learning的训练过程如下:

1. 初始化Q值函数,将所有状态-动作对的Q值初始化为0。

2. 在每个时间步,根据当前状态选择一个动作。可以使用ε-greedy策略来平衡探索和利用。

3. 执行选择的动作,并观察环境返回的奖励和下一个状态。

4. 根据Q值函数的更新规则更新Q值。Q值的更新公式为:Q(s, a) = Q(s, a) + α * (r + γ * max(Q(s', a')) - Q(s, a)),其中α是学习率,γ是折扣因子,r是奖励,s是当前状态,a是选择的动作,s'是下一个状态,a'是在下一个状态下选择的动作。

5. 重复步骤2-4,直到达到停止条件。

Q-learning的优点是可以在没有先验知识的情况下自动学习最优策略,并且可以处理连续状态和动作空间。它在许多领域中都有广泛的应用,如机器人控制、游戏策略和交通路线规划等。

二、TSP问题介绍

旅行商问题(Traveling salesman problem, TSP)是一个经典的组合优化问题,它可以描述为一个商品推销员去若干城市推销商品,要求遍历所有城市后回到出发地,目的是选择一个最短的路线。当城市数目较少时,可以使用穷举法求解。而随着城市数增多,求解空间比较复杂,无法使用穷举法求解,因此需要使用优化算法来解决TSP问题。TSP问题的应用非常广泛,不仅仅适用于旅行商问题本身,还可以用来解决其他许多的NP完全问题,如邮路问题、转配线上的螺母问题和产品的生产安排问题等等。因此,对TSP问题的有效求解具有重要意义。解决TSP问题的方法有很多,其中一种常用的方法是蚁群算法。除了蚁群算法,还有其他一些常用的解决TSP问题的方法,如遗传算法、动态规划和强化学习等。这些方法各有特点,适用于不同规模和特征的TSP问题。

三、Qlearning求解TSP问题

1、部分代码

可以自动生成地图也可导入自定义地图,只需要修改如下代码中chos的值即可。

import matplotlib.pyplot as plt
from Qlearning import Qlearning
#Chos: 1 随机初始化地图; 0 导入固定地图
chos=1
node_num=36 #当选择随机初始化地图时,自动随机生成node_num-1个城市
# 创建对象,初始化节点坐标,计算每两点距离
qlearn = Qlearning(alpha=0.5, gamma=0.01, epsilon=0.5, final_epsilon=0.05,chos=chos,node_num=node_num)
# 训练Q表、打印路线
iter_num=1000#训练次数
Curve,BestRoute,Qtable,Map=qlearn.Train_Qtable(iter_num=iter_num)
#Curve 训练曲线
#BestRoute 最优路径
#Qtable Qlearning求解得到的在最优路径下的Q表
#Map TSP的城市节点坐标


## 画图
plt.figure()
plt.ylabel("distance")
plt.xlabel("iter")
plt.plot(Curve, color='red')
plt.title("Q-Learning")
plt.savefig('curve.png')
plt.show()


2、部分结果

(1)以国际通用的TSP实例库TSPLIB中的测试集bayg29为例:

Q-learning得到的最短路线: [1, 28, 6, 12, 9, 26, 29, 3, 5, 21, 2, 20, 10, 4, 15, 18, 14, 22, 17, 11, 19, 25, 7, 23, 27, 8, 24, 16, 13, 1]

(2)随机生成18个城市

Q-learning得到的最短路线: [1, 17, 6, 9, 13, 7, 4, 11, 8, 18, 3, 14, 15, 12, 10, 2, 5, 16, 1]

(3)随机生成28个城市

Q-learning得到的最短路线: [1, 14, 3, 25, 4, 7, 28, 5, 22, 19, 12, 9, 23, 13, 24, 21, 16, 27, 17, 8, 2, 10, 18, 20, 15, 6, 26, 11, 1]

四、完整Python代码

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

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

相关文章

【刷题篇】动态规划(八)

文章目录 1、分割回文串 IV2、分割回文串 II3、最长回文子序列4、让字符串成为回文串的最少插入次数5、最长公共子序列6、不相交的线 1、分割回文串 IV 给你一个字符串 s ,如果可以将它分割成三个 非空 回文子字符串,那么返回 true ,否则返回…

浅谈WPF之Popup弹出层

在日常开发中,当点击某控件时,经常看到一些弹出框,停靠在某些页面元素的附近,但这些又不是真正的窗口,而是页面的一部分,那这种功能是如何实现的呢?今天就以一个简单的小例子,简述如…

车辆行驶控制运动学模型的matlab建模与仿真,仿真输出车辆动态行驶过程

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 4.1 基本假设 4.2 运动学方程 5.完整工程文件 1.课题概述 车辆行驶控制运动学模型的matlab建模与仿真,仿真输出车辆动态行驶过程. 2.系统仿真结果 3.核心程序与模型 版本:MATLAB2022a .…

内存分区模型---C++

目录 内存分区模型1.1 程序运行前1.2 程序运行后1.2.1 new操作符 内存分区模型 C程序在执行时,将内存大方向划分为4个区域 代码区:存放函数体的二进制代码,由操作系统进行管理的;全局区:存放全局变量和静态变量以及常…

微服务自动化.etcd跨主机集群

目录 一、容器间内部通信 二、跨主机通信 1、直接路由 2、Pipework 3、Flannel ①、Flannel特点 三、环境搭建 ETCD版本问题 ①、修改配置文件 ②、api 2 使用方法 ③、 api 3 使用方法 4、 ETCD中保存网络信息 ①、使用v2版的set命令向ETCD中保存flannel覆盖网络信…

111.连接已终止的线程、线程分离、线程取消

一、连接已终止的线程 功能:和一个已经终止的线程进行连接 回收子线程的资源 这个函数是阻塞函数,调用一次只能回收一个子线程 参数:thread:需要回收的子线程的ID retval: 接收子线程推出时的返回值 返回值&#xff1a…

JVM基础(2)——JVM内存模型

一、简介 JVM会加载类到内存中,所以 JVM 中必然会有一块内存区域来存放我们写的那些类。Java中有类对象、普通对象、本地变量、方法信息等等各种对象信息,所以JVM会对内存区域进行划分: JDK1.8及以后,上图中的方法区变成了Metasp…

Java使用IText生产PDF时,中文标点符号出现在行首的问题处理

Java使用IText生成PDF时,中文标点符号出现在行首的问题处理 使用itext 5进行html转成pdf时,标点符号出现在某一行的开头 但这种情况下显然不符合中文书写的规则,主要问题出在itext中的DefaultSplitCharacter类,该方法主要用来判断…

基于ChatGPT4+Python近红外光谱数据分析及机器学习与深度学习建模

2022年11月30日,可能将成为一个改变人类历史的日子——美国人工智能开发机构OpenAI推出了聊天机器人ChatGPT3.5,将人工智能的发展推向了一个新的高度。2023年4月,更强版本的ChatGPT4.0上线,文本、语音、图像等多模态交互方式使其在…

C# Open Vocabulary Object Detection 部署开放域目标检测

目录 介绍 效果 模型信息 owlvit-image.onnx owlvit-post.onnx owlvit-text.onnx 项目 代码 Form1.cs OWLVIT.cs 下载 C# Open Vocabulary Object Detection 部署开放域目标检测 介绍 训练源码地址:https://github.com/google-research/scenic/tree/…

性格是如何形成的?能不能改变性格?

有一句话叫“性格决定命运”,广泛流传,也就是说 “命运”与“性格”是紧密相连的,可见“性格”对于一个人的重要性。 性格是怎么来的? 1、遗传基因 根据一些心理学家的最新研究,认为性格与人体内的基因有关系&#x…

浏览器缓存引发的odoo前端报错

前两天,跑了一个odoo16项目,莫名其妙的前端报错, moment.js 报的错, 这是一个时间库,不是我自己写的代码,我也没做过任何修改,搞不清楚为什么报错。以为是odoo的bug,所以从gitee下载…

【Python】编程练习的解密与实战(一)

​🌈个人主页:Sarapines Programmer🔥 系列专栏:《Python | 编程解码》⏰诗赋清音:云生高巅梦远游, 星光点缀碧海愁。 山川深邃情难晤, 剑气凌云志自修。 目录 🪐1. 初识Python &a…

RuntimeError: CUDA error: invalid device ordinal解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

C#基础-空处理

在c#中,值对象是没有办法赋值为null的。比如说,你想要定义一个布尔值,你的赋值数据要么得是true、要么就得是false,默认情况下我们永远没可能给这个布尔赋值为null,即使只是对这个变量进行声明而不初始化数据&#xff…

ChatGPT会给教育界带来怎样的冲击,又将与教育碰撞出怎样的火花?

11 月 7 日凌晨,美国人工智能公司 OpenAI 的开发者大会正式开启,创始人 Sam Altman 和其同事,发布了团队最新的成果GPT-4 Turbo,新一代的GPT不仅更快、有更长的上下文、而且更好的控制。而随之推出的「GPTs」——让人们能用自然语…

服务器执行rm命令时自动记录到审计日志中

目的 当在服务器上执行类似于 rm 命令时,自动记录该命令执行的时间,在哪里执行的,删除的什么文件,记录到审计日志中,能够查找到某些文件丢失原因 配置 # 需要root权限,sudo不行,这里假设执行…

Java:爬虫htmlunit实践

之前我们已经讲过使用htmlunit及基础,没有看过的可以参考Java:爬虫htmlunit-CSDN博客 我们今天就来实际操作一下,爬取指定网站的数据 1、首先我们要爬取一个网站数据的时候我们需要对其数据获取方式我们要进行分析,我们今天就拿双…

注册中心(Nacos)

简介 Dynamic Naming and Configuration Service的首字母简称,一个更易于构建云原生应用的动态服务发现、配置管理和服务管理平台。 Nacos 致力于帮助您发现、配置和管理微服务。Nacos 提供了一组简单易用的特性集,帮助您快速实现动态服务发现、服务配置、服务元数据及流量管…

基于DNA的密码学和隐写术综述

摘要 本文全面调研了不同的脱氧核糖核酸(DNA)-基于密码学和隐写术技术。基于DNA的密码学是一个新兴领域,利用DNA分子的大规模并行性和巨大的存储容量来编码和解码信息。近年来,由于其相对传统密码学方法的潜在优势,如高存储容量、低错误率和对环境因素的抗性,该领域引起…