模拟退⽕算法经典实例_深度学习经典算法模拟退⽕算法详解模拟退⽕算法基本思想 现代的模拟退⽕算法形成于20世纪80年代初，其思想源于固体的退⽕过程，即将固体加热⾄⾜够⾼的温度，再缓慢冷却。升温时，固体内部粒⼦随温度升⾼变为⽆序状，内能增⼤，⽽缓慢冷却时粒⼦⼜逐渐趋于有序，从理论上讲，如果冷却过程⾜够缓慢，那么冷却中任⼀温度时固体都能达到热平衡，⽽冷却到低温时将达到这⼀低温下的内能最⼩状态。 在这⼀过程中， 任⼀恒定温度都能达到热平衡是个重要步骤， 这⼀点可以⽤MonteCarlo算法模拟，不过其需要⼤量采样，⼯作量很⼤。但因为物理系统总是趋向于能量最低，⽽分⼦热运动则趋向于破坏这种低能量的状态，故⽽只需着重取贡献⽐较⼤的状态即可达到⽐较好的效果， 因⽽1953年Metropolis提出了这样⼀个重要性采样的⽅法， 即设从当前状态i⽣成新状态j.若新状态的内能⼩于状态i的内能(即
Ej<Ei)，则接受新状态j作为新的当前状态； 否则，以概率
接受状态j， 其中k为Boltzmann常数， 这就是通常所说的Metropolis准则。
1953年， Kirkpatrick把模拟退⽕思想与组合最优化的相似点进⾏类⽐， 将模拟退⽕应⽤到了组合最优化问题中，在把模拟退⽕算法应⽤于最优化问题时，⼀般可以将温度T当做控制参数，⽬标函数值f视为内能E，⽽固体在某温度T时的⼀个状态对应⼀个解 。
然后算法试图随着控制参数Ｔ的降低，使⽬标函数值f(内能E)也逐渐降低，直⾄趋于全局最⼩值(退⽕中低温时的最低能量状态)，就像
固体退⽕过程⼀样。
其他⼀些参数的说明
退⽕过程由⼀组初始参数， 即冷却进度表(cooling schedule) 控制， 它的核⼼是尽量使系统达到准平衡，以使算法在有限的时间内逼近最优解。冷却进度表包括：
①控制参数的初值T。：冷却开始的温度。
②控制参数Ｔ的衰减函数：因计算机能够处理的都是离散数据，因此需要把连续的降温过程离散化成降温过程中的⼀系列温度点，衰减
函数即计算这⼀系列温度的表达式。
③控制参数T的终值T，(停⽌准则)。
④Markov链的长度L.：任⼀温度T的迭代次数。
算法基本步骤
①令T=T。，即开始退⽕的初始温度，随机⽣成⼀个初始解⼯，并计算相应的⽬标函数值E(x0)。
②令Ｔ等于冷却进度表中的下⼀个值Ti。
③根据当前
，进⾏扰动(扰动⽅式可以参考后⾯的实例)，产⽣⼀个新解
、计算应的⽬标函数值E(
)，得到△E=E(
chunqingint
)⼀E(
)。
④若△E<0，则新解
被接受，作为新的当前解；若△E>0，则新解
，
按概率exp(⼀△E/
) 接受，
为当前温度。
⑤在温度
下，重复L，次的扰动和接受过程，即执⾏步骤③与④。
⑥判断T是否已到达
马克思劳动价值论，是，则终⽌算法；否，则转到步骤②继续执⾏。
算法实质分两层循环，在任⼀温度随机扰动产⽣新解，并计算⽬标函数值的变化，决定是否被接受。由于算法初始温度⽐较⾼，这样，使E 增⼤的新解在初始时也可能被接受.因⽽能跳出局部极⼩值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解。还有⼀点要说明的是，虽然在低温时接受函数已经⾮常⼩了，但仍不排除有接受更差的解的可能，因此⼀般都会把退⽕过程中碰到的最好的可⾏解(历史最优解)也记录下来，与终⽌算法前最后⼀个被接受解⼀并输出。
⼏点说明
为了更好地实现模拟退⽕算法，还需要注意以下⼀些⽅⾯。
状态表达
上⽂已经提到过，SA算法中优化问题的⼀个解模拟了(或说可以想象为)退⽕过程中固体内部的⼀种粒⼦分布情况。这⾥状态表达即指实际问题的解(即状态)如何以⼀种合适的数学形式被表达出来，它应当适⽤于SA的求解、⼜能充分表达实际问题，这需要仔细地设计。可以参考遗传算法和禁忌搜索中编码的相关内容。常见的表达⽅式有：背包问题和指派问题的0-1编码， TSP问题和调度问题的⾃然数编码：还有⽤于连续函数优化的实数编码等。 新解的产⽣
新解产⽣机制的基本要求是能够尽量遍及解空间的各个区域，这样、在某⼀恒定温度不断产⽣新解时，就可能跳出当前区域的极⼩以搜索其他区域，这是模拟退⽕算法能够进⾏⼴域搜索的⼀个重要条件。大良实验小学
收敛的⼀般性条件
收敛到全局最优的⼀般性条件是：
①初始温度⾜够⾼：
②热平衡时间⾜够长；
③终⽌温度⾜够低；
④降温过程⾜够缓慢。但上述条件在应⽤中很难同时满⾜。
参数的选择
(1)控制参数Ｔ的初值T。
求解全局优化问题的随机搜索算法⼀般都采⽤⼤范围的粗略搜索与局部的精细搜索相结合的搜索策略。只有在初始的⼤范围搜索阶段到全局最优解所在的区域，才能逐渐缩⼩搜索的范围.最终求出全局最优解。模拟退⽕算法是通过控制参数Ｔ的初值T。和其衰减变化过程来实现⼤范围的粗略搜索和局部精细搜索。
⼀般来说，只有⾜够⼤的T。才能满⾜算法要求(但对不同的问题“⾜够⼤”的含义也不同，有的可能T。=100就可以，有的则要1010)。在问题规模较⼤时，过⼩的T。往往导致算法难以跳出局部陷阱⽽达不到全局最优。但为了减少计算量，T。不宜取得过⼤，⽽应与其他参数折中选取。
(2)控制参数Ｔ的衰减函数
衰减函数可以有多种形式，⼀个常⽤的衰减函数是
，，，，
其中.a是⼀个常数，可以取为0.5~0.99，它的取值决定了降温的过程。⼩的衰减量可能导致算法进程迭代次数的增加，从⽽使算法进程接受更多的变换，访问更多的邻域，搜索更⼤范围的解空间，返回更好的最终解。同时由于在
值上已经达到准平衡，则在
时只需少量的变换就可达到准平衡。这样就可选取较短长度的Markov链来减少算法时间。
(3) Markov链长度
Markov链长度的选取原则是：在控制参数Ｔ的衰减函数已选定的前提下，
应能使在控制参数Ｔ的每⼀取值上达到准平衡。从经验上来说，对简单的情况可以令
=100n，n为问题规模。
算法停⽌准则：对Metropolis准则中的接受函数
分析可知，在Ｔ⽐较⼤的⾼温情况下，指数上的分母⽐较⼤，⽽这是⼀个负指数，所以整个接受函数可能会趋于1，即⽐当前解x，更差的新解⼯，也可能被接受，因此就有可能跳出局部极⼩⽽进⾏⼴域搜索，去搜索解空间的其他区域；⽽随着冷却的进⾏，T 减⼩到⼀个⽐较⼩的值时，接受函数分母⼩了，整体也⼩了，即难以接受⽐当前解更差的解，也就是不太容易跳出当前的区域。如果在⾼温时，已经进⾏了充分的⼴域搜索，到了可能存在最好解的区域，⽽在低温再进⾏⾜够的局部搜索，则可能最终到全局最优了。因此，⼀般T，应设为⼀个⾜够⼩的正数，⽐如0.01~5，但这只是⼀个粗糙的经验，更精细的设置及其他的终⽌准则可以查阅⽂献。Python实现
函数：
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 # 提取最终退⽕解
国家税务总局公告2017年第45号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
《matlab在数学建模中的应⽤》
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议