模拟退火算法研究概况样本

模仿退火算法文献综述吕正祥交控15011模仿退火算法简述1.1模仿退火算法来源模仿退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。模仿退火算法(SimulatedAnnealing，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步。2.模仿退火算法流程2.1模仿退火算法流程图2.2模仿退火算法中参数选取2.2.1冷却进度表咱们称调节模仿退火法一系列重要参数为冷却进度表。它控制参数T初值及其衰减函数，相应MARKOV链长度和停止条件，非常重要。

一种冷却进度表应当规定下述参数：1．控制参数t初值t0;

2．控制参数t衰减函数；

3．马尔可夫链长度Lk。（即每一次随机游走过程，要迭代多少次，才干趋于一种准平衡分布，即一种局部收敛解位置）

4．结束条件选取

2.2.2有效冷却进度表判据：

一．算法收敛：重要取决于衰减函数和马可夫链长度及停止准则选取

二．算法实验性能：最后解质量和CPU时间

参数选用：

一）控制参数初值T0选用

普通规定初始值t0值要充分大，即一开始即处在高温状态，且Metropolis接受率约为1。(1)均匀抽样一组状态，以各状态目的值方差为初温。(2)随机产生一组状态，拟定两两状态间最大目的值差|Δmax|，然后根据差值，运用一定函数拟定初温。例如，t0=－Δmax/pr，其中pr为初始接受概率。

二）衰减函数选用

衰减函数用于控制温度退火速度，一种惯用函数为：T(n+1)=K*T(n)，其中K是一种非常接近于1常数。

三）马可夫链长度L选用

原则是：在衰减参数T衰减函数已选定前提下，L应选得在控制参数每一取值上都能恢复准平衡。

四）终结条件

有诸各种终结条件选取，各种不同条件对算法性能和解质量有很大影响，咱们只简介一种惯用终结条件。即上一种最优解与最新一种最优解之差不大于某个容差，即可停止本次马尔可夫链迭代。3模仿退火算法优缺陷

长处：计算过程简朴，通用，鲁棒性强，合用于并行解决，可用于求解复杂非线性优化问题。缺陷：收敛速度慢，执行时间长，算法性能与初始值关于及参数敏感等缺陷典型模仿退火算法缺陷：（1)如果降温过程足够缓慢，多得到解性能会比较好，但与此相对是收敛速度太慢；(2)如果降温过程过快，很也许得不到全局最优解。模仿退火算法改进：(1)设计适当状态产生函数，使其依照搜索进程需要体现出状态全空间分散性或局部区域性。(2)设计高效退火方略。(3)避免状态迂回搜索。(4)采用并行搜索构造。(5)为避免陷入局部极小，改进对温度控制方式(6)选取适当时始状态。(7)设计适当算法终结准则。也可通过增长某些环节而实现对模仿退火算法改进。重要改进方式涉及：(1)增长升温或重升温过程。在算法进程恰当时机，将温度恰当提高，从而可激活各状态接受概率，以调节搜索进程中当前状态，避免算法在局部极小解处停滞不前。(2)增长记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到最优解，可通过增长存储环节，将某些在这之前好态记忆下来。(3)增长补充搜索过程。即在退火过程结束后，以搜索到最优解为初始状态，再次执行模仿退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索方略，以概率接受区域内最优状态，而非原则SA单次比较方式。(5)结合其她搜索机制算法，如遗传算法、混沌搜索等。(6)上述各办法综合应用。4船舶碰撞有关领域关于模仿退火算法应用4.1舶碰撞危险量化研究基本上经历了四个阶段:第一阶段是基于交通流理论，以船舶会遇率(或会遇次数等)、特定水域历史碰撞事故等，评价特定水域碰撞危险度。第二阶段是从微观角度，依照人体行为学及心理学等，以船舶领域或动界评价碰撞危险度。第三阶段在拟定船舶碰撞危险度时，应当综合考虑DDCPA和TTCPA两方面影响。第四阶段是实现TTCPA与DDCPA拟定碰撞危险度[1]。船舶会遇态势划分船舶会遇是海上最常用船舶交会态势，其划分原则是依照国际海上避碰规则、航海习惯和自动避碰办法三者综合分析成果。由文献[1]可知，海上互见中两船，可划分为对遇(F)、交叉相遇(A、B、E)和追越(C、D)几类会遇态势，如图1所示。图中对相对舷角为F、A、B区域来船，本船为让路船。对来自F、A区域船，本船应采用向右转向避让操纵，对来自B区域船，因与本船相对舷角较大，可采用向左转向避让操纵；对相对舷角为E、D、C区域来船，本船可视为直航船而不采用任何避让操纵，只有当浮现紧近局面时，本船才采用避让操纵。图一互见中两船会遇态势划分4.2船舶碰撞危险度拟定本文将综合前人研究成果,以来船与本船构成方位(B)、距离(D)、船速比(K)、近来会遇距离(DCPA)和近来会遇时间(TCPA)为参数,给出来船与本船构成碰撞危险度预计。设与本船会遇目的船数为n≥1艘，UDCPAi、UTCPAi、UDi、UBi、UKi为目的船i各参数危险从属度且属于[0，1]，i=1，2,…,n，则目的船i碰撞危险度fi可表达[18]为：fi(uDCPAi、uTCPAi、uDi、uBi、uKi)=aDCPAuDCPAi+aTCPAuTCPAi+aDuDi+aBuBi+aKuKiD1为最晚避让距离，D2为可采用避让办法距离；C为碰角(0≤C≤180°)；W为常数，取W=2；aDCPA、aTCPA、aD、aB、aK为目的船参数权重，均属于[0，1],且aDCPA+aTCPA+aD+aB+aK=1。4.3目的函数模型当本船与各种来船会遇时,如何依照各种来船会遇态势,选取较为合理和最为有效转让幅度问题，始终是人们关注和研究焦点。将本船与多船间转向避碰幅度问题视作一类多目的函数优化问题,然后应用模仿退火算法,从可行解空间中求出满足目的函数和约束条件最优转向避碰幅度解,使得转让后本船满足：①与各会遇目的船间碰撞危险度尽量减小;②尽量使转让角度最小；③航行至少时间后，本船恢复原航向、航速。4.4模仿退火算法最优转向避碰幅度决策模仿退火算法[2]是源于对固体退火过程直接简朴模仿而建立起一种通用随机搜索技术。由于其具备稳键性、健壮性和高效性等特点,近年来已在求解许多组合优化问题,特别是在解NP完全问题中得到了成功应用。本文将结合船舶避碰实际,把模仿退火算法引入到船舶避碰决策领域,在可行解空间中随机搜索,从中求出本船满足多目的函数和约束条件最优转向幅度。详细实现环节为：①以均匀概率在可行解空间[30，180]中随机产成一种转向幅度x,作为初始状态当前最长处;②设立初始温度T0=Tmax；③设立循环初值num=1；④算出本船转向前与各目的船构成碰撞危险度fi和转向x后与各目的船构成碰撞危险度f1i(x),i=1，2,…,n；⑤计算残差和；⑥对当前最长处x作一随机扰动(如加白噪声),产生一种新最长处。重新计算增量Δ；⑦应用Meteopolis规则拟定与否接受新产生最长处。如果Δ<0,则接受该新产生最长处为当前最长处,否则以概率接受该新产生最长处为当前最长处；⑧判断num,若num<终结步数,则num=num+1,转至环节④,否则进行降温,使T0取值为T，这里0<T<1；⑨若持续若干次降温后最长处没有改进或降温到给定阈值,或残差最小,则输出当前长处,计算结束;否则转至环节④。参照文献：[1]