模拟退火算法综述

综合性介绍模拟退火算法

　　　　　　　　　　　　　　　《微计算机信息》1998年第14卷第5期

模拟退火算法综述

　A

SummaryOnTheSimulatedAnnealingAlgorithm

(434104　湖北荆州师范高等专科学校计算机系)　谢云

【摘要】本文综合介绍模拟退火算法的原理、实现形式、渐近收敛性、应用及其并行策略,对模拟退火算法给出一个简明、全面、客观的综合评价。

关键词:模拟退火算法,组合优化问题,NP完全问

题,并行算法

Abstract:Inthispaper,asummaryonprinciple,real2izableform,asymptoticconvergence,applicatiparalleltacticsofthesimalgoisgiven.A,,psiisgiven.ngAlgorithm,

CobinatorialOptimizationProblem,NondeterministicPolynomialComplete

Problem,ParallelAlgorithm

于固体退火过程:将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,。根据

Metropolis,e

(kT)-E,,E,

,ann。

f,温度T演化成控制参数t,:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→判断是否接受→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解。退火过程由冷却进度表(CoolingSched2每ule)控制,包括控制参数的初值t及其衰减因子 t、个t值时的迭代次数(称为一个Mapkob链的长度)L和停止条件S。

一问题的由来

三实现形式

从如下几个方面描述:

(1)数学模型:由解空间、目标函数和初始解三部

在自然科学、管理科学和工程技术等科技领域,存

在着大量的组合优化问题(CombinatorialOptimiza2tionProblem),其中的NP完全问题(NondeterministicPolynomialCompleteProblem),其求解时间随问题规模呈指数级增长,当规模稍大时就会因时间限制而失去可行性(Feasibility)。如著名的货郎担问题(Travel2ingSalesmanProblem,简记为TSP),即在n个顶点的完全图中找一条最小Hamilton回路,当图为对称图时,要从(n-1)! 2个可能解中找出最优者,需进行(n-1)! 2-1次比较,若用每秒运算一亿次的计算机,n=10时只需010018秒,n=20时就需19年,n=30时则猛增为114×1015年。显然,如此求其精确解是不可行的。

为解决这类问题,人们提出了许多近似算法。但这些算法或因过于注意个别问题的特征而缺乏通用性,或因所得解强烈地依赖初始解的选取而缺乏实用性。模拟退火算法(SimulatedAnnealingAlgorithm)就是对其中的局部搜索算法(LocalSearchAlgorithm)改进而提出的。　　

分组成。

解空间:对所有可能解均为可行解的问题定义为可能解的集合,对存在不可行解的问题,或限定解空间为所有可行解的集合,或允许包含不可行解但在目标函数中用罚函数(PenaltyFunction)惩罚以致最终完全排除不可行解;

目标函数:对优化目标的量化描述,是解空间到某个数集的一个映射,通常表为若干优化目标的一个和式,应正确体现问题的整体优化要求且较易计算,当解空间包含不可行解时还应包括罚函数项;

初始解:是算法迭代的起点,试验表明,模拟退火算法是健壮的(Robust),即最终解的求得不十分依赖初始解的选取,从而可任意选取一个初始解。

(2)新解的产生和接受机制:由四个步骤构成一轮试验。

首先,按某种随机机制由当前解产生一个新解,通常通过简单变换(如对部分元素的置换、互换或反演等)产生,可能产生的新解构成当前解的邻域;

其次,计算新解伴随的目标函数差,一般由变换的

二模拟退火算法

模拟退火算法提出于本世纪80年代初,其思想源

—66—

综合性介绍模拟退火算法

软件时空　　　　　　　　　　　　　　　　　　　　　　　　　　　　()改变部分直接求得;第三,由接受准则,即新解更优,或恶化但满足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—

综合性介绍模拟退火算法

　　　　　　　　　　　　　　　《微计算机信息》1998年第14卷第5期

lem)、独立集问题(IndependentSetProblem)、图着

成试验的处理机直接对公共存贮区的当前解进行下一轮试验,此时其它处理机可能会修改当前解,各处理机的结果可能发生混乱,但随着控制参数t值的减小,接受概率越来越小,解也渐趋有序直至最终排除混乱。如图2所示,其中每条线段表示一个试验,在线段错开处可能发生混乱。

对上述并行策略,操作并行中可并行的步骤数受具体问题的限制,整个算法只能同步并行,但不同步骤可分别并行。独立试验并行实际上相当于P台单机分别串行,最后从P个结果中选出最优者所以并不能。(,5(,可望得到较好的解或较高,虽然该方法仍是同步并行的,但可较好的发挥并行计算的优越性,是一种很好的并行方法。区域分裂是完全异步并行的,加速和效率都很高,是一种较好的并行方法,但要求定义空间允许分裂,同时分裂方法还要能反映整体优化要求(如TSP就要求分裂的各个区间必须相变),此外,区域分裂法也包含有混乱松驰的思想。混乱松驰法采用“不怕出错”的思想,是一种高效的异步并行算法,但其渐近收敛性尚待进一步研究,此外,此方法在实际应用时需作适当调整,避免进程中的混乱影响最终结果。　　

色问题(GraphColouringProblem)、调度问题

(SchedulingProble)、划分问题(PartitionProblem)以及布局问题(PlacementProblem),均以较高的效率得到了较好的结果。　　

六并行策略

模拟退火算法是一种随机近似算法,所求解的质

量有赖于大量的试验。随着问题规模的增大和对解的质量要求的提高,所需时间也随之增长,而冷却进度表并不能从根本上提高算法的效率,解决的办法是将算法并行实现以提高其性能。

算法中每轮试验的后三个步骤均依赖于前一步聚的结果,故四个步骤只能串行执行,组合优化问题的特点,。

(1):P,1所示,其

。

图1操作并行示意图

(2)试验并行:由多个处理机同时并行试验,根据

对各处理机的中间结果是否综合取舍,又分为两种形式。

独立试验并行,由P台处理机各自独立地试验并完成整个算法,最后比较所得的P个结果并从中选出最优者。

协同试验并行:P台处理机同时开始试验,分别产生P个新解并作出判断,对所有满足接受准则者按某个法则5选择一个接受,其余的全部舍弃,再在此基

础上进行下一轮试验。

七结论

综上所述,模拟退火算法是一种通用、高效、健壮、

可行的拟物型随机近似算法,并且可以较容易地并行实现以进一步提高运行效率,适合求解大规模组合组合优化问题特别是NP完全问题,因此具有很大的实用价值。同时由于其讨论涉及随机分析、Mapkob理论、渐近收敛性、统计分析方法和并行算法等学科,所以其研究还具有重要的理论意义,此外,对模拟退火算法作一些局部或策略上的修改,还可得到一些推广或变异形式,此外不再赘述。

作者简介谢云,荆州师范高等专科学校计算机系主任、副教授,武汉大学计算机软件工程国家重点实验室客座研究员,湖北省有突出贡献的中青年专家。主要从事计算机软件和并行算法研究。参加了八六三项目“非数值计算的并行算法”并负责模拟退火算法的研究。

(收稿日期:98,6,10)

图2混乱松驰并行示意图

(3)区域分裂并行:将定义空间分裂成P个子空

间,由P台处理机分别在这些子空间上试验。

(4)混乱松驰并行:各处理机同时开始试验,先完

—68—

本文来源：https://www.bwwdw.com/article/smkm.html