模拟退火算法综述

综合性介绍模拟退火算法

　　　　　　　　　　　　　　　　　《微计算机信息》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—