模拟退火的工作原理

本页采用了机器翻译。点击此处可查看英文原文。

算法概述

模拟退火算法执行以下步骤：

该算法生成一个随机试验点。该算法根据当前温度的尺度，通过概率分布来选择试验点与当前点的距离。您可以使用 AnnealingFcn 选项将试验点距离分布设置为函数。选择：
- @annealingfast（默认）-步长等于当前温度，方向均匀随机。
- @annealingboltz - 步长等于温度的平方根，方向均匀随机。
- @myfun - 自定义退火算法，myfun。有关自定义退火函数语法，请参阅算法设置。
生成试验点后，算法会根据需要对其进行移动，以保持在边界内。该算法将试验点的每个不可行分量移动到在违反的边界和上一次迭代的（可行）值之间均匀随机选择的值。
该算法确定新的点是否比当前点更好或更差。如果新点比当前点更好，它就成为下一个点。如果新点比当前点差，算法仍然可以将其作为下一个点。该算法根据接受函数来接受较差的点。使用 AcceptanceFcn 选项选择接受函数。选择：
- @acceptancesa（默认）-模拟退火接受函数。接受的概率是
  $\frac{1}{1 + \exp (\frac{Δ}{\max (T)})},$
  其中
  Δ = 新目标 - 旧目标。
  T₀ =分量的初始温度 i
  T = 当前温度。
  由于 Δ 和 T 都为正数，因此接受的概率介于 0 和 1/2 之间。温度越小，接受概率就越小。此外，Δ 越大，接受概率就越小。
- @myfun - 自定义接受函数，myfun。有关自定义接受函数语法，请参阅算法设置。
该算法系统地降低温度，存储迄今为止发现的最佳点。TemperatureFcn 选项指定算法用于更新温度的函数。让 k 表示退火参数。（退火参数与迭代次数相同，直到重新退火。）选项:
- @temperatureexp (默认) - T = T₀ * 0.95^k。
- @temperaturefast — T = T₀ / k.
- @temperatureboltz — T = T₀ / log(k).
- @myfun - 自定义温度函数，myfun。有关自定义温度函数语法，请参阅温度选项。
simulannealbnd 在接受 ReannealInterval 点后重新退火。重新退火将退火参数设置为低于迭代次数的值，从而提高每个维度的温度。退火参数取决于目标函数在每个维度上的估计梯度的值。基本公式为
$k_{i} = \log (\frac{T_{0}}{T_{i}} \frac{\max_{j} (s_{j})}{s_{i}}),$
其中
k_i =分量 i 的退火参数。
T₀ =分量 i 的初始温度。
T_i =分量 i 的当前温度。
s_i = 方向 i 上目标的梯度乘以方向 i 上的边界差。
simulannealbnd 保护退火参数值免受 Inf 和其他不正确值的影响。
当目标函数的平均变化相对于 FunctionTolerance 较小，或者达到任何其他停止条件时，算法停止。请参阅算法的停止条件。

有关该算法的更多信息，请参阅 Ingber [1]。

算法的停止条件

模拟退火算法使用以下条件来确定何时停止：

FunctionTolerance - 算法运行直到 StallIterLim 次迭代中目标函数值的平均变化小于 FunctionTolerance 的值。默认值为 1e-6。
MaxIterations - 当迭代次数超过此最大迭代次数时，算法停止。您可以将最大迭代次数指定为正整数或 Inf。默认值为 Inf。
MaxFunctionEvaluations 指定目标函数的最大评估次数。如果函数计算的次数超过 MaxFunctionEvaluations 的值，则算法停止。默认值为 3000*numberofvariables。
MaxTime 指定算法在停止之前运行的最大时间（以秒为单位）。默认值为 Inf。
ObjectiveLimit - 当最佳目标函数值小于 ObjectiveLimit 的值时，算法停止。默认值为 -Inf。

参考资料

[1] Ingber, L. Adaptive simulated annealing (ASA): Lessons learned. Invited paper to a special issue of the Polish Journal Control and Cybernetics on “Simulated Annealing Applied to Combinatorial Optimization.” 1995. Available from https://www.ingber.com/asa96_lessons.ps.gz

另请参阅

simulannealbnd

模拟退火的工作原理

算法概述

算法的停止条件

参考资料

另请参阅

相关主题

WeChat