模拟退火算法综述(2)

综合性介绍模拟退火算法

软件时空　　　　　　　　　　　　　　　　　　　　　　　　　　　　()改变部分直接求得;第三,由接受准则,即新解更优,或恶化但满足Metropolis准则,判断是否接受新解,对有不可行解而限定解空间仅包含可行解时,还需先判断其可行性;

最后,满足接受准则时进行当前解和目标函数值的迭代,否则舍弃新解。

(3)冷却进度表:即(t, t,L,S)。应使得t充

前邻域时,一般均可较快地探索到该邻域的最优解,从而无法再优化,总之,算法在有限时间内必定会现出解在连续M个Mapkob链中无任何改变的情况,即完全可以在有限时间内终止,因此从概率的角度是渐近收敛的。不过对于最坏情况的算法时间问题,还有待于进一步的研究和试验。　　

分大且衰减得充分慢、L足够大,S通常选为解在连续

M个Mapkob链中无任何改变时终止算法。

(4)伪程序:用k=M表示停止条件,Generate(jfromi)表示从当前解i产生新解j的产生过程,0,1〕内均匀分布的随机数,则算法的伪Random为〔

五应用实例

作为例子,给出解货郎担问题(TSP)的算法描述

如下:

(1):有nG=(V,E,,其中=}为边集,

D,回路,使路

程序如下:

PROCEDUREAnneal(t, t,L,M,VARi);BEGIN

　k:=0;t:=SE;　　p:=1TOLDO　　BEGIN

　　　Generate(jfromi);

　　　 f:=f(j)-f(i);{求最大值时改为 f:=f(i)-f(j)}

　　　IF( f<0)OR(EXP(- f t)>Random)

　　　THENBEGINi:=j;f:=f+ f;Accept:

=TRUEEND

():　8={(V1…Vn) (V1…Vn)为1,…,n的循环排列},其中(V1…Vn)表示回路V1→…→Vn→v1;

(3)目标函数:　f(V1…Vn)=2DVk,Vk

+1],k=1,…,n且约定vn+1=V1;

(4)初始解;不访就选为(1,…,n);

(5)新解的产生机制:由当前解经一次2-变换或3-变换得到,其中2-变换:随机选取两个项点p<q,

将路径Vp…Vq反向,即(V1…Vp…Vq…Vn)→V1…

Vp-1Vq…VpVq+1…Vn;

3-变换:随机选取顶点p≤q<r或r+1<p≤q,

将路径Vp…Vq插到Vr之后,即(v1…vp…vq…vr…

vn)→(v1…p-1v[q+1]…vrvp…vqvr+1…vn或(v1…vr…vp…vq…vn)→(v1…vrvp…vqvr+1…vp+1vq+1…vn;

(6)目标函数差:相对于2-变换和3-变换分别为2-变换: f=-D〔vp-1,vp〕-D〔vq,vq+1〕+D

　　END;

　IFNOTAcceptTHENk:=k+1ELSEk:=0

UNTILk=MEND;

四渐近收敛性

对上述算法,首先要考虑其可行性,即能否在有限

〔;3-变换: f=-D〔vp-1,vq〕+D〔vp,vq+1〕vp-1,

vp〕-D〔vq,Vq+1〕-D〔vr,vr+1〕+D〔vp-1,;vq+1〕+D〔vr,vp〕+D〔vq,vr+1〕

(7)接受准则:( f<0)OR(e～- f t

时间内得出结果,由于算法的随机性,转为讨论其渐近收敛性,即算法按渐近的概率原则是否收敛。其研究涉及到Mapkob理论,本文不拟深入讨论,可以证明:在多项式时间里算法渐近地收敛于一近似最优解,这个结果对于NP完全问题已是较好的了,下面仅对上述伪程序的运行过程作一简单分析。

对恶化解,随着t值的衰减,e- f t

>Random);

(8)新解的接受:实现当前解的迭代i:=j,同时

修正目标函数值f:=f+ f;

(9)冷却进度表:根据实际情况选择,通常较精细的冷却进度表可得到较好解但所需时间也较长,而粗略的冷却进度表所用时间较少但解往往也较差。

(10)程序;根据上述描述和算法的伪程序不难写出,此处不再列出。

笔者用该算法成功地解决了货郎担问题(Travel2ingSalesmanProble)、最大截问题(MaxCut

0-1背包问题(Zero-OneKnapsackProb2Problem)、

→∞,故t衰减

到一定程序时即不再接受,至于优化解,由于算法中产

生新解的邻域结构通常选得较简单(否则可能因专注个别问题特征而丧失算法通用性,或者因变成精确算法而导致算法不可行),因此在不能由解的恶化跳出当

—67—