优化综述报告

1 模拟退火算法综述 一 模拟退火算法的研究进展 模拟退火算法 Simulated Annealing Algorithm 简称SAA 是一种基于对金 属退火过程的模拟发展起来的随机搜索算法 1953年 Metropolis N 等人在研 究二维相变时提出了Metropolis准则 随着对固体退火过程研究的的深入 Kirkpatrick S 1980 等人和Cerny V 1981 首先意识到其与组合优化问题 之间存在的类似性并相继独立的提出了SA思想 不久 他们将Metropolis准则 引入到组合优化过程当中 形成了最早的常规模拟退火算法 1983年 并首先 将这种算法应用到了VLSI的设计 但对于类似的大规模的组合优化问题而言 它的收敛速度很慢 由此 1986年Szu H提出了一种退火率与时间成反比的快速 模拟退火算法 FSA 1987年 Laarhoven P 和Aarts出版了 模拟退火理论与 应用 对SA算法做了比较系统的阐述 总结 极大地促进了之后SA算法的理论 研究与实际应用 在SA发展史上具有里程碑式的意义 在其后的二十几年里 针对模拟退火算法实际应用中出现的各种问题 许多人有侧重性的进行了不同 程度的研究和实验 对工程实际问题的解决起到了较好指导和借鉴作用 取得 了不错的效果 如 1990年Gunte D 和Tobias S 对算法中的Ts 初始温度 的 确定方法进行了研究 1995年Tarek M 对算法进行了并行优化计算的研究 以 求提高计算效率 用以解决比较复杂的科学和工程计算问题 1993年 Kirkpatrick S 将SA算法用于优化总是 取得了不错的效果 2002年耿平等人 采用人工神经网络方法建立多变量与多目标函数之间的关系 并将模拟退火算 法与人工神经网络BP算法相结合 解决了这类复杂系统中多函数变量与多目标 函数之间没有确定的解析关系因而无法进行直接优化的难题 并为解决多变元 非线性复杂系统的优化问题提供了一种新的有效的方法 当然 这同计算机技 术 数学 以及相关学科的发展是分不开的 总体表现为 从理论研究上来讲 业已证明SA算法可以达到全局极小值 它是基于有限状态奇异Markov链的有关 理论 给出SA算法的某些关于理想收敛模型的充分条件或必要条件 这些条件 在理论上证明了退火三原则 初始温度足够高 降温速度足够慢 终止温度足 够低 满足时 SA算法能够以概率1获取全局最优解 因而也就表明在局部层次 上 针对算法的参数 结构等的各种研究对于算法的整体把握和工程应用是有 意义的 从实际应用上来讲 理论研究的深入和多样性 使得模拟退火算法已 从经典的常规模拟退火算法发展成为一种混合型或复合型的模拟退火算法 比 如 遗传 模拟退火算法 它是将遗传算法良好的收敛性和模拟退火解变换的自 适性有效结合起来 带返回搜索的模拟退火算法 它是一种将传统算法快速 2 良好的局部搜索能力以及针对退火内循环迭代过程中可能先前已获得了最优解 却必须经过暂时恶化的 山脊梁 使得最终解不一定是最优解的情况对解予以 记忆处理结合起来一种算法 当然 他们的应用受限于具体的实际问题 没有 完全的通用性可言 只是针对某一类 这对算法研究者提供了解决空间和挑战 目前 正处于模拟退火算法兴盛期 无论是理论研究和应用研究都是十分热门 的课题 有待于我们去探索和实践 二 模拟退火算法的特点 1 以一定的概率接受劣解 传统算法在搜索进程中只接受好解 不接爱劣 解 而模拟退火算法以一定的概率随机接受劣解 有利于改善解的质量 增强 新解迭代过程中的自适应性和灵活性 可避免陷于局部最优的 陷阱 确保 缩短算法运行时间 确保获得较好的近似最优解 2 引入算法控制参数T T始终贯穿于算法的整个进程 具体表现为它对外循 环的直接控制和内循环的间接控制 就内循环而言 在每个控制参数T下 借用 前一迭代解和摄动装置可产生新的随机迭代解 T对其中的好解 df0 以态概率exp df T 是否大于由随机矩阵rand产生的 随机数决定是否接受劣解 很明显 状态概率的大小主要由T决定 并且在很大 程度上决定着Markov链的长度 就外循环而言 直接控制参数T缓慢降低 提高 接收准则 直至 T趋向0 状态链稳定于优化问题的最优状态 提高SA算法获得 全局最优解的可靠性 3 使用目标函数值 即适应值 进行搜索 传统搜索算法不仅需要利用目标函 数值 而且往往需要且标函数的导数值等其它一些辅助信息才能确定搜索方向 当这些信息不存在时 算法就会无效 而SA算法仅使用由目标函数变换来的适 应度函数值就可完成 此外 SA算法的适应度函数不仅不受连续可微的约束 而且其定义域可以任意设定 对适应度函数唯一要求是 对于输入可计算出加 以比较的正的输出 这个特性对很多无法或很难求导数的函数 或导数不存在 的函数的优化以及组合优化等问题 应用SA算法就显得比较方便 4 隐含并行性 并行算法是6O年代发展起来的 发展迅速 它的特点是收敛 速度较其它算法要快 SA算法隐含并行性的特点启示我们 如果能将并行策略 加入到SA算法中 将会提高解的质量和收敛速度 这也是它优于其它算法求解 过程的关键所在 另外 SA算法的隐含并行性还有助于处理非线性问题 5 搜索复杂区域 由于SA算法不受初始解的限制并且能够以一定的概率接受 新解 因而最善于搜索复杂区域 从中找出期望值高的区域 上述特点使得SA法使用简单 鲁棒性强 易于并行化 从而应用范围甚广 三 模拟退火算法存在的主要问题及解决方法 3 模拟退火算法虽然能够以一定的概率动态接受劣解 改变搜索方向 跳出 局部最优的 陷阱 从而获得近似的全局最优解 但也有许多不中主要表现为 1 如果降温过程比较缓慢 得到好解的机率比较大 与此相对的收敛速度 会太慢 如果问题的规模不可避免地增大时 运行时间将会非常长 算法将失 效 2 如果降温过程过快 很可能陷入局部搜索 得不到全局最优解 显然 两种比较极端的情况都背离了我们设计和运用算法以求较好解决问题的初衷 因此 非常有必要探求改进算法的实验性能 提高算法执行效率的可行途径 主要如下 1 设计合适的状态发生器 使其搜索过程能够尽可能覆盖全部解 空间 2 选取合理的冷却进度表 冷却进度表中的 t0 tf Lk a 在很大程 度上决定着算法的进程 这有赖于实验和经验 3 设计高效的退火过程 在运行时间允许的条件下 尽可能使退 火缓慢平稳进行是获取全局最优解的关键 4 采用并行搜索结构 并行搜索结构可以加快收敛的速度 缩短 运行时间 5 为避免陷入局部极小 改进对温度的控制方式 6 增加某些局部环节 如升温或重升温过程 加温退火算法 在算法进程中 适当升温 可激活各状态接受概率 调整搜索进程以避免陷于 局部极小 增强记忆 带记忆式模拟退火算法 用以记忆可能遗失的最优解 增加补充搜索过程 回火退火法 在退火完成后 以当前所获得的最优解再次 退火搜寻最优解 结合其它搜索机制 如基于粒子群的模拟退火算法等 四 模拟退火算法的发展趋势 目前 关于SA算法的研究通常分为两类 第一类 基于有限状态奇异马尔可 夫链的有关理论 给出SA的某些关于理想收敛模型的充分条件或充要条件 这 些条件在理论上证明了当退火三原则 初始温度足够高 降温速度足够慢 终止 温度足够低 满足时 SA以概率1达到全局最优解 第二类 针对某些具体问题 给出了SA的若干成功应用 前者在指导应用方面作用有限 在定参过程中 往 往很难给出有益的定量关系 后者各自的领域中有应用价值 但过分依赖于问 题 不具有普遍意义 事实上 在现有情况下给出关于SA的具有普遍意义的定 量关系式是不现实的 因此 对SA进行的有意义研究应集中在引入新思想在此 基础上提出在应用中实现新思想的可能途径 并通过典型实验对其效果进行验 证 SA的未来发展方向应着重解决以下几个问题 1 如何把传统的启发式搜索方法与SA随机搜索算法结合起来 4 2 如何把SA算法与GA 遗传 算法有机结合起来 开发出一种更具有理论意义和 应用价值的随机搜索算法 3 由于SA及其变种所固有的特点 它们在解决某些特殊领域的问题时具有很好 的性能 寻找更多的使用领域 并在这些领域中给出成功的应用系统 也是一 个颇具理论意义和应用价值的研究方向 1 冯玉蓉 模拟退火算法的研究及应用 M 昆明理工大学 2005 3 2 王凌 智能优化算法及其应用 M 北京 清华大学出版社 2001 3 耿平 刘静 曾梅光 多变元非线性复杂系统的优化与模拟退火算法 J 东北大学学报 自