浅析模拟退火算法

前面几篇主要是解释仿生群体行为的启发式算法，而本文所述模拟退火算法则是一种通用的概率优化算法(虽然求解用到概率手段，但是得到的解往往是全局最优或次优的解)，以下通过一些浅显的剖析来突出该算法的特点。其实谈到这个算法个人比较亲切，这是算是在原理上和我专业最接近的一个优化算法，它的原理主要是来自固体退火原理，其主要过程是将固体加温至充分高，再让其以一定的速度缓慢冷却。

相关理论&原理

• 众所周知，在升温时加温时，固体内部粒子(或者叫分子)随温度升高变成无序状，其内能逐渐增大(热力学第一定律，

, 吸收的热量

增大导致内能增大)

• 在缓慢冷却时由于释放热量内部粒子逐渐趋于有序熵变降低，且如果冷却的过程温度足够缓慢，则冷却中任意温度下固体都能达到热平衡，此时是该固体在该温度下的内能最小状态，因为能量越低越稳定

• 内能为目标函数，目标是让内能达到最低状态，即全局最小值(求最大值时可对目标函数取倒数或相反数)
• 升温降温是改变这种热平衡的重要推力，所以在温度变化过程中一定会存在状态切换
• 如果在某一个冷却温度下需要相当长时间(即有状态切换不能平稳收敛)才能达到热平衡，则需要重新进行重要性采样(重要性是指可以让内能下降贡献比较大的那个状态)

状态切换(核心搜索规则)

算法思路

• 在算法运用时，固体在温度T时的一个状态对应一个解向量x，状态切换则是在搜索自变量可行解空间，温度T为控制参数，随着T逐渐降低，内能E也会逐渐降低，直到趋于全局内能最低状态时此时的状态才很难再发生切换
• 温度T由冷却进度表控制，冷却进度表是一个逻辑概念，包含温度初值，的冷却衰减函数，马尔科夫链长度(这里的马尔科夫链是指固定温度T_i的条件下重复执行的次数，重复的环节是每次的状态会接受扰动而不相同，之所以为马尔科夫链是因为当前状态只由上一次的状态决定，存在状态转移关系，为的是找到这一个温度下的最低内能)，终止温度， 它的核心作用是使系统尽量达到准平衡，以使算法在有限的时间内逼近最优解

本质上来说，不知道读者有没有这样的疑问，如果我们一直无限制的降低外界

，那么内能不就一直下降不收敛吗，笔者在学习时其实有过这样的疑问，我是这样想的我们所理解的内能是基于物理化学规律的，而这里的内能是我们的目标函数，目标函数的复杂及收敛程度不同，也就是会存在你就算不断降低外界温度，这个内能也不会怎么改变，因为这里的内能只由状态决定，而下降温度只是会影响状态切换的概率而已，并且当内能全局最低时，此时的状态也不会轻易切换状态了(因为找不到比他内能还低的新状态)

算法步骤

一般性条件

• 初始温度可以选择适度高，因为有较小的转移概率避免随机游走，且迭代次数长
• 平衡时间可以适度长，即马氏链长度，可以跳出局部最优

• 降温过程可以稍微缓慢，即可更广泛的搜索自变量空间

注意：即使最后得到了"全局最优解x"，即使此时的接受概率最小，但是仍然有可能接受比全局最优解差的解(只是说明状态切换的概率很小但不是没有，甚至可能最优解的转移概率值大于了随机数从而发生状态切换选择了次优解)，所以一般算法输出会把历史最优解一并输出

参数选择

一些应用

因为该算法的自变量是固体粒子的状态，如果自变量是一个向量，则说明一个自变量的每一维度可以代表固体中的一个粒子，这个优势天然的就和TSP旅行商问题结合在一起，所以说模拟退火算法更能解决一些0-1指派问题、背包问题、生产调度问题等真实业务场景

话说有机会可以这么试试，踏遍祖国大好河山