模拟退火算法研究概况(1).pdf

学 海 无 涯 模拟退火算法文献综述模拟退火算法文献综述 吕正祥吕正祥 交控交控 15011501 1 1 模拟退火算法简述模拟退火算法简述 1 11 1 模拟退火算法的来源模拟退火算法的来源 模拟退火算法来源于固体退火原理 将固体加温至充分高 再让 其徐徐冷却 加温时 固体内部粒子随温升变为无序状 内能增大 而徐徐冷却时粒子渐趋有序 在每个温度都达到平衡态 最后在常温 时达到基态 内能减为最小 模拟退火算法 Simulated Annealing SA 最早由 Kirkpatrick 等应用于组合优化领域 它是基于 Monte Carlo 迭代求解策略的一种 随机寻优算法 其出发点是基于物理中固体物质的退火过程与一般组 合优化问题之间的相似性 模拟退火算法从某一较高初温出发 伴随 温度参数的不断下降 结合概率突跳特性在解空间中随机寻找目标函 数的全局最优解 即在局部最优解能概率性地跳出并最终趋于全局最 优 模拟退火算法是一种通用的优化算法 理论上算法具有概率的全 局优化性能 目前已在工程中得到了广泛应用 诸如 VLSI 生产调度 控制工程 机器学习 神经网络 信号处理等领域 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概 率突跳性 从而可有效避免陷入局部极小并最终趋于全局最优的串行 结构的优化算法 1 21 2 模拟退火算法模拟退火算法的模型的模型 模拟退火算法可以分解为解空间 目标函数和初始解三部分 学 海 无 涯 1 1 3 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 然后转第 2 步 学 海 无 涯 2 2 模拟退火算法流程模拟退火算法流程 2 12 1 模拟退火算法流程图模拟退火算法流程图 2 2 2 2 模拟退火算法模拟退火算法中中参数的选择参数的选择 2 2 2 2 1 1 冷却进度表冷却进度表 我们称调整模拟退火法的一系列重要参数为冷却进度表 它控制 参数 T 的初值及其衰减函数 对应的 MARKOV 链长度和停止条件 非 学 海 无 涯 常重要 一个冷却进度表应当规定下述参数 1 控制参数 t 的初值 t0 2 控制参数 t 的衰减函数 3 马尔可夫链的长度 Lk 即每一次随机游走过程 要迭代多少次 才能趋于一个准平衡分布 即一个局部收敛解位置 4 结束条件的选择 2 2 2 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 3 模拟退火算法的优缺点模拟退火算法的优缺点 优点 计算过程简单 通用 鲁棒性强 适用于并行处理 可用 于求解复杂的非线性优化问题 缺点 收敛速度慢 执行时间长 算法性能与初始值有关及参数 敏感等缺点 经典模拟退火算法的缺点 1 如果降温过程足够缓慢 多得到的解的性能会比较好 但与此相 对的是收敛速度太慢 2 如果降温过程过快 很可能得不到全局最优解 模拟退火算法的改进 1 设计合适的状态产生函数 使其根据搜索进程的需要 表现出状态的全空间分散性或局部区域性 2 设计高效的退火策略 3 避免状态的迂回搜索 学 海 无 涯 4 采用并行搜索结构 5 为避免陷入局部极小 改进对温度的控制方式 6 选择合适的初始状态 7 设计合适的算法终止准则 也可通过增加某些环节而实现对模拟退火算法的改进 主要的改 进方式包括 1 增加升温或重升温过程 在算法进程的适当时机 将温度适当提 高 从而可激活各状态的接受概率 以调整搜索进程中的当前状 态 避免算法在局部极小解处停滞不前 2 增加记忆功能 为避免搜索过程中由于执行概率接受环节而遗失 当前遇到的最优解 可通过增加存储环节 将一些在这之前好的态记 忆下来 3 增加补充搜索过程 即在退火过程结束后 以搜索到的最优解为 初始状态 再次执行模拟退火过程或局部性搜索 4 对每一当前状态 采用多次搜索策略 以概率接受区域内的最优 状态 而非标准 SA 的单次比较方式 5 结合其他搜索机制的算法 如遗传算法 混沌搜索等 6 上述各方法的综合应用 4 4 船舶碰撞相关领域有关模拟退火算法的应用船舶碰撞相关领域有关模拟退火算法的应用 4 14 1 舶碰撞危险的量化研究基本上经历了四个阶段舶碰撞危险的量化研究基本上经历了四个阶段 第一阶段是基于交通流理论 以船舶会遇率 或会遇次数等 特定水域历史碰撞事故等 评价特定水域的碰撞危险度 第二阶段是 学 海 无 涯 从微观的角度 根据人体行为学及心理学等 以船舶领域或动界评价 碰撞危险度 第三阶段在确定船舶碰撞危险度时 应该综合考虑 DDCPA 和 TTCPA两方面的影响 第四阶段是实现TTCPA与 DDCPA 确定碰撞危险度 1 船舶会遇态势的划分 船舶会遇是海上最常见的船舶交会态势 其划分原则是根据国际 海上避碰规则 航海习惯和自动避碰方法三者综合分析的结果 由文 献 1 可知 海上互见中的两船 可划分为对遇 F 交叉相遇 A B E 和追越 C D 几类会遇态势 如图 1 所示 图中对相对舷角为 F A B 区域的来船 本船为让路船 对来自 F A 区域的船 本船 应采取向右转向避让操纵 对来自 B 区域的船 因与本船的相对舷角 较大 可采用向左转向避让操纵 对相对舷角为 E D C 区域的来船 本船可视为直航船而不采取任何避让操纵 只有当出现紧近局面时 本船才采取避让操纵 图一 互见中的两船会遇态势的划分 4 24 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 aDCPA uDCPAi aTCPAuTCPAi aDuDi aBuBi aKuKi D1为最晚避让距离 D2为可采取避让措施距离 C 为碰角 0 C 学 海 无 涯 180 W 为常数 取 W 2 aDCPA aTCPA aD aB aK为目标船参数的 权重 均属于 0 1 且 aDCPA aTCPA aD aB aK 1 4 34 3 目标函数模型目标函数模型 当本船与多个来船会遇时 如何根据多个来船的会遇态势 选 择较为合理和最为有效的转让幅度问题 一直是人们关注和研究的焦 点 将本船与多船间的转向避碰幅度问题视作一类多目标函数优化 问题 然后应用模拟退火算法 从可行解空间中求出满足目标函数 和约束条件的最优转向避碰幅度解 使得转让后的本船满足 与 各会遇目标船间的碰撞危险度尽量减小 尽量使转让的角度最小 航行最少的时间后 本船恢复原航向 航速 4 44 4 模拟退火算法的最优转向避碰幅度决策模拟退火算法的最优转向避碰幅度决策 模拟退火算法 2 是源于对固体退火过程的直接简单模拟而建 立起的一种通用随机搜索技术 由于其具有稳键性 健壮性和高效性 等特点 近年来已在求解许多组合优化问题 特别是在解 NP完全问 题中得到了成功应用 本文将结合船舶避碰实际 把模拟退火算法 引入到船舶避碰决策领域 在可行解空间中随机搜索 从中求出本 船满足多目标函数和约束条件的最优转向幅度 具体实现步骤为 以均匀概率在可行解空间 30 180 中随机产成一个转向幅度 x 作为初始状态的当前最优点 设置初始温度 T0 Tmax 设置循环初值 num 1 算出本船转向前与各目标船构成的碰撞危险度 fi和转向 x 后 学 海 无 涯 与各目标船构成的碰撞危险度 f 1 i x i 1 2 n 计算残差和 对当前最优点x 作一随机扰动 如加白噪声 产生一个新的最优 点 重新计算增量 应用 Meteopolis 规则确定是否接受新产生的最优点 如果 0 则接受该新产生的最优点为当前最优点 否则以概率接 受该新产生的最优点为当前最优点 判断 num 若 num 终止步数 则 num num 1 转至步骤 否 则进行降温 使 T0 取值为 T 这里 0 T 1 若连续若干次降温后最优点没有改进或降温到给定的阈值 或残 差最小 则输出当前优点 计算结束 否则转至步骤 参考文献 1 郑中义 吴兆麟 船舶最佳转向避碰幅度决策模型 J 大连海 事大学学报 2000 26 4 5 8 13 2 康立山 谢云 尤矢勇 等 非数值并行算法 第一册 模 拟退火算法 M 北京 科学出版社 1998 3 李雪 基于模拟退火机制的微粒群算法在城市土地空间布局中的 研究与应用 D 山东师范大学 2009 4 陈梦 模拟退火算法在班轮航线配船优化中的应用 D 大连海事 大学 2010 。