模拟退火算法的研究及其应用19

发布时间：2016-12-20 08:13

本文关键词：模拟退火算法的研究及其应用，由笔耕文化传播整理发布。

模拟退火算法的研究及其应用；作者：；学位授予单位：冯玉蓉昆明理工大学；1.EibenAE.AartsEH.VanHee；2.HollandJHAdaptationinn；3.王晓东算法设计与分析2003；4.张尧庭.杜劲松人工智能中的概率统计方法199；5.王凌.郑大钟Meta-heuristic算法；6.雷功炎数学模型讲义1999；7.MitraD.Rom

模拟退火算法的研究及其应用

作者：

学位授予单位：冯玉蓉昆明理工大学

1.Eiben A E.Aarts E H.Van Hee K M Global convergence of genetic algorithms:An infinite Markov chainanalysis 1991

2.Holland J H Adaptation in natural and artificial systems 1992

3.王晓东算法设计与分析 2003

4.张尧庭.杜劲松人工智能中的概率统计方法 1998

5.王凌.郑大钟 Meta-heuristic算法研究进展[期刊论文]-控制与决策 2000(3)

6.雷功炎数学模型讲义 1999

7.Mitra D.Romeo F.Vincentelli A S Convergence and finite-time behavior of simulated annealing 1986

8.Metropolis N A.A Rosenbluth.M Rosenbluth.A Teller E Teller Equation of state calculations by fastcomputing machines 1953

9.Kirkpatrick S.C D Gelatt Jr.P Bruckner Complexity of machine scheduling problems 1977

10.Leong H W.D G Wong.C L Liu A simulated annealing channel router 1985

11.Vecchi M P.S Kirkpatrick Global wiring by simulated annealing 1983

12.王凌.郑大钟一类GASA混合策略及其收敛性研究[期刊论文]-控制与决策 1998(6)

13.Tan H L.S B Gelfandand.E J Delp Acost minimization approach to edge detection using simulatedannealing 1992(01)

14.Chang C.C Wu Optimal frame pattern design of a TDMA mobile communication system using a simulatedannealing algorithm 1993

15.Duque Anton M.D Kunz.B Ruber Channel assignment for cellular radio using simulated annealing1993(01)

16.王凌.郑大钟模拟退火算法求解Flow-shop问题的研究 1997

17.Rose C Low mean internodal distance network topologies and simulated annealing 1992(08)

18.杨浩模型与算法 2002

19.Wayman J L Optimization of signal distribution networks using simulated annealing 1992(03)

20.Wong K P.Y W Wong Genetic and genetic/simulated-annealing approaches to economic 1994(05)

21.Lockwood C.T Moore Harvest scheduling with spatial constraints:a simulated annealing approach1993(03)

22.Nilar S H Applications of the simulated annealing method to intermolecular interactions 1991(08)

23.Pospichal J.V Kvasnicka Fast evaluation of chemical distrane by simulated-annealingalgorithm1993(06)

24.刘岩.韩承德.王义和模拟退火算法的背景与单调升温的模拟退火算法[期刊论文]-计算机研究与发展 1996(1)

25.王强模拟退火算法的改进及其应用 1993(04)

26.康立山.谢云.尤矢勇.罗祖华非数值并行算法－模拟退火算法 1998

27.Mahfoud S W.Goldberg D E Paralel recombinative simulated annealing:A genetic algorithm 1995

28.Huntley Cl.Brown DE Parallel genetic algorithms with local search 1996(06)

29.王卓鹏.高国成.杨卫平一种改进的快速模拟退火组合优化法[期刊论文]-系统工程理论与实践 1999(2)

30.杨若黎.顾基发一种高效的模拟退火全局优化算法 1997(05)

31.庞哈利.郑秉霖.徐心和一种自适应的模拟退火算法[期刊论文]-控制与决策 1999(5)

32.Gil C.Ortega J Meta-heruistic for circuit partition in parallel test generation In 1998

33.黄桐城.王金桃运筹学基础教程 2004

34.束金龙.闻人凯线性规划理论与模型应用 2003

35.《铅锌冶金学》编委会铅锌冶金学 2003

36.陈希孺.王松桂现代实用回归分析 1984

37.王松桂.史建红.尹素菊.吴密霞线性模型引论 2004

38.Yang Chunhua 查看详情 1997(04)

39.王雅琳.黄泰松.桂卫华.阳春华锌电解过程分时供电优化决策系统

40.陈宝林最优化理论与算法 1989

41.杨浩模型与算法 2002

42.杨庆之无约束优化问题模拟退火算法的改进[期刊论文]-高等学校计算数学学报 2001(2)

43.江加和.宋子善.沈为群.邱力为模拟退火算法在连续变量全局优化问题中应用[期刊论文]-北京航空航天大学学报 2001(5)

44.向阳.龚新高推广模拟退火方法及其应用[期刊论文]-物理学进展 2000(3)

45.席自强单纯形—模拟退火算法[期刊论文]-湖北工学院学报 2000(1)

46.胡山鹰非线性规划问题全局优化的模拟退火法[期刊论文]-清华大学学报(自然科学版) 1997(6)

47.徐雷一种改进的模拟退火组合优化法 1990(03)

48.Yip Pui Chiv The role of regional guidance in optimization:The guidede evolutionary simulatedannealing approach 1993

49.邱卫宁具有稳健初值的选权迭代法[期刊论文]-武汉大学学报(信息科学版) 2003(4)

50.吴坚.郑康平.王小椿用隐式多项式平面曲线拟合数据点[期刊论文]-机床与液压 2003(4)

51.部茂祖.姜俊峰.李静梅模拟退火算法中冷却调度选取方法的研究[期刊论文]-计算机工程 2000(9)

52.杜玉晓.吴敏.桂卫华面向生产目标的铅锌烧结过程智能集成建模与优化控制技术[期刊论文]-中国有色金属学报2004(1)

53.李文勇.李泉永基于模拟退火的全局优化算法[期刊论文]-桂林电子工业学院学报 2001(2)

54.赵凤治.尉继英约束最优化计算方法 1991

55.孙文瑜.徐成贤.朱德通最优化方法 2004

56.D S Johnson.C R Aragor.L A Megooch Optimization by simulated annealing:An experimental evaluationPartl 1987

1.学位论文张正新模拟退火算法解决静态RWA问题的研究 2006

在WDM光网络中，业务量工程技术(TrafficEngineering，TE)是按用户的要求把业务量映射到光网络的物理拓扑上，从而达到优化网络资源利用率、避免拥塞和提高网络可靠性的目的。随着OXC(OpticalCrossConnect，光交叉连接设备)、OADM(OpticalAdd/DropMultiplexer，光分插复用设备)技术的不断成熟，基于DWDM(DenseWavelengthDivisionMultiplexing)技术的光传送网已不再局限于点对点传输，，而是组网运用。既然是网络，就必然存在对网络资源的按需分配问题和优化问题。优化的目标是在实际的约束限制条件下，尽量合理配置资源，使得网络的总代价最小、资源占用率最少，以及在资源紧张时满足尽可能多的业务请求。为了更好地解决资源的按需分配问题和优化配置问题，必须在WDM光网络中引入业务量工程技术，更好地满足业务的要求。在WDM光传送网中，给定一组光路连接需求，通过选路和波长分配算法来建立相应光路的问题称为路由与波长分配问题

(RoutingandWavelengthAssignment，RWA)问题。WDM光网络中的一个核心问题就是如何选择有效的算法和协议来建立光路，也就是如何解决RWA问题。RWA问题的研究对网络资源的利用、网络管理和控制都有很大的影响。根据业务请求提出的方式不同，可以大致分为动态和静态RWA问题，本文主要对研究对象为静态RWA问题。目前在解决这种问题时，引入了多种算法，比如启发式算法，线性规划算法等等。

本文研究了用模拟退火算法解决光网络业务量工程中静态RWA问题，在已有网络上，根据多个业务需求，合理分配网络资源，完成端到端通路的建立，达到一定的优化目标。根据网络节点是否具有波长转换能力分为2种情况进行优化：1、所有节点都具有波长转换能力，2、所有节点都没有波长转换能力。为了衡量模拟退火算法解决静态RWA问题的结果，采用了一种启发性算法作为参考。首先考察实际的网络模型，根据业务需求，引入K路由算法的结果作为模拟退火算法和启发性算法备选路由集合，在链路带宽有限的约束下对网络资源进行分配，同时引入业务路由的通路保护问题的研究，实现了共享保护和专用保护两种通路保护方式；针对全波长转换网络和无波长转换能力网络，根据为所有连接请求所分配的总资源最少和满足请求的业务数目最多两种优化目标对资源分配进行优化，研究了备选路由集大小对模拟退火算法结果的影响；对模拟退火算法与启发性算法的性能在两个不同的网络中进行了比较。

2.会议论文赵伟.夏云飞.李文辉基于非线性规划的凸多面体间碰撞检测算法研究 2007

空间中两个物体间的距离计算是碰撞检测问题研究的一个重要方面,提出用顶点的凸包来表示凸多面体,将两凸物体间距离的问题归结为一个带约束条件的非线性规划问题,所以问题主要是求解优化的时间复杂度。利用模拟退火遗传算法对该问题进行求解,主要是利用模拟退火的接收准则来交叉,变异。结果表明,模拟退火遗传算法对该问题的求解有更高的计算效率和更快的计算速度。

3.期刊论文罗亚中.唐国金.LUO Ya-zhong.TANG Guo-jin 两层非线性规划问题的并行模拟退火全局优化 -系统仿真学报2005,17(5)

两层非线性规划问题的非凸性和非可微性给全局最优解的求解带来了较大的困难,目前还缺乏成熟的全局优化策略,同时其易并行计算特性未得到重视.提出了基于模拟退火算法的两层非线性规划问题的并行全局优化策略.融合单纯形法和模拟退火算法设计了一种并行模拟退火算法,用来求解上层问题,用精确惩罚函数处理约束.下层的非线性规划问题则采用可变容差单纯形算法完成求解.所设计的组合算法有效地结合了两层非线性规划问题的易并行性,便于实现网络并行计算.计算表明算法有着可靠的全局收敛性和较高的收敛速度.

4.学位论文王菲菲一维最优下料问题研究 2004

近年来,随着国民经济的飞速发展,一维下料问题在建筑、电力、水利等领域获得了越来越广泛的应用.寻找一种最优的下料方案,不仅可以节省原材料,降低生产成本,而且能够为企业带来直接的经济效益,促进国民经济的健康发展.因此,开展对一维下料问题的研究具有重要的理论意义和工程应用价值.该文首先深入地分析了一维下料问题,提出了一种截切方案的计算机自动生成的算法,建立了该类问题的数学模型.然后,分别采用三种方法对一维下料问题进行优化求解,并进行了具体算例的比较分析.1.线性规划.线性规划的单纯形法是求解一维下料问题的传统方法.该文首先应用这种方法对一维下料问题进行优化求解,并分析了这种方法存在的缺陷,如:所得的结果不全为整数;或由于问题的规模过大而导致算法失效,出现病态解甚至无解的情况.2.遗传算法.该文从应用的角度对遗传算法做了认真的分析和研究,然后将其应用于一维下料问题的求解,提出了一种基于遗传算法的求解方法.在求解过程中,给出了遗传算法求解的编码方法、适应度函数的定义、遗传算子以及关键参数.实际应用表明,采用该方法求解是可行的,并且取得了较好的寻优效果.3.遗传模拟退火算法.针对遗传算法存在"过早收敛"的现象及其良好的兼容性,考虑将模拟退火算法与遗传算法相结合,用来求解一维下料问题.这是一个新的尝试.该算法首先通过遗传算法来进化生成一个群体,然后利用模拟退火算法进一步调整优化解.基于算例的求解结果验证了该文所提出的遗传模拟退火算法的有效性和高效性,其下料结果明显优于线性规划和遗传算法.

5.期刊论文李智.李伟模拟退火算法在铸造生产配料优化中的应用 -铸造技术2004,25(11)

以铸造配料成本最低为目标函数,建立了铸造优化配料数学模型.运用模拟退火算法和Matlab语言,以ZG35Cr24Ni7SiN的炉料配比为例,对该数学模型进行了仿真优化计算.结果表明:在保证化学成分在控制要求成分的条件下,其吨钢成本比原手工配料方法节约550元,而且计算速度快于经典的线性规划数学方法,模拟退火算法应用于铸造生产配料是可行的,实现了铸造配料的优化配比.

6.学位论文陈建 SOC布图规划与考虑热量的测试规划研究 2006

当今系统级芯片(SOC)已成为热点，而且芯片规模以及复杂度不断提高，基于IP复用的设计方法已经成为必然趋势。对于这种层次化的设计流程，作为物理设计第一阶段的布图规划将变的越来越重要。而且随着SOC复杂度和规模的不断增加，SOC的测试变得越来越复杂，测试的费用也越来越高。基于上述原因，本文主要研究SOC的布图规划算法和考虑热量的测试规划算法。

在基于权重的布图规划算法中，本文提出在模拟退火过程中不是以均匀分布的概率来选择当前进行移动的模块，而是权重大的模块选择概率较小，权重小的模块选择概率较大。首先提出了模块权重的概念，并在此基础上提出基于权重的布图规划算法，实验表明基于权重的布图算法取得了较好布图结果。布图规划问题规模不断增大，使用模拟退火算法其求解时间过长，本文提出快速布图算法。构造法可以快速的得到一个布图，但是结果并不是最优解。而线性规划算法速度较快，最终结果也令人满意，却需要输入一个好的初始布图。综合考虑后，本文结合两者算法，用快速的构造法来构造初始布图，并保证得到一个较好的拓扑结构，再用线性规划对这个初始布图进行优化，从而得到最优解。实验表明本算法能在较短的时间内得到较好的布图。

随着集成电路工艺发展，工作电压降低，电流密度和连线长度增大，电源网络电压降的问题将越发突出。本文提出在布图规划过程中考虑电压降的优化，降低最终布图的电压降以及尽量满足各模块的电压降容限，加快物理设计收敛。首先提出在布图规划过程中优化电压降的目标函数，然后讨论模拟退火过程中的选择策略，最后用线性规划进行软模块压缩。实验表明本算法取得一个较好的布图同时，能有效地降低最终布图平均电压降和最大电压降。

考虑到测试过程的高发热对于芯片的不良影响，本文提出在对SOC进行测试规划时考虑避免热点和均匀地分布热量，从而提高芯片测试的成品率。文中将热点问题以及热量均匀分布问题转化为模块之间距离问题，通过模块之间的距离来决定它们是否可以同时测试。然后，用测试兼容图来描述各个测试之间的约束关系，并通过测试兼容图中来提取并行测试集合。最后，通过Bin-Packing算法对并行测试集合进行测试规划。实验表明本算法能有效地降低测试过程中的平均温度以及最高温度，并且只带来较小的测试时间增加。

7.期刊论文顾治华.黄霞.Gu Zhihua.Huang Xia 非线性规划优化问题中的模拟退火算法 -中国水运（理论版）2007,5(1)

模拟退火SA(Simulated Annealing)算法,是一种仿金属退火物理过程的随机算法,对于复杂的组合优化问题的求解,表现出比其他传统优化算法更加独特和优越的性能.本文介绍了模拟退火算法的原理、实现方法及其求解步骤,并以一具体实例来说明模拟退火算法在解决非线性规划优化问题时的有效性和优越性.

8.学位论文赵长虹超大规模集成电路的平面布图规划算法研究 2006

随着超大规模集成电路的飞速发展，越来越多的模块被集成到同一块芯片上，基于分级的设计流程已成为必然趋势，因此平面布图规划越来越重要。基于这样的原因，本文深入探讨了平面布图规划的各种表示方法，主要研究了传统的平面布图规划问题和新约束条件下的平面布图规划问题。在传统的平面布图规划领域的研究中，提出基于权重的平面布图规划算法和基于线性规划的软模块调整方法。在考虑各种新约束的平面布图规划算法中，提出多时钟系统的平面布图规划算法和考虑电压降的平面布图规划算法。

在基于权重的平面布图规划算法研究中，针对各个模块的面积以及长边长度的不同提出权重的概念，并在此基础上提出基于权重的布图规划算法，该算法根据各个模块权重的不同在优化过程中以不同概率选择相应的模块，克服了原有算法以相同的概率选择各个模块的缺点，达到了更好的布图规划效果。针对软模块的调整问题，本文分析了基于最优化求解超大规模集成电路平面布图规划的方法，对目标函数中的芯片面积本文提出通过估计芯片的长宽比对目标函数进行线性化。此外本文提出利用分段线性的方法对模块面积约束条件线性化，保证了解空间的可行性。实验结果表明使用本文提出的线性规划模型在保证了解空间可行性的同时达到了良好的布图规划效果。

针对多时钟系统的平面布图规划，本文给出了容许的多时钟系统平面布图的定义以及相应的定理和证明，并基于序列对表示法和模拟退火算法提出了多时钟系统平面布图规划算法，对软模块的优化采用了线性规划的方法。本文提出算法在不增加时间复杂度的前提下，根据多时钟系统的特点大大减小了解空间。实验结果表明本文提出的算法对多时钟域平面布图规划有良好效果。

随着集成电路工艺发展，工作电压降低，功耗密度增大，电源网络电压降的问题将越发突出。本文提出在平面布图规划阶段考虑电压降约束，在物理设计初期解决电压降问题，从而加快了物理设计收敛。首先提出了一个快速而满足一定精度的量化电压降的模型，然后基于模拟退火算法和序列对表示法提出考虑电压降的平面布图算法。对软模块的优化采用了线性规划的方法。实验结果表明，本算法在达到良好的平面布图规划效果的同时，有效地降低芯片的平均电压降以及最大电压降。

9.期刊论文钱伟懿.杨宇.王宏杰.杨菊.QIAN Wei-yi.YANG Yu.WANG Hong-jie.YANG Ju 一种具有非线性约束线性规划全局优化算法 -运筹与管理2007,16(1)

本文提出了一种新的适用于处理非线性约束下线性规划问题的全局优化算法.该算法通过构造子问题来寻找优于当前局部最优解的可行解.该子问题可通过模拟退火算法来解决.通过求解一系列的子问题,当前最优解被不断地更新,最终求得全局最优解.最后,本算法应用于几个典型例题,并与罚函数法相比较,数值结果表明该算法是可行的,有效的.

10.学位论文李歧强生产过程的智能决策与调度 1998

调度的复杂性、调度领域知识的多样性和生产环境的动态性决定了调度问题的解决单纯依靠人或计算机是难以完成的,必须把人、人工智能技术、数学规划和计算机有机地结合起来去研究调度问题.如何体现人在生产调度中的决策作用以及如何用多知识表达方式实现一个调度问题是该文研究工作的重点.该文主要包括以下内容:从复杂系统的分析入手,研究了生产系统的分级问题.首先总结了一些分级原则,在此基础上给出了一个分级的生产系统.这种分级的生产系统不但层次清晰,任务明确,而且信息流向清楚,便于生产管理系统设计和分析时的应用.生产调度的执行离不开生产计划的指导,为此研究人员研究了长期生产计划和短期生产计划的混合整数线性规划模型.该模型结构清晰,易于扩展,具有较高的实用价值.为了解决由急件产品或设备故障引起的产品生产周期的动态决策问题,研究人员提出了动态甘特图.该动态甘特图形象、直观,能辅助决策者迅速作出新的决策.以状态任务网为基于建立的化工过程生产调度的模

型具有层次清晰、容易理解和易于扩展等特点,但这种模型仍然摆脱不了维数爆炸或非线性问题.在研究了化工过程的生产调整模型之后,研究人员提出了具有约束指导的模拟退火算法,有效地解决了上述模型求解存在的问题.由于用部分约束指导模拟退火算法的解的产生,减少了不可行解,并由此大大减小了由约束违背所带来的目标值和各约束条件的计算量,较大地加快了算法的收敛速度.为了有效利用调度经验则支持动态调度问题,充分体现决策者的知识作用,该文建立了一种以分散式模糊神经网络为核心的模糊决策支持的生产调度系统.该系统的最大特点在于能通过各网络的推理提取一些新规则,为调度经验经验的进一步完善打下了基础.为加快模糊神经网络的学习速度,研究人员提出了自适应动量和步长解耦的伪牛顿算法,为生产调度系统的在线应用提供了良好的条件.

本文链接：

授权使用：武汉工业学院(whgyxy)，授权号：82d0d53c-380a-4d33-8855-9e4300da5f28

下载时间：2010年12月5日

下载地址：模拟退火算法的研究及其应用19.Doc

　　【】