模拟退火算法研究概况

模拟退火算法文献综述吕正祥交控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，这里0T1；⑨若连续若干次降温后最优点没有改进或降温到给定的阈值,或残差最小,则输出当前优点,计算结束;否则转至步骤④。参考文献：[1]郑中义,吴兆麟.船舶最佳转向避碰幅度决策模型[J].大连海事大学学报,2000,26(4):5-8,13.[2]康立山,谢云,尤矢勇,等.非数值并行算法(第一册)——模拟退火算法[M].北京:科学出版社,1998.[3]李雪.基于模拟退火机制的微粒群算法在城市土地空间布局中的研究与应用[D].山东师范大学,2009.[4]陈梦.模拟退火算法在班轮航线配船优化中的应用[D].大连海事大学,2010.