模拟退火

当对象数量变得庞大时，某些优化问题会变得难以使用组合方法处理。一个典型的例子是旅行推销员问题，它属于 NP-完全 问题类。 对于这些问题，有一种非常有效的实用算法，称为模拟退火（之所以这样命名，是因为它模仿了金属中错位原子在加热然后缓慢冷却时所经历的过程）。虽然这种技术不太可能找到最优解，但即使在存在噪声数据的情况下，它通常也能找到非常好的解。

旅行推销员问题可以用作模拟退火的应用示例。在这个问题中，推销员必须访问大量城市，同时最大限度地减少旅行的总里程。如果推销员从随机行程开始，他可以成对交换城市访问的顺序，希望每次交换都能减少里程。这种方法的困难在于，虽然它可以快速找到局部最小值，但它无法从那里到达全局最小值。

模拟退火通过引入两个技巧改进了这种策略。第一个是所谓的“Metropolis 算法”（Metropolis et al. 1953），其中一些不会降低里程的交换被接受，因为它们有助于求解器“探索”更多可能的解空间。 允许使用以下标准接受此类“坏”交换：

其中 是交换所暗示的距离变化（“好”交换为负；“坏”交换为正）， 是“合成温度”， 是区间 中的随机数。 被称为“成本函数”，对应于金属退火情况下的自由能（在这种情况下，温度参数实际上是 ，其中 是玻尔兹曼常数， 是物理温度，单位为开尔文绝对温标）。如果 很大，则会接受许多“坏”交换，并且可以访问大部分解空间。 要交换的对象通常是随机选择的，尽管可以使用更复杂的技术。

第二个技巧再次类似于金属的退火，是降低“温度”。在进行多次交换并观察到成本函数仅缓慢下降后，人们会降低温度，从而限制允许的“坏”交换的大小。 在将温度多次降低到较低值后，人们可以“淬火”该过程，仅接受“好”交换，以便找到成本函数的局部最小值。 有各种“退火计划”用于降低温度，但结果通常对细节不太敏感。

还有另一种更快的策略，称为阈值接受（Dueck 和 Scheuer 1990）。 在这种策略中，所有好的交换都被接受，任何使成本函数升高幅度小于固定阈值的坏交换也被接受。 然后定期降低阈值，就像退火中降低温度一样。 这消除了玻尔兹曼标准中的求幂和随机数生成。 因此，这种方法在计算机模拟中可以更快。 模拟退火实现为NMinimize[f, vars,Method -> "SimulatedAnnealing"].