企业官网建设流程全解析

常见的启发式/元启发式算法，可以先按下面这个脉络理解：

局部搜索类（Local Search）

Hill Climbing / 爬山算法

Simulated Annealing（SA，模拟退火）

参考：
博客：模拟退火（速通教程） - 程序员郭半仙 - 博客园
视频：【大学生速通模拟退火算法】 https://www.bilibili.com/video/BV1Hb4y1J7PN/?share_source=copy_web&vd_source=755ba288dfa41ccc7be2a4b731e37a4d

Q1:模拟退火是什么算法？
模拟退火是模拟物理上退火方法，通过N次迭代（退火），逼近函数的上的一个最值（最大或者最小值）。

Q2:模拟退火为什么可行？
讨论这个问题需要理解一下物理原型是怎么样的，也就是原来是怎么“退火”的：

模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。

注意标粗字体：

温度高->运动速度快（温度低->运动速度慢）
温度是缓慢（想象成特别慢的那种）降低的
温度基本不再变化后，趋于有序(最后内能达到最小，也就是接近最优)

Q3：怎么做？

模拟退火就是一种循环算法。

① 我们先设定一个初始的温度T（这个温度会比较高，比如2000）
②每次循环都退火一次。（具体怎么操作后面详解）

③然后降低T的温度，我们通过让T和一个“降温系数”ΔT（一个接近1的小数，比如0.99)相乘，达到慢慢降低温度的效果，直到接近于0（我们用eps来代表一个接近0的数(比如0.00001)，只要T>eps就可以退出循环了）

所以总的来说，用伪代码表示退火的流程是这样的：

double T = 2000; //代表开始的温度 double dT = 0.99; //代表系数delta T double eps = 1e-14; //相当于0.0000000000000001 while(T > eps) { //-------------- //这里是每一次退火的操作 //-------------- T = T * dT; //温度每次下降一点点， T * 0.99 }

退火详解：

1. 我们先随机找一点x0 ，不论是哪个点都可以，随机！（不超过定义域就行）。

   这个点作为我们的初始值（相当于物体里的一个粒子）

2. 再找到一点f(x0),来代表x0所对应的函数值

3. 现在正式开始退火！

   刚才我们说了x0相当于是一个粒子，所以我们会进行一个无序运动，也就是向左或者向右随机移动

   是的，是随机移动，可能向左，也可能向右，但是请记住一个关键点：移动的幅度和当前的温度T有关。

   温度T越大，移动的幅度越大。温度T越小，移动的幅度就越小。这是在模拟粒子无序运动的状态。

4. 接受(Accept)更"好"的状态

   假设我们移动到了x1处，那么这个点对应的f(x1)很明显答案是优于（大于）当前的f(x0)的

5. 因此我们将答案进行更新。也就是将初始值进行替换：x0=x1,f(x0)=f(x1)。这是一种贪心的思想。

6. 以一定概率接受(Accept)更差的状态

   这是退火最精彩的部分。

   为什么我们要接受一个更加差的状态呢？因为可能在一个较差的状态旁边会出现一个更加高的山峰

   如果我们鼠目寸光，只盯着右半区，很容易随着温度的下降、左右跳转幅度的减小而迷失自己，最后困死在小山丘中。

   而我们如果找到了左边山峰的低点，以一定的概率接受了它（概率大小和温度以及当前的值的关键程度有关），会在跳转幅度减少之前，尽可能找到最优点。

7. 那么我们以多少的概率去接受它呢？我们用一个公式表示（这个公式我们只需记住，这是科学家推导出来的结论）：

   别慌！很简单！我们来理解一下这里面的变量：

   1. e是自然对数，约等于2.71。我们可以把右上角这一坨值ΔfkT看成一个整体x:
      的图形画出来是这样的：

      因为我们想要函数ex来代表一个概率值，所以我们只需要关注x为负数的部分即可：

      负数部分的值域是在(0,1)开区间内，x越小，越接近0，越大越靠近1。

      因为在0到1之间，所以这个值相当于是概率了。比如ex=0.97，那么我们接受的概率就是97%

      而正数部分的值域会大于1，也就是说概率会超过100%，所以会一定选（其实是上一种找到更优的情况）

   2. kT:
      k其实是个物理学常数，我们在代码中不会用到。
      T很简单，就是当前的温度。所以实际上这个分母就是T，k当做1使用。

   3. Δf :
      我们着重讲一下什么是Δf。
      其实从前面的函数ex中可以发现，Δf必须是个负数！
      我们想要函数ex来代表一个概率值，一定要让它的值域属于(0,1)，所以Δf / kT必须是个负数。但是kT在我们的模拟中一定是正数，那么Δf必须是个负数！
      其实Δf就是当前解的函数值与目标解函数值之差，Δf=−|f(x0)−f(x1)|，并且一定是个负数。这个需要具体问题具体分析。
      比如现在我们求一个函数的最大值，那么如果f(x0)<f(x1)了，那就说明结果变好了，我们肯定选择它（见第4点）
      如果f(x0)>f(x1)，那就说明结果变差了，我们需要概率选择它，因此Δf=−(f(x0)−f(x1))
      
      所以总结一下就是：
      随机后的函数值如果结果更好，我们一定选择它(即x0=x1,f(x0)=f(x1))
      随机后的函数值如果结果更差，我们以的概率接受它
      
      
      Search（TS，禁忌搜索）
      禁忌搜索算法是局部搜索算法的推广，算法特点为禁止重复前面的工作，有助于跳出局部最优点。

• Variable Neighborhood Search（VNS，变邻域搜索）

②进化算法类（Evolutionary Algorithms）

• Genetic Algorithm（GA，遗传算法）
• Evolution Strategy（ES）
• Differential Evolution（DE，差分进化）

③群智能类（Swarm Intelligence）

• Particle Swarm Optimization（PSO，粒子群）
• Ant Colony Optimization（ACO，蚁群）
• Artificial Bee Colony（ABC，人工蜂群）

④其他常见元启发式

• GRASP（贪婪随机自适应搜索）
• Iterated Local Search（ILS，迭代局部搜索）
• Large Neighborhood Search（LNS，大邻域搜索）
• Adaptive Large Neighborhood Search（ALNS，自适应大邻域搜索）
• Hybrid Genetic Search（HGS，混合遗传搜索）