跟清华大学马少平教授学AI：如何用随机算法求解组合优化问题（六）
第四篇 如何用随机算法求解组合优化问题（六）
清华大学计算机系 马少平
第六节：模拟退火算法的参数选择
小明：艾博士，从您的介绍看，参数选择对于模拟退火算法是否能找到最优解起关键的作用，如何合理地设置模拟退火算法的参数呢？
艾博士：接下来我们就介绍模拟退火算法中一些参数的选择原则。
从上面的分析我们知道，模拟退火算法以概率1找到全局最优解的基本条件，是初始温度必须足够高，在每个温度下状态的交换必须足够充分，温度t的下降必须足够缓慢。因此初始的温度 、在每个温度下状态的交换次数、温度t的下降方法，以及温度下降到什么程度算法结束等参数确定，成为模拟退火算法求解实际问题时必须考虑的首要问题。
并不是任何一组参数，都能够保证模拟退火算法收敛于最优解或者某个满意的近似最优解，大量的实验表明，解的质量与算法的运行时间是成正比关系的，很难做到两全其美。下面我们给出模拟退火算法中一些参数或者准则的确定方法，试图在求解时间与解的质量之间作一个折中的选择。这些参数或者准则包括：
（1）初始温度 ；
（2）温度t的衰减函数，即温度的下降方法；
（3）算法的终止准则，终止温度 或者终止条件；
（4）每个温度t下的马尔可夫链长度 ，即算法的内循环次数。
1、起始温度 的选取
艾博士：模拟退火算法要求初始温度足够高，这样才能够使得在初始温度下，以等概率处于任何一个状态。多高的温度才算“足够高”呢？这显然与具体的问题有关，就像金属材料中，不同的材料具有不同的溶解温度一样。因此，初始温度应根据具体的问题而定。
小明：那么是否有一个基本的确定初始温度的方法呢？
艾博士：一些基本原则是有的，不同的角度也可以给出不同的确定初始温度的方法，在实际中一般也需要多次尝试才能有一个比较好的结果。
什么是合适的初始温度呢？一个合适的初始温度，应保证到达每一个状态的概率基本相等，也就是接受概率 近似等于1。由于模拟退火算法接受好解的概率为1，只有遇到差解时才以概率接受，所以在Metropolis准则下，初始温度应该使得接受差解的概率接近于1，即：
（ ）
其中 为状态j与状态i的指标函数差，并假定了f(j)>f(i)。
如果我们给定一个比较大的接受概率 ，比如 =0.9或者0.95，就可以从式（4.19）计算出 值：
其中 可以通过随机产生一个状态序列S计算得出。具体方法可以取序列中最大指标函数值与最小指标函数值的差值：
艾博士：下面我们给出一个具体的计算例子。假定 =0.9， ＝100，那么初始温度 是多少呢？
小明认真计算起来，很快有了计算结果：
艾博士检查了小明的计算结果无误后继续讲到：我们也可以从另外的角度考虑如何计算初始温度 。
假设我们随机地生成一个状态序列，对于该序列中任意相邻两个状态i和j，假设i在前j在后，则从状态i到状态j可能被接受，也可能不被接受。如果两个状态的指标函数值f(j)≤f(i)，则一定会被接受，设序列中这样的情况共有m1个。如果两个状态的指标函数值f(j)＞f(i)，则按照概率 接受。如果我们用 表示f(j)-f(i)的平均值，则平均的接受概率为 。设序列中f(j)＞f(i)的情况共有 个，则 种情况中平均接受次数为：
所以该序列中任意两个相邻的状态共有 个，从前一个状态i到后一个状态j的接受总次数为两种情况相加，即 。这样我们可以得到平均接受率为：
从上式可以求解出初始温度t0为：
如果给定了一个初始接受概率 ，再随机地产生一个状态序列，则可以计算出初始温度 。
艾博士介绍到这里问小明：以上我们介绍了两种确定初始温度 的办法，小明你看这两种方法有什么不同呢？
小明：我觉得这两种方法基本思路是一样的，都是根据设定的初始接受概率计算初始温度 。第一种方法相当于直接用 计算初始接受概率，而没有考虑状态序列中前一个状态的指标函数值大于后一个状态的情况，而在这种情况下后一个状态是被100%接受的。所以这样得到的初始接受概率值偏低，计算出的 会稍微大一点。而第二种方法则是分别考虑了序列中后一个状态指标函数值小于等于前一个状态和大于后一个状态两种情况，估计的初始接受概率会比第一种方法稍大，得到的初始温度 也会相对小一些。
艾博士：小明分析的是对的。我们对比式（4.20）和式（4.25）也可以发现，在不考虑 的情况下，这两个计算公式是一样的。我们对比式（4.20）和式（4.25）分母中的括号部分，式（4.25）有：
由此可见，式（4.25）的分母部分大于等于式（4.20）的分母，从而由式（4.25）计算得到的 要小于等于由式（4.20）计算得到的 。这与小明的分析完全一致。
表4.2给出了在 的情况下，由式（4.20）得到的 与由式（4.25）得到的 之比值（表中用 (20)/ (25)表示），由表中可以看出，式（4.20）得到的 大约是式（4.25）得到的 的2倍。当然这个结果与假设 有关。
表4.2：分别由式（4.20）和式（4.25）得到的 之比
艾博士继续讲解到：仿照金属的升温过程，我们也可以通过逐步升温的方法，得到一个合适的初始温度。基本思想就是先设定一个比较小的初始温度，随机产生一个状态序列，按照Metropolis准则计算状态的接受次数，从而计算出接受概率。如果计算的接受概率比较小，则逐步升温，直到接受概率满意为止。
小明：这种方法就好比摇晃怪杯子，先以一个较慢的速度摇晃，然后观察豆子在杯子中的跳动情况。如果豆子基本在杯子下部分运动，则说明摇晃的速度不够，应该增加摇晃速度。一点点增加摇晃速度，直到豆子在杯子中几乎上下均匀地跳动为止，就认为达到了一个合适的初始速度。
艾博士：就是这样的思想。通过升温方法获得初始温度 的算法如下：
（1）给定一个希望的初始接受概率 ，给定一个较低的初始温度 ，比如 ＝1；
（2）随机的产生一个状态序列，并计算该序列的接收率：
接 受 的 状 态 数 产 生 的 状 态 总 数
如果接收率大于给定的初始接受概率 ，则转（4）；
（3）提高温度，更新 ，转（2）；
（4）结束。
其中更新t0可以采用每次乘一个大于1的常数K的方法：
也可以采用每次加固定值的方法：
＋
这里的T为一个事先给定的常量。
小明：感觉这也是一种比较好的方法，完全依靠产生的状态序列实验决定初始温度 。
艾博士强调说：也不好说具体哪种方法更好，需要结合具体问题多次实验决定，以上几种方法都只是给出一个大概的参考值。
2、温度的下降方法
艾博士：退火过程的条件之一是要求温度下降足够缓慢，因此模拟退火算法的降温过程也必须足够缓慢才行。在模拟退火算法中常用的温度下降方法有以下三种：
（1）等比例下降法
该方法通过设置一个衰减系数α，使得温度每次以相同的比率下降：
， 。
其中 是当前温度， 是下一个时刻的温度， 是一个常数。越接近于1，温度下降的越慢，一般可以选取0.9～0.98左右的一个值。该方法简单实用，是一种常用的温度下降方法。
小明：如果要求温度下降足够缓慢，是不是α越大越好呢？α越大就越接近与1，温度下降就越慢。
艾博士：从“温度下降越缓慢越好”的角度来说，确实α越大越好，但是如果α过大的话（在α小于1的前提下），最终温度要下降到接近于0度所需要的时间也就越长，严重影响了算法的计算效率。所以必须选择一个合适的α值，在效率与效果之间折中选择。
（2）等值下降法
艾博士：温度下降的另一种方法是采取等值下降的办法。顾名思义，所谓等值下降方法就是温度每次下降一个固定值，而不考虑当前的温度是多少。
设K是希望的温度下降总次数，则：
其中 是初始温度。
该方法的好处是可以控制总的温度下降次数，但由于每次温度下降的是一个固定值，如果设置过小，在高温时温度下降太慢，如果设置的过大，在低温下温度下降的又可能太快。
小明：看起来这种方法不是太好，很难照顾到高温和低温的情况。
（3）基于距离参数的下降方法
艾博士：对于状态i和j，如果温度从 下降到 的话，当温度下降幅度很小时，则在温度 下从状态i到状态j的被接受概率 应该与在温度 下从状态i到状态j的被接受概率 差别不大，两个概率之比应该接近于1。所以有：
其中 是一个较小的正数，被称作距离参数。
假定状态i的指标函数值小于状态j，则有：
当给定δ后，上式虽然可以由 计算出 ，但是公式中涉及两个状态i和j的指标函数值。我们希望温度下降方法与具体的状态无关，可以取一个比较保守的数值，用3倍的 代替 f(j)-f(i)，其中 为温度 下状态的指标函数值的标准差，实际计算时，可通过在该温度下随机产生若干个状态统计得到。
小明：这里为什么用3倍标准差代替f(j)-f(i)呢？
艾博士：在统计学中有一个3倍标准差原则，如果假设状态的指标函数值服从正态分布，则超过99%的情况下3倍标准差会大于任意两个状态的指标函数差值f(j)-f(i)，因此用3倍标准差代替f(j)-f(i)将会涵盖多于99%的情况。这属于一种比较保守的估计。
用 代替 f(j)-f(i)后，可得温度的衰减函数：
小明：这里的δ值如何确定呢？
艾博士：δ是一个大于0的比较小的数，可以设为0.01、0.02等，一般也是要根据具体问题实验确定。
小明：这三种温度下降方法，各自有哪些特点呢？
艾博士：在以上温度下降方法中，（1）、（2）两种方法独立于具体的问题，而方法（3）是与具体问题有关的温度下降方法，因为用到了与问题有关的状态指标函数值的标准差。第一种等比下降方法由于其简单有效，用的比较多。第二种等值下降方法存在的问题比较多，用的比较少。而第三种基于距离参数的下降方法用的也比较多。
3、每一温度下的停止准则
艾博士：根据前面的分析，模拟退火算法在每个温度下必须有足够的交换，才能使得到达任何状态的概率趋于稳定值。从找到最优解的角度来说，交换的次数越多越好，从求解效率上来说，则不能交换的太多，因此又是一个需要折中考虑的问题。
如果用 表示在温度 下的迭代次数的话，也就是算法内循环的循环次数，则 应使得在这一温度下的状态交换尽可能的充分。
小明：如何判断是否充分交换了呢？
艾博士：客观地说，也没有什么太好的方法，有以下几个常用的停止准则：
（1）固定长度方法
艾博士：固定长度方法，就是说算法内循环的循环次数是固定的，不随温度等因素而变化，这是最简单的一种方法，在每一个温度下，都使用相同的 。 的选取与具体的问题相关，一般与邻域的大小直接关联，由于邻域越大可选的状态越多，所以需要更多的循环次数才有可能达到充分交换的目的。通常选择为问题规模n的一个多项式函数。例如对于n城市旅行商问题中，如果采用交换两个城市的方法产生邻域的话，邻域的大小为 ，则 可以选取如 、 等，其中C为常数。
小明：这里的固定长度指的是问题规模确定后内循环次数是固定的的吧？并不是在任何规模下都是一个固定值。
艾博士：是这样的，规模越大内循环次数应该越多，因为问题规模大了以后，可能的状态数也会更多，没有足够的循环次数很难达到平衡。
（2）基于接受率的停止准则
艾博士：由前面我们对退火过程的分析知道，在比较高的温度时，系统处于每一个状态的概率基本相同，而且每一个状态的接受概率也接近于1。因此在高温时，即便比较小的迭代数，也可以基本达到平稳状态。而随着温度的下降，被拒绝的状态数随之增加，因此在低温下迭代数应增加，以免由于迭代数太少，而过早的陷入局部最优状态。因此一个直观的想法就是随着温度的下降适当的增加迭代次数。
一种方法就是，规定一个接受次数R，在某一温度下，只有被接受的状态数达到R时，在该温度下的迭代才停止，转入下一个温度。由于随着温度的下降，状态被接受的概率随之下降，因此这样的一种准则是满足随着温度的下降适当的增加迭代次数的原则。但由于在温度比较低时，接受差解的概率很低，为了防止出现过多的迭代次数，一般设置一个迭代次数的上限，当迭代次数达到上限时，即便不满足接受次数R，也停止这一温度的迭代过程。
与上一种方法相类似的，可以规定一个状态接受率R，R等于该温度下接受的状态数除以生成的总状态数。如果接受率达到了R，则停止该温度下的迭代，转入下一个温度。为了防止迭代次数过少或者过多，一般定义一个迭代次数的下限和上限，只有当迭代次数达到了下限并且满足所要求的接受率R时，或者达到了迭代次数的上限时，才停止这一温度的迭代。
还可以通过引入“代”的概念来定义停止准则。在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。
在某一温度下的迭代次数与温度的下降幅度是紧密相关的。如果温度每次下降的幅度比较小的话，则相邻两个温度之间的平稳分布相差也应该比较小。一些研究表明，过长的迭代次数对提高解的质量影响并不大，只会导致增加系统的运算时间。因此一般选取比较小的温度衰减值，只要迭代次数适当大就可以了。
小明：我大体上了解了每一温度下的停止原则，具体如何确定迭代次数，同前面讲过的算法其他参数一样，还是需要通过实验决定。
艾博士：确实是这样的，实际问题千变万化，有很多不确定的因素，只能根据这些基本原则通过实验确定具体的参数值。
4、算法的终止原则
艾博士：模拟退火算法从初始温度 开始逐步下降温度，最终当温度下降到一定值时，算法结束。合理的结束条件，应使得算法收敛于问题的某一个近似解，同时应能保证解具有一定的质量，并且应在一个可以接受的有限时间内算法停止。
同样，我们一般有下面几种确定算法终止的方法或者原则。
（1）零度法
艾博士：从理论上讲，当温度趋近于0时，模拟退火算法才结束。因此，可以设定一个常数 >0，当 时算法结束。
小明：这个跟算法的理论要求是一致的，只要 足够小就可以了。
艾博士：是这样的。但是这里同样有效果与效率的平衡问题。理论上是温度越接近0度越好，但是太低的温度则会影响到求解效率，需要寻找一个合适的结束温度。什么样的温度才是一个合适的结束温度，可能与我们求解的具体问题有关。比如我们前面遇到的做弹簧例子，温度只要降到室温就可以了，没有必要放到冰箱里。但是有些情况下，则可能降低到室温是不行的，需要进一步降低温度才行。
（2）循环总控制法
艾博士：循环总控制法就是给定一个指定的温度下降次数K，当温度的下降次数达到K次时则算法停止。这要求给定一个合适的K。如果K值选择不合适，对于小规模问题将导致增加算法无谓的运行时间，而对于大规模问题，则可能难于得到高质量的解。
小明：那么这个K设置多大才合适呢？该不是又是实验确定吧？
艾博士听小明这么说，哈哈大笑起来：确实需要实验确定。但是我们可以观察算法停止前几个温度下得到解的变化情况。如果最后几个温度下得到的解还在发生变化，则说明K设置的有些过小，需要加大K值。如果算法结束前多个温度下的解都是基本不变的，则说明K值设置的有些过大，可以适当减少K值。如果最后两三个、三四个温度下得到了一个基本不变的解，而之前的温度下解有一定的变化，则说明得到了一个比较合适的值。
（3）无变化控制法
艾博士：随着温度的下降，虽然由于模拟退火算法会随机的接受一些不好的解，但从总体上来说，得到的解的质量应该逐步提高，在温度比较低时，更是如此。如果在相邻的n个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。即便是收敛于局部最优解，由于在低温下跳出局部最优解的可能性也已经很小，因此算法可以终止了。
讲到这里艾博士问小明：你说说看方法（3）和方法（2）有什么关系吗？
小明认真对比之后说：感觉这两种方法本质上是一样的，只是方法（2）是人为地判断终止条件，而方法（3）是把人的查看改成了算法自动控制结束条件。
艾博士：非常正确，正是这样的。一般当相邻的两三个结果没有变化时，就可以考虑停止了。但是也可能会存在一些偶然的结果，在比较高的温度下凑巧相邻的几次结果没有发生变化，这种情况虽然发生的概率比较小，但是也是会发生的。这种情况下，可以再设定一个温度值，只有当温度低于该设定值时，并且相邻的几个结果一致时，算法才结束。
小明：明白了，这样就可以防止一些偶然结果的出现，提高了算法的求解质量。
（4）接受概率控制法
艾博士：当温度比较低时，从一个状态到另一个状态的接受概率会非常小，无论是陷入局部最优解还是全局最优解，都很难从当前解跳出来了。我们设定一个比较小的概率值 ，如果在当前温度下除了当前状态外，其他状态的接受概率均小于 值，则算法结束。
（5）邻域平均概率控制法
艾博士：这种方法是方法（4）的一种推广，自动确定概率值 。具体实现方法是：设大小为N的一个邻域，在邻域内一个状态被接受的平均概率为1/N。设 、 为该领域中的局部最优值和局部次最优值。按照式（4.14）、（4.15）给出的产生概率和接受概率，则次最优解是除了局部最优解以外接受概率最大的，其接受概率为：
如果该概率值小于平均值1/N时，即：
可以认为从局部最优解跳出的可能性已经很小了，因此可以终止算法。此时的终止温度 为：
小明：这里的 、 怎么计算呢？
艾博士：就是目前得到的最好解和次最好解。
（6）相对误差估计法
艾博士：我们多次提到，很多情况下并不一定要求得到最优解，只要获得一个满意解就可以了。
小明：但是如何知道解是否满意呢？
艾博士：这确实是一个问题，我们并不好评价解的满意性。如果在计算过程中我们能大体估计出解的误差，可以用该误差评价解的满意性。
小明：但是又怎么估计误差呢？
艾博士：假设 是初始温度， 是结束温度， 是初始温度 时指标函数的平均值， 是结束温度tf时指标函数的平均值， 是结束温度 时指标函数平方的平均值。则我们可以给出解 对于 的相对误差估计：
如果ε>0是给定的相对误差，则得到算法的停止条件：
其中 是温度为t时产生的解序列。
小明有些看不懂为什么是这个结果，问到：艾博士，这个结果是怎么得到的？
艾博士：这个结果推导起来有些麻烦，我们就不讲解了，有兴趣的话可以参看有关书籍。
小明：好的，我课后找相关书籍看看。
艾博士最后再次强调说：小明，以上我们介绍了用模拟退火算法求解组合优化问题时确定算法参数的一些方法，这些方法基本上都是基于经验的，基本上是一些指导性的原则，在具体使用时需要根据具体的问题具体分析，经多次实验、反复调整后，确定具体的参数。
小明读书笔记
实现一个好的模拟退火算法，其参数选择至关重要。主要参数包括：初始温度，温度的下降方法，每个温度下算法的循环次数，算法的终止条件。
初始温度的选择有几种方法，但其中心思想是在初始温度下接受任何一个状态，也就是解的概率接近于1。按照这样的思路，从不同的角度可以有几种设置初始温度的方法。
最常用的温度下降方法是等比例下降，也就是每次乘一个接近于1的衰减系数α。另外还有基于距离参数的下降方法，其思想来源于当温度下降一个很小的幅度时，相邻两个温度下从状态i转换到状态j的概率应该变化很小。如果给定了一个概率允许的变化范围，则可以估计温度下降允许的最大幅度，那么温度下降不超过该估计值即可。
一般来说每个温度下算法的循环次数与待求解的问题规模成多项式关系，问题规模越大循环次数应该越多，以便达到充分交换的目的。
算法的终止条件主要依据是温度趋近于0度，当温度值小于某个给定值时，算法就可以结束了。但是温度多低算是接近于0度了呢？可能与具体的问题有关。一种最常用的办法是无变化控制法，即如果几个温度下求解的结果都不再发生变化了，算法就认为可以结束了。因为这种情况下，即便是陷入了局部最优解，也很难从中跳出来了。通过估计解的相对误差也是一种判断算法是否结束的方法。
未完待续
本文内容来自公众号：图灵人工智能、AI光影社
01
参考书籍
《艾博士：深入浅出人工智能》
ISBN：9787302646969
作者：马少平
定价：89.80元
内容简介
本书是一本针对初学者介绍人工智能基础知识的书籍。本书采用通俗易懂的语言讲解人工智能的基本概念、发展历程和主要方法，内容涵盖人工智能的核心方法，包括什么是人工智能、神经网络（深度学习）是如何实现的、计算机是如何学会下棋的、计算机是如何找到**路径的、如何用随机算法求解组合优化问题、统计机器学习方法是如何实现分类与聚类的、专家系统是如何实现的等，每种方法都配有例题并给出详细的求解过程，以帮助读者理解和掌握算法实质，提高读者解决实际问题的能力。此外，本书可以帮助人工智能的开发人员理解各种算法背后的基本原理。书中的讲解方法和示例，有助于相关课程的教师讲解相关概念和算法。总之，这是一本实用性强、通俗易懂的人工智能入门教材，适合不同背景的读者学习和使用。