第八章 启发式算法.ppt

第八章_启发式算法binatorialOptimizationandDesignofAlgorithm1第八章启发式算法本章介绍的启发式算法也称智能算法、现代优化算法,自20世纪80年代初以来已得到深入研究和广泛应用,主要包括模拟退火算法、神经网络算法、遗传算法、,通过与组合优化求解进行类比,找出它们的一些共性,,有一定的普适性,、相互渗透、§1模拟退火算法§2神经网络算法§3遗传算法3第八章启发式算法§1模拟退火算法模拟退火(SimulatedAnnealing,简记SA),它来源于固体的退火过程,,改善切削加工性;消除残余应力,稳定尺寸,减少变形与裂纹倾向;细化晶粒,调整组织,,它的所有分子在状态空间D中自由运动,,这些分子逐渐停留在不同的状态,系统能量逐渐下降,最后在常温时达到基态,分子重新以一定的结构排列,§1模拟退火算法一、原理与步骤进一步研究表明,,在温度T,分子停留在状态r满足Boltzmann概率分布其中,E(r)表示状态r的能量,kB>0为B–常数,(T)为概率分布的标准化因子Metropolis准则:如果,则接受新状态,;T=T(t)为一随时间t增加而下降的参数,,,会如何?5第八章启发式算法金属物体组合优化问题状态能量最低的状态最优解能量费用函数解模拟退火算法的基本原理:称为Metropolis过程1、给定温度t及点x0,计算函数值f(x0);2、随机产生扰动,得到新点x1=x0+,计算f(x1)及;3、若,则接受新点,作为下一次模拟的出发点;4、若,则计算新点接受概率,,产生[0,1]区间上均匀分布的伪随机数r,若则接受新点作为下一次模拟的出发点;否则放弃新点,,重复M-过程,§1模拟退火算法令控制参数t担当固体退火过程中温度的角色,对于t的每一取值,算法采用Metropolis过程,持续进行“产生新解——判断——接受/舍弃”的迭代过程而达到该“温度”下的“平衡点”,随着参数t徐徐“降温”并趋向于零时,:Step1任选一初始解xi0;xi=xi0;k=0;t0=,则到Step3;否则,从邻域N(xi)中随机选取一xj,计算;若,则xi=xj,否则若时,则xi=xj;+1=d(tk);k=k+1;若满足停止条件,终止计算;否则,(衰减函数)在(0,1)之间均匀分布的伪随机数7第八章启发式算法在上述的SA算法中,,它表明在同一个温度tk时,;迭代步数增加;,如果这个解更好,则采用集中策略,,采用扩散策略,,模拟退火过程是从一个状态到另一个不断地随机游动,{X(k)}k=0,1,2,…为随机变量序列,X(k)=i称在时刻k处于状态i,i∈,,P{X(n)=j︱X(1)=i1,X(2)=i2,…,X(n-1)=i}=P{X(n)=j︱X(n-1)=i}i1,i2,…,,i,j∈{X(k)}k=0,1,2,…,§1模拟退火算法模拟退火算法主要可以分为两类:第一类为时齐算法,对每一个固定的t,计算对应的Markov链,直至达到一