第四篇 如何用随机算法求解组合优化问题（十三）
清华大学计算机系 马少平
第十三节：模拟退火算法与遗传算法的对比
小明：艾博士，模拟退火算法和遗传算法都属于随机算法，那么这两个算法之间有哪些异同呢？
艾博士：为了说明这两个算法之间的异同，我们做个类比。
模拟退火算法相当于一个喝醉了酒的猴子爬香山。
小明：喝醉了酒的猴子？这个比喻有些新鲜啊。
艾博士：一只喝的酩酊大醉的猴子去爬香山，由于醉酒使得猴子神志不清、步履蹒跚，向上一步、下滑一步地在山上四处乱走，没有明确的行进方向。这就好比在温度非常高时的退火现象，达到各个地方的概率是近乎相等的。
小明：咦，这个比喻确实比较形象。
艾博士：随着时间的流逝，猴子逐渐有些清醒，它慢慢地知道自己要爬向香山的顶峰，步履也不是那么蹒跚，但由于还没有完全清醒，还是会出现向下滑动的情况，但是总的来说向上爬的情况越来越多了，而向下滑的情况越来越少。这就相当于退火过程的温度缓慢下降时，接受好解的概率越来越大，而接受差解的概率越来越小。
慢慢地猴子越来越清醒，也就越来越增加了向上爬的可能性，而降低了向下滑的可能性。最后猴子终于清醒的时候，也就大概率地爬到了香山的最高峰。这就好比是退火过程中当温度最终趋近于绝对0度时，以概率1趋近于最优解。
小明：这个比喻真的太好了。
艾博士：在猴子爬香山的过程中，猴子是有意识、有目标的，他的心里知道自己的目标是香山的最高峰。但是由于醉酒的关系，猴子做不到每一步都向上爬，尤其是刚开始、正酩酊大醉的时候，但是随着逐渐清醒，会越来越爬向香山山顶的方向。这里强调的是，猴子是有意识的，目标就是爬到香山的最高峰。这一点一定要记住。
小明：好的，我记住了这一点。
艾博士：遗传算法好比是生活在香山上的一群猴子。
小明：为什么遗传算法要用一群猴子类比呢？
艾博士：生物遗传必须要达到一定的群体规模才能实现进化，所以遗传算法中需要一个具有一定规模的群体。
小明：我明白了，遗传进化必须有一定的群体来保证。
艾博士：假定一群猴子生活在香山上，分布在山上的不同位置，有些在山脚下，有些在半山腰。这些猴子自己并没有意识，没有爬到香山顶峰的愿望，只是上蹿下跳自在地生活着。突然来了一帮猎人分散在香山的四周，他们随机地向着山上射击。由于位置的关系，山脚下子弹比较密集，越往山上子弹越稀疏。这样就导致了越是在山脚下的猴子越容易被猎人的子弹打中，从而被淘汰。而越是处于高处的的猴子越不容易被打中，从而生存下来的概率就越大。
小明：我知道了，猎人的子弹就相当于环境的变化，猴子所处的高度就相当于适应值，适应值越大的猴子被选择保留下来的概率就越大，反之被淘汰的概率就越大。
艾博士：正是这样的一个结果。随着时间的推移，生活在山脚下，也就是适应值低的猴子就逐渐被淘汰了，而生活在高处的猴子生存了下来，继续过着它们的生活，繁衍后代。
小明：那这些猴子为了能生存下去、不被淘汰，是不是要往山上跑呢？
艾博士：这正是我想要说的，并不是这样的。这些猴子不知道向哪个方向跑生存的概率更大，因此猴子本身并没有意识到向山上跑生存的可能性会更大。只是由于环境的自然选择，也就是猎人的猎枪使得生活在山下的猴子越来越少，越往山顶存活的猴子越多。经过若干代的进化之后，一些存活下来的猴子到达了山顶。这也是达尔文进化论的主要贡献之一，即进化是无方向的，只是能适应环境生活的那些生物被自然选择保留了下来。就好比说长颈鹿，它们并不知道脖子长就可以生存下来，然后有意识地向脖子长的方向进化，而是各种进化都有，只是最终脖子长的被环境选择生存了下来。
刚才讲模拟退火算法的类比时，提到过那里的猴子是有意识要爬到香山最高峰的，也一直努力向最高峰爬，虽然有时候由于醉酒的关系并不能做到步步如愿。而遗传算法中的猴子是无意识的，这也是遗传算法的特点。这正是两种算法的不同特征。
小明：那么是否也可以让遗传算法中的猴子具有意识呢？这样是不是就可以尽快实现优胜劣汰，达到香山的顶峰，而不是被动的选择？
艾博士：小明说的很有道理，有学者将模拟退火算法和遗传算法结合在一起就是基于这样的想法。
小明：这两种完全不同的算法怎么结合在一起呢？
艾博士：有两种结合方式，一种是以遗传算法为基本框架，在遗传过程中引入模拟退火算法，让每个“猴子”具有意识。另一种方法是以模拟退火算法为基本框架，在模拟退火过程中引入遗传算法，使得“猴子”在降温过程中获得优秀的基因。
小明：看起来这些都是比较有意思的研究工作。
艾博士：这里我们只简要说明了一下基本思想，两种算法结合也存在很多需要解决的问题，具体就不做介绍了，有兴趣的话可以参阅有关书籍和论文。
小明：谢谢艾博士给我讲解了这么多很有意思的工作。
小明读书笔记
模拟退火算法和遗传算法都属于随机算法，有各自不同的特点。模拟退火算法相当于有意识的猴子爬山，它的目标是爬到山的顶峰，但由于醉酒等因素使得猴子不能准确地做到每一步都向上爬。“有意识、有目标、主动向上”是模拟退火算法的特点。遗传算法相当于一群生活在山上的猴子，这些猴子并不知道如何行动可以更好地生存下来，只是由于环境的问题，自然选择淘汰了更多的生活在比较靠近山脚下的猴子，让生活在高处的猴子获得了更大的生存可能。这样一代代地遗传、进化，让更多的猴子达到了山顶。“无意识、无目标”是遗传算法的特点。可以将两种不同的随机算法结合在一起，让“遗传”中的猴子具有“意识”，或者让“退火”中的猴子具有“遗传”，发挥两个算法的特点，更有效地求解复杂问题。
未完待续