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
1700496723
算法之美：指导工作与生活的算法 随机性，进化和创造力
1700496724
1700496725
1943年，萨尔瓦多·卢里亚并不知道他的发现将会为他赢得诺贝尔奖，他以为只是去参加一个舞会。卢里亚是一名从墨索里尼统治下的意大利搬到美国的移民，他父亲之前生活在意大利，卢里亚是一名研究细菌如何从病毒中获得免疫的研究人员。当他在印第安纳大学附近的一个乡村俱乐部参加了一场教师聚会时，他的研究还远未达到他所想的程度。
1700496726
1700496727
他当时看着他的一个同事玩老虎机：
1700496728
1700496729
我不是一个赌徒，当我取笑一个赌徒不可避免会遭受损失时，他突然中了头奖（大约3美元）他给了我一个鄙视的眼神，然后走开了。就在那时，我开始思考老虎机真正的数字命理学：在这样做的时候，我突然意识到老虎机和细菌的突变有一些可以相互借鉴的地方。
1700496730
1700496731
20世纪40年代，人们还不知道细菌对病毒的耐药性（以及对抗生素的耐药性）是如何产生的。它们是在细菌中对病毒的反应，还是仅仅是正在发生的突变偶尔产生的耐药性？似乎没有办法设计出一种可以提供决定性答案的实验，直到卢里亚看到那台老虎机，并突然顿悟。卢里亚意识到，如果他培育了几代不同的细菌，然后把最后一代细菌暴露在病毒中，就会发生两种截然不同的事情。如果耐药性是对病毒的反应，他认为在所有细菌培养基中，无论它是第几代，几乎都有相同数量的耐药细菌出现。另一方面，如果耐药性来自偶然突变，他可能会看到一些更不平均的东西（就像老虎机的奖金一样）。即大多数代系的细菌都不会显示出耐药性，一些代系中可能会有一个“孙”代的培养基出现突变，产生耐药性。在极少数情况下，如果在“家族谱系图”上有几代细菌都发生了适当的突变，那将会有一个“大奖”出现——所有的“孙辈”细菌都将产生耐药性。卢里亚立刻离开了舞会，并开始实验。
1700496732
1700496733
在经历了几天的紧张、不安的等待后，卢里亚回到实验室检查他的菌落。大奖出现了。
1700496734
1700496735
卢里亚的发现是关于机会的作用：关于随机与偶然突变是如何产生病毒的耐药性的。但这至少在某种程度上，也是由于机会发挥的作用。在正确的时间，正确的地点，卢里亚看到的老虎机触发了一个新的想法。关于发现的故事往往也有类似的时刻：牛顿的苹果（可能是杜撰的），阿基米德在浴缸里说“我发现了”，以及被忽视的培养青霉素的培养皿。的确，这是一个普遍现象，因此有一个新词就被发明出来：1754年，霍勒斯·沃波尔基于《锡兰三位王子》（锡兰是斯里兰卡古时的名字）的童话冒险故事，编了一个新词“意外发现”（serendipity），故事中的王子们“总是能意外地、睿智地发现一些他们不想追求的东西”。
1700496736
1700496737
随机性的这种双重作用是生物学的一个重要组成部分，也是主要发现之一，反复吸引了那些想要解释人类创造力的心理学家的注意。威廉·詹姆斯提出了这个想法的早期实例。1880年，詹姆斯被任命为哈佛大学的心理学助理教授，并在10年后出版了他在心理学上的权威理论。他在《大西洋月刊》上发表了一篇文章《伟人，伟大的思想和环境》。这篇文章以他的论点开篇：
1700496738
1700496739
我的知识从未注意到，有一种非凡的平行，一方面存在于社会进化的事实和种族的精神发展之间，另一方面存在于如达尔文先生所阐述的，社会进化与动物的进化之间。
1700496740
1700496741
在詹姆斯写作的时候，“动物进化”这个概念仍然是十分新鲜的（在1859年《物种起源》出版和达尔文本人还活着的时候）。詹姆斯讨论了进化思想如何应用于人类社会的不同方面，并在文章的最后转向了思想的进化：
1700496742
[
上一页 ]
[ :1.700496693e+09 ]
[
下一页 ]