连续变量问题全局优化的模拟退火法.pdf

19 95年9月 系统工程理论与实践 第9期 连续变量问题全局优化的模拟退火法 胡山鹰陈丙珍何小荣 清华 大学 化学系 北 京100 08 4 摘要本文针对 过程系统连续变量优化问题 中普遗 存在的多峰 现象 探索了应用模 拟退火 法求解其全局最优 解 文 中根据连续变量问题的特性 提出 了一种相邻状态的产生函数和 迭代 方案 并分析了模 拟退火过 程的起始温度 终止温度以及降温速度等参数对优 化计算 的影 响 给出 了这些 参数的适 宜区域 通过三个例题的计 算 将模拟退 火法 与传统优化 方 法一梯度法 进 行了对比分 析 结果表明该法能 够有效地解决传统的确定型 优化方 法所不 能奏 效的全局优化问题 关健词连续 变量全局优化模拟退火 退火方 案 相邻 状态 ASim ulated A nne aling M etho df o r G lob al O Ptimiz ation tothe C o n t inu ous 与 Jria bl e P ro b l e m s H u Sh a 盯i ng ChenBing zhen H e X ia o r ong D ep a r t m en to f Ch em iea l E n gineening T sing h u a U niv ersity B ei jing 1000 8 4 Ab str a c tInthi sPa P e r a i 而n g at m ult元 Pe砍Phen o m enon whiehg en e ra l l y e范sts inth ePro e e s ssystemoPtim 汤a tio nProb l ems w ith e o n ti n uous v a r ia bles asimu l atedannea l ing a P Pr o a eh 15in t rodue ed to s ea reh the g l o ba l o Ptima l s o lu ti n n A e e o rding totheProPe rt y o fth ee on tin u ous v a r iabl e Pro卜 lem a f u netiono fProdu eingad j a centstate 1 5Pr oPo s ed andef f eetsofin itia l temPe ra t ur e te rmina ltemperatur e a s w ell a sa n ne a l i ngs ehedu leto the oPti ma l ea leuation a r e a n a ly s ed and their suita b le s eoPe s a r e g i v e n T he r esu lts o fth re eex a m Ples and the e o mPa ri s on withthe solu tio ns byth e g ra d ient ba s ed m atho d sshow the simulateda nne a li n g aPPr o a ch e anef f ieie n tly s o l v e thegl o b a l oPtima lPr ob l em w hieh15dif f i eultly d ealt with bythetraditio n 成 d eterm ioistie oPtim a lm etho d s K eywor d seo l l t in u ous v a r iab le globaloPtimiza tio n simu lated annea l ing a n neal ing sehedule a d j ae entstate 1 引言 目前应用数学规划方法 尤其是非线性规划方法进行优化计算时 所遇到的一个最难解决的问 别就是求全局最优解 由于非 线性规划 问题绝大多数是 多峰的 存在局部最优解 对于不同的决策变 量初值 往往得到不 同的最优解 这导致了这 类方法 的应用受到很大 的限制 如 过程系统的优化综合 1 1 2 及换热网络的柔性分析1 3 4 都可转化为非 线性规划 问题进行求解 但 由于非线性规划本身的求 解方法还存在上述的 困难 使得这些过程系统优化方法及柔性分析方法难以进行实际实用 上 述 问题 0 本文于199 5年7月14 日收到 国家自然科学基金和 国家教委留学回国启动基 金资助项目 第二 届全国过程 系统工程学术研讨会获奖论文 系统工程理论与实践 19 9 5年9 月 要求对连续变量全局最优解具有较好的处理方法 迄今为止已有许多学者对这一问题进行了研究 在 化工领域 G R K o c i sl s c A F l oud a sl o 对该问题进行了一定的研究 Ko ci s 的方法是通过外部 近似和等式松驰算法以及两 阶段策略进行求解 F l o u da s 的方 法主要是将变量 分为复杂变量 和非复 杂变量 从而将问题分解为多个凸子问题 分别求解 然后得出全局最优解 但是这些方法既不能从数 学上严格地保证 达到 全局最优解 而且求解过程比较冗长 不 便于 工程实际应用 另外一种处理局部 最优的方法 是通过改变初值点进行 多次优化寻找全局最优点 该 法具有简明易行特点 但更无法保 证得到全局最优解 由此可以看出 连续变量 的全局优化问题是一个非常难以解决的问题 针对 这一 情况 本文将探索一种较为有效而又简便实用的方法解决这一问题 随着应用数学方法 的发展 到八 十年代初 5 K ir kpa tr ic kl v 提出 了模拟 退 火方法 该方法应用 于复杂的组合优化中得出了很好的 结果 这类方法是一种 仿金属退 火的随机算 法 在理想状态下 可得出全局最优解 目前这类算法在离 散问题的优化中已取得很好的效果 7一1 1 长在化工领域中 A N Pa t e l ll z 将之用于多产品间歇生产 的予 设计也很有效 但在连续变量 问题的优化上 尚缺乏系统的研究 本文旨在将此方法应用于连续变 量 问题求解全局最优解进行探讨 2 模拟退火方法简介 模拟退 火法是模拟 金属 退火 的方 法 这种方法是 如何 寻找全局最 优解呢 统 计热力学表明 在 平衡状态下 原子 能量 的概率分布在给温度T满足B o lt z m an 方程 尸 E E 门 l Z T 餐 1 其 中E 门为状态 的能量 kB 为 Bo lt z m an 常数 Z T 为概率分布的标准化因子 在任意一个 温度下 平衡状态最可 能在原子能量最低的状态达到 这与组合优化问题有相同之处 如将能量状 态看成组合优化问题 中的一个状 态 能量最低 的点也就转化成求费用函数的最小值点 由此 K irkp atriek 将此方法首次应用到组合优化问 题中 以往的优化算法主要是确定型算法 其 基本思想是选择一个初始点 而后逐步迭代 这种算法会遇到下列问题 1 最终结果依赖于起始点 2 最终结果 可能是 一个局部最优点 模 拟退火方法改变了确定性 这 是一种启发式算 法 其特点是既能 向目标降低的方向迭代 又 能以一定概率接受目标函数升高的情况 当迭 代温度中够高时 这种迭代就可跳出局部最优 点 找到全局 最优 解 模拟 退火法的一般算法如 图1所示 模拟 退火法目前主要应用于离散问题的优化 对 连 续变量 的优化尚缺乏研究 本文将探讨 如何将 模拟退 火方 法应用于连续问题求全局最优解 起起始温度度 生生成 初始化 化 参参数初始化化 生生成 下一个相邻 状态态 是是 否接 受该相邻状 态 选选选选选选选选选选选择 新 新 达达到平衡 的温度 度 是是否满足终止准则则 输输出最优解解 图 1 一般模拟退火算法 第9期连续变 量问题全局优化的模拟退火法 3 连续变t全局优化 模拟退火求连续变量全局优化问题时 从理论上讲 是对每个温度通过多次迭代达到平衡 当温 度从足够高降到足够低时 就可求出总体的目标函数最低点 即全局最优解 但这是 理想的结果 因 为在任一沮度下要达到能量平衡 需迭代无穷多次 这在计算上是不可能实现的 只能包括所有的范 围 而且理想的退火要求温度连 续下 降 这也是 计算不可能达到有 这些因素都使模拟 退火算法实际 上 也是 近似的 但是如何设计上述变量使该法在有限的计算得出尽量好的结果 这是本文对模拟退火 方法进行研究的目的 针对连续变量问题的特点 还要解决相邻状态 的产生 以及如何满足约束条件 等关键问题 1 问题的提出 本文所要解决的问题是对如下连续变量优化问题求全局最优解 nlnC X f X Y 三0 从X y 0 2 其中C为目标函数 f和h为不等式和等式约束条件 X为决策变量 Y为状态变量 均为向 本文首先解决一类较为简单的问题 即约束条件不包含等式约束 这样相 应地不存在状态变量 同时不等式约束仅含一种特殊情况 即决策变量的上下 限约束 这样在这部 分所要解决的问题可 量 Y 表示为 InlnC X X L X C 则目标函数上升 求概率p 二 e x p 一 C T 其中 c cN 一co T为当前退 火温度 产生一个 一1 间随机数R 如 果尸ZR 则接受x N为 新的状态取代X 否则不接受X N 及以x 继续迭代 1121 2 起始温度 乃 模拟退火的起始温度乃要取得足够 大使 C 二CN 一CO 1 从而能够跳出局部陷阱 但为 了减少计算量 乃不宜取太大 11 1 3 终止温度 几 终止温度几应该是T趋向零时判别终止 但由于使 T 0 需迭代无穷多次 故取 几 为一较 小数使 exp C 几 0 收敛到最优解 4 某一温度 及到下一温度及 1 的降温速度 第9期连续变 量问题全局优化的模拟退火法 3 连续变t全局优化 模拟退火求连续变量全局优化问题时 从理论上讲 是对每个温度通过多次迭代达到平衡 当温 度从足够高降到足够低时 就可求出总体的目标函数最低点 即全局最优解 但这是 理想的结果 因 为在任一沮度下要达到能量平衡 需迭代无穷多次 这在计算上是不可能实现的 只能包括所有的范 围 而且理想的退火要求温度连 续下 降 这也是 计算不可能达到有 这些因素都使模拟 退火算法实际 上 也是 近似的 但是如何设计上述变量使该法在有限的计算得出尽量好的结果 这是本文对模拟退火 方法进行研究的目的 针对连续变量问题的特点 还要解决相邻状态 的产生 以及如何满足约束条件 等关键问题 1 问题的提出 本文所要解决的问题是对如下连续变量优化问题求全局最优解 nlnC X f X Y 三0 从X y 0 2 其中C为目标函数 f和h为不等式和等式约束条件 X为决策变量 Y为状态变量 均为向 本文首先解决一类较为简单的问题 即约束条件不包含等式约束 这样相 应地不存在状态变量 同时不等式约束仅含一种特殊情况 即决策变量的上下 限约束 这样在这部 分所要解决的问题可 量 Y 表示为 InlnC X X L X C 则目标函数上升 求概率p 二 e x p 一 C T 其中 c cN 一co T为当前退 火温度 产生一个 一1 间随机数R 如 果尸ZR 则接受x N为 新的状态取代X 否则不接受X N 及以x 继续迭代 1121 2 起始温度 乃 模拟退火的起始温度乃要取得足够 大使 C 二CN 一CO 1 从而能够跳出局部陷阱 但为 了减少计算量 乃不宜取太大 11 1 3 终止温度 几 终止温度几应该是T趋向零时判别终止 但由于使 T 0 需迭代无穷多次 故取 几 为一较 小数使 exp C 几 0 收敛到最优解 4 某一温度 及到下一温度及 1 的降温速度 第9期连续 变量 问题全局优化的模拟退火法 要检验新值是 否超限 如果超限 则以上下限值代之 当 x 变为 x 尹时 X从 老状 态 X 产生出新的相邻状态X N 解决上述问题之后 可以确定 一个求解连续变量全局 最优 问题的算法如图 2 所示 4 计算结果分析 下面以一个实例计算结果分析连续变量模拟退火算法各参数 例 1 刃a ln c x 二 4 4 5 xl一 4 x 对 2 x 孟 一 Z x lx 心 一10 0 0 三 xi 三10 0 0 一100 0 兰 劣2 三10 0 0 2二了 xZ 由解析法可 知该 问题存在一个全 局最优点C1 0 5 3 1 025 C 一0 5 134 一个局部最优点 1 9 41 3 85 4 C 0 98 55和 一个鞍点 0 6 1 17 1 49 3 C 2 83 0 应用所提出的模拟 退火算法求解该 问题 当取 a 0 9 5 l e n g th 5 s ca l e 初值为100 0 b二0 9 5 T 二 1 0 0 2飞 0 0 01 时 不论从何初值点开始均可得出全局最优解 误差很小 如表 1 所示 表1模 拟退火求解 例1结 果表2降温速度 和 迭 代长度分析 初初 值值 目标函数 数 相对误差 差 10 0 1 0 0 一0 5132 2 20 0 4 一10 0 100 一0 513 4 4 4O O O 10 0 一1 0 0 一0 5 134 4 40 0 0 一100 一100 一0 5134 4 40 0 0 3 6 一0 5 13 0 0 00 0 8 a a a a a 迭代次数数 l en g t h h h目标函数 数 0 0 0 95 5 5180 0 05 5 5 刁 5 134 4 4 0 0 0 9 0 0 08 8 8 85 5 5 刁刃 2 68 8 8 0 0 0 8 0 0 04 2 2 220 0 0 一习 5131 1 1 0 0 0 7 5 5 533 3 320 0 0 一0 47 6 8 8 8 0 0 0 5 0 0 014 4 450 0 0 一0 513 2 2 2 0 0 0 4 5 5 51 2 2 250 0 0 一0 419 0 0 0 对于降温速度对 优化的影响进行了分析 从 同一初值 1 0 1 0 开始 取乃 二10 0 几 二0 00 1 s ca l e 初值 1 0 00 b二0 9 5 对 a 和l e n g t h 的不同值进行了计算 结果如表 2 所示 可知当 a 和l e n g th 分别取 0 9 5 和5 0 8和2 0 0 5和50 时结果都不错 说明每一温度下迭代长度较小时 温度下 降速度要求较慢 而迭代长度较大 时 温度下降可更快 总的迭代次数差不多 参数的选择可根据具 体情况而定 对于乃和 马 的取值 也进行了分析 如表3所示 其 中变量初值为 5 0 50 a 0 9 5 l e n g th 5 s ca l e 初值 10 0 0 b二0 9 5 变化 乃时 几 0 00 1 变化 几 时 乃 1 0 0 结果表明当T I取值太 小时 跳不出局 部极值点 几 的取值增大时精度下降 一般来说乃 几 1 0 0 0 时 结果不好 本 例中取乃 1 0 0和 马 住G0 1 较好 自适应邻域因子s ca l e 初值及自适应系数b的取 值对优化计算的影 响如表 4 所示 变量初值为 10 0 1 00 a 0 9 5leng th 5 T 1 10 0 T E 0 0 0 1 计算结果表明 se ale 的终值不大于 0 1 较好 在此基础上应使 s ca le 初值尽量大 一般取b a 则 sc a l e 初值可取乃 几 0 1 系统工程理论与实践 19 9 5年9 月 表 3 起始温度 和终止温度 分 析 表4邻域因 子分 析 T T T 汉毖 毖 乃 几 几 目标函数 数 T T T z 10 0 0 0 1 X 0 0 0 0 一0 5 1 33 3 3 乃乃 LO O O 10 0 0 0 一0 4 8 90 0 0 乃乃 0 1 1 11 0 0 0 00 6 8 8 8 T T T E 0 001 1 11 0 000 0 0 一习 5 133 3 3 了了毖 0 01 1 110 00 0 0 一0 5 126 6 6 2 2 2飞 0 1 1 110 0 0 01 553 3 3 s s s e ale 初 值值 b b b s e ale 终值值 目标函数 数 1 1 10 0 0 0 00 9 8 8 82 2 4 4 45 5 9 9 9 1 1 1000 0 00 9 5 5 50 1 1 1 刁 5 1 34 4 4 1 1 10 0 0 0 00 9 9 90 0 0 0 0 0 2 2 2 一0 5 1 3 3 3 3 1 1 10 0 0 00 98 8 82 24 4 4 一0 5 072 2 2 1 1 10 0 0 00 9 5 5 50 01 1 1 刁 5134 4 4 1 1 10 0 0 0 0 00 95 5 51 0 0 0 一0 5 0 9 1 1 1 1 1 10 0 0 0 0 00 9 9 90 0 0 0 0 2 2 2 一0 5 13 3 3 3 5 模拟退 火法与梯度法比较 为了说 明模拟退火法在求解全局最优问题 的优越性 本文将该法与传统的优化方法一梯度法的 优化计算结果进行比较 表 5 列出 了两种方法对上述例题从不同初值开始得到的最优解 可 以看出 对于某些初值点梯度法只能求局部最优解 而模拟退火法对任一初值点皆可求出全局最优解 以一初值点 3 6 为例 模拟 退火法和梯度法迭代过程 中目标函数的变化如 图 3 所示 可以看 出梯度法到局 部最优解后不能跳出来 而模拟退 火法在迭代过程中能接受目标函数增加的情况 致使 决策变量可以从局部最优点 附近跳出 最终达到全局最优 对于另外两个例题 用模拟 退火法和梯度 法计算相比 结果如表 6 7 所示 表明模拟退火法 能够有效地得出全局最优解 而梯度法则不能 例 2 minc 一 1 8X I一 7X 蚤 劣 一 豪 二 二 一 s t x 全0 坛 1 2 该例题研究的范围是非负域 其全局最优解为 4 0 2 0 C二 一3 4 2 8 局部极值点为 2 0 2 0 C 二 一1 98 5 取 a 0 9 5 l en g th 5 T I 1 0 T E 0 00 0 1 s ea le 初值 100 b 0 95 表5模拟退火法 和梯度法 比较 模模模拟退 火法法梯度法法 初初值值最优解解 目标函数 数最优 解解 目标函数 数 3 3 一1 075 1 0 19 刁 5 130 0 0 1 9 3 9 3 84 6 0 98 5 6 6 6 2 4 一1 0 5 5 1 0 19 刁 5 13 3 3 3 1 9 3 9 3 84 6 0 9 856 6 6 刁 2 2 5 一1 0 36 1 0 32 刁 5132 2 2 一1 0 5 3 1 0 2 8 一0 5 13 4 4 4 3 一3 一1 0 5 6 1 0 3 6 刁 5 13 3 3 3 一1 0 5 2 1 0 2 6 0 5134 4 4 0 8 1 5 一1 0 6 3 1 018 一0 512 8 8 8 一1 940 3 8 5 2 一0 9 8 5 6 第9期 连续变 量 问题全局优化的模拟退火法 79 表6 模拟 退火法和梯度法求解例2 比较 模拟 退火法 梯度法 初值 2 2 2 2 6 6 6 4 最 优解 3 9 97 2 004 4 0 2 0 2 0 1 0 3 9 9 8 2 013 4 0 0 1 1 9 9 9 目标函数 一3 4 2 8 一3 4 2 8 一3 4 2 8 一3 4 2 8 最优解 目标函数 2 00 0 2 0 0 1 2 0 0 0 2 0 0 0 3 9 99 2 0 0 0 一3 9 99 2 0 0 3 一1 985 一1 9 85 一3 428 一3 4 2 8 例 3 1 ll ln 5 t C X x 全O 一 8 x l一 7 x 十 一 奎 x t 争 一 一 一 1 2 本例题研究的范围亦为非负域 全局最优解 为 4 2 l C 一0 4 6 40 局部最优解为 2 2 l C 0 2 6 8 6 取 a 0 9 5 length 5 T I 0 0 5汉飞 0 0 0 005 se ale 初值 10 0 0 b 0 9 5 表7模拟 退火法和梯 度法求解 例3 比较 模模模拟退火法 法 梯 度法法 初初值值最 优解解 目标函数 数最 优解解 目标函数 数 2 1 1 3 9 6 9 1 9 8 8 0 9 9 0 一0 463 8 8 8 2 0 00 1 9 9 3 1 0 00 一0 2686 6 6 2 2 l 4 0 2 7 2 0 02 0 9 9 8 一0 46 3 9 9 9 2 0 0 0 2 0 00 1 0 0 0 一0 26 8 6 6 6 6 4 2 4 0 4 2 1 92 1 1 0 4 3 一0 4 6 37 7 7 4 00 0 2 0 0 4 1 0 0 0 一0 4 64 0 0 0 2 5 1 5 1 5 3 998 1 9 66 1 012 一0 4 6 3 8 8 8 3 9 9 9 1 9 9 8 1 0 0 0 一0 4 6 40 0 0 6 结论 本文对模拟 退火法在连续变量 全局最优 问题中的应用进行了研究 解决了如 下问题 1 提出了连续变量问题相邻状态的产生 函数及 自适应邻域因子的概念 2 确定了连续问题某一温度下的迭代 方案 3 形成了一个无约 束连续变量全局优化问题的模拟退火算法 4 给出了有关计算参数选取的适 宜范围 结果表明模拟退火法具有计算无 需梯 度信息 简便 有效以及通用性强等实用 的特 点 对有约束 问题可通过罚函数法 检验法等进行处 理解决 由于该法能 同时适用于离散问题和连续 问题 因此亦 可望有效地应用到混合整数非 线性规划 问题 中 该 法的