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