2023年国赛数学建模思路 - 案例:退火算法
文章目录
- 1 退火算法原理
- 1.1 物理背景
- 1.2 背后的数学模型
- 2 退火算法实现
- 2.1 算法流程
- 2.2算法实现
- 建模资料
## 0 赛题思路
(赛题出来以后第一时间在CSDN分享)
https://blog.csdn.net/dc_sinor?type=blog
1 退火算法原理
1.1 物理背景
在热力学上,退火(annealing)现象指物体逐渐降温的物理现象,温度愈低,物体的能量状态会低;够低后,液体开始冷凝与结晶,在结晶状态时,系统的能量状态最低。大自然在缓慢降温(亦即,退火)时,可“找到”最低能量状态:结晶。但是,如果过程过急过快,快速降温(亦称「淬炼」,quenching)时,会导致不是最低能态的非晶形。
如下图所示,首先(左图)物体处于非晶体状态。我们将固体加温至充分高(中图),再让其徐徐冷却,也就退火(右图)。加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小(此时物体以晶体形态呈现)。
1.2 背后的数学模型
如果你对退火的物理意义还是晕晕的,没关系我们还有更为简单的理解方式。想象一下如果我们现在有下面这样一个函数,现在想求函数的(全局)最优解。如果采用Greedy策略,那么从A点开始试探,如果函数值继续减少,那么试探过程就会继续。而当到达点B时,显然我们的探求过程就结束了(因为无论朝哪个方向努力,结果只会越来越大)。最终我们只能找打一个局部最后解B。
根据Metropolis准则,粒子在温度T时趋于平衡的概率为exp(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变数,k为Boltzmann常数。Metropolis准则常表示为
Metropolis准则表明,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:P(dE) = exp( dE/(kT) )。其中k是一个常数,exp表示自然指数,且dE<0。所以P和T正相关。这条公式就表示:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(因为退火的过程是温度逐渐下降的过程),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。随着温度T的降低,P(dE)会逐渐降低。
我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。也就是说,在用固体退火模拟组合优化问题,将内能E模拟为目标函数值 f,温度T演化成控制参数 t,即得到解组合优化问题的模拟退火演算法:由初始解 i 和控制参数初值 t 开始,对当前解重复“产生新解→计算目标函数差→接受或丢弃”的迭代,并逐步衰减 t 值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值 t 及其衰减因子Δt 、每个 t 值时的迭代次数L和停止条件S。
2 退火算法实现
2.1 算法流程
(1) 初始化:初始温度T(充分大),初始解状态S(是算法迭代的起点), 每个T值的迭代次数L
(2) 对k=1,……,L做第(3)至第6步:
(3) 产生新解S′
(4) 计算增量Δt′=C(S′)-C(S),其中C(S)为评价函数
(5) 若Δt′<0则接受S′作为新的当前解,否则以概率exp(-Δt′/T)接受S′作为新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解,结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少,且T->0,然后转第2
2.2算法实现
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')
实现结果
建模资料
资料分享: 最强建模资料
相关文章:

2023年国赛数学建模思路 - 案例:退火算法
文章目录 1 退火算法原理1.1 物理背景1.2 背后的数学模型 2 退火算法实现2.1 算法流程2.2算法实现 建模资料 ## 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 退火算法原理 1.1 物理背景 在热力学上&a…...

怎么借助ChatGPT处理数据结构的问题
目录 使用ChatGPT进行数据格式化转换 代码示例 ChatGPT格式化数据提示语 代码示例 批量格式化数据提示语 代码示例 ChatGPT生成的格式化批处理代码 使用ChatGPT合并不同数据源的数据 合并数据提示语 自动合并数据提示语 ChatGPT生成的自动合并代码 结论 数据合并是…...

Docker容器无法启动 Cannot find /usr/local/tomcat/bin/setclasspath.sh
报错信息如下 解决办法 权限不够 加上--privileged 获取最大权限 docker run --privileged --name lenglianerqi -p 9266:8080 -v /opt/docker/lenglianerqi/webapps:/usr/local/tomcat/webapps/ -v /opt/docker/lenglianerqi/webapps/userfile:/usr/local/tomcat/webapps/u…...
Pytorch-day08-模型进阶训练技巧-checkpoint
PyTorch 模型进阶训练技巧 自定义损失函数动态调整学习率 典型案例:loss上下震荡 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BndMyRX0-1692613806232)(attachment:image-2.png)] 1、自定义损失函数 1、PyTorch已经提供了很多常用…...
【ArcGIS Pro二次开发】(61):样式(Style)和符号(Symbol)
在 ArcGIS Pro SDK 中,地图要素符号(Symbol)和符号样式(Style)是2个很重要的概念。 【Symbol】是用于表示地图上不同类型的要素(如点、线、面)的图形化表示。 在地图中,各种要素都…...
深入理解 HTTP/2:提升 Web 性能的秘密
HTTP/2 是一项重大的网络协议升级,旨在提升 Web 页面加载速度和性能。在这篇博客中,我们将深入探讨 HTTP/2 的核心概念以及如何使用它来加速网站。 什么是 HTTP/2? HTTP/2 是 HTTP 协议的下一个版本,旨在解决 HTTP/1.1 中的性能…...

800V高压电驱动系统架构分析
需要电驱竞品样件请联:shbinzer (拆车邦) 过去一年是新能源汽车市场爆发的一年,据中汽协数据,2021年新能源汽车销售352万辆,同比大幅增长157.5%。新能源汽车技术发展迅速,畅销车辆在动力性能…...
Camunda_3:主动撤回
貌似国际主流认知工作流通常不支持撤回/驳回,流程只能向前进行。而撤回/驳回算是一种中国特色吧。 因此Camunda对于流程修改也仅仅提供了runtimeService.createProcessInstanceModification(instanceId)来修改流程。对于撤回/驳回这种操作得自己想办法。通常的撤回/…...

ClickHouse(二十三):Java Spark读写ClickHouse API
进入正文前,感谢宝子们订阅专题、点赞、评论、收藏!关注IT贫道,获取高质量博客内容! 🏡个人主页:含各种IT体系技术,IT贫道_Apache Doris,大数据OLAP体系技术栈,Kerberos安全认证-CSDN博客 &…...
Linux下的GPIO基本概念指南
一、什么是GPIO 在Linux中,GPIO(General Purpose Input/Output,通用输入输出)是一种用于控制外部设备和传感器的通用接口。它允许你通过软件控制数字信号,从而实现各种硬件设备的交互,如LED、按钮、传感器、马达等。 每个GPIO引脚…...
快速解决Spring Boot跨域困扰:使用CORS实现无缝跨域支持
跨域问题 什么是跨域? 跨域(Cross-Origin Issue)的存在是因为浏览器的安全限制,它防止恶意网站利用跨域请求来获取用户的敏感信息或执行恶意操作。浏览器通过实施同源策略来限制网页在不同源之间进行资源访问或交互的情况。当一…...

【【萌新的STM32学习-13之GPIO寄存器的用法】】
萌新的STM32学习-13之GPIO寄存器的用法 从外部来看我们有很多个GPIO 分为ABCDEF等等 每个GPIO都有16个引脚 每个引脚的名字是PA0到PA15 这是外部的看法 对于内部 引脚自然会有引脚的功能传入的模式 状态 频率 等…...

Android开发基础知识总结(一)初识安卓Android Studio
一.基础理论知识 1.Linux相当于是地基。 MIUI,EMUI等操作系统,是基于安卓的改版——且裁掉了一部分Google的服务。 (鸿蒙虽然是改版,但和安卓的架构基本上一致) 2.Kotlin和Java都是JVM语言,必须先复习好…...

常见的网络设备有哪些?分别有什么作用?
个人主页:insist--个人主页 本文专栏:网络基础——带你走进网络世界 本专栏会持续更新网络基础知识,希望大家多多支持,让我们一起探索这个神奇而广阔的网络世界。 目录 一、网络设备的概述 二、常见的网络设备 1、…...

斗鱼财报盈利的背后:左手艳舞、右手擦边
本月14日,直播平台斗鱼发布了其第二季度财报,面对“看起来还不错的数据”,其对外着重强调了“连续两个季度实现盈利”,并称“斗鱼收入结构持续优化”“斗鱼盈利能力提升”“斗鱼稳健增长可期”“督导提升了内容审核能力”。 财报…...

布隆过滤器
思考一个问题:如果我想判断一个元素是否存在某个集合里面怎么做? 一般的解决方案是先把所有元素保存起来,然后通过循环比较来确定。 但是如果我们有几千万甚至上亿的数据的时候},虽然可以通过不同的数据结构来优化数据…...

element-ui中二次封装一个带select的form组件
带select的form组件 样式 代码 <template><el-form-item label"是否有" class"append" prop"tag"><el-form-itemprop"isShare"><el-select v-model"query.tag"><el-option v-for"(item, …...
07.利用Redis实现点赞排行榜功能
学习目标: 提示:学习如何利用Redisson实现点赞排行榜功能,按照时间顺序 当用户给某一篇文章点赞后,会再数据库中存储一条数据,并且在Redis中存储一条数据为当前博客的点赞用户标识,来区分哪个用户对文章进…...

【前端vue升级】vue2+js+elementUI升级为vue3+ts+elementUI plus
一、工具的选择 近期想将vuejselementUI的项目升级为vue3tselementUI plus,以获得更好的开发体验,并且vue3也显著提高了性能,所以在此记录一下升级的过程对于一个正在使用的项目手工替换肯定不是个可实现的解决方案,更优方案是基于…...

多维时序 | MATLAB实现SCNGO-BiLSTM-Attention多变量时间序列预测
多维时序 | MATLAB实现SCNGO-BiLSTM-Attention多变量时间序列预测 目录 多维时序 | MATLAB实现SCNGO-BiLSTM-Attention多变量时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 多维时序 | MATLAB实现SCNGO-BiLSTM-Attention多变量时间序列预测。 模型描…...

Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...