最新要闻
- 环球快报:“蜀道电行者”打好森林防火“组合拳”
- 快资讯:日媒:后锂离子电池时代竞争 中国碾压式领先日本、美国
- 全球今日讯!279元大额券:杰士邦零感003系列18枚30.9元狂促
- 每日报道:5.75亿超《你的名字》!《铃芽之旅》成中国影史日本动画票房第一
- 环球快看点丨安徽淮北9级大风:女子睡醒发现房顶被吹走 网友羡慕睡眠质量
- 知名演员王刚清空社交账号 本人回应:没兴趣没精力经营
- 热消息:陕西发布清明出行预测:公路基本畅通运行,高速车流量是平日1.3倍
- 今日聚焦!导演陆川:AI 15秒生成的海报 比专业公司一个月做得还好
- 318川藏线突现雪崩 行车记录仪拍下惊险一幕
- 世界微资讯!5500元 一图读懂特斯拉补能神器CyberVault赛博充:专为中国用户定制
- 信息:“喝酒吃药”卷土重来!公募基金重仓股TOP50中贵州茅台仍在榜首,还有17只票被增持(附表)
- 【报资讯】南漳:油菜花开春意浓
- 世界观察:揭秘你不知道的“寒食节”:春秋时期延续至今 要吃青团、凉面
- 车评人批丰田埃尔法不装后防撞梁:一个倒车碰撞车体就变形
- 天天热资讯!消灭刘海挖孔!曝iPhone 17 Pro将是首款真全面屏苹果手机
- 全球信息:5A级薄荷抗菌 凉感冰丝太爽:卡帝乐鳄鱼夏季平角裤7.3元/条发车
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
数学建模(三):模拟退火算法(SA)
- 模拟退火算法(SA)
- 一、 概述
- 1、 算法简介
- 2、 核心思想
- 3、 数学原理
- 4、 模拟退火的流程
- 二、 实例分析
- 1、 初始化参数
- 2、 Metrospolis 准则
- 3、 生成新的值
- 4、 获取最优值
- 5、 主程序
- 6、 总代码
- 一、 概述
模拟退火算法(SA)
一、 概述
1、 算法简介
模拟退火算法(simulated annealing,SA)来源于固体退火原理,是一种基于概率的算法。
模拟退火算法(SA)来源于固体退火原理,是一种基于概率的算法。将固体加温至充分高的温度,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,分子和原子越不稳定。而徐徐冷却时粒子渐趋有序,能量减少,原子越稳定。在冷却(降温)过程中,固体在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。
(资料图片仅供参考)
模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性,从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
2、 核心思想
模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。
这里的 “一定的概率” 的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。将温度 T 当作控制参数,目标函数值 f 视为内能 E ,而固体在某温度 T 时的一个状态对应一个解 \(x_i\),然后算法试图随着控制参数 T 的降低,使目标函数 f (内能 E )也逐渐降低,直至趋于全局最小值(退火中低温时的最低能量状态),就像金属退火过程一样。
关于爬山算法与模拟退火,有一个有趣的比喻:
爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。
模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
3、 数学原理
从上面我们知道,会结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,那么具体的更新解的机制是什么呢?如果新解比当前解更优,则接受新解,否则基于Metropolis
准则判断是否接受新解。接受概率为:
假设开始状态在A,随着迭代次数更新到B局部最优解,这时发现更新到B时,能量比A要低,则说明接近最优解了,因此百分百转移,状态到达B后,发现下一步能量上升了,如果是梯度下降则是不允许继续向前的,而这里会以一定的概率跳出这个坑,这个概率和当前的状态、能量等都有关系,如果B最终跳出来了到达C,又会继续以一定的概率跳出来,直到到达D后,就会稳定下来。
4、 模拟退火的流程
(1) 初始化:初始温度 T (充分大),初始解状态S(是算法迭代的起点),每个 T 值的迭代次数 L
(2) 对 k=1, …, L 做第(3)至第(6)步:
(3) 产生新解 S′
(4) 计算增量 ΔT = C(S′)-C(S),其中 C(S) 为目标函数, C(S) 相当于能量
(5) 若 ΔT<0 则接受 S′ 作为新的当前解,否则以概率 exp(-ΔT/T) 接受S′作为新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解,结束程序。
(7) T 逐渐减少,且 T->0 ,然后转第2步。
其中有几个需要注意的点:
- 初始点的选取对算法结果有一定的影响,最好是多次运行对结果进行综合判断。
- 在算法运行初期,温度下降快,避免接受过多的差结果。当运行时间增加,温度下降减缓,以便于更快稳定结果。
- 当迭代次数增加到一定次数时,结果可能已经达到稳定,但是距离算法结束还有一段时间。在设计程序时应该加入适当的输出条件,满足输出条件即可结束程序。
可以大概分为这四个步骤:
- 第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
- 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。
- 第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是 Metropolis 准则: 若 ΔT < 0 则接受 S′ 作为新的当前解 S,否则以概率 P 接受 S′ 作为新的当前解 S。
- 第四步是当新解被确定接受时,用新解代替当前解,这只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时,则在原当前解的基础上继续下一轮试验。
二、 实例分析
1、 初始化参数
# -*- coding: utf-8 -*-"""Created on Mon Apr 3 19:17:28 2023@author: steve"""from random import randomimport mathimport matplotlib.pyplot as pltmax_iter = 100 # 每一次温度降低的迭代次数alpha = 0.99 # 降温系数T_f = 0.01 # 温度的终值T_n = 100 # 当前的温度,也是初始温度x, y = [random() * 10 - 5 for i in range(max_iter)], [random() * 10 - 5 for i in range(max_iter)] # 进行数据的初始化f = lambda x, y : (4 * x ** 2 - 2.1 * x ** 4 + x ** 6 / 3 + x * y - 4 * y ** 2 + 4 * y ** 4) # 我们需要求的函数result = { "f": [], "t": [] } # 用来存放每一次下降的最优解
2、 Metrospolis 准则
def metrospolis(T_n, old, new): """ 进行 Metrospolis 准则的判断 Parameters ---------- T_n : int 当前的温度. old : double 函数扰动之前的值. new : double 函数扰动之后的值. Returns ------- int 是否需要重新寻找值. """ if old >= new: return 1 else: p = math.exp((old - new) / T_n) if random() < p: return 1 else: return 0
3、 生成新的值
def generate_new(T_n, x, y): """ 其为扰动的过程 Parameters ---------- T_n : int 当前的温度. x : double DESCRIPTION. y : double DESCRIPTION. Returns ------- list 返回生成的新值. """ while True: x_new = x + T_n * (random() - random()) y_new = y + T_n * (random() - random()) if (-5 <= x_new <= 5) & (-5 <= y_new <= 5): break #重复得到新解,直到产生的新解满足约束条件 return x_new, y_new
4、 获取最优值
def best(max_iter, f, x, y): """ 计算这个温度下的最优值 Parameters ---------- max_iter : int 最大的迭代次数. f : function 我们需要求的函数. x : double DESCRIPTION. y : double DESCRIPTION. Returns ------- list 返回最优值,以及它的索引. """ min_val, min_inx = f(x[0], y[0]), 0 for i in range(max_iter): val = f(x[i], y[i]) if min_val > val: min_val, min_inx = val, i return [min_val, min_inx]
5、 主程序
def plot(result): plt.plot(result["t"], result["f"]) plt.title("SA") plt.xlabel("t") plt.ylabel("f") plt.gca().invert_xaxis() plt.show()def main(max_iter, alpha, T_f, T_n, x, y, f, result): count = 0 # 统计迭代了多少次 while T_n > T_f: # 外层循环,当前温度小于最低温度时,终止循环 for i in range(max_iter): # 内层循环 x_new, y_new = generate_new(T_n, x[i], y[i]) # 产生新值 if metrospolis(T_n, f(x[i], y[i]), f(x_new, y_new)): # 将原值与新产生的值进行比较 x[i] = x_new # 如果接收新值,则存入数组中 y[i] = y_new # 迭代 max_iter 后,记录该温度下的最优解 [ft, _] = best(max_iter, f, x, y) result["f"].append(ft) result["t"].append(T_n) T_n = T_n * alpha # 进行降温操作 count += 1 # 得到最优解 [f_best, inx] = best(max_iter, f, x, y) print(f"F={f_best}, x_1={x[inx]}, x_2={y[inx]}") # 进行图像表示 plot(result)
6、 总代码
# -*- coding: utf-8 -*-"""Created on Mon Apr 3 19:17:28 2023@author: steve"""from random import randomimport mathimport matplotlib.pyplot as pltdef metrospolis(T_n, old, new): """ 进行 Metrospolis 准则的判断 Parameters ---------- T_n : int 当前的温度. old : double 函数扰动之前的值. new : double 函数扰动之后的值. Returns ------- int 是否需要重新寻找值. """ if old >= new: return 1 else: p = math.exp((old - new) / T_n) if random() < p: return 1 else: return 0 def generate_new(T_n, x, y): """ 其为扰动的过程 Parameters ---------- T_n : int 当前的温度. x : double DESCRIPTION. y : double DESCRIPTION. Returns ------- list 返回生成的新值. """ while True: x_new = x + T_n * (random() - random()) y_new = y + T_n * (random() - random()) if (-5 <= x_new <= 5) & (-5 <= y_new <= 5): break #重复得到新解,直到产生的新解满足约束条件 return x_new, y_new def best(max_iter, f, x, y): """ 计算这个温度下的最优值 Parameters ---------- max_iter : int 最大的迭代次数. f : function 我们需要求的函数. x : double DESCRIPTION. y : double DESCRIPTION. Returns ------- list 返回最优值,以及它的索引. """ min_val, min_inx = f(x[0], y[0]), 0 for i in range(max_iter): val = f(x[i], y[i]) if min_val > val: min_val, min_inx = val, i return [min_val, min_inx]def plot(result): plt.plot(result["t"], result["f"]) plt.title("SA") plt.xlabel("t") plt.ylabel("f") plt.gca().invert_xaxis() plt.show()def main(max_iter, alpha, T_f, T_n, x, y, f, result): count = 0 # 统计迭代了多少次 while T_n > T_f: # 外层循环,当前温度小于最低温度时,终止循环 for i in range(max_iter): # 内层循环 x_new, y_new = generate_new(T_n, x[i], y[i]) # 产生新值 if metrospolis(T_n, f(x[i], y[i]), f(x_new, y_new)): # 将原值与新产生的值进行比较 x[i] = x_new # 如果接收新值,则存入数组中 y[i] = y_new # 迭代 max_iter 后,记录该温度下的最优解 [ft, _] = best(max_iter, f, x, y) result["f"].append(ft) result["t"].append(T_n) T_n = T_n * alpha # 进行降温操作 count += 1 # 得到最优解 [f_best, inx] = best(max_iter, f, x, y) print(f"F={f_best}, x_1={x[inx]}, x_2={y[inx]}") # 进行图像表示 plot(result) max_iter = 100 # 每一次温度降低的迭代次数alpha = 0.99 # 降温系数T_f = 0.01 # 温度的终值T_n = 100 # 当前的温度,也是初始温度x, y = [random() * 10 - 5 for i in range(max_iter)], [random() * 10 - 5 for i in range(max_iter)] # 进行数据的初始化f = lambda x, y : (4 * x ** 2 - 2.1 * x ** 4 + x ** 6 / 3 + x * y - 4 * y ** 2 + 4 * y ** 4) # 我们需要求的函数result = { "f": [], "t": [] } # 用来存放每一次下降的最优解main(max_iter, alpha, T_f, T_n, x, y, f, result)
最后的运行结果为:
关键词:
-
今日要闻!Advanced Installer傻瓜式打包教程
工具AdvancedInstaller11 0前言这个包不复杂,没有服务和注册表等操作,但需要 NETFramework4 5和MyS...
来源: 最全.NET Core 、.NET 5、.NET 6和.NET 7简介和区别
数学建模(三):模拟退火算法(SA)
今日要闻!Advanced Installer傻瓜式打包教程
环球快报:“蜀道电行者”打好森林防火“组合拳”
快资讯:日媒:后锂离子电池时代竞争 中国碾压式领先日本、美国
全球今日讯!279元大额券:杰士邦零感003系列18枚30.9元狂促
每日报道:5.75亿超《你的名字》!《铃芽之旅》成中国影史日本动画票房第一
环球快看点丨安徽淮北9级大风:女子睡醒发现房顶被吹走 网友羡慕睡眠质量
知名演员王刚清空社交账号 本人回应:没兴趣没精力经营
热消息:陕西发布清明出行预测:公路基本畅通运行,高速车流量是平日1.3倍
JAVA多线程并发编程-避坑指南
今日热闻!安装MYSQL_5.0/8.0教程(附数据库和客户端工具下载链接)
今日热议:易基因: oxRRBS+RRBS揭示炎症性肠病导致发育异常的表观遗传机制|甲基化研究
今日聚焦!导演陆川:AI 15秒生成的海报 比专业公司一个月做得还好
318川藏线突现雪崩 行车记录仪拍下惊险一幕
世界微资讯!5500元 一图读懂特斯拉补能神器CyberVault赛博充:专为中国用户定制
信息:“喝酒吃药”卷土重来!公募基金重仓股TOP50中贵州茅台仍在榜首,还有17只票被增持(附表)
【报资讯】南漳:油菜花开春意浓
世界观察:揭秘你不知道的“寒食节”:春秋时期延续至今 要吃青团、凉面
车评人批丰田埃尔法不装后防撞梁:一个倒车碰撞车体就变形
天天热资讯!消灭刘海挖孔!曝iPhone 17 Pro将是首款真全面屏苹果手机
全球信息:5A级薄荷抗菌 凉感冰丝太爽:卡帝乐鳄鱼夏季平角裤7.3元/条发车
观焦点:标准版终于要上高刷了!iPhone或2025年全系列引入LTPO技术
天天热讯:扫叶林风后,拾薪山雨前
day35 860. 柠檬水找零
当前快播:全网最详细中英文ChatGPT-GPT-4示例文档-智能AI辅助写作从0到1快速入门——官网推荐的48种最佳应用场景(附python/node.js/
环球微速讯:四月份去贵州旅游好吗_四月份去贵州旅游
戴苹果手表致手腕红肿你遇见没?苹果客服回应:或与皮肤敏感有关
全球微资讯!《拿破仑》年内公映
世界热消息:北汽越野BJ90狂降71万:打2.8折提换壳奔驰GLS
天天观天下!就是玩!马斯克将推特图标换成柴犬头像:还发了一幅漫画
每日讯息!村民回应网传奥迪轿车被当祭品焚烧:确实是意外
前沿热点:美克生能源携手新凤鸣集团 打造5MWh用户侧储能电站
天天关注:男生1900元买iPhone 14 Pro Max开机竟是安卓系统:商家被平台封禁
世界速看:铠侠成功研制出HLC闪存!SSD容量暴增:速度/耐用性比QLC还拉跨
环球观热点:2999元起 魅族20系列首销一秒破亿!京东、天猫多平台销冠
世界即时看!ChatGPT出现大规模封号; 我国移动网络IPv6流量首次突破50%;菜鸟首个航空运货中心落户深圳|Do早报
观焦点:Centos 分割卷组
焦点消息!中国恒大:公司与债权人特别小组成员签订三份重组支持协议
三利好助A股四月开门红 “小阳春”行情值得期待
每日消息!交易拥挤度创23年纪录 TMT板块还能热多久
要闻:国际金融市场早知道:4月4日
环球快资讯丨大家都越骂越买?iPhone 13成全球最畅销手机 小米为安卓挽尊
每日消息!国内将上映!真人电影《小美人鱼》最新预告 这美人鱼网友看完感叹
今日热闻!AMD Zen4加持!ROG首款掌机来了:比Switch强大太多
读SQL进阶教程笔记07_EXISTS谓词
gw文件用什么软件打开手机上_gw文件用什么软件打开
环球快播:《王者荣耀》杨玉环新皮肤官宣:时尚芭莎指导 春天的神女
环球速讯:外卖超20元才送?江苏省消保委:停止被迫“凑单”
前沿热点:LCD电视跌成白菜价 面板一哥京东方去年利润下滑71%
腰粗大树刮断砸中小轿车 女车主:不慌 先拍个视频
【当前独家】网传青海现野生大熊猫!专家:绝对不可能
【聚看点】c语言分解质因数_分解质因数的概念
全球要闻:网红书店言几又被强制执行6400万
centos 8 上sql server 安装
【全球热闻】HP发布暗影精灵9系列游戏本:RTX 4080干到13999元
【新要闻】1199元!海康Mage20 Pro家庭存储NAS发布:支持最大40TB容量
每日看点!对线!枪迷称落后22分曼联追分无望,内维尔怼阿森纳前15年战绩差
天天最资讯丨Flask
世界新消息丨Autoconfiguration详解——自动注入配置参数
当前速看:1080. 根到叶路径上的不足节点
【环球速看料】上下五千年 熊猫第一次有了站姐
环球滚动:菜鸟首个航空货运中心落户深圳:包裹效率提升30%
世界焦点!计算机系统的组成(1硬件系统篇)
昆自股份拟通过拍卖方式购买14套房产作为公司经营活动场所 评估价值为3516.56万
引入人工智能!米哈游刘伟:《崩坏:星穹铁道》将在NPC加入AI
终结者来临?让开发者都畏惧的AI真的对人类有威胁吗
【独家焦点】重回1元/包:中石化出品原生竹浆90抽*3层抽纸大促
观天下!11.98万起 广汽埃安爆款2023上新:48小时订单破万
我国民营火箭公司天兵科技将研发空天飞机:载100人全球任意地点往返
债市日报:4月3日
天天快报!上古卷轴五强制随从代码_上古卷轴5强制随从代码
天天消息!夜宿海底捞引争议!究竟谁在留宿?多数都为旅游的年轻人
当前资讯!00后男生坚持做副业月入万元:父母能力有限 只能靠自己
即时焦点:等等党赢了!全球车企正迈向产量过剩:价格战或卷土重来
15999元 微星泰坦GP68HX游戏本预售:16寸2.5K屏+RTX 4080
焦点消息!2023 LPL季后赛爆冷:BLG 3比0横扫WBG 提前进入四强
dmesg 时间误差现象
天天消息!韩国音乐下载网站(求专门下载韩国歌曲的网站··)
最新快讯!网信办:移动物联网连接数首次超移动电话用户数 已县县通5G
炫富风波后中金人均降薪20万 平均收入降至约78万元
3月朋友圈疯传的十大谣言:闰月上坟祸事临门、反复烧开水致癌都是假的
首次融入生成式AI!百度地图V18版发布:数字人小姐姐“坐”你副驾
环球快看:超威超能石墨烯电池旧车挑战赛:平均续航103.6km仍余电
环球快看点丨记录--Canvas实现打飞字游戏
微信小程序订阅消息开发指南(java)
环球动态:Midjourney? 文心一格? 一张思维导图带你了解图片生成AI
张同乐-从零开始,打造高效可靠的Locust性能测试
星城控股20亿元私募债券获上交所受理
张颂文败给了新海诚?同上映11天:两部新片口碑相仿 票房差距5亿
世界速递!成都一公寓按排量收停车费每月最低1200元 官方回应:可自行定价
北野武悼念坂本龙一:朋友们都不在了 只剩下我一个人
环球新动态:无任何定语!真我GT Neo5 SE预售销量破纪录:1999元真香
世界微头条丨《小美人鱼》新镜头截图:爱丽儿抚摸王子脸 王子尬笑
极氪001车主吐槽:语音助手突然出现故障,无法语音识别指令
Flask框架cbv的写法、请求与响应、请求扩展、session源码分析、闪现
HEU KMS Activator 30.2.0全能系统数字许可激活工具 (全新激活版)
DecisionTreeClassifier&DecisionTreeClassRegression
GPT-4 还没玩透,GPT-5已遭众人围剿
Python常见面试题015.请实现一个如下功能的函数