计算机算法设计与分析 新型算法.ppt

文档介绍：新型算法四川大学计算机学院左劼算法设计 1 .新型算法的引入?基本的确定性算法在很多时候不能满足要求?在现实世界中,存在很多现象,能自发地呈现很好的性质,虽然可能还不确切了解这些现象的本质?从模仿这些现象出发而设计的算法,在很多时候能得到意想不到的优势一些典型的自然现象?退火过程?人脑的条件反射?生物的进化根据这些现象设计的算法?模拟退火算法?人工神经网络?进化计算模拟退火算法 5 .模拟退火算法原理?这是一种启发式随机搜索算法?将固体加温至充分高,使得每一粒子都具有充分的随机性?再让其徐徐冷却,粒子渐趋有序?在每个温度都达到平衡态,最后在常温时达到基态, 内能减为最小?如果急速降温(即为淬火)则不能达到最低点 Metropolis 准则?系统具有能量 E时位于一个特定状态的概率为: P = exp(-E/T)/Z(T) ?其中 E为温度 T时的内能, Z(T) 是一个归一化常数,使得 0<=P<=1 ,在算法过程中并不需要计算 Z(T) 。?如果其中一个磁体指向上方,则它对整个系统贡献一个单位的正的能量;指向下方则为负。?随着能量的提高,可能的状态数量是呈指数下降的,这就解释了准则中概率对 E的关系。?大致说来,高温给了系统更多的能量,使出现高能量的状态的概率增大。这也定性解释了准则中概率对 T的相依关系: ?在高温时,所有状态出现的概率分布大致平均, 而低温时,系统则集中分布在具有最低能量的状态周围。模拟退火算法的步骤 1) 初始化:初始温度 T( 充分大) ,初始解状态 S( 是算法迭代的起点),每个 T值的迭代次数 L 2)对 k=1 , ……,L做第(3) 至第 6步: 3)产生新解 S′ 4)计算增量Δ E=E(S ′)-E(S) ,其中 E(S) 为评价函数 5)若Δ E<0 则接受 S′作为新的当前解,否则以概率 exp(- Δ E/T) 接受 S′作为新的当前解. 6) 如果满足终止条件则输出当前解作为最优解,结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 7)T逐渐减少,且 T>0 ,然后转第 2步。