经典算法-模拟退火算法的python实现
经典算法-模拟退火算法的python实现
模拟退火算法基本思想
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却。加温时,固体内部粒子随温度升高变为无序状,内能增大,而缓慢冷却时粒子又逐渐趋有序。从理论上讲,如果冷却过程足够缓慢,那么冷却中任一温度时固体都能达到热平衡,而冷却到低温时将达到这一低温下的内能最小状态。
LLM大模型相关文章:
大模型查询工具助手之股票免费查询接口
GPT实战系列-LangChain + ChatGLM3构建天气查询助手
GPT实战系列-大模型为我所用之借用ChatGLM3构建查询助手
GPT实战系列-简单聊聊LangChain
GPT实战系列-Baichuan2本地化部署实战方案
GPT实战系列-大话LLM大模型训练
GPT实战系列-ChatGLM3本地部署CUDA11+1080Ti+显卡24G实战方案
根据Metropolis准则,粒子在温度T时趋于平衡的概率为e(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
因为物理系统总是趋向于能量最低,而分子热运动则趋向于破坏这种低能量的状态,故而只需着重取贡献比较大的状态即可达到比较好的效果, 因而1953年Metropolis提出了这样一个重要性采样的方法, 即设从当前状态i生成新状态j。若新状态的内能小于状态i的内能(即Ej<Ei),则接受新状态j作为新的当前状态; 否则,以概率 e x p [ − ( E j − E i ) K T ] exp[\frac{-(E_j-E_i)}{KT}] exp[KT−(Ej−Ei)]接受状态j, 其中K为Boltzmann常数, 这就是通常所说的Metropolis准则。
初始化算法参数
self.interval = interval # 给定状态空间 - 即待求解空间self.T_max = T_max # 初始退火温度 - 温度上限self.T_min = T_min # 截止退火温度 - 温度下限self.iterMax = iterMax # 定温内部迭代次数self.rate = rate # 退火降温速度
算法基本步骤
①令 T = T 0 T=T_0 T=T0,即开始退火的初始温度,随机生成一个初始解工,并计算相应的目标函数值 E ( x 0 ) E(x_0) E(x0)。
②令T等于冷却进度表中的下一个值 T i T_i Ti。
③根据当前 x i x_i xi,进行扰动(扰动方式可以参考后面的实例),产生一个新解 x j x_j xj、计算应的目标函数值 E ( x j ) E(x_j) E(xj),得到$ △E=E(x_j)一E(x_i)$。
④若△E<0,则新解 x j x_j xj 被接受,作为新的当前解;若 △ E > 0 △E>0 △E>0,则新解 x j x_j xj ,按概率 e x p ( − △ E / T i ) exp(-△E/T_i) exp(−△E/Ti) 接受, T i T_i Ti为当前温度。
⑤在温度 T i T_i Ti下,重复 L k L_k Lk次的扰动和接受过程,即执行步骤③与④。
⑥判断T是否已到达 T j T_j Tj,是,则终止算法;否,则转到步骤②继续执行。
x1 = self.x_seedT = self.T_maxwhile T >= self.T_min:for i in range(self.iterMax):f1 = self.func(x1)delta_x = random.random() * 2 - 1if x1 + delta_x >= self.interval[0] and x1 + delta_x <= self.interval[1]: # 将随机解束缚在给定状态空间内x2 = x1 + delta_xelse:x2 = x1 - delta_xf2 = self.func(x2)delta_f = f2 - f1x1 = deal(x1, x2, delta_f, T)T *= self.rateself.x_solu = x1 # 提取最终退火解
算法实质分两层循环,在任一温度随机扰动产生新解,并计算目标函数值的变化,决定是否被接受。由于算法初始温度比较高,这样,使E增大的新解在初始时也可能被接受。因而能跳出局部极小值,然后通过缓慢地降低温度,算法就最终可能收敛到全局最优解。还有一点要说明的是,虽然在低温时接受函数已经非常小了,但仍不排除有接受更差的解的可能,因此一般都会把退火过程中碰到的最好的可行解(历史最优解)也记录下来,与终止算法前最后一个被接受解一并输出。
参数说明
退火过程由一组初始参数, 即冷却进度表(cooling schedule) 控制, 它的核心是尽量使系统达到准平衡,以使算法在有限的时间内逼近最优解。冷却进度表包括:
- ①控制参数的初值 T 0 T_0 T0:冷却开始的温度。
- ②控制参数T的衰减函数:因计算机能够处理的都是离散数据,因此需要把连续的降温过程离散化成降温过程中的一系列温度点,衰减函数即计算这一系列温度的表达式。
- ③控制参数T的终值 T j T_j Tj,(停止准则)。
- ④Markov链的长度 L k L_k Lk:任一温度T的迭代次数。
参数的选择
(1)控制参数T的初值 T 0 T_0 T0
求解全局优化问题的随机搜索算法一般都采用大范围的粗略搜索,与局部的精细搜索相结合的搜索策略。只有在初始的大范围搜索阶段找到全局最优解所在的区域,才能逐渐缩小搜索的范围.最终求出全局最优解。模拟退火算法是通过控制参数T的初值 T 0 T_0 T0和其衰减变化过程,来实现大范围的粗略搜索和局部精细搜索。
一般来说,只有足够大的 T 0 T_0 T0才能满足算法要求(但对不同的问题“足够大”的含义也不同,有的可能 T 0 T_0 T0=100就可以,有的则要1000)。在问题规模较大时,过小的 T 0 T_0 T0往往导致算法难以跳出局部陷阱而达不到全局最优。但为了减少计算量, T 0 T_0 T0不宜取得过大,而应与其他参数折中选取。
(2)控制参数T的衰减函数
衰减函数可以有多种形式,一个常用的衰减函数是
T k + 1 = α T k , k = 0 , 1 , 2 , . . . T_{k+1} = \alpha T_k, k=0, 1, 2, ... Tk+1=αTk,k=0,1,2,...
其中.a是一个常数,可以取为0.5~0.99,它的取值决定了降温的过程。小的衰减量可能导致算法进程迭代次数的增加,从而使算法进程接受更多的变换,访问更多的邻域,搜索更大范围的解空间,返回更好的最终解。同时由于在 T k T_k Tk值上已经达到准平衡,则在 T k + 1 T_{k+1} Tk+1时只需少量的变换就可达到准平衡。这样就可选取较短长度的Markov链来减少算法时间。
(3) Markov链长度
选取原则:
在控制参数T的衰减函数已选定的前提下, L k L_k Lk 应能使在控制参数T的每一取值上达到准平衡。从经验上来说,对简单的情况可以令 L k L_k Lk =100n,n为问题规模。
算法停止准则:
对Metropolis准则中的接受函数 e x p [ − ( E j − E i ) K T ] exp[\frac{-(E_j-E_i)}{KT}] exp[KT−(Ej−Ei)] 分析可知,在T比较大的高温情况下,指数上的分母比较大,而这是一个负指数,所以整个接受函数可能会趋于1,即比当前解x,更差的新解工,也可能被接受,因此就有可能跳出局部极小而进行广域搜索,去搜索解空间的其他区域;而随着冷却的进行,T减小到一个比较小的值时,接受函数分母小了,整体也小了,即难以接受比当前解更差的解,也就是不太容易跳出当前的区域。如果在高温时,已经进行了充分的广域搜索,找到了可能存在最好解的区域,而在低温再进行足够的局部搜索,则可能最终找到全局最优了。因此,一般T,应设为一个足够小的正数,比如0.01~5,但这只是一个粗糙的经验,更精细的设置及其他的终止准则可以查阅文献。
设计要点
为了更好地实现模拟退火算法,还需要注意以下方面。
状态表达
上文已经提到过,SA
算法中优化问题的一个解模拟了(或说可以想象为)退火过程中固体内部的一种粒子分布情况。这里状态表达即指实际问题的解(即状态),如何以一种合适的数学形式被表达出来,它应当适用于SA的求解、又能充分表达实际问题,这需要仔细地设计。
可以参考遗传算法和禁忌搜索中编码的相关内容。常见的表达方式有:背包问题和指派问题的0-1编码, TSP问题和调度问题的自然数编码:还有用于连续函数优化的实数编码等。
新解的产生
新解产生机制的基本要求是能够尽量遍及解空间的各个区域,这样、在某一恒定温度不断产生新解时,就可能跳出当前区域的极小以搜索其他区域,这是模拟退火算法能够进行广域搜索的一个重要条件。
收敛的一般性条件
收敛到全局最优的一般性条件是:
- ①初始温度足够高:
- ②热平衡时间足够长;
- ③终止温度足够低;
- ④降温过程足够缓慢。但上述条件在应用中很难同时满足。
Python实现
函数: f ( x ) = ( x 2 − 5 x ) s i n ( x 2 ) f(x) = (x^2 - 5x)sin(x^2) f(x)=(x2−5x)sin(x2)
import numpy as np
import matplotlib.pyplot as plt
import randomclass SA(object):def __init__(self, interval, tab='min', T_max=10000, T_min=1, iterMax=1000, rate=0.95):self.interval = interval # 给定状态空间 - 即待求解空间self.T_max = T_max # 初始退火温度 - 温度上限self.T_min = T_min # 截止退火温度 - 温度下限self.iterMax = iterMax # 定温内部迭代次数self.rate = rate # 退火降温速度#############################################################self.x_seed = random.uniform(interval[0], interval[1]) # 解空间内的种子self.tab = tab.strip() # 求解最大值还是最小值的标签: 'min' - 最小值;'max' - 最大值#############################################################self.solve() # 完成主体的求解过程self.display() # 数据可视化展示def solve(self):temp = 'deal_' + self.tab # 采用反射方法提取对应的函数if hasattr(self, temp):deal = getattr(self, temp)else:exit('>>>tab标签传参有误:"min"|"max"<<<')x1 = self.x_seedT = self.T_maxwhile T >= self.T_min:for i in range(self.iterMax):f1 = self.func(x1)delta_x = random.random() * 2 - 1if x1 + delta_x >= self.interval[0] and x1 + delta_x <= self.interval[1]: # 将随机解束缚在给定状态空间内x2 = x1 + delta_xelse:x2 = x1 - delta_xf2 = self.func(x2)delta_f = f2 - f1x1 = deal(x1, x2, delta_f, T)T *= self.rateself.x_solu = x1 # 提取最终退火解def func(self, x): # 状态产生函数 - 即待求解函数value = np.sin(x**2) * (x**2 - 5*x)return valuedef p_min(self, delta, T): # 计算最小值时,容忍解的状态迁移概率probability = np.exp(-delta/T)return probabilitydef p_max(self, delta, T):probability = np.exp(delta/T) # 计算最大值时,容忍解的状态迁移概率return probabilitydef deal_min(self, x1, x2, delta, T):if delta < 0: # 更优解return x2else: # 容忍解P = self.p_min(delta, T)if P > random.random(): return x2else: return x1def deal_max(self, x1, x2, delta, T):if delta > 0: # 更优解return x2else: # 容忍解P = self.p_max(delta, T)if P > random.random(): return x2else: return x1def display(self):print('seed: {}\nsolution: {}'.format(self.x_seed, self.x_solu))plt.figure(figsize=(6, 4))x = np.linspace(self.interval[0], self.interval[1], 300)y = self.func(x)plt.plot(x, y, 'g-', label='function')plt.plot(self.x_seed, self.func(self.x_seed), 'bo', label='seed')plt.plot(self.x_solu, self.func(self.x_solu), 'r*', label='solution')plt.title('solution = {}'.format(self.x_solu))plt.xlabel('x')plt.ylabel('y')plt.legend()plt.savefig('SA.png', dpi=500)plt.show()plt.close()if __name__ == '__main__':SA([-5, 5], 'max')
实际应用中,模拟退火算法的参数和操作可根据具体问题做适当的调整。
觉得有用 收藏 收藏 收藏
点个赞 点个赞 点个赞
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博客
相关文章:
经典算法-模拟退火算法的python实现
经典算法-模拟退火算法的python实现 模拟退火算法基本思想 模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却。加温时,固体内部粒子随温度升高变为无序状,内能增大,而缓慢冷却时粒子又逐渐趋有序。…...

谷粒学院项目redirect_uri 参数错误微信二维码登录
谷粒学院项目redirect_uri 参数错误_redirect_uri": "http%3a%2f%2fguli.shop%2fapi%2fuce-CSDN博客 修改本地配置 # ����˿� server.port8160 # ����&#x…...

Jenkins+nexus
jiekins安装完成 1、安装java环境 [rootnexus ~]# tar -xf jdk-8u211-linux-x64.tar.gz -C /usr/local [rootnexus ~]# vim /etc/profile.d/java.sh JAVA_HOME/usr/local/jdk1.8.0_211 PATH$PATH:$JAVA_HOME/bin [rootnexus ~]# source /etc/profile.d/java.sh 必须要选择与n…...

「JavaSE」类和对象1
🎇个人主页:Ice_Sugar_7 🎇所属专栏:快来卷Java啦 🎇欢迎点赞收藏加关注哦! 类和对象 🍉类的定义🍌类的实例化 🍉this引用🍉对象的构造及初始化🍌…...

Ubuntu server搭建dhcp服务器
安装 直接使用一下命令进行安装 apt-get install isc-dhcp-server 以下就是安装好的图片 然后进入dhcp目录 cd /etc/dhcp 进入后用ls查看当前目录存在哪些文件 使用如下进入dhcp.conf vim dhcpd.conf 红:设置ip域和子网掩码 绿:设置ip池范围 黄…...

2024--Django平台开发-Web框架和Django基础(二)---Mysql多版本共存(Mac系统)
MySQL多版本共存(Mac系统) 想要在Mac系统上同时安装【MySQL5.7 】【MySQL8.0】版本,需要进行如下的操作和配置。 想要同时安装两个版本可以采取如下方案: 方案1:【讲解】 MySQL57,用安装包进行安装。 MyS…...
Pytorch 反向传播 计算图被修改的报错
先看看报错的内容 RuntimeError: one of the variables needed for gradient computation has been modified by an inplace operation: [torch.FloatTensor [5, 1]], which is output 0 of AsStridedBackward0, is at version 2; expected version 1 instead. Hint: enable an…...

android studio设置gradle和gradle JDK版本
文章目录 1.gradle JDK版本2.gradle版本 1.gradle JDK版本 file -> project structure -> SDK Location -> Gradle Settings -> Gradle JDK -> Download JDK 2.gradle版本 file -> project structure -> Project...

Android 15即将到来,或将推出5大新功能特性
Android15 OneUI电池优化 三星最近完成了对其所有设备的稳定版 One UI 6.0 更新的推出,引起了用户的极大兴奋。据新出现的互联网统计数据显示,即将发布的基于 Android 15 的 One UI 7 将通过优化电池和功耗来重新定义用户体验,这是一项具有突…...
sqlalchemy 事务自动控制(类java aop)
最近使用它交互数据库,想实现类似java aop那种自动事务控制,不用手动commit或者rollback。我是用的是flaskdenpendency-injecter 这是我的db的配置类,里面会初始化一些session配置,里面比较重要的是把autocommit和autoflush关闭了…...

vue2-手写轮播图
轮播图5长展示,点击指示器向右移动一个图片,每隔2秒移动一张照片! <template><div class"top-app"><div class"carousel-container"><div class"carousel" ref"carousel">&…...

Google I/O大会:Android 13
3个体验升级的方向 以智能手机为场景核心、 扩大智能终端的应用边界以及实现多设备间更好地协同。具体到系统体验层,安卓13将支持图标颜色随主题更换、为不同应用设定使用的语言、新的媒体中心界面等等,同时谷歌也推出了自家的钱包应用(Goog…...

VUE指令(一)
vue会根据不同的指令,针对不同的标签实现不同的功能。指令是带有 v- 前缀的特殊标签属性。指令的职责是,当表达式的值改变时,将其产生的连带影响,响应式地作用于 DOM。 1、v-text:设置元素的文本内容,不会解…...

微信小程序开发学习笔记《7》全局配置以及小程序窗口
微信小程序开发学习笔记《7》全局配置以及小程序窗口 博主正在学习微信小程序开发,希望记录自己学习过程同时与广大网友共同学习讨论。全局配置官方文档 一、全局配置文件及常用的配置项 小程序根目录下的app.json 文件是小程序的全局配置文件。 常用的配置项如…...

Vue、uniApp、微信小程序、Html5等实现数缓存
此文章带你实现前端缓存,利用时间戳封装一个类似于Redis可以添加过期时间的缓存工具 不仅可以实现对缓存数据设置过期时间,还可以自定义是否需要对缓存数据进行加密处理 工具介绍说明 对缓存数据进行非对称加密处理 对必要数据进行缓存,并…...

如何将ArcGIS工程文件迁移到ArcGIS Pro内
当你刚接触ArcGIS Pro的时候,尝试新建一个工程文件会发现工程文件的后缀已经改变,那么以前在ArcGIS内辛苦制作的工程文件是否就不能在ArcGIS Pro内使用了,答案是否定的,对此Esri也给出了解决方案,这里为大家介绍一下迁…...

Jenkins基础篇--添加用户和用户权限设置
添加用户 点击系统管理,点击管理用户,然后点击创建用户(Create User) 用户权限管理 点击系统管理,点击全局安全配置,找到授权策略,选择安全矩阵,配置好用户权限后,点击…...

C语言基础内容(七)——第08章_C语言常用函数
文章目录 第08章_C语言常用函数本章专题脉络1、字符串相关函数1.1 字符串的表示方式1.2 两种方式的区别1.2 字符串常用函数strlen()strcpy()strncpy()strcat()strncat()strcmp()strlwr()/strupr()1.3 基本数据类型和字符串的转换基本数据类型 -> 字符串字符串 -> 基本数据…...

CRM系统针对销售管理有哪些功能?如何帮助销售效率增长?
从长远来看,有效的CRM管理系统可以帮助您的企业达到甚至超过收入目标。现代大多数企业都依靠CRM系统来管理其销售周期并增加收入。但是,当大多数人提到CRM时,他们指的是使能够改善业务关系并轻松管理不断团队的软件或工具。合格的CRM系统能够…...

基于Pixhawk和ROS搭建自主无人车(一):底盘控制篇
参考 ArduPilot Development超维空间科技乐迪MiniPix车船使用说明书 1. 硬件篇 1.1 底盘构成一览 1.2 底盘接线示意 2. 软件篇 2.1 APM 固件下载 pixhawk 是硬件平台,PX4 是 pixhawk 的原生固件,APM(Ardupilot Mega)是硬件平台…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...

vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...