模拟退火算?/p>
模拟退火算法是一种通用的随机搜索算法,是局部搜
索算法的扩展。它的思想是再
1953
年由
metropolis
提出
来的,到
1983
年由
kirkpatrick
等人成功地应用在组合
优化问题中?/p>
模拟退火算法来源于固体退火原理,将固体加温至?/p>
分高,再让其徐徐冷却,加温时,固体内部粒子随温升?/p>
为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在?/p>
个温度都达到平衡态,最后在常温时达到基态,内能减为
最小。根?/p>
Metropolis
准则,粒子在温度
T
时趋于平?/p>
的概率为
e-
ΔE/(kT
)
,其?/p>
E
为温?/p>
T
时的内能,ΔE
?/p>
其改变量?/p>
k
?/p>
Boltzmann
常数。用固体退火模拟组合优
化问题,将内?/p>
E
模拟为目标函数?/p>
f
,温?/p>
T
演化成控
制参?/p>
t
,即得到解组合优化问题的模拟退火算法:由初
始解
i
和控制参数初?/p>
t
开始,对当前解重复“产生新?/p>
→计算目标函数差→接受或舍弃”的迭代,并逐步衰减
t
值,算法终止时的当前解即为所得近似最优解,这是基?/p>
蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过
程由冷却进度?/p>
(Cooling Schedule)
控制,包括控制参?/p>
的初?/p>
t
及其衰减因子
Δt、每?/p>
t
值时的迭代次?/p>
L
?/p>
停止条件
S
?/p>
模拟退火算法新解的产生和接受可分为如下四个?/p>
骤:
第一步是由一个产生函数从当前解产生一个位于解?/p>
间的新解;为便于后续的计算和接受,减少算法耗时,?/p>
常选择由当前新解经过简单地变换即可产生新解的方法,
如对构成新解的全部或部分元素进行置换、互换等,注?/p>
到产生新解的变换方法决定了当前新解的邻域结构,因?/p>
对冷却进度表的选取有一定的影响?/p>
第二步是计算与新解所对应的目标函数差。因为目?/p>
函数差仅由变换部分产生,所以目标函数差的计算最好按
增量计算。事实表明,对大多数应用而言,这是计算目?/p>
函数差的最快方法?/p>
第三步是判断新解是否被接?/p>
,
判断的依据是一个接
受准则,最常用的接受准则是
Metropo1is
准则
:
?
Δt?lt;0
则接?/p>
S′作为新的当前解
S
,否则以概率
exp(-
Δt?T)接受
S′作为新的当前解
S
?/p>