2023年8月1日发(作者：)

爬⼭算法（HillClimbing）模拟退⽕（SA,SimulatedAnnealing）⼀. 爬⼭算法 ( Hill Climbing )爬⼭算法是⼀种简单的贪⼼搜索算法，该算法每次从当前解的临近解空间中选择⼀个最优解作为当前解，直到达到⼀个局部最优解。爬⼭算法实现很简单，其主要缺点是会陷⼊局部最优解，⽽不⼀定能搜索到全局最优解。假设C点为当前解，爬⼭算法搜索到A点这个局部最优解就会停⽌搜索，因为在A点⽆论向那个⽅向⼩幅度移动都不能得到更优的解。

⼆. 模拟退⽕(SA,Simulated Annealing)思想在实际⽇常中，⼈们会经常遇到如下问题：在某个给定的定义域X内，求函数f(x)对应的最优值。此处以最⼩值问题举例（最⼤值问题可以等价转化成最⼩值问题），形式化为：

如果X是离散有限取值，那么可以通过穷取法获得问题的最优解；如果X连续，但f(x)是凸的，那可以通过梯度下降等⽅法获得最优解；如果X连续且f(x)⾮凸，虽说根据已有的近似求解法能够找到问题解，可解是否是最优的还有待考量，很多时候若初始值选择的不好，⾮常容易陷⼊局部最优值。

随着⽇常业务场景的复杂化，第三种问题经常遇见。如何有效地避免局部最优的困扰？模拟退⽕算法应运⽽⽣。其实模拟退⽕也算是启发式算法的⼀种，具体学习的是冶⾦学中⾦属加热-冷却的过程。由trick, 和在1983年所发明的，V.Čern在1985年也独⽴发明此演算法。不过模拟退⽕算法到底是如何模拟⾦属退⽕的原理？主要是将热⼒学的理论套⽤到统计学上，将搜寻空间内每⼀点想像成空⽓内的分⼦；分⼦的能量，就是它本⾝的动能；⽽搜寻空间内的每⼀点，也像空⽓分⼦⼀样带有“能量”，以表⽰该点对命题的合适程度。演算法先以搜寻空间内⼀个任意点作起始：每⼀步先选择⼀个“邻居”，然后再计算从现有位置到达“邻居”的概率。若概率⼤于给定的阈值，则跳转到“邻居”；若概率较⼩，则停留在原位置不动。⼀、模拟退⽕算法基本思想模拟退⽕其实也是⼀种贪⼼算法，但是它的搜索过程引⼊了随机因素。在迭代更新可⾏解时，以⼀定的概率来接受⼀个⽐当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝⾊点A，模拟退⽕算法会快速搜索到局部最优解B，但在搜索到局部最优解后，不是就此结束，⽽是会以⼀定的概率接受到右边的移动。也许经过⼏次这样的不是局部最优的移动后会到达全局最优点D，于是就跳出了局部最⼩值。

根据热⼒学的原理，在温度为T时，出现能量差为dE的降温的概率为p(dE)，表⽰为:

其中k是波尔兹曼常数，值为k=1.3806488(13)×10−23，exp表⽰⾃然指数，且dE<0。因此dE/kT<0，所以p(dE)函数的取值范围是(0,1)。满⾜概率密度函数的定义。其实这条公式更直观意思就是：温度越⾼，出现⼀次能量差为p(dE)的降温的概率就越⼤；温度越低，则出现降温的概率就越⼩。在实际问题中，这⾥的“⼀定的概率”的计算参考了⾦属冶炼的退⽕过程。假定当前可⾏解为x，迭代更新后的解为x_new，那么对应的“能量差”定义为：

其对应的“⼀定概率”为： 注：在实际问题中，可以设定k=1。因为kT可以等价于⼀个参数T。如设定k=2、T=1000，等于直接设定T=2000的效果。⼆、模拟退⽕算法描述1. 初始化：初始温度T（充分⼤），温度下限Tmin（充分⼩），初始解状态x(是算法迭代的起点)，每个T值的迭代次数L；2. 对l=1,2,...,L做第3⾄第6步；3. 产⽣新解x_new: (x_new=x+Δx)；4. 利计算增量Δf=f(x_new)−f(x)，其中f(x)为优化⽬标；5. 若Δf<0(若寻找最⼤值，Δf>0)则接受x_new作为新的当前解，否则以概率exp(−Δf/(kT))接受x_new作为新的当前解；6. 如果满⾜终⽌条件则输出当前解作为最优解，结束程序。(终⽌条件通常取为连续若⼲个新解都没有被接受时终⽌算法。)；7. T逐渐减少，且T>Tmin，然后转第2步。

三、模拟退⽕算法的优缺点模拟退⽕算法的应⽤很⼴泛，可以⾼效地求解NP完全问题，如货郎担问题(Travelling Salesman Problem，简记为TSP)、最⼤截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着⾊问题(Graph ColouringProblem)等等，但其参数难以控制，不能保证⼀次就收敛到最优值，⼀般需要多次尝试才能获得（⼤部分情况下还是会陷⼊局部最优值）。观察模拟退⽕算法的过程，发现其主要存在如下三个参数问题：　　(1) 温度T的初始值设置问题

　　温度TT的初始值设置是影响模拟退⽕算法全局搜索性能的重要因素之⼀、初始温度⾼，则搜索到全局最优解的可能性⼤，但因此要花费⼤量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。　　(2) 退⽕速度问题，即每个TT值的迭代次数

　　模拟退⽕算法的全局搜索性能也与退⽕速度密切相关。⼀般来说，同⼀温度下的“充分”搜索是相当必要的，但这也需要计算时间。循环次数增加必定带来计算开销的增⼤。　　(3) 温度管理问题

　　温度管理问题也是模拟退⽕算法难以处理的问题之⼀。实际应⽤中，由于必须考虑计算复杂度的切实可⾏性等问题，常采⽤如下所⽰的降温⽅式：

T=α×T.α∈(0,1).注：为了保证较⼤的搜索空间，α⼀般取接近于1的值，如0.95、0.9。　　关于爬⼭算法与模拟退⽕，有⼀个有趣的⽐喻：　　爬⼭算法：兔⼦朝着⽐现在⾼的地⽅跳去。它找到了不远处的最⾼⼭峰。但是这座⼭不⼀定是珠穆朗玛峰。这就是爬⼭算法，它不能保证局部最优值就是全局最优值。　　模拟退⽕：兔⼦喝醉了。它随机地跳了很长时间。这期间，它可能⾛向⾼处，也可能踏⼊平地。但是，它渐渐清醒了并朝最⾼⽅向跳去。这就是模拟退⽕。附上模拟退⽕算法伪代码：四. 使⽤模拟退⽕算法解决旅⾏商问题　　旅⾏商问题 ( TSP , Traveling Salesman Problem ) ：有N个城市，要求从其中某个问题出发，唯⼀遍历所有城市，再回到出发的城市，求最短的路线。　　旅⾏商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。　　使⽤模拟退⽕算法可以⽐较快的求出TSP的⼀条近似最优路径。（使⽤遗传算法也是可以的，我将在下⼀篇⽂章中介绍）模拟退⽕解决TSP的思路：1. 产⽣⼀条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )2. 若L(P(i+1)) < L(P(i))，则接受P(i+1)为新的路径，否则以模拟退⽕的那个概率接受P(i+1) ，然后降温3. 重复步骤1，2直到满⾜退出条件　　产⽣新的遍历路径的⽅法有很多，下⾯列举其中3种：1. 随机选择2个节点，交换路径中的这2个节点的顺序。2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。3. 随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后⾯。五. 算法评价 模拟退⽕算法是⼀种随机算法，并不⼀定能找到全局的最优解，可以⽐较快的找到问题的近似最优解。 如果参数设置得当，模拟退⽕算法搜索效率⽐穷举法要⾼。

2023年8月1日发(作者：)

爬⼭算法（HillClimbing）模拟退⽕（SA,SimulatedAnnealing）⼀. 爬⼭算法 ( Hill Climbing )爬⼭算法是⼀种简单的贪⼼搜索算法，该算法每次从当前解的临近解空间中选择⼀个最优解作为当前解，直到达到⼀个局部最优解。爬⼭算法实现很简单，其主要缺点是会陷⼊局部最优解，⽽不⼀定能搜索到全局最优解。假设C点为当前解，爬⼭算法搜索到A点这个局部最优解就会停⽌搜索，因为在A点⽆论向那个⽅向⼩幅度移动都不能得到更优的解。

⼆. 模拟退⽕(SA,Simulated Annealing)思想在实际⽇常中，⼈们会经常遇到如下问题：在某个给定的定义域X内，求函数f(x)对应的最优值。此处以最⼩值问题举例（最⼤值问题可以等价转化成最⼩值问题），形式化为：

如果X是离散有限取值，那么可以通过穷取法获得问题的最优解；如果X连续，但f(x)是凸的，那可以通过梯度下降等⽅法获得最优解；如果X连续且f(x)⾮凸，虽说根据已有的近似求解法能够找到问题解，可解是否是最优的还有待考量，很多时候若初始值选择的不好，⾮常容易陷⼊局部最优值。

随着⽇常业务场景的复杂化，第三种问题经常遇见。如何有效地避免局部最优的困扰？模拟退⽕算法应运⽽⽣。其实模拟退⽕也算是启发式算法的⼀种，具体学习的是冶⾦学中⾦属加热-冷却的过程。由trick, 和在1983年所发明的，V.Čern在1985年也独⽴发明此演算法。不过模拟退⽕算法到底是如何模拟⾦属退⽕的原理？主要是将热⼒学的理论套⽤到统计学上，将搜寻空间内每⼀点想像成空⽓内的分⼦；分⼦的能量，就是它本⾝的动能；⽽搜寻空间内的每⼀点，也像空⽓分⼦⼀样带有“能量”，以表⽰该点对命题的合适程度。演算法先以搜寻空间内⼀个任意点作起始：每⼀步先选择⼀个“邻居”，然后再计算从现有位置到达“邻居”的概率。若概率⼤于给定的阈值，则跳转到“邻居”；若概率较⼩，则停留在原位置不动。⼀、模拟退⽕算法基本思想模拟退⽕其实也是⼀种贪⼼算法，但是它的搜索过程引⼊了随机因素。在迭代更新可⾏解时，以⼀定的概率来接受⼀个⽐当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝⾊点A，模拟退⽕算法会快速搜索到局部最优解B，但在搜索到局部最优解后，不是就此结束，⽽是会以⼀定的概率接受到右边的移动。也许经过⼏次这样的不是局部最优的移动后会到达全局最优点D，于是就跳出了局部最⼩值。

根据热⼒学的原理，在温度为T时，出现能量差为dE的降温的概率为p(dE)，表⽰为:

其中k是波尔兹曼常数，值为k=1.3806488(13)×10−23，exp表⽰⾃然指数，且dE<0。因此dE/kT<0，所以p(dE)函数的取值范围是(0,1)。满⾜概率密度函数的定义。其实这条公式更直观意思就是：温度越⾼，出现⼀次能量差为p(dE)的降温的概率就越⼤；温度越低，则出现降温的概率就越⼩。在实际问题中，这⾥的“⼀定的概率”的计算参考了⾦属冶炼的退⽕过程。假定当前可⾏解为x，迭代更新后的解为x_new，那么对应的“能量差”定义为：

其对应的“⼀定概率”为： 注：在实际问题中，可以设定k=1。因为kT可以等价于⼀个参数T。如设定k=2、T=1000，等于直接设定T=2000的效果。⼆、模拟退⽕算法描述1. 初始化：初始温度T（充分⼤），温度下限Tmin（充分⼩），初始解状态x(是算法迭代的起点)，每个T值的迭代次数L；2. 对l=1,2,...,L做第3⾄第6步；3. 产⽣新解x_new: (x_new=x+Δx)；4. 利计算增量Δf=f(x_new)−f(x)，其中f(x)为优化⽬标；5. 若Δf<0(若寻找最⼤值，Δf>0)则接受x_new作为新的当前解，否则以概率exp(−Δf/(kT))接受x_new作为新的当前解；6. 如果满⾜终⽌条件则输出当前解作为最优解，结束程序。(终⽌条件通常取为连续若⼲个新解都没有被接受时终⽌算法。)；7. T逐渐减少，且T>Tmin，然后转第2步。

三、模拟退⽕算法的优缺点模拟退⽕算法的应⽤很⼴泛，可以⾼效地求解NP完全问题，如货郎担问题(Travelling Salesman Problem，简记为TSP)、最⼤截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着⾊问题(Graph ColouringProblem)等等，但其参数难以控制，不能保证⼀次就收敛到最优值，⼀般需要多次尝试才能获得（⼤部分情况下还是会陷⼊局部最优值）。观察模拟退⽕算法的过程，发现其主要存在如下三个参数问题：　　(1) 温度T的初始值设置问题

　　温度TT的初始值设置是影响模拟退⽕算法全局搜索性能的重要因素之⼀、初始温度⾼，则搜索到全局最优解的可能性⼤，但因此要花费⼤量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。　　(2) 退⽕速度问题，即每个TT值的迭代次数

　　模拟退⽕算法的全局搜索性能也与退⽕速度密切相关。⼀般来说，同⼀温度下的“充分”搜索是相当必要的，但这也需要计算时间。循环次数增加必定带来计算开销的增⼤。　　(3) 温度管理问题

　　温度管理问题也是模拟退⽕算法难以处理的问题之⼀。实际应⽤中，由于必须考虑计算复杂度的切实可⾏性等问题，常采⽤如下所⽰的降温⽅式：

T=α×T.α∈(0,1).注：为了保证较⼤的搜索空间，α⼀般取接近于1的值，如0.95、0.9。　　关于爬⼭算法与模拟退⽕，有⼀个有趣的⽐喻：　　爬⼭算法：兔⼦朝着⽐现在⾼的地⽅跳去。它找到了不远处的最⾼⼭峰。但是这座⼭不⼀定是珠穆朗玛峰。这就是爬⼭算法，它不能保证局部最优值就是全局最优值。　　模拟退⽕：兔⼦喝醉了。它随机地跳了很长时间。这期间，它可能⾛向⾼处，也可能踏⼊平地。但是，它渐渐清醒了并朝最⾼⽅向跳去。这就是模拟退⽕。附上模拟退⽕算法伪代码：四. 使⽤模拟退⽕算法解决旅⾏商问题　　旅⾏商问题 ( TSP , Traveling Salesman Problem ) ：有N个城市，要求从其中某个问题出发，唯⼀遍历所有城市，再回到出发的城市，求最短的路线。　　旅⾏商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。　　使⽤模拟退⽕算法可以⽐较快的求出TSP的⼀条近似最优路径。（使⽤遗传算法也是可以的，我将在下⼀篇⽂章中介绍）模拟退⽕解决TSP的思路：1. 产⽣⼀条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )2. 若L(P(i+1)) < L(P(i))，则接受P(i+1)为新的路径，否则以模拟退⽕的那个概率接受P(i+1) ，然后降温3. 重复步骤1，2直到满⾜退出条件　　产⽣新的遍历路径的⽅法有很多，下⾯列举其中3种：1. 随机选择2个节点，交换路径中的这2个节点的顺序。2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。3. 随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后⾯。五. 算法评价 模拟退⽕算法是⼀种随机算法，并不⼀定能找到全局的最优解，可以⽐较快的找到问题的近似最优解。 如果参数设置得当，模拟退⽕算法搜索效率⽐穷举法要⾼。