[经济学]模拟退火算法.pptVIP

第三篇 模拟退火算法 一、模拟退火算法的基本思想 二、模拟退火算法的实现 三、模拟退火算法的应用 一、模拟退火算法的基本思想 启发 注意到一个自然规则：物质总是趋于最低的能态。 水总是向低处流。 电子总是向最低能级的轨道排布。 最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。 模拟退火算法的设计与原理猜想 物质自动趋向的最低能态与函数最小值之间有相似性！！！ 模拟退火算法的设计与原理物理模型——固体退火 退火俗称固体降温 先把固体加热至足够高温，使固体中所有粒子处于无序的状态（最高的熵值），然后将温度缓慢下降，粒子渐渐有序（熵值下降），这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态（最低的熵值）。 模拟退火算法的设计与原理类比 根据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 链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机有哪些信誉好的足球投注网站过程。 模拟退火算法的实现算法描述 Simulated Annealing (SA) Algorithm: 1 初始化：系统初温T ，初始状态S0 ，马尔可夫链长L，终止条件AIM 2 while (true) 2.1 对于k=1..L, 执行2.1.1到2.1.4 2.1.1 从当前解S,产生新解SN ，他们之间的差值为D. 2.1.2 若 (D0 或 满足概率 exp(-D/T)),则 S:=SN. 2.1.3 若(当前解S当前最优解 SB),则SB:=S. 2.1.4 if (T趋于0 或 连续AIM次迭代物最优值), 则可近似认为SB为最优，转3. 2.2 降温 2.3 S=SB 3 输出 SB 模拟退火算法的实现实现技术 冷却进度表、邻域结构和新解产生器、接受准则和随机数产生器一起构成算法的三大支柱。 从算法结构可知，新状态产生函数、新状态接受函数、退温函数、退火结束准则以及初始温度是直接影响算法优化结果的主要环节。 模拟退火算法的实现冷却进度表 冷却进度表包含：初始温度，退温速率，退火结束准则， Markov 链长。 它直接决定了算法的效率，需要大量试验才能得出其最佳的组合。 模拟退火算法的优化回火技术 如图所示，若粒子开始处于D状态，若让能量逐渐减小，则粒子最终到达的是A 点(局部最低点)而不是B(全局最低点)点，这是我们所不希望的。 解决的办法是对系统经常地”摇动”一下，就很可能把粒子从D点越过C点摇到B 点，而把它摇到A点的可能性减小。 这就是回火技术：降温后以一定概率升温，引入产生函数扰动因子，来控制搜寻全局最优值的范围。 模拟退火算法的应用前景NP问题与计算复杂性理论 计算复杂性理论通俗的解释： 多项式时间: 运行时间最多是输入量的多项式函数。 P类问题是可被“在多项式时间运行”