2026/9/12 19:11:33
FEATURED · 精选文章 
常见的启发式/元启发式算法可以先按下面这个脉络理解局部搜索类Local SearchHill Climbing / 爬山算法Simulated AnnealingSA模拟退火参考博客模拟退火速通教程 - 程序员郭半仙 - 博客园视频【大学生速通模拟退火算法】 https://www.bilibili.com/video/BV1Hb4y1J7PN/?share_sourcecopy_webvd_source755ba288dfa41ccc7be2a4b731e37a4dQ1:模拟退火是什么算法模拟退火是模拟物理上退火方法通过N次迭代退火逼近函数的上的一个最值最大或者最小值。Q2:模拟退火为什么可行讨论这个问题需要理解一下物理原型是怎么样的也就是原来是怎么“退火”的模拟退火算法的思想借鉴于固体的退火原理当固体的温度很高的时候内能比较大固体的内部粒子处于快速无序运动当温度慢慢降低的过程中固体的内能减小粒子的慢慢趋于有序最终当固体处于常温时内能达到最小此时粒子最为稳定。注意标粗字体温度高-运动速度快温度低-运动速度慢温度是缓慢想象成特别慢的那种降低的温度基本不再变化后趋于有序(最后内能达到最小也就是接近最优)Q3怎么做模拟退火就是一种循环算法。① 我们先设定一个初始的温度T这个温度会比较高比如2000②每次循环都退火一次。具体怎么操作后面详解③然后降低T的温度我们通过让T和一个“降温系数”ΔT一个接近1的小数比如0.99)相乘达到慢慢降低温度的效果直到接近于0我们用eps来代表一个接近0的数(比如0.00001)只要Teps就可以退出循环了所以总的来说用伪代码表示退火的流程是这样的double T 2000; //代表开始的温度 double dT 0.99; //代表系数delta T double eps 1e-14; //相当于0.0000000000000001 while(T eps) { //-------------- //这里是每一次退火的操作 //-------------- T T * dT; //温度每次下降一点点 T * 0.99 }退火详解我们先随机找一点x0 不论是哪个点都可以随机不超过定义域就行。这个点作为我们的初始值相当于物体里的一个粒子再找到一点f(x0),来代表x0所对应的函数值现在正式开始退火刚才我们说了x0相当于是一个粒子所以我们会进行一个无序运动也就是向左或者向右随机移动是的是随机移动可能向左也可能向右但是请记住一个关键点移动的幅度和当前的温度T有关。温度T越大移动的幅度越大。温度T越小移动的幅度就越小。这是在模拟粒子无序运动的状态。接受(Accept)更好的状态假设我们移动到了x1处那么这个点对应的f(x1)很明显答案是优于大于当前的f(x0)的因此我们将答案进行更新。也就是将初始值进行替换x0x1,f(x0)f(x1)。这是一种贪心的思想。以一定概率接受(Accept)更差的状态这是退火最精彩的部分。为什么我们要接受一个更加差的状态呢因为可能在一个较差的状态旁边会出现一个更加高的山峰如果我们鼠目寸光只盯着右半区很容易随着温度的下降、左右跳转幅度的减小而迷失自己最后困死在小山丘中。而我们如果找到了左边山峰的低点以一定的概率接受了它概率大小和温度以及当前的值的关键程度有关会在跳转幅度减少之前尽可能找到最优点。那么我们以多少的概率去接受它呢我们用一个公式表示这个公式我们只需记住这是科学家推导出来的结论别慌很简单我们来理解一下这里面的变量e是自然对数约等于2.71。我们可以把右上角这一坨值ΔfkT看成一个整体x:的图形画出来是这样的因为我们想要函数ex来代表一个概率值所以我们只需要关注x为负数的部分即可负数部分的值域是在(0,1)开区间内x越小越接近0越大越靠近1。因为在0到1之间所以这个值相当于是概率了。比如ex0.97那么我们接受的概率就是97%而正数部分的值域会大于1也就是说概率会超过100%所以会一定选其实是上一种找到更优的情况kT:k其实是个物理学常数我们在代码中不会用到。T很简单就是当前的温度。所以实际上这个分母就是Tk当做1使用。Δ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))所以总结一下就是随机后的函数值如果结果更好我们一定选择它(即x0x1,f(x0)f(x1))随机后的函数值如果结果更差我们以的概率接受它SearchTS禁忌搜索禁忌搜索算法是局部搜索算法的推广算法特点为禁止重复前面的工作有助于跳出局部最优点。Variable Neighborhood SearchVNS变邻域搜索②进化算法类Evolutionary AlgorithmsGenetic AlgorithmGA遗传算法Evolution StrategyESDifferential EvolutionDE差分进化③群智能类Swarm IntelligenceParticle Swarm OptimizationPSO粒子群Ant Colony OptimizationACO蚁群Artificial Bee ColonyABC人工蜂群④其他常见元启发式GRASP贪婪随机自适应搜索Iterated Local SearchILS迭代局部搜索Large Neighborhood SearchLNS大邻域搜索Adaptive Large Neighborhood SearchALNS自适应大邻域搜索Hybrid Genetic SearchHGS混合遗传搜索
启发式算法思想汇总
常见的启发式/元启发式算法可以先按下面这个脉络理解局部搜索类Local SearchHill Climbing / 爬山算法Simulated AnnealingSA模拟退火参考博客模拟退火速通教程 - 程序员郭半仙 - 博客园视频【大学生速通模拟退火算法】 https://www.bilibili.com/video/BV1Hb4y1J7PN/?share_sourcecopy_webvd_source755ba288dfa41ccc7be2a4b731e37a4dQ1:模拟退火是什么算法模拟退火是模拟物理上退火方法通过N次迭代退火逼近函数的上的一个最值最大或者最小值。Q2:模拟退火为什么可行讨论这个问题需要理解一下物理原型是怎么样的也就是原来是怎么“退火”的模拟退火算法的思想借鉴于固体的退火原理当固体的温度很高的时候内能比较大固体的内部粒子处于快速无序运动当温度慢慢降低的过程中固体的内能减小粒子的慢慢趋于有序最终当固体处于常温时内能达到最小此时粒子最为稳定。注意标粗字体温度高-运动速度快温度低-运动速度慢温度是缓慢想象成特别慢的那种降低的温度基本不再变化后趋于有序(最后内能达到最小也就是接近最优)Q3怎么做模拟退火就是一种循环算法。① 我们先设定一个初始的温度T这个温度会比较高比如2000②每次循环都退火一次。具体怎么操作后面详解③然后降低T的温度我们通过让T和一个“降温系数”ΔT一个接近1的小数比如0.99)相乘达到慢慢降低温度的效果直到接近于0我们用eps来代表一个接近0的数(比如0.00001)只要Teps就可以退出循环了所以总的来说用伪代码表示退火的流程是这样的double T 2000; //代表开始的温度 double dT 0.99; //代表系数delta T double eps 1e-14; //相当于0.0000000000000001 while(T eps) { //-------------- //这里是每一次退火的操作 //-------------- T T * dT; //温度每次下降一点点 T * 0.99 }退火详解我们先随机找一点x0 不论是哪个点都可以随机不超过定义域就行。这个点作为我们的初始值相当于物体里的一个粒子再找到一点f(x0),来代表x0所对应的函数值现在正式开始退火刚才我们说了x0相当于是一个粒子所以我们会进行一个无序运动也就是向左或者向右随机移动是的是随机移动可能向左也可能向右但是请记住一个关键点移动的幅度和当前的温度T有关。温度T越大移动的幅度越大。温度T越小移动的幅度就越小。这是在模拟粒子无序运动的状态。接受(Accept)更好的状态假设我们移动到了x1处那么这个点对应的f(x1)很明显答案是优于大于当前的f(x0)的因此我们将答案进行更新。也就是将初始值进行替换x0x1,f(x0)f(x1)。这是一种贪心的思想。以一定概率接受(Accept)更差的状态这是退火最精彩的部分。为什么我们要接受一个更加差的状态呢因为可能在一个较差的状态旁边会出现一个更加高的山峰如果我们鼠目寸光只盯着右半区很容易随着温度的下降、左右跳转幅度的减小而迷失自己最后困死在小山丘中。而我们如果找到了左边山峰的低点以一定的概率接受了它概率大小和温度以及当前的值的关键程度有关会在跳转幅度减少之前尽可能找到最优点。那么我们以多少的概率去接受它呢我们用一个公式表示这个公式我们只需记住这是科学家推导出来的结论别慌很简单我们来理解一下这里面的变量e是自然对数约等于2.71。我们可以把右上角这一坨值ΔfkT看成一个整体x:的图形画出来是这样的因为我们想要函数ex来代表一个概率值所以我们只需要关注x为负数的部分即可负数部分的值域是在(0,1)开区间内x越小越接近0越大越靠近1。因为在0到1之间所以这个值相当于是概率了。比如ex0.97那么我们接受的概率就是97%而正数部分的值域会大于1也就是说概率会超过100%所以会一定选其实是上一种找到更优的情况kT:k其实是个物理学常数我们在代码中不会用到。T很简单就是当前的温度。所以实际上这个分母就是Tk当做1使用。Δ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))所以总结一下就是随机后的函数值如果结果更好我们一定选择它(即x0x1,f(x0)f(x1))随机后的函数值如果结果更差我们以的概率接受它SearchTS禁忌搜索禁忌搜索算法是局部搜索算法的推广算法特点为禁止重复前面的工作有助于跳出局部最优点。Variable Neighborhood SearchVNS变邻域搜索②进化算法类Evolutionary AlgorithmsGenetic AlgorithmGA遗传算法Evolution StrategyESDifferential EvolutionDE差分进化③群智能类Swarm IntelligenceParticle Swarm OptimizationPSO粒子群Ant Colony OptimizationACO蚁群Artificial Bee ColonyABC人工蜂群④其他常见元启发式GRASP贪婪随机自适应搜索Iterated Local SearchILS迭代局部搜索Large Neighborhood SearchLNS大邻域搜索Adaptive Large Neighborhood SearchALNS自适应大邻域搜索Hybrid Genetic SearchHGS混合遗传搜索 
)
