1. 概述模拟退火算法由 Scott Kirkpatrick、George Gelatt 和 Mario Vecchi 于 1983 年开发。在研究高温下液体和固体的性质时，发现金属转变为液态，颗粒随机分布，而能量最小的状态是在初始温度足够高、冷却时间足够长的条件下实现的。如果不满足此条件，那么材料将发现自身处于具有非最小能量的亚稳态 — 这称为硬化，它是由材料的急剧冷却造成。在这种情况下，原子结构不具备对称性（各向异性状态，或晶格内材料的性质不均匀）。在缓慢的退火过程中，材料也变成固态，但具有组织化的原子和对称性，故此拟议使用该过程开发一种优化算法，该算法可以在复杂问题中找到全局最优。该算法也被提议作为解决组合优化问题的方法。
因此，该算法的主要思路是基于金属退火过程的数学模拟。在退火过程中，为了均匀分布其内能，将金属加热到高温后缓慢冷却，令金属分子移动，并有序进入更稳定的状态，同时释放金属中的内应力，去除晶间缺陷。术语“退火”也与热力学自由能有关，热力学自由能是材料的一个属性，取决于其状态。模拟退火优化算法使用类似的过程。该算法应用了类似于加热和冷却材料的操作。该算法从初始解开始工作，该初始解可以是随机的，也可从以前的迭代中获得。然后，它应用操作来更改解的状态（可以是随机的、或受控的），从而获得新状态，即使它比当前状态更差。做出更差决策的概率由“冷却”函数决定，该函数降低了随着时间的推移做出更差决策的概率，允许算法暂时“跳出”局部最优值，并在搜索空间的其它地方寻找更好的解。模拟退火算法基于三个主要概念：
随机性的应用：该算法使用随机操作来改变解的状态，并选择下一个状态。这允许探索搜索空间的不同区域，并避免陷入局部最优状态。
接受更糟糕的决策：SA 是极少数算法之一，它更喜欢具有一定概率的更糟糕决策，而不是更好的决策。
逐渐降低做出更糟糕决策的可能性：该算法使用“冷却”过程，随着时间的推移降低做出更糟糕决策的可能性。这令赫兹量化交易软件能够首先更广泛地探索搜索空间，然后专注于改进解，平衡搜索空间的探索和拓展。
模拟退火优化算法是元启发式中所用的方法之一，它描述了一类用于求解复杂优化问题的算法。它们基于启发式方法，允许在搜索空间中搜索近似解，而无需完全搜索所有可能的选项。随机性是元启发式的关键要素之一，它令它们能够发现新的和有前途的解区域。该算法属于一组称为“随机优化方法”的算法。SA 算法有其缺点，赫兹量化交易软件将在下面讨论。其它基于 SA 的算法也有所开发，例如自适应模拟退火（ASA），和量子归一化（QN），也称为量子退火（QA）。
2. 算法作者提议的模拟退火算法的基本版本非常简单，但如果没有直观地显示温度变化过程的图形，和做出最坏决策的概率图，就不容易想象该算法是如何工作的。赫兹量化交易软件一步一步地弄清楚。该算法在一定的初始高温（外部参数）下开始工作，这对应于冶金中加热材料。高温意味着分子的高能量在不同能量状态（较低或较高）间移动。与金属中的这种高能运动过程类似，该系统可以按一定的概率做出更糟糕的决策。如果我们想象一个滑雪者从山顶上移动，那么当他发现自己所在是某个低地时，滑雪者可能会决定他已经到达了山脚下。为了确保这个决定是正确的，我们需要稍微调整我们的位置，并上升到一定的高度，以便以更快的速度冲下来。这就是以某种概率做出更糟糕决定的意义所在。为了跳出局部“陷阱”，开发了一种量子退火算法，该算法模拟了同时在两个地方的量子效应，其中推测它穿过隧道跳过“壁垒”，但尝试摆脱一些缺点，量子退火还有其它，特别是选择量子跃迁强度的问题。使用若干简单的方程来描述模拟退火。能量计算方程：E = f (x)换言之，E 表示个体当前状态的适应度函数值。能量变化计算方程：ΔE = E_new - E_old其中：
ΔE - 从当前状态过渡到新状态期间的能量变化（两次连续迭代时，适应度函数值的差值）
E_new - 新状态的能量值
E_old - 先前状态的能量值
计算做出更糟糕决策概率的公式：P = exp (-ΔE / T)其中：
P - 做出更糟糕决定的概率
T - 当前温度
从下图中可以看出，P 概率依赖性越高，ΔE 越高，概率越低。这意味着随着温度的降低，高能向下跃迁的概率比能量差值较小时向下跃迁得更快。换言之，算法在尝试摆脱“陷阱”时承担的风险越来越小，而只倾向于改进解。概率图如图例 1 所示，尽管该算法使用温度的非线性变化，但为了清楚起见，使用了温度的线性降低。
添加图片注释，不超过 140 字（可选）图例 1. 随着温度线性下降，能量变化的决策概率图变得更糟温度更新方程：Tnew = α * Tprev其中：
α - 冷却比。α 通常在 0.8 到 0.99 之间
Tnew - 新温度
Tprev - 以前的温度
在起始温度 T = 500 时，α = 0.99、0.8、0.5 和 0.1 的每次迭代时温度变化图如图例 2 所示。温度逐渐降低，这对应于材料的冷却。每次迭代时降低温度，会导致做出更糟糕决策的可能性降低，这相当于分子随着温度降低，而改变其能量状态的能力降低。
添加图片注释，不超过 140 字（可选）图例 2. α = 0.99、0.8、0.5 和 0.1 的温度变化图生成新系统状态的公式：x_new = GenerateNeighbor (x)其中：
x_new - 基于当前 x 状态生成的新状态
GenerateNeighbor(x) - 通过引入对当前状态具有均匀分布的随机变化，来生成新状态的函数
现在我们已经了解了模拟退火算法的所有理论基础，编写 SA 代码对我们来说并不难。我们可以按结构（S_Agent）的形式表示改变其能量状态的分子运动，该结构包含有关优化问题中个体的信息。字段和结构方法：
Init(int coords) - 方法初始化个体，并为 “c” 和 “cPrev” 数组分配内存大小为 “coords”。它还将 “f” 和 “fPrev” 的初始值设置为 “-DBL_MAX”（负无穷大）
c [] - “c” 数组表示个体在优化空间中的坐标
cPrev [] - “cPrev” 数组表示个体的先前坐标
f - 个体当前坐标的适应度函数值
fPrev - 个体的适应度函数的上一个值
//————————————————————————————————————————struct S_Agent{ void Init (int coords) { ArrayResize (c, coords); ArrayResize (cPrev, coords); f = -DBL_MAX; fPrev = -DBL_MAX; } double c []; //coordinates double cPrev []; //previous coordinates double f; //fitness double fPrev; //previous fitness};//————————————————————————————————————————我们来讲述一下 SA 算法类，并将其命名为 C_AO_SA。结果会非常简单，因为它不包含任何我们以前没有用到过的异常内容，除了特定的热变量和常数。类的字段和方法：
cB [] - 优化算法在当前迭代时找到的最佳坐标数组
fB - 最佳坐标的适应度函数值
a [] - 表示个体的数组。它用于存储有关优化问题中每个个体的信息。数组的每个元素都是 S_Agent 结构的一个实例
rangeMax [] - 用于判定每个个体坐标的搜索上边界，每个坐标的最大搜索范围值的数组
rangeMin [] - 每个坐标的最小搜索范围值数组，用于判定每个个体坐标的搜索下边界
rangeStep [] - 数组表示每个坐标的搜索步骤
Init(const int coordsP, const int popSizeP, const double tP, const double aP, const double dP) - 该方法初始化优化算法，接受参数：坐标数 “coordsP”、种群大小 “popSizeP”、初始温度 “tP”、温度降低比 “aP”、和扩散系数 “dP”。该方法初始化类和个体字段
Moving () - 该方法在优化期间移动个体，并使用该算法判定个体的新坐标
Revision () - 该方法根据个体的当前值，执行最佳坐标和适应度函数的修订和更新
SeInDiSp(double In, double InMin, double InMax, double Step) - 用于规范从 “InMin” 到 “InMax” 范围内的 “In” 值的私密方法，步长为 “Step”
RNDfromCI(double min, double max) - 在给定范围内从 “min” 到 “max” 生成随机数的私密方法
应该注意的是，原始 SA 版本中不存在 dP 扩散比。作者的思路是生成系统的新状态，并相应地在每个坐标从 “min” 到 “max” 的整个范围内生成一个新的个体坐标。这对应于接受退火的金属在整个“体积”中的分子混沌运动。我的实验表明，如果分子振动的范围仅限于以整个允许区间的一部分表示的某个区间，则结果会有所改善。这是扩散比参数的确切目标 - 限制分子可能混合的区域。为了获得与原始 SA 等效的结果，只需将参数设置为 1（默认为 0.2）。//————————————————————————————————————————class C_AO_SA{ //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Agent a []; //agent public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordsP, //coordinates number const int popSizeP, //population size const double tP, //temperature const double aP, //temperature reduction coefficient const double dP); //diffusion coefficient public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: double T; private: double α; private: double d; private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max);};//————————————————————————————————————————Init 函数将用作初始化方法，其初始化类的所有字段，并分配优化算法工作所需的数组大小。//————————————————————————————————————————void C_AO_SA::Init (const int coordsP, //coordinates number const int popSizeP, //population size const double tP, //temperature const double aP, //temperature reduction coefficient const double dP) //diffusion coefficient{ MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; revision = false; coords = coordsP; popSize = popSizeP; T = tP; α = aP; d = dP; ArrayResize (a, popSize); for (int i = 0; i < popSize; i++) a .Init (coords); ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords);}//————————————————————————————————————————编写 Moving 方法，以便在搜索空间中移动个体。在第一次迭代时，当算法刚刚启动时，变量 - “revision” 标志等于 “false”。有必要用位于均匀分布的 [min;max] 坐标范围内的初始值初始化种群个体。我们调用 SeInDiS 函数对获得的个体坐标值进行常规化，以便维护所需的移动步长。接下来，“revision” 标志设置为 “true”，指示需要在下一次迭代中应用模拟退火算法运算。如果这是原始的 SA，那么我们将执行我们在第一次迭代中所做的操作，即继续在给定范围内生成随机数，并在第二次和后续迭代中均匀分布。而在我们略微修正的版本中，我们将做同样的事情，但调整了值的范围，从而限制了分子在金属中的扩散相互作用区域，而运动是从分子在上一次迭代中的位置进行的。我们调用 SeInDiS 函数对获得的个体坐标值进行常规化，以便维护所需的移动步长。 |
微信扫一扫
