算法|最硬核的决策算法，灵感竟来自于金属冷却 it芯片

文章图片

文章图片

假设你正在创办一家制造和销售的企业，你必须要做出一些重要的决定，比如你应该把工厂、仓库和配送中心放在哪里？这听起来可能不是一个令人费解的问题，但它实际上非常复杂。显然，你会希望这些位置尽可能贴近客户和供应商，以减低运输成本。此外，还需要维护成本、电力能源和租金等一系列因素。
这种情况称为约束优化问题，需要寻找各种竞争因素的最佳平衡，同时保证解决方案是可实施的。约束优化并没有得到太多关注，你以前可能从未听说过，但它是几乎所有人类努力背后的隐藏架构。解决此类问题最流行的方法之一，是从一个不寻常的来源获得的灵感：金属冷却的方式。

当我们谈到决策时，我们首先想到的不是冶金，这也不是计算机科学家的第一个想法。他们最初设计了许多有效的算法来找到约束优化问题的解决方案，当问题具有良好的数学形式时，这些方法效果最好。但当问题涉及复杂的大量变量时，即使是计算机也需要很长时间的计算才能找到答案。所以最终，研究人员在自然界中寻找灵感，找到了不是最完美但非常接近的解决方案。
1983年，三位研究人员在优化和冷却金属之间进行了类比。当金属被加热然后缓慢冷却时，它的原子倾向于以尽可能低的能量进入排列。换句话说，原子的排列自然得到优化。这在金属加工中很方便，因为如果你想把一些金属加工成某种形状，原子都整齐地排列在晶体结构中是最容易的。

【算法|最硬核的决策算法，灵感竟来自于金属冷却】通常情况下金属会存在缺陷，如原子错位和晶体不同部位之间的断层线，所以工人使用一种称为退火的技术：先把金属加热到一定的温度，然后保持足够时间慢慢冷却。当金属温度很高时，它的原子会剧烈运动，但是随着冷却的发生，它们的运动会越来越小，越来越不可能从低能量位置跳到高能量位置。因此，它们自然而然处于能量最低的配置中，即几乎没有缺陷的晶体。因为冷却速度缓慢，所以原子更可能在“冻结”前找到低能量位置。

对于研究人员来说，这个自然过程不仅仅是关于金属加工的简单事实，这也是优化算法的灵感来源。换句话说，计算机可以遵循类似的过程来解决复杂的约束优化问题，他们把这一方法称为模拟退火。就像物理退火通过不同的原子排列一样，该算法通过不同的解决方案来解决受约束的优化问题。这比较听起来不直观，但它的工作方式如下。
在前面创办企业的示例中，我们首先会生成一些随机选择的产品、设施和位置等，然后我们将继续进行随机更改。最初，我们允许一些利润率低的更改，例如将仓库从工厂旁移开。这是因为在这一点上，允许有害的变化就像对金属加热，让原子进入一个临时的能量更高的状态。然而，随着时间的推移，算法变得越来越不愿意接受不会改善结果的变化，就像随着金属冷却，原子越来越难以到达高能量状态一样。最终，我们将得到一个接近完美的解决方案。

模拟退火非常流行，它已被用于超过百万份研究论文和实际项目中。假设你是一名分子生物学家，试图弄清楚一种蛋白质的结构。你希望你的结构尽可能匹配你的实验数据，但它受到结构必须在物理上是可能的事实的限制，这时使用模拟退火是一个好的选择。此外，飞机航线规划、大学考试安排、机器人从a点到b点的最佳路线等都可以使用模拟退火算法。