文档介绍：第三篇模拟退火算法一、模拟退火算法的基本思想二、模拟退火算法的实现一、模拟退火算法的基本思想启发注意到一个自然规则:物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。模拟退火算法的设计与原理猜想物质自动趋向的最低能态与函数最小值之间有相似性!!!我们能不能设计一种算法求函数最小值,就像物质”自动”地趋向最低能态?降温图像离散函数图像相似性?最小值最低能态模拟退火算法的设计与原理物理模型——固体退火退火俗称固体降温先把固体加热至足够高温,使固体中所有粒子处于无序的状态(最高的熵值),然后将温度缓慢下降,粒子渐渐有序(熵值下降),这样只要温度上升得足够高,冷却过程足够慢,则所有粒子最终会处于最低能态(最低的熵值)。最低能态时间温度模拟退火算法的设计与原理类比根据Metropolis准则,粒子在温度T时趋于热平衡的概率为其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。可以设计算法:将系统熵值类比为函数值F,来模拟这个退火过程。模拟退火算法的设计与原理提出模拟退火算法(SA)就是这样一个将退火过程中系统熵值类比为目标函数值F,来模拟这个退火系统的算法。模拟退火算法的设计与原理数学模型——马尔可夫过程模拟退火算法在概率理论上有一个很好的数学模型的来解释:马尔可夫(Markov)过程。马尔可夫过程及马尔可夫链简介马尔可夫过程是一个随机过程,它具备这样的性质,即可知tm时刻过程处在状态的条件下,在时刻tm以后过程将要到达的状态的情况与该时刻以前过程所处的状态无关。这个性质也称为过程的无后效性或过程的马尔可夫性。对一个状态空间(I)离散、参数为非负整数的随机过程 ,若它满足条件: 这样的随机过程称为马尔可夫链。马尔可夫链在t时刻的一步条件转移概率也称作t时刻的状态转移(i→j)概率。显然有:二、模拟退火算法的实现SA算法在Markov链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解。这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。模拟退火算法的实现思想SA算法的计算过程可视为重复递减控制参数值(温度)并进行Metropolis算法的迭代过程。一次Metropolis算法是指,对于控制参数t的每一取值,算法在Markov链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。