第四篇 如何用随机算法求解组合优化问题（十四）
清华大学计算机系 马少平
第十四节：总结
艾博士：小明，这篇如何用随机算法求解组合优化问题我们就讲这么多，请你总结一下我们都讲解了哪些内容。
小明边回忆边回答说：这篇内容讲得挺多的，重点是两个随机算法——模拟退火算法和遗传算法，我试着总结一下。
（1）首先讲解了什么是组合优化问题。求给定条件下某问题的最优解，当解的数量是有限个时，该问题就属于组合优化问题。一般来说，组合优化问题属于比较难求解的问题，目前还没有有效的求解算法。
（2）以爬山法为例，引出了局部搜索算法的概念，如何利用局部信息寻求问题的最优解是局部搜索算法的特点。当问题具有多个局部最优值时，局部搜索算法不能保证找到全局最优解，存在诸如局部最优问题、步长问题和起始点问题等，可以通过随机接受差解、变步长、随机产生起始点多次运行等思路弱化这些问题的影响。
（3）通过一个做弹簧的例子引出了物理中的金属退火现象,通过将组合优化问题与退火现象做类比，提出了模拟退火算法。总体上来说模拟退火算法还是属于局部搜索方法，受物理退火现象中依据Metropolis准则接受新状态的启发，采用同样的策略改进局部搜索算法，这也是模拟退火算法这一名称的来源。
（4）具体分析了为什么满足一定条件下退火过程最终当温度趋近于绝对0度时，系统趋向于内能最低状态的概率为1。在讲解过程中引入了一个“怪杯子”做类比实验，结合具体的数学分析，从感性和理性两方面了解了退火过程背后所蕴含的理论原理。
（5）退火过程需要满足的三个条件：足够高的初始温度、每个温度下足够充分的状态交换和温度下降足够缓慢。在“三个足够”的条件下，当温度趋近于绝对0度时，系统以概率1处于内能最小状态。
（6）模拟退火算法用于求解实际问题时，需要解决初始温度如何设定、温度如何下降、每个温度下解的交换次数、算法结束条件等问题，介绍了解决这些问题的一些原则和方法。以旅行商问题为实例，讲解了如何用模拟退火算法求解该问题。
（7）为引入遗传算法，介绍了达尔文进化论“物竞天择、适者生存”的基本思想。所谓的“适者”就是一定条件下的“优者”。那么是否可以将进化论思想用于求解组合优化问题呢？遗传算法就是基于这样的想法提出来的一个用于求解组合优化问题的随机算法。
（8）将生物的进化过程与遗传算法建立了对应关系，通过求解给定范围下x2最大值问题，介绍了如何通过定义编码、交叉操作、变异操作、适应函数和选择过程等与进化过程建立具体的对应关系，实现“优胜劣汰”的进化思想。
（9）介绍了具体的遗传算法框架，并通过求解给定范围下的x2最大值问题，详细介绍了遗传算法求解问题的具体步骤和过程。
（10）分别结合不同的实例，讲解了二进制编码和整数编码方法，以及不同编码下相应的交叉操作、变异操作方法。
（11）介绍了以指标函数为基础的定义适应函数的方法，以及提高“优胜劣汰”效果、加快进化过程的适应函数加速方法，包括线性加速和非线性加速两种方法，以及算法的停止准则。
（12）结合旅行商问题，给出了一个用遗传算法求解该问题的实例。
（13）最后，以猴子为例，讲解了模拟退火算法和遗传算法两个算法的不同之处，模拟退火算法是“有意识”地、“主动”地达到最优值，而遗传算法是“无意识”、“无目的”的进化，通过“优胜劣汰”达到最优值，体现了“适”就是“优”的思想。两种算法求解问题的思路不同，各有各的特点，可以将两个不同的算法结合在一起构造出综合各自特点的新算法。
艾博士：小明总结的非常全面。我们学习这些算法，一方面是掌握算法的具体内容，利用这些算法求解实际问题，另一方面是了解算法的基本原理和提出思想，掌握算法的精髓，为改进甚至提出新算法掌握基本的技能。
《如何用随机算法求解组合优化问题》篇完结