gusucode.com > 十大算法matlab程序说明 > 十大算法matlab程序说明/模拟退火算法/模拟退火算法.txt
模拟退火算法 作者:佚名 来源:转载 成都理工数学实验室 发布时间:2008-4-13 9:59:45 减小字体 增大字体 模拟退火算法 模拟退火算法(Simulated Annealing,简称SA算法)是模拟加热熔化的金属的退火过程,来寻找全局最优解的有效方法之一。 模拟退火的基本思想和步骤如下: 设S={s1,s2,…,sn}为所有可能的状态所构成的集合, f:S—R为非负代价函数,即优化问题抽象如下: 寻找s*∈S,使得f(s*)=min f(si) 任意si∈S (1)给定一较高初始温度T,随机产生初始状态S (2)按一定方式,对当前状态作随机扰动,产生一个新的状态S’ S’=S+sign(η).δ 其中δ为给定的步长, η为 [-1,1]的随机数 计算Δ=f(S’)-f(S) (3)若Δ<0,则令S=S’,转第(5)步 (4)若Δ≤0,则以概率exp(-Δ/T)接受S’,即S=S’ 具体操作:产生一个在[0,1]上服从均匀分布的随机数x,若x<exp(-Δ/T),则S=S’ 否则S保持不变 (5)按一定方式降温,使T= , < Ti, 如: =αTi, 习惯上取α∈(0.8,0.9999) (6)检查退火是否结束 是——转向第(7)步 否——转向第(2)步 (7)以当前Si作为最优解输出 注:1、结束标志:温度是否小于某一阀值(循环次数) f的值变化是否明显 2、初始温度的高低:下降是否充分慢对结果有影响