网站栏目类型,鄂尔多斯建设招投标网站,网站建设 骏域网络建设专家广州,域名解析是什么意思## 0 赛题思路
#xff08;赛题出来以后第一时间在CSDN分享#xff09;
https://blog.csdn.net/dc_sinor?typeblog
1 退火算法原理
1.1 物理背景
在热力学上#xff0c;退火#xff08;annealing#xff09;现象指物体逐渐降温的物理现象#xff0c;温度愈低#…## 0 赛题思路
赛题出来以后第一时间在CSDN分享
https://blog.csdn.net/dc_sinor?typeblog
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表示自然指数且dE0。所以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) 对k1……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, tabmin, T_max10000, T_min1, iterMax1000, rate0.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-, labelfunction)plt.plot(self.x_seed, self.func(self.x_seed), bo, labelseed)plt.plot(self.x_solu, self.func(self.x_solu), r*, labelsolution)plt.title(solution {}.format(self.x_solu))plt.xlabel(x)plt.ylabel(y)plt.legend()plt.savefig(SA.png, dpi500)plt.show()plt.close()if __name__ __main__:SA([-5, 5], max)实现结果
