基于模拟退火算法的应急物流仓库选址优化
第31卷第3期2010年6月
大连交通大学学报
J OURN AL OF DALIA N JI AOT ONG UNI VERS I TY
Vo.l31No.3
Jun.2010
文章编号:167329590(2010)0320102205
基于模拟退火算法的应急物流仓库选址优化
赵振亚,贺国先
(兰州交通大学交通运输学院,甘肃兰州730070)
摘要:论述了在应急物流管理中应急仓库优化选址问题,分析了应急物资仓库建立的必要性及重要性.
为了较准确的分析选址方案对仓库布局覆盖能力及其广义时间费用的影响,在合理假设的基础上,构建应急仓库选址问题的集合覆盖双层规划模型,既考虑配送过程中广义时间费用最小(上层目标),且满足服务范围覆盖整个区域的应急仓库数目最小(下层目标),并以模拟退火算法求解问题最优解.最后以实例分析证明模型和算法的有效性,为决策部门在灾害管理的灾害准备阶段科学合理进行应急仓库选址提供参考依据.
关键词:应急物流;仓库选址;双层规划;模拟退火算法
中图分类号:F252.24文献标识码:A
0引言
作为重要的灾时物资应急保障形式,应急物流是一种以政府为中心,健全应急管理法律法规、先进的信息平台和信息流转机制为支撑,以追求时间效益最大化和灾害损失最小化为目标的特殊物流活动.面对紧急突发性事件时,力求在最短的时间内有效整合政府和企业的资源,完成应急物资准确送抵物资需求地点的要求,一般性物流的经济效益原则将不再作为一个物流活动的中心目标加以考虑.
在应急物流管理中,应急仓库优化选址具有十分重要的作用,是应急灾害管理初期工作的基础,这项工作的决策合理与否决定灾害响应阶段工作能否顺利展开及快速实施.在应急物资保障及安排调度方面,Bryson和Crosby认为,城市在灾难发生后能否迅速做出适当的反应体现了一座城市的管理能力.城市管理能力是由可得资源和资本的多少,以及有效发挥这些资源最大效用的能力决定的[1].Steven和Shoou2Ji u n W ang等人针对应急系统区域性划分带来的问题,即影响城市应急服务质量,限制了救援服务的反应时间(排队和行进时间),提出了模拟退火算法,并且根据特定区域设计绩效评估体系[2].计国君提出应综合考虑救急物资的可重复利用和不可重复利用两种因素,并利用救灾物资与机会成本之间的关系建立应急物流配送的整数规划模型[3].围绕应急开始时间最早、出救点数目最少,刘春林等和方磊等人分别研究了连续消耗问题和应急系统优化选址问题[425].也有学者提出了制定应急物资保障计划的流程,构建了应急物资保障计划制定的数学模型,并应用运筹学的方法对其进行了优化,利用该模型可以选取各级应急物资保障资源点并计算各个资源点保障物资的数量[6].本文将应急管理灾害准备阶段[7]的应急仓库选址优化问题作为研究对象,重点考虑提供应急物资采购及储存的应急仓库,如何科学合理地确定开设位置,使其在处置突发应急事件时能够提供及时、有效的物资供应.
1应急物流应急仓库优化选址模型1.1问题的提出
应急物资仓库主要承担应急救灾物资的存放、理货、再包装等功能.与一般性仓库或配送中心优化选址不同,因无法预测灾害发生的时间与地点,应急仓库选址是在灾害发生前期所做的应
*收稿日期:2009212228
作者简介:赵振亚(1985-),女,硕士,助教,主要从事交通运输规划与管理、物流管理与供应链的研究E2m a i:l jilly-ya@163.co m.
第3期赵振亚,等:基于模拟退火算法的应急物流仓库选址优化103
急灾害准备工作,通常不涉及准确的需求信息,目的是在灾情发生时,能够以最快的速度整理物资、备货、配送,最大限度的节约时间.因此本文讨论不涉及仓库建设规模前提下的应急仓库的选址问题,重点研究某一区域中合理建设多个应急仓库,使得应急仓库的服务范围覆盖整个区域,且在仓库建设数目最小的情况下,物资配送过程中广义时间费用最小[829].
根据以上设定构建应急仓库选址问题的集合覆盖双层规划模型,并通过模拟退火算法求解此模型.
1.2建立模型
1.2.1问题的描述
图1无向连通图
将研究的问题描述为在给定的区域范围之内,在区域重要城市和交通通道地区设立必要数量的常设应急物资仓库,使应急仓库服务范围覆盖整个区域,使服务范围覆盖整个区域的应急仓库数目最小,且满足配送过程中广义时间费用最小.如图1所示,G(V,E)为无向连通图,其中:V 表示节点集合,E表示边集合,V={v1,v2,,, v n},E={e1,e2,,,e m},C ij为E的权值(节点i到节点j之间的广义时间费用).邻接矩阵为C= (c ij)n@n.则存在V c A V使得V中所有节点被V c覆盖,使得|V c|最小,并且V c所覆盖路径广义时间费用最小.
1.2.2应急仓库优化选址模型
模型参数:
x i表示在i地建设应急物流仓库,此值为1,否则为0;
w i表示在i地建设应急物流仓库为受灾点提供服务的广义时间费用;
R(x
i
)表示计算建设应急物流仓库总的广义时间费用时重复计算的费用;
c ij表示第i个仓库向第j个受灾点提供服务的广义单位时间费用;
t ij表示第i个仓库向第j个受灾点提供服务的运输时间费用;
V m表示独立变量,包含从第i个仓库向第j个受灾点的道路等级、备选道路、天气等自然灾害对道路运输造成的影响等因素;
a m表示第m项影响因素的系数;
b jk表示如果受灾点k被仓库j服务到,则b jk= 1,否则为0;
n表示备选仓库地点的数目.
则该问题的上层规划模型为:
(U2.1)m i n F=E
n
i=1
w i x i-E
n
i=1
R(x i)(1) s.t w i=
0,x i=0
E n
j=1
c ij(1-x j),x i=
1
(2)
R(x i)=
0,x i=1
E n
j=1
c ij x j-m in c ij x j,x i=
(3)
c ij=t ij+E
m
a m v m(4)
上层目标函数式(1)使应急物流仓库提供服务的总的广义时间费用最小.其中x i由下层规划模型(L1.1)求得.下层规划模型为:
(L2.1)m in z=E
n
i=1
x i(5)
E n
j=1
b jk x i\1P k(6)
x i I{0,1}P i(7)下层目标函数使建设应急物流仓库的数目最小,并对所有可能的受灾点提供服务.第一个约束保证至少有一个仓库为所有受灾点提供服务;第二个约束为决策变量的0-1约束.
式(2)在i地建设应急物流仓库为受灾点提供服务的广义时间费用.式(3)表示计算建设应急物流仓库总的广义时间费用时重复计算的费用,若节点i是选中仓库节点,则R(x i)=0,若节点i是被覆盖节点,则R(x i)表示被覆盖节点所有覆盖路径与最小覆盖路径之差.式(4)表示广义时间费用的构成,其值不仅代表从节点i到节点j 的时间长短,在应急物流车辆运输过程之中,还需考虑路径的等级,配送可选方案数,发生突发性灾害对道路的影响等因素,式(4)表示节点i到节点j之间多种因素影响下的广义时间费用.式(6)表示至少有一个选中仓库节点被选中服务其他节点k的约束.其中X=(x1,x2,,,x n),分量取值为1或0的所有n元向量X构成问题的解空间.满足约束条件的为可行解,目标值达到最小的可行解为
104大连交通大学学报第31卷
最优解.由于问题存在可行解(例如(1,1,1,,, 1)),且解的数目是有限的,因此该模型存在最优解.
此问题属于NP)难问题.NP)难问题的算法研究一般有两个方向:完全算法能保证得到问题的最优解,但时间复杂度是指数型,因而难以适应较大规模实例的求解;不完全算法(比如禁忌搜索算法、模拟退火算法、遗传算法等)则只要求找到问题的近似最优解,因而往往可在多项式时间内结束.这些拟人策略有时处理NP)难问题很有效,它们或者能使得资源利用得更充分,或者能有效地跳出/局部陷阱0.针对确定集合覆盖这一难解问题,本文结合模拟退火算法,得出能快速收敛到问题的高质量解.
1.3模型求解算法
1.3.1算法思想
模拟退火(si m u lated annea li n g)算法思想基于固体退火原理,金属物体加热至一定温度后,它所有的分子在状态空间中自由运动.随着温度的变化,这些分子逐渐停留在不同的状态,在温度最低时,分子以一定结构重新排列.其主要思想是:在搜索区间(二维平面中)随机游走(即随机选择点),再以M etr opolis抽样准则,使随机游走逐渐
图2模拟退火算法流程图收敛于局部最优解.
其算法流程为如图2所示.
1.3.2参数控制问题
模拟退火算法的应用很广泛,可以求解NP 完全问题,但其参数难以控制,其主要问题有以下三点:
(1)温度T的初始值设置问题
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高,则搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响.实际应用过程中,初始温度一般需要依据实验结果进行若干次调整.
(2)退火速度问题
模拟退火算法的全局搜索性能也与退火速度密切相关.一般来说,同一温度下的/充分0搜索(退火)是相当必要的,但这需要计算时间.实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件.
(3)温度管理问题
温度管理问题也是模拟退火算法难以处理的问题之一.实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:T(t+1)=k@T(t)式中k为正的略小于1.00的常数,t为降温的次数.
本文提出的算法如下:
(1)邻域函数为任意产生一个数,将这个数所对应位置的数置为0或者1的相对数,共有N 个邻居;
(2)评价函数直接取目标函数值,即函数目标值表示的选择节点数目最小,而后计算节点数目最小的时间权值最小方案数;
(3)起始温度设一固定值,终止原则为给定一个比较小的正数E,当t k[E时,算法停止,表示已经达到最低温度,本文给定当温度t小于给定数E=1@10-6时算法终止;
(4)温度下降的方法采用直观的t k+1=A t k,k \0,其中0 (5)每一温度的迭代步数为给定一个充分大的步长上限Upper和一个接受次数指标R,当在给定温度接受次数等于R时,在这一温度不再迭代而使温度下降,否则,一直迭代到上限步数Upper,本文中给定的温度接受次数为R=100,步长上限为Upper=5000. 第3期赵振亚,等:基于模拟退火算法的应急物流仓库选址优化105 2 算法模拟及结果分析 2.1 算法模拟说明 本文用C++语言设计了此问题的模拟退火程序,在M icrosoftV isua l C++6.0软件上测试运行.对于一个随机生成的55个点的图,模拟算法运行结果说明如下: 解表示为x n o w ,目标函数为f no w ,邻域映射CA N _N (x no w ) 解的形式:x no w [15]={1、0、1、0、1、1、0、0、1、1、1、0、0、1、1}.x n o w [5]=1表示第6个节点在应 急仓库覆盖集中,x no w [7]=0表示第8个节点不 在覆盖集中.2.2 算例分析 假设在55个重要城市及交通要道作为潜在节点的区域范围内分析应急仓库选址优化方案:(1)生成初始解x In itia l [55]={1101110010111111110111110101011111110111110110000001100},判断初始解可行,即可服务覆盖区域内部各节点; (2)运行程序模拟退火程序,得出结果,最小应急仓库方案覆盖集合内节点数目为7,节点集合及相应权值即广义时间费用如下所示:U 1={2579101222},W 1=799;U 2={1247111222},W 2=790;U 3={1257111222},W 3=771;U 4={1257101222},W 4=802;(3)根据以上结果,求得最终目标函数最小的广义时间费用为771,节点集合为U 3={1257111222},模拟退火过程的收敛分析如图3~6所示. 由以上分析,对于一个55个点规模的图,模型模拟时间为6.625s ,找到的最小边覆点数是7,最小广义时间费用是771.从以上数据和图形中可以看出,此算法收敛效果较好,能够获得最优解或理想可行解,模拟效率较高 . 图3 当前 解与温度下降的关系 图4 最 优解与温度下降的关系 图5 当前解与时间的关系图 图6 最优解与时间的关系3 结语 本文分析了应急物资仓库建立的必要性及重要性,对其涉及的关键问题进行了较为深入的分 析.在合理假设的基础上,构建应急仓库选址问题的集合覆盖双层规划模型,通过在区域重要地理位置及交通通道地区应设有适当数量的常设应急仓库,使得服务范围覆盖整个区域的应急仓库数目最小,且满足配送过程中广义时间费用最小.设计了适合求解应急仓库优化选址模型的模拟退火算法,最后在C++语言环境下编程求取一个算例,证明了模型和算法的有效性.针对应急仓库布点选址问题设计此双层规划模型及算法,模拟内容不涉及具体配送问题以及仓库建设规模的问题,以上研究可以为决策部门在灾害管理的灾害 准备阶段科学合理进行应急仓库选址提供科学依 106大连交通大学学报第31卷 据,在应急管理的灾害准备阶段初期可参考使用该方法. 参考文献: [1]G WYNDAF W I LLI A M S,STUART BAT HO,LYN NE RUSSELL.R espond i ng to urban crisis2The e m ergency planning respo nse t o t he bo mb i ng of M anchester c ity centre[J].C ities,2000,17(4):2932304. [2]S TE VEN J D.A M ICO,S HOOU2JI UN WANG,RAJ AN B ATTA,et a.l Ansi m ulated annea li ng approach to poli ce d i str i c t desig n[J].Co mputers&Op e ratio ns R esea rch, 2002,49(6):6672684. [3]计国君,朱彩虹.突发事件应急物流资源配送优化问 题研究[J].中国流通经济,2007,13(2):18221. [4]刘春林,沈厚才.一类离散应急供应系统的两目标优 化模型[J].中国管理科学,2003,11(4):27231. [5]方磊,何建敏.给定限期条件下的应急系统优化选址 模型及算法[J].管理工程学报,2004,18(1):48251. [6]王铁宁,徐宗昌,曹钰.应急物资保障计划辅助决策模 型研究[J].物流科技,2004(4):83286. [7]李保俊,袁艺,邹铭,等.中国自然灾害应急管理研究 进展与对策[J].自然灾害学报,2004,13(3):18223. [8]高自友,孙会君.现在物流与交通运输系统[M].北 京:人民交通出版社,2003:2552287. [9]孙会君,高自友.物流配送中心合理选址研究[J].技 术经济,2002(11):24225. Op ti m iza tion of Em ergency L ogistic W a rehouse L oca tion Based on Si m u la tion Annea ling A lgor ithm Z HAO Zhen2ya,HE Guo2xian (School of T ra ffi c and Transporta tion,Lanzho u Jiaotong Un i versity,Lanzhou730070,Chi na) A bstra ct:Emer gency warehouse l o cation opti m ization pr oble m of e mergency logistic manage m entwas discussed in deta i,l and the i m portance and necessity of the e mergencywarehouse estab lishmentwas analyzed.In order to ana l y ze accurate l y the infl u ence ofwarehouse l a yout on the coverage ab ility and generalized ti m e cost based on reasonable assumption,a b i2leve l progra mm i n g model was constructed,consi d eri n g t h e m i n i m um generalized ti m e cost of d i s tribution pr ocess,and the m i n i m u m nu mber of e m er gency warehouses covering t h e whole area to obta i n the opti m a l sol u ti o n by si m u lati o n annealing algorithm.The eff ectiveness of the model and a l g orit h m is ana l y zed and verified to provi d e e mergency storage location ref erence f or d isasterm anage ment dec ision2mak i n g depart m ents i n the d isaster preparation phase. K ey words:e mergency logisti c s;warehouse locati o n;b i2leve l progra mm i n g;si m u lated annea li n g algorithm 专业综合设计报告 课程名称：电子专业综合设计 设计名称：基于模拟退火算法的TSP算法姓名： 学号: 班级：电子0903 指导教师：朱正为 起止日期：2012.11.1-2012.12.30 专业综合设计任务书 学生班级：电子0903 学生姓名：学号： 20095830 设计名称：基于模拟退火算法的TSP算法 起止日期： 2012.11.1-2012.12.30 指导教师 专业综合设计学生日志 专业综合设计考勤表 专业综合设计评语表 一设计目的和意义 (6) 二设计原理 (6) 2.1 模拟退火算法的基本原理 (5) 2.2 TSP问题介绍................................................................................................................... .. (6) 三详细设计步骤................................................................................................................... . (9) 3.1.算法流程 (8) 3.2模拟退火算法实现步骤........................................................ 错误!未定义书签。四设计结果及分析.. (9) 4.1 MATLAB程序实现及主函数 (9) 4.1.1 计算距离矩阵 (9) 4.1.2 初始解................................................................................................................... . (10) 4.1.3 生成新解................................................................................................................... (10) 4.1.4 Metropolis 准则函数................................................................................................ (10) 4.1.5 画路线轨迹图 (11) 4.1.6 输出路径函数 (12) 4.1.7 可行解路线长度函数 (12) 4.1.8 模拟退火算法的主函数 (13) 解析模拟退火算法 一.爬山算法(Hill Climbing) 介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。 爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。 二.模拟退火(SA,Simulated Annealing)思想 爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。 模拟退火算法描述： 若J(Y(i+1))>=J(Y(i))(即移动后得到更优解)，则总是接受该移动 若J(Y(i+1)) 作者简介：李香平（１９７８￣），男，湖北监利人，中国地质大学计算机学院硕士研究生，研究方向为科学研究与可视化；张红阳（１９８２￣），男，湖北咸宁 人，中国地质大学计算机学院硕士研究生，研究方向为数据挖掘与数据仓库。 模拟退火算法原理及改进 李香平，张红阳 （中国地质大学计算机学院，湖北武汉４３００７４） 摘 要：模拟退火算法是一种强大的随机搜索算法，能应用于许多前提信息很少的问题，能渐进地收敛于最优值。对 ＳＡ算法进行了介绍，论述了ＳＡ算法的原理并对算法进行了改进，展示了计算实验的结果。 关键词：模拟退火；全局优化中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１６７２－７８００（２００８）０４－００４７－０２ ０引言 近年来，传统的单一算法越来越不适应大规模非线性规划 问题。它们要求目标函数是可微的和收敛的。ＳＡ能很好地弥补它们的缺陷。 从用于统计力学的ＭｏｎｔｅＣａｒｌｏ方法上受到启发，ＳＡ算法在 １９８３被Ｋｉｒｋｐａｔｒｉｃｋ提出来。对比传统局部搜索算法，ＳＡ在搜索 时会在搜索空间上下移动而不依赖初始条件，擅长解决多维问题。此外，它能处理任意程度的非线性、 不连续和随机的问题。能处理任意边界和约束的评估函数。因此，它能轻易处理有脊背和高地的函数。只要初温高、退火表适当，它就能得到全局最优。ＳＡ成功应用于组合优化、神经网络、图像处理和代码设计。 １模拟退火算法原理 组合优化问题是在给定的约束条件下，求目标函数的最值 的问题。设（Ｓ，ｆ）是组合优化问题的一个实例，ｉｏｐｔ∈Ｓ若对所有 ｉ∈Ｓ，都有ｆ（ｉｏｐｔ）≥ｆ（ｉ），则称ｆ（ｉｏｐｔ）≤ｆ（ｉ）为ｍｉｎｆ（ｉ）的最优解。 ＳＡ来源于物理热力学原理，综合了固体退火与组合优化 之间的类似性。类似固体的复杂系统，先被加热到一个物质粒子能自由移动的很高的温度，当它慢慢冷却时，它的能量减少。如果“冷却”过程足够慢，系统将忽略局部稳定构造，到达能量最低状态，即基态。 在模拟的每一步中，新解的产生按照Ｍｅｔｒｏｐｏｌｉｓｔｒａｎｓｉｔｉｏｎ法则，一个新的状态从现有的状态中产生，这个法则能以一定的概率接受能量上升（即产生劣解）的新状态，而能量下降是优化的总目的。法则如下所示： ｐ（ｘ＝＞ｙ）＝ １， ｆ$%ｙ≤ｆ$%ｘｅｘｐ－ｆ$% ｘｆ$%ｙ $ % ， ｏｔｈｅｒｗｉｓ&ｅ ｆ是系统能量，ｔ是温度。ＳＡ的一般框架： Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｓｔａｔｅａｔｒａｎｄｏｍ；Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｔｅｍｐｅｒａｔｕｒｅ；ＲＥＰＥＡＴＲＥＰＥＡＴ ｙ＝ｇｅｎｅｒａｔｅ（，）； ＩＦａｃｃｅｐｔ（，ｙ，）ＴＨＥＮ＝ｙ ＵＮＴＩＬ＇ｉｎｎｅｒｌｏｏｐｓｔｏｐｃｒｉｔｅｒｉｏｎ＇ｓａｔｉｓｆｉｅｄ 为了提高ＳＡ的性能，我们应该仔细处理控制参数的协调。（１）初始温度的选择。初始温度太高会花费高昂的计算时间，太低会拒绝劣解的接受，会丢失ＳＡ全局优化的优点。本文提出了一个初始温度的公式： ｔ０＝’ｆ＋ ｌｎｘ －１ ’ｆ＋ 是函数增量的平均值，χ 是初始的接受概率。（２）温度降低策略。温度降低越快，陷入局部的概率就越大。然而，温度降低太慢会导致算法速度慢得不能接受。本文采用了一种快速的非线性降低法： ｔｋ＝ ｔ０ １＋ｋ ｋ＝１，２，３，…… （３）适当的邻域结构。在退火期间，步长太小导致算法在探索相位空间效率低，太大新解总被拒绝。在持续优化时，新的等价值均一地按间距分布在以ｘｉ的坐标为中心的邻域中，沿轴的间距的一半被看作步长向量ξ。当点落在ｆ的定义域内时，就随机产生新解。 （４）终止标准。内循环是单一温度下在各种条件下Ｍａｒｃｏｖ链的一种渐进接近全局最优的模拟实现，即循环Ｍａｒｃｏｖ链长次数结束。外循环取某个温度ｔ作为算法终止标准，或者是迭代若 软件导刊 ＳｏｆｔｗａｒｅＧｕｉｄｅ 第７卷第４期 ２００８年４月Ｖｏｌ．７Ｎｏ．４Ａｐｒ．２００８ 第4卷第2期2007年4月 工程地球物理学报 CHIN ESE J OU RNAL OF EN GIN EERIN G GEOP H YSICS Vol 14,No 12Apr 1,2007 文章编号:1672—7940(2007)02—0135—06 模拟退火算法及其改进 蒋龙聪,刘江平 (中国地质大学地球物理与空间信息学院,武汉430074) 作者简介:蒋龙聪(1983— ),男,硕士研究生,现在主要从事地震数据处理和反演理论方法研究。E 2mail :longcja @https://www.wendangku.net/doc/0612897080.html, 刘江平(1957— ),男,教授,博士生导师,主要从事地震勘探的科研与教学工作。E 2mail :liujp @https://www.wendangku.net/doc/0612897080.html, 摘 要:借鉴遗传算法中的非均匀变异思想,用非均匀变异策略对当前模型扰动产生新的模型,对传统的模 拟退火算法提出了改进,通过多峰值函数数值优化测试结果表明,该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,大大加快了收敛速度,证实了该改进算法的有效性和高效性。 关键词:模拟退火算法;非均匀变异;数值最优化;反演 中图分类号:P631文献标识码:A 收稿日期:2006— 12—07R evised Simulated Annealing Algorithm Jiang Longcong ,Liu Jiangping (I nstitute of Geop hysics and Geomatics ,China Universit y of Geosciences ,W uhan 430074,China ) Abstract :Based on t he idea of non 2uniform mutation in genetic algorit hm ,we present a novel revised simulated annealing (RSA ),which used t he non 2uniform mutation to generate a new model f rom current model.Tested by some numerical f unctions ,RSA can search in t he large area for t he solutions in high temperat ure.Wit h t he lowering of t he temperat ure ,t he area of searching t he solutions will be gradually reduced and convergence will speed up.So t he re 2sult s p rove t he effectiveness of RSA. K ey w ords :simulate annealing ;non 2uniform mutation ;numerical optimal ;inversion 1 引 言 人类对地球内部物理性质(包括速度、密度、电导率、温度等)以及矿产资源分布的了解,大多来自地表地质和地球物理、地球化学资料的反演和解释[1]。反演方法可以分为线性反演和非线性反演两种,线性反演已成为一套科学的反演理论,然而,绝大部分地球物理问题都是非线性的,并且实践表明,线性反演方法有容易陷入局部极值和依赖于初始值等缺点。因此,地球物理学者们不 断的尝试开发非线性反演方法,比如人工神经网 络[2]、小波多尺度反演[3]、模拟退火算法[4]等。 模拟退火算法是近年发展起来的全局最优化算法,其主要优点是;不用求目标函数的偏导数及解大型矩阵方程组,即能找到一个全局最优解,而且易于加入约束条件,编写程序简单。目前此法已开始用于解决非线性地球物理反问题,如波形反演、静校正、叠前偏移速度分析等非线性反演中,并取得了较好的效果。 然而,由于模拟退火法是建立在随机搜寻方法的基础上,要达到一定的精度要求,每一模型参 模拟退火算法 一、模拟退火算法概念 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T 时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann 常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 二、模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 模拟退火的基本思想: (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L (2) 对k=1，……，L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。 终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 算法对应动态演示图： 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。 模 拟退火算法 一 定义 1 概念 什么是退火？在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」）时，会导致不是最低能态的非晶形。如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。 似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。 模拟退火算法(SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝色点A ，模拟退火算法会快速搜索到局部最优解B ，但在搜索到局部最优解后，不是就此结束，而是会以一定的概率接受到左边的移动。也许经过几次这样的不是局部最优的移动后会到达全局最优点D ，于是就跳出了局部最小值。 根据热力学的原理，在温度为T 时，出现能量差dE 的降温的概率为P(dE)，表示 为: ()?? ? ??=kT dE E P ex p d 。其中k 是波尔兹曼常数，值为-2310×13)1.3806488(=k ，exp 表示自然指数，且dE<0。因此dE/kT<0，所以P(dE)函数的取值范围是(0,1)。满足概率密度函数的定义。其实这条公式更直观意思就是：温度越高，出现一次能量差为P(dE)的降温的概率就越大；温度越低，则 关于模拟退火算法及其影 ｉ《＿■ ＳＩＬＩＣＯＮＶ ＶＡＬＬＥ工响因素的研究 邓超陈文宣王树青 （东莞南博职业技术学院广东东莞５２３０８３）信毫科学 插要：通过使用模拟退火算法模拟逼近函数：ｙ＝ｘ＋ｃｏｓｘ＋ｉ开展实验，并在实验过程中对模拟退火算法的影响因素进行比较ｔ并提出相应的改进方案，直观的将两者的差别体现出来。 关键词：模拟退火算法；权系数；阀值：神经网络结构；ＭＡＴＬＡＢ 中圈分类号：ＴＰ３文献标识码：Ａ文章编号ｚ１６７１－７５９７（２０１０）０４１００４５－－０１ １鬟拟量火算法的基本曩客 模辛｝ｌ退火算法最初的思想［自Ｍｅｔｒｏｐｏｌｉｓ在１９５３年提出，其来源统计物理学中对于固体退火过程的模拟。他采用Ｍｅｔｒｏｐｏｌｉｓ准则接收新解，用冷去系数的参数对算法进程进行控制。使得算法在多项时间里得出最优解．２对曩板退火算法进行试ｔ研究 １）用模拟退火算法模拟逼近函数：ｙ＝ｘ＋ｃｏｓｘ＋１并对神经网络的权系数、阀值进行学习其神经网络结构为１—３－４＿３—１． ２）具体试验过程如下： 模拟退火算法的实现主要采用了¨ＴＬＡＢ软件，利用其中的神经网络工具箱进行编程模拟．在网络ＵＵｌ练方面，隐层采用ｌｏｇｓｉｇ（厂（ｊ）＝＿—二—＿＿－） Ｈ’ａ烈一哪函数作为传递函数。在输出层方面采用线性输出函数ｉｍｒｅｌｉｎ（，（善）＝＃）．降温函数采用ｔ＝＾ｔ． ①给定的学习样本、初始温度、结柬温度及降温速率＾． ＠在某一温度下．以正态分布（Ｍａｔｌａｂ中用ｒａｎｄｎ）生成函数产生新的权系数增量△翻。‘虬．＝缈＋△翻生成新的权系数。 ③根据代价函数求出神经网络的输出偏差Ｅ∥ｔ 胛＝；（歹一ｙ）２． ＠如果Ｐ，ｒＳ０，则取翻ｒ＋ｌ为新值，即ｑ＝够＋ｌ? ⑤如果Ｐ玎＞ｏ，采用接收函数：Ｂ（ｉ）＝［Ｉ＋ｅ＝Ｖ／‘】＿１ 以其值和［０，ｌ】随机数ｄ进行比较： 若Ｂ（ｉ）＞ｄ。则Ｃｄ＝够．。；， 若Ｂ（ｉ）≤ｄ，则国不变。 ＠以ｔ：ｘｔ修改参数ｔ．即缓慢降温。返回②执行． ３）试验生产的原函数和网络输出图如下： ４）结果分析ｔ 由学习的结果来看，学习的曲线和原曲线相差较大，而且函数收敛得很慢．其原因是模拟退火法的初始参数包括初温ｔＯ，结束温度ｔｆ’衰减温度ｄｅｌｔａＴ及控制内循环的马尔可夫链长Ｌ的选择对整个结果产生较大影响。 ３樱报遗火法的改盛可行性方毫 １）设计合适的状态产生函数：设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构：改进对温度的控制方式；选择合适的初始状态；设计合适的算法终止准则。 ２）也可通过增加某些来实现：如增加升温或重升温过程；增加记忆功能｛增加朴充搜索过程。 ４－｝墨横挂鼍火算法的实验改进方囊 ”对原算法的神经喇络结构进行更改．由卜３－４—３一ｌ改为卜１０一ｈ ２）调整即网络训练参数：具体为添加代码为： ｎｅｔ．ｔｒａｉｎＰａｒａＬｅｐｏｃｈｓ２３０００： ｎｅｔ．ｔｒａｉｎＰａｒ∞．ｇｏａｌ＝０．００２： ｎｅｔ．ｔｒａｉｎＰａｒａｎＩｒ２０．０ｌ： Ｉ开始训练 ｎｅｔ２ｔｒａｉｎ（ｎｅｔ，ｘ．ｙ）：） 在对原算法改进后试验产生的原函数和网络输出图如下（改进处在源程序中体现）： 由结果可以看到，改进后的算法收敛速度加快，函数的逼近和精度都已经较高。 参考文献： 【ｌ】王士同、陈剑夫等编著。问题求解的人工智能神经网络方法ｒ气象出版社． ［２］焦李成．神经网络系统理论，西安，西安电子科技大学出版社，１９９６．６． 作者简介： 邓超（１９７９－），男．汉族．广东省韶关市人，硕士．东莞南博职业技术 学院助教，研究方向；神经网络? 万方数据 智能信息处理实验报告 14电科一班 XX XXXX 模拟退火算法解决函数优化问题 实验二 一、实验目的 1. 掌握模拟退火算法的基本原理和步骤。 2. 复习VB 、VC 的基本概念、基本语法和编程方法，并熟练使用VB 或VC 编写遗传算法程序。 二、实验设备 微机 三、实验原理 模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，模拟退火算法由某一较高初温开始，利用具有概率突跳特性的Metropolis 抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。 标准模拟退火算法的一般步骤可描述如下： (1) 令m =0，给定初温t m ，随机产生初始状态s m ； (2) Repeat ； s old =s m ； (2.1) Repeat ； (2.1.1) 产生新状态：s new =Generate(s old )； (2.1.2) 若min{1, exp[(C (s old )-C (s new ))/t m ]}≥random[0, 1]，则s old =s new ； (2.1.3) Until 抽样稳定准则满足； (2.2) 退温：t m +1=update(t m )，s m +1=s old ，m =m +1； (3) Until 算法终止准则满足； (4) 输出算法搜索结果：s m 。 四、实验内容及步骤 1. 上机编写程序，解决以下函数优化问题：()221min 10i i i f x x =??=≤ ? ?? ∑X 2. 调试程序。 3. 根据实验结果，写实验报告。 模拟退火算法文献综述 吕正祥交控1501 1模拟退火算法简述 1.1模拟退火算法的来源 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 模拟退火算法(Simulated Annealing，SA)最早由Kirkpatrick 等应用于组合优化领域，它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。 1.2模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 1.3模拟退火的基本思想 (1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L (2) 对k=1，……，L做第(3)至第6步： (3) 产生新解S′ (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 (5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。 (7) T逐渐减少，且T->0，然后转第2步。 模拟退火算法 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。 如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态i 之下的能量为)(i E ，那么材料在温度T 时从状态i 进入状态j 就遵循如下规律： （1）如果)()(i E j E ≤，接受该状态被转换。 （2）如果)()(i E j E >，则状态转换以如下概率被接受： 其中K 是物理学中的波尔兹曼常数，T 是材料温度。 在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i 的概率满足波尔兹曼分布： ∑∈--= =S j KT j E KT i E T e e i x P )()()( 其中x 表示材料当前状态的随机变量，S 表示状态空间集合。 显然 | |1lim )()(S e e S j KT j E KT i E T = ∑∈-- ∞ → 其中||S 表示集合S 中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时， ∑∑∑?-- ∈-- -- →∈-- -- →+ =min min min min min min min )()()(0 )()(0 lim lim S j KT E j E S j KT E j E KT E i E T S j KT E j E KT E i E T e e e e e ?? ? ??∈==∑∈-- -- →其它若 0 ||1 lim min min )()(0 min min min S i S e e S j KT E j E KT E i E T 其中)(min min j E E S j ∈=且})(|{min min E i E i S ==。 上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。 假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。 考虑这样一个组合优化问题：优化函数为+→R x F :，其中S x ∈，它表示优化问题的一个可行解，}0,|{>∈=+y R y y R ，S 表示函数的定义域。S x N ?)(表示x 的一个邻域集合。 首先给定一个初始温度0T 和该优化问题的一个初始解)0(x ，并由 )0(x 生成下一个解))0(('x N x ∈，是否接受'x 作为一个新解)1(x 依赖于下 面概率： ??? ??<=→--其它若 ))0(()'(0 )) 0(()'( 1)')0((T x f x f e x f x f x x P基于模拟退火算法的TSP算法
模拟退火算法介绍
模拟退火算法原理及改进
模拟退火算法及其改进_蒋龙聪
模拟退火算法基本原理介绍
模拟退火算法报告
关于模拟退火算法及其影响因素的研究
模拟退火算法解决函数优化问题
模拟退火算法研究概况
数学建模优秀方法-模拟退火算法简介