读算法简史：从美索不达米亚到人工智能时代08组合优化

1. 组合优化

1.1. 蛮力搜索算法会尝试所有可能的组合并从中选择最好的那个
1.2. 旅行商问题是众多组合优化(combinatorial optimization)问题中的一个，它要求许多固定元素以可能的最佳方式进行组合

• 1.2.1. 固定元素可以有无数种排列方式
  
• 1.2.2. 目标是找到唯一的、最好的那个组合
  
• 1.2.3. 在旅行商问题中，固定元素是城市到城市之间的距离，而“可能的最佳方式”是最短的路线
  

1.3. 路线图并不是组合优化问题的唯一体现
1.4. 匹配问题寻求以最佳方式配对对象

• 1.4.1. 一个典型的匹配问题是将有希望的大学申请人与可供申请的课程进行配对
  

2. 艾兹格·迪杰斯特拉

2.1. Edsger Dijkstra

• 2.1.1. 迪杰斯特拉是荷兰的第一位专业程序员
  

2.2. 1951年，在英格兰完成一项编程课程后，他在阿姆斯特丹的数学中心(Mathematical Centre)获得了一份计算机程序员的兼职工作

• 2.2.1. 迪杰斯特拉在数学中心做兼职的同时，也在莱顿大学学习数学和物理
  
• 2.2.2. 3年后，他觉得自己无法同时兼顾编程和物理
  

2.3. 1952年，艾兹格·迪杰斯特拉（Edsger Dijkstra）提出了一个快速算法，解出了世界上最常见的组合优化问题

• 2.3.1. 迪杰斯特拉算法类似于玩棋盘游戏
  
• 2.3.2. 它通过在路线图上的城市之间移动一个标牌来找到最短的路线
  
• 2.3.3. 把标牌放置在起点城市上
  
  
  
  • 2.3.3.1. 在旁边写下城市的名字和标牌走过的距离，距离此时为零
    
  
  
• 2.3.4. 考虑每一个直接相连的城市
  
  
  
  • 2.3.4.1. 计算出从起点到这些城市的距离
    

    2.3.4.1.1. 将标牌旁边的数字加上从标牌所在城市到直接连接的城市的距离
    

    
    
  • 2.3.4.2. 如果一个城市已经被标注过，并且标注的距离小于这个计算值，那么现有标注值就保持不变
    
  • 2.3.4.3. 如果新计算的值小于已经标注的距离，则替换掉原标注值
    

    2.3.4.3.1. 把这个新的距离和标牌走过的路线一起记录下来
    

    
    
  
  
• 2.3.5. 标牌旁边的城市的列表就是所走的路线，最末位的是新城市的名字
  
• 2.3.6. 当对所有直接连接的城市执行了这些步骤后，将标牌移到标注距离数值最小且尚未访问的城市
  
• 2.3.7. 重复进行，直到标牌到达期望的目的地
  
• 2.3.8. 用时间代替距离可以让迪杰斯特拉算法找到最快的路线，而不是最短的路线
  

2.4. 如今，他的算法运行在数十亿电子设备中
2.5. 迪杰斯特拉算法之所以重要的原因

• 2.5.1. 它保证能找到最短的路线
  
• 2.5.2. 算法速度很快
  
  
  
  • 2.5.2.1. 精简了繁杂的搜索，避开了糟糕的解，把算力集中在好的解上
    
  
  
• 2.5.3. 寻路问题无处不在
  
  
  
  • 2.5.3.1. 世界上的每一个人和每一辆车都必须导航
    
  
  

2.6. 他发明了分布式计算(distributed computing)的算法

• 2.6.1. 多台计算机协同运行解决计算复杂度很高的问题
  

2.7. 1972年的图灵奖颁给了迪杰斯特拉
3. 机器人沙基

3.1. Shakey the Robot

• 3.1.1. 机器人沙基是第一个具有推理能力的通用移动机器人
  

3.2. 1968年，加州斯坦福研究院(Stanford Research Institute，SRI)的三名研究人员强化了这个算法

• 3.2.1. 这些研究人员是“机器人沙基”(Shakey the Robot)团队的成员
  

3.3. 开发团队发现了迪杰斯特拉算法的一个低效之处

• 3.3.1. 该算法偶尔会浪费时间将标牌转移到远离最终目的地的城市
  
  
  
  • 3.3.1.1. 这些城市看起来很有前景，因为它们与被标牌标记的城市有更短的连接
    
  • 3.3.1.2. 它们把算法引向了错误的方向，这些城市最终也会被算法剔除
    
  
  

3.4. 彼得·哈特(Peter Hart)、尼尔斯·尼尔森(Nils Nilsson)和伯特伦·拉斐尔(Bertram Raphael)提出了A*（A星）算法

• 3.4.1. A*使用了一个修改后的距离度量
  
• 3.4.2. 在迪杰斯特拉的原始算法中，度量是已经移动的距离
  
• 3.4.3. 在A*中，度量是到目前为止所走的距离加上从当前城市到最终目的地的直线距离
  
• 3.4.4. 迪杰斯特拉算法只考虑到目前为止的路线，而A*还估计了从起点到终点的完整路线的长度
  
• 3.4.5. A*不倾向于让标牌去那些把标牌从目的地带偏的城市
  

3.5. 如今，从卫星导航到智能手机，地球上所有的导航应用程序都在使用A*算法的变体

• 3.5.1. 为了提高准确性，道路交叉路口取代了城市，但原则保持不变
  
• 3.5.2. 迪杰斯特拉算法的衍生算法现在被用于通过互联网路由数据
  

4. 盖尔和沙普利

4.1. 关于配对的开创性论文是由大卫·盖尔(David Gale)和劳埃德·沙普利(Lloyd Shapley)在1962年发表的

• 4.1.1. 两人在新泽西州的普林斯顿大学建立了友谊，他们都在那里攻读数学博士学位
  
• 4.1.2. 从普林斯顿大学毕业后，盖尔加入了位于罗得岛的布朗大学，而沙普利则去了兰德公司
  
• 4.1.3. 盖尔和沙普利的论文解决了一个由来已久的问题，即为单身人士匹配婚恋对象
  

4.2. “稳定婚姻问题”(Stable Marriage Problem)寻求的是让男性和女性配对结婚

• 4.2.1. 女性参与者根据自己的喜好对所有男性进行排名（第1名、第2名、第3名等）
  
• 4.2.2. 男性也对女性进行排名
  
• 4.2.3. 问题的目标是让参与者以一种让婚姻稳定的方式配对
  
• 4.2.4. 如果不存在一男一女对彼此的偏爱超过他们各自对自己配偶的偏爱，那么他们与其配偶的组合就被认为是稳定的
  

4.3. 在论文中，盖尔和沙普利使用稳定婚姻问题作为现实世界中一系列双向(two-way)匹配问题的代表

• 4.3.1. “双向”指的是双方都有自己的偏好，而不仅仅是一方有
  
• 4.3.2. 盖尔-沙普利算法迅速成为实际上的双向匹配方法
  
• 4.3.3. 该算法至今仍被广泛应用于各种实践场景中，包括为危重病人匹配器官捐赠者
  

4.4. 盖尔-沙普利算法在连续的多个回合中匹配男性和女性

• 4.4.1. 在每一轮匹配中，所有单身男性都要求婚一次
  
• 4.4.2. 作为一种安排约会的方法，盖尔-沙普利算法是残酷的
  
• 4.4.3. 人类在寻找伴侣时是否真的会从直觉上遵循类似于盖尔-沙普利算法的思想过程
  
  
  
  • 4.4.3.1. 事实上，人的偏好会随着时间的推移而演变
    
  • 4.4.3.2. 分手的情感代价意味着个人不愿做出重大改变
    
  
  

4.5. 沙普利和阿尔文·罗斯(Alvin Roth)因为他们在博弈论(game theory)领域的研究于2012年被授予诺贝尔经济学奖

• 4.5.1. 博弈论是数学的一个分支，研究聪明决策者之间的竞争与合作
  
• 4.5.2. 沙普利被广泛认为是一位伟大的理论家，他为罗斯关于市场如何运作的实践性研究奠定了基础
  
• 4.5.3. 他们的诺贝尔奖授奖词强调的贡献之一是盖尔-沙普利算法
  
  
  
  • 4.5.3.1. 盖尔于2008年去世，因此无法获得诺贝尔奖
    
  
  

4.6. 沙普利于2016年去世，享年92岁
5. 波士顿池算法

5.1. Boston Pool
5.2. 美国住院医师匹配计划(National Residency Matching Program，NRMP)每年都会开展世界上规模最大的匹配活动之一

• 5.2.1. 将医学院毕业生与美国各地医院的实习机会进行配对
  

5.3. 1952年创立时，NRMP采用了之前一家票据清算所的匹配算法

• 5.3.1. 波士顿池(Boston Pool)算法被NRMP一用就是40年
  

5.4. 20世纪70年代，人们发现波士顿池算法实际上和独立开发的盖尔-沙普利算法是一样的东西

• 5.4.1. 这对著名的数学家-经济学家组合做出这项发明比不知名的波士顿池团队晚了超过10年，这相当令人尴尬
  
• 5.4.2. 前者的学术论文包含了正式的证明
  
• 5.4.3. 波士顿池算法是专门针对票据清算写的
  

5.5. 20世纪90年代，著名经济学家、数学家阿尔文·罗斯(Alvin Roth)参与了对NRMP匹配算法的改进

• 5.5.1. 随着时代的发展，罗斯的新方法允许从医的夫妻寻求同城工作
  
• 5.5.2. 还力求防止不怀好意的申请者利用系统为自己谋利
  
• 5.5.3. 与波士顿池算法不同，罗斯的技术依赖于单向匹配，即只考虑申请人的偏好
  

6. 约翰·霍兰

6.1. John Holland
6.2. 1929年，霍兰出生于印第安纳州的韦恩堡
6.3. 在MIT，他为旋风(Whirlwind)计算机编写了一个程序

• 6.3.1. 旋风计算机由美国海军和空军资助，是第一台采用屏幕显示的实时计算机
  

6.4. 霍兰的博士导师是亚瑟·伯克斯，他在1946年向媒体演示了ENIAC
6.5. 在大学图书馆浏览图书时，霍兰偶然发现了罗纳德·费希尔(Ronald Fisher)1930年出版的一本老书——《自然选择的遗传学理论》(The Genetical Theory of Natural Selection)

• 6.5.1. 1995年霍兰在科普期刊《科学美国人》(Scientific American)上发表了一篇关于遗传算法(genetic algorithm)的文章
  
• 6.5.2. 同年，他的书的第二版也出版了
  
• 6.5.3. 最终，遗传算法破圈进入计算研究的主流
  
• 6.5.4. 霍兰这部长期被忽视的著作现在已经被6万多本书和科学论文引用（作为正式的参考文献）​
  
  
  
  • 6.5.4.1. 以学术标准衡量，这个被引次数是巨大的成功
    
  
  

6.6. 20世纪60年代，约翰·霍兰（John Holland）采用了一种激进的方法来解决组合优化问题

• 6.6.1. 他的算法有40亿年的历史
  

6.7. 1967年，霍兰被任命为密歇根大学计算机科学与工程学教授

• 6.7.1. 除了发明遗传算法外，他还对复杂性和混沌理论做出了重大贡献
  
• 6.7.2. 他还成了心理学教授
  

6.8. 自然演化通过3种机制使物种适应其环境

• 6.8.1. 选择(selection)
  
  
  
  • 6.8.1.1. 选择指的是具有有利特征的个体更有可能存活到成年并繁殖后代
    
  
  
• 6.8.2. 遗传(inheritance)
  
  
  
  • 6.8.2.1. 遗传是指子代表现出与其父母相似的生理特征的倾向
    
  • 6.8.2.2. 幸存者的后代往往具有相同的有利特征
    
  
  
• 6.8.3. 经过许多代繁衍后，选择和遗传意味着一个种群将倾向于拥有更多带有利于生存和繁殖特征的个体
  
• 6.8.4. 突变(mutation)
  
  
  
  • 6.8.4.1. 突变是遗传给子代的遗传物质发生随机变化的现象
    
  • 6.8.4.2. 根据染色体受到影响的部分的差异，突变可能对生命体没有影响，可能影响有限，也可能造成极端的改变
    
  • 6.8.4.3. 突变就像一副牌中的王牌
    

    6.8.4.3.1. 大多数情况下，它对种群没有影响
    

    6.8.4.3.2. 有的时候，它会为某种极为有利的改变埋下种子
    

    
    
  
  
• 6.8.5. 这个过程作用于生活在野外环境的物种
  

6.9. 霍兰认为人工演化可以用来解决组合优化问题

• 6.9.1. 可能的解可以被视为群体中的个体
  
• 6.9.2. 从遗传学得到启示，提出每个解都可以用一组字母来表示
  
• 6.9.3. 为了解决旅行商问题，路线可以用城市名字的第一个字母来表示：BFHM
  
  
  
  • 6.9.3.1. 认为这个序列类似于生命体的染色体（或者说DNA）
    
  
  
• 6.9.4. 霍兰的遗传算法作用于这些“人工染色体”(artifi cial chromosome)组成的人工染色体池
  
• 6.9.5. 经过许多代后，这3种机制的协同作用提高了优良解在群体中的占比
  
  
  
  • 6.9.5.1. 选择引导着算法去寻找更好的解
    
  • 6.9.5.2. 遗传以意想不到的方式糅合了有希望的答案，从而产生新的候选解
    
  • 6.9.5.3. 突变则提高了群体的多样性，开辟了新的可能性
    
  
  

6.10. 霍兰的算法

• 6.10.1. 随机产生一群染色体
  
• 6.10.2. 重复以下步骤
  
  
  
  • 6.10.2.1. 评估每条染色体的性能
    
  • 6.10.2.2. 弃去性能最差的染色体
    
  • 6.10.2.3. 随机配对存活的染色体
    
  • 6.10.2.4. 每对染色体交配产生两个子代染色体
    
  • 6.10.2.5. 把子代染色体添加到群体中
    
  • 6.10.2.6. 随机改变一小部分染色体
    
  • 6.10.2.7. 在达到指定的代数之后，停止重复
    
  
  
• 6.10.3. 输出表现最佳的染色体
  

6.11. 霍兰利用染色体来控制模拟商品市场的计算机程序的行为

• 6.11.1. 他所利用的染色体逐渐发展到了制造投机泡沫和金融危机的地步，尽管最初它们并不是被编程来干这些的
  

6.12. 约翰的独特之处在于，他从演化生物学中汲取灵感来改善计算机科学中的搜索和优化，然后利用他在计算机科学中的发现让我们重新思考演化动力学

• 6.12.1. 能在两种学科阵地之间进行这种严谨的转换，是深邃思想的一个特征
  

6.13. 虽然遗传算法仍然很受欢迎，但它们通常不是解决给定优化问题的最高效方法

• 6.13.1. 当我们并不知道如何将好的解组合在一起时，遗传算法的工作效率最高
  
• 6.13.2. 遗传算法在随机置换的驱动下盲目地在设计空间中探索
  
• 6.13.3. 由于遗传算法易于编程，因此研究人员通常就让计算机用遗传算法来完成工作，而不是花费宝贵的时间发明一种新的快速搜索算法
  

6.14. 2015年，霍兰去世，享年86岁

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！