2024年美赛数学建模思路 - 案例:退火算法

文章目录

    • 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 random

class 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_seed
        T = self.T_max
        while T >= self.T_min:
            for i in range(self.iterMax):
                f1 = self.func(x1)
                delta_x = random.random() * 2 - 1
                if x1 + delta_x >= self.interval[0] and x1 + delta_x <= self.interval[1]:   # 将随机解束缚在给定状态空间内
                    x2 = x1 + delta_x
                else:
                    x2 = x1 - delta_x
                f2 = self.func(x2)
                delta_f = f2 - f1
                x1 = deal(x1, x2, delta_f, T)
            T *= self.rate
        self.x_solu = x1                                            # 提取最终退火解

    def func(self, x):                                              # 状态产生函数 - 即待求解函数
        value = np.sin(x**2) * (x**2 - 5*x)
        return value

    def p_min(self, delta, T):                                      # 计算最小值时,容忍解的状态迁移概率
        probability = np.exp(-delta/T)
        return probability

    def p_max(self, delta, T):
        probability = np.exp(delta/T)                               # 计算最大值时,容忍解的状态迁移概率
        return probability

    def deal_min(self, x1, x2, delta, T):
        if delta < 0:                                               # 更优解
            return x2
        else:                                                       # 容忍解
            P = self.p_min(delta, T)
            if P > random.random(): return x2
            else: return x1

    def deal_max(self, x1, x2, delta, T):
        if delta > 0:                                               # 更优解
            return x2
        else:                                                       # 容忍解
            P = self.p_max(delta, T)
            if P > random.random(): return x2
            else: return x1

    def 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')

实现结果

在这里插入图片描述

建模资料

资料分享: 最强建模资料
在这里插入图片描述
在这里插入图片描述

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

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

相关文章

文献速递:人工智能医学影像分割---基于合成MRI辅助的深度注意力全卷积网络的CT前列腺分割

文献速递&#xff1a;人工智能医学影像分割—基于合成MRI辅助的深度注意力全卷积网络的CT前列腺分割**** 01文献速递介绍 Prostate cancer is the most common cancer and the second leading cause of cancer death among men in the United States.1 Depending on the risk…

TA百人计划学习笔记 3.2混合模式及剔除

资料 源视频 【技术美术百人计划】图形 3.2 混合模式及剔除_哔哩哔哩_bilibili ppt https://github.com/sunkai174634/PhotoShopBlendModeUnityShader 实例 notargs.com混合模式 unity 官方文档 ShaderLab&#xff1a;混合 - Unity 手册 是什么 从渲染流程解释 从效果上解释 Bl…

常见的二十种软件测试方法详解

一.单元测试&#xff08;模块测试&#xff09; 单元测试是对软件组成单元进行测试。其目的是检验软件组成单位的正确性。测试对象是&#xff1a;模块。 对模块进行测试&#xff0c;单独的一个模块测试&#xff0c;属于静态测试的一类 测试阶段&#xff1a;编码后或者编码前&…

支付宝推出新年“五福节”活动,新增四大AI玩法;大型语言模型综合指南

&#x1f989; AI新闻 &#x1f680; 支付宝推出新年“五福节”活动&#xff0c;新增四大AI玩法 摘要&#xff1a;支付宝宣布今年的“集五福”活动升级为“五福节”&#xff0c;新增了四大AI玩法&#xff1a;飙戏小剧场、时空照相馆、会说话红包和大家来找福。用户可以通过拼…

“接口”公共规范的遵守者

&#x1f468;‍&#x1f4bb;作者简介&#xff1a;&#x1f468;&#x1f3fb;‍&#x1f393;告别&#xff0c;今天 &#x1f4d4;高质量专栏 &#xff1a;☕java趣味之旅 欢迎&#x1f64f;点赞&#x1f5e3;️评论&#x1f4e5;收藏&#x1f493;关注 &#x1f496;衷心的希…

Kubernetes多租户实践

由于namespace本身的限制&#xff0c;Kubernetes对多租户的支持面临很多困难&#xff0c;本文梳理了K8S多租户支持的难点以及可能的解决方案。原文: Multi-tenancy in Kubernetes 是否应该让多个团队使用同一个Kubernetes集群? 是否能让不受信任的用户安全的运行不受信任的工作…

VUE3好看的我的家乡网站模板源码

文章目录 1.设计来源1.1 首页界面1.2 旅游导航界面1.3 上海景点界面1.4 上海美食界面1.5 上海故事界面1.6 联系我们界面1.7 在线留言界面 2.效果和结构2.1 动态效果2.2 代码结构 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/…

在无公网IP环境下实现VS Code远程开发的方法

哈喽大家好&#xff0c;我是咕噜美乐蒂&#xff0c;很高兴又见面啦&#xff01; 随着云计算和远程协作的普及&#xff0c;越来越多的开发者选择使用VS Code进行远程开发。然而&#xff0c;有时我们会发现自己处于一个没有公网IP的网络环境&#xff0c;这可能会导致无法直接访问…

EasyCVR视频融合平台铁路抑尘喷洒监控系统视频搭建方案

一、建设背景与需求分析 随着我国铁路建设的迅猛发展&#xff0c;铁路抑尘喷洒设备质量监控系统在技术和管理方面都取得了显著的进步&#xff0c;面临安全压力也随之加大。为了确保铁路运输的安全和稳定&#xff0c;车站监控室、喷洒区域、操作间以及安全防护区域等关键区域都…

Docker Image(镜像)

Docker镜像是什么 Docker image 本质上是一个 read-only 只读文件&#xff0c;这个文件包含了文件系统、源码、库文件、依赖、工具等一些运行 application 所必须的文件。我们可以把 Docker image 理解成一个模板&#xff0c; 可以通过这个模板实例化出来很多容器。image 里面…

eNSP学习——VLAN基础配置及Access接口

目录 原理概述 实验内容&#xff1a; 实验目的&#xff1a; 实验步骤&#xff1a; 实验拓扑 配置过程 实验编址 基本配置 创建vlan 配置Access接口 原理概述 早期的局域网技术是基于总线型结构的。总线型拓扑结构是由一根单电缆连接所有主机&#xff0c;就导致所…

【设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构】

文章目录 一、什么是LRU&#xff1f;二、LinkedHashMap 实现LRU缓存三、手写LRU 一、什么是LRU&#xff1f; LRU是Least Recently Used的缩写&#xff0c;意为最近最少使用。它是一种缓存淘汰策略&#xff0c;用于在缓存满时确定要被替换的数据块。LRU算法认为&#xff0c;最近…

EasyX的安装与使用(VisualStudio C++免费绘图库)

EasyX Graphics Library 是针对 Visual C 的免费绘图库 安装教程 安装到Visual C 2010 EasyX 安装完毕。 在VC2010中建立控制台工程 工程建好后&#xff0c;鼠标右键点击工程名&#xff0c;并选择属性 安装到Visual C 2010 EasyX 安装完毕。 安装示例程序 easyxdemo.cpp 在VC…

什么是工控软件?一款很火的Web工业控制组态软件

随着工业4.0和智能制造的发展&#xff0c;工控软件的应用越来越广泛&#xff0c;它们在提高生产效率、降低能耗和减少人力成本等方面发挥着越来越重要的作用。 什么是工控软件&#xff1f; 工控软件是指用于工业控制系统的软件&#xff0c;主要应用于各种生产过程控制、自动化…

【服务器】安装宝塔面板

目录 &#x1f33a;【前言】 &#x1f33c;【前提】连接服务器 &#x1f337;方式一 使用工具登录服务器如Xshell &#x1f337;方式二 阿里云直接连接 &#x1f33c; 1. 安装宝塔 &#x1f337;获取安装脚本 方式一 使用下面提供的脚本安装 方式二 使用官网提供的脚本…

网络安全---防御保护--子接口小实验

子接口小实验&#xff1a; 环境准备&#xff1a; 防火墙区域配置为trust&#xff1a; PC设置其ip为同一个网段&#xff1a; 此时尝试ping无法ping通的原因是没有打开防火墙允许ping&#xff0c;我们在图形化界面允许ping即可 最终结果&#xff1a; .com域名服务器&#xff1a; …

HCIP-12

一、网关作为了一个广播域的中心出口&#xff1b;生成树的根网桥也是一棵树的中心&#xff0c;也是流量的集合点&#xff1b; 若将两者分配不同的设备将导致网络通讯资源浪费&#xff0c;故强烈建议两者在同一台设备上&#xff1b; 若使用基于vlan或基于分组的STP协议来工作三…

如何使用阿里云CDN服务?

如何使用阿里云CDN服务 一、开通阿里云CDN服务 注册自己阿里云账号&#xff0c;找到CDN服务&#xff0c;进行加速即可 二、配置域名信息 1、各配置参数的含义 添加加速域名&#xff1a; 如果需要使用CDN加速指定网站上的业务&#xff0c;则需要将该网站作为源站&#xff0…

swagger+knife4j整合

swagger pom配置 <!-- swagger 接口文档 --><dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.9.2</version></dependency><dependency><groupId>io.s…

Linux第35步_在“移植uboot”前安装libncurses5-dev

在“移植uboot”前&#xff0c;需要在Ubuntu中安装“libncurses5-dev”&#xff0c;否则在“编译uboot”时&#xff0c;会报错。目的是保证顺利移植“uboot”。 1、打开终端 2、输入“sudo apt-get install libncurses5-dev bison flex回车”&#xff1b; 3、输入密码“1234…