1700496672
1700496673
“错误风景”：描述了解决方案质量如何在不同的可能性之间变化
1700496674
1700496675
想想龙虾陷阱里的龙虾：可怜的动物，它并没有意识到离开笼子就意味着要回到笼子的中心，它需要到笼子中心才能出去。龙虾陷阱只不过是由线构成的局部最大值——一种致命的局部最大值。
1700496676
1700496677
在旅行计划一例中，幸运的是，局部最大值没有那么致命，但是它们具有相同的特点。即使我们找到了一个无法通过任何细小调整来改进的解决方案，我们仍然有可能遗漏了全局最大值。真正的最佳旅行路线可能需要对旅行方案进行彻底的修整：以不同的顺序来安排整个计划路线，例如，一路向西而不是向东。如果我们想继续寻求改进，我们可能需要暂时恶化我们的解决方案。随机性提供了一种策略（实际上有好几个策略）就是这么做的。
1700496678
1700496679
1700496680
1700496681
1700496683
算法之美：指导工作与生活的算法 局部最大值之外
1700496684
1700496685
其中一种方法就是用所谓的“抖动”来增大爬山算法。如果你看起来像是被卡住了，那就把它混合起来。做一些随机的小调整（即使它们的情况更糟），然后再回到爬山算法，看看你最后是不是在一个更高的山顶上。
1700496686
1700496687
另一种方法是，当我们达到一个局部最大值时，要完全地打乱我们的解决方案，然后从这个随机的新起点重新开始。这种算法被称为“随机重复爬山法”，或者，更鲜明的叫法是“猎枪爬山法”。他说：“当一个问题中遇到很多局部最大值时，这一策略被证明非常有效。例如，计算机科学家在尝试破译密码时使用了这种方法，因为有很多方法可以解密一条看起来很有用的消息，但最终无疾而终。在解密过程中，有一段看起来接近于合理的文本并不意味着你肯定是在正确的轨道上。因此，有时最好不要过于依赖一个既定的初始方向，而只是从头开始。
1700496688
1700496689
但还有第三种方法：当你用于某个问题时，不要变成全量的随机性，每次你做决定时都要使用一点儿随机性。这是由洛斯阿拉莫斯的团队开发出来的一种技术，它采用了蒙特卡罗法，被称为“梅特罗波利斯算法”。梅特罗波利斯算法就像爬山算法一样，都尝试在解决方案上进行不同的小规模调整，但它们有一个重要的不同之处：在任何一个给定的点上，它都有可能接受坏的调整和好的调整。
1700496690
1700496691
我们可以想象把这个应用到我们的假期计划问题上。之后，我们再次试图通过对不同城市位置上的调整来改变提出的解决方案。如果一个随机生成的结果会给我们旅行路线的调整带来改进，那么我们可以一直接受它，并继续在此基础上进行调整。但是，如果这种改变会让事情变得更糟，我们还是有机会将事情继续下去（尽管，越糟糕继续的机会就越小）。这样，我们就不会在任何地方停滞太长时间了：最终我们会尝试另一种解决方案，尽管它花费更大，同时有可能在路上提出一个新的更好的计划。
1700496692
1700496693
无论是抖动、随机重启，还是偶然的恶化，随机性对于避免局部最大值都是非常有用的。随机不仅仅是处理棘手优化问题的可行方法，在许多情况下，它是必不可少的。然而，有一些问题挥之不去。你应该使用多少随机性？何时使用？考虑到像梅特罗波利斯算法这样的策略可以无限地改变我们的行程，你怎么知道你已经完成了？对于正在研究最优化的科研人员来说，这些问题有一个惊人的确定答案将来自另一个领域。
1700496694
1700496695
1700496696
1700496697
1700496699
算法之美：指导工作与生活的算法 模拟退火算法
1700496700
1700496701
20世纪70年代末和80年代初，斯科特·柯克帕特里克认为自己是一名物理学家，而不是计算机科学家。柯克帕特里克对统计物理学尤其感兴趣，这门学科会用随机性来解释某些自然现象，例如与退火相关的物理学内容，以及材料在加热和冷却时改变状态的方式。退火过程中最有趣的特性或许是材料冷却的速度往往会对其内部结构产生巨大的影响。柯克帕特里克解释道：
1700496702
1700496703
从熔体中生长出一个晶体要经过细致的退火过程，首先要将物质熔化，然后缓慢地降低温度，并且要在冰点附近的温度上花费很长时间。如果这一步没有完成，该物质脱离平衡，那么产生的水晶将会有许多缺陷，或者该物质就可能成为一个玻璃，没有序结晶。
1700496704
1700496705
当时，柯克帕特里克在IBM公司工作，该公司当时最大、最棘手也是最神圣的问题之一就是如何在IBM制造的芯片上铺设电路。这个问题有许多可能的解决方案可供考虑，还有一些严格的约束。一般来说，最好是把组件放在一起，但不要太近，否则就没有空间了。当你移动任何东西时，你必须重新计算所有的线路在新的假设性布局中是如何运行的。
1700496706
1700496707
当时，这个过程是由IBM公司内部的一个神秘的专家型人物所引导的。正如柯克帕特里克回忆的那样：“在IBM公司，他是最优秀的人，他在芯片上挤进去更多电路……他用一种最神秘的方式来解释他在做什么。他不想把实际操作告诉你。”
1700496708
1700496709
柯克帕特里克的朋友和IBM的同事丹·盖拉特对这个问题很感兴趣，很快这个问题就吸引了具有敏锐洞察力的柯克帕特里克。“物理系统研究的方法是把它们加热，然后再冷却，让系统自行编组。”这样一来，似乎就把所有最优化问题都当成是一件很自然的事情，就像是你想要组织的自由度是小的原子，或者是自旋，或者是你有的任何东西。”
1700496710
1700496711
在物理学中，我们所说的“温度”实际上是一种速度——在分子尺度上的随机运动。柯克帕特里克的解释是，这是一种直接的类似于随机的抖动，可以添加到爬山算法中，有时可以使其从更好的解决方案回溯到较差的方案中。事实上，梅特罗波利斯算法最初在物理系统中是为了模拟随机行为而设计的（在这种情况下，是核爆炸）。那么，柯克帕特里克想知道的是，如果你像处理退火问题那样处理最优化问题，比如如果你“加热”，然后再慢慢地“冷却”会发生什么？
1700496712
1700496713
在上面的去10个城市度假的例子中，我们可以从“高温”开始，完全随机地选择我们出发的路线，从所有可能的解决办法中挑出一个，不管价格是多少。然后，当我们考虑对城市排列顺序进行调整时，我们可以用掷骰子的方法开始慢慢地“冷却”我们的搜索。一个高等级的变化总是有意义的，但是我们只会在骰子出现2点或者更多的时候，才会选择较低的变化。之后，如果骰子掷出3点或更多——然后是4点，之后是5点，我们只会通过提高价格来进一步降低这样的随机性。最终，我们主要都是在向上爬，只有当偶尔掷出6点在时才会做出低级别改变。最后，我们将只会向上爬坡，直到我们到达下一个局部最大值。
1700496714
1700496715
这种方法被称为模拟退火算法，这似乎是将物理学映射到问题解决上的一种有趣方法。但它有效吗？在更传统的最优化问题的研究人员中，对该算法最初的反应是，整个方法似乎有点儿太过隐晦了。柯克帕特里克说：“我无法让数学界人士相信，这些复杂的东西与温度，以及充满类比的东西都是真实的，因为数学家都被训练得不相信直觉。”
1700496716
1700496717
但是，对这种基于类比的方法的不信任很快便会消失：在IBM公司，柯克帕特里克和盖拉特使用模拟退火算法设计出比那些专家设计的更好的芯片布局。他们并没有对他们的秘密武器保持沉默，让自己成为神秘的权威人物。而是在《科学》杂志上发表了他们的方法，并将其公开给其他人，在接下来的几十里，这篇论文将被引用多达32000次。到目前为止，模拟退火算法仍然是最优化问题在该领域最具前景的处理方法之一。
1700496718
1700496719
1700496720
1700496721
[
上一页 ]
[ :1.700496672e+09 ]
[
下一页 ]