（地球探测与信息技术专业论文）混沌模拟退火算法在储层参数反演中的应用.pdf

摘要 混沌模拟退火算法在储层参数反演中的应用 作者：霍风斌，男，1 9 8 1 年生，成都理工大学地球探测与信息技术专业硕士， 现从事地震资料处理、反演与解释等方面 摘要 油田进入勘探、开发阶段，地震解释不但是构造解释，更重要的是进行岩性 解释和对储层进行描述。然而，一般的地震资料只是间接地反映地下岩性关系的 界面型材料，不能开展储层描述，需要进行地震反演。 在近几年来，非线性地震反演，无论从理论还是应用方面都得到了很大的发 展，基于混沌优化的非线性反演是非线性地震反演理论中的一部份。而地震反演 问题一般都存在非线性、强约束性、随机性、大规模等特性，单一的算法自身具 有局限性，在解决实际的反演优化问题时出现了许多难以克服的困难，如优化参 数容易陷入局部极小、优化时间过长、优化结果达不到预期的指标所以本文引 入了一种基于模拟退火算法和混沌优化的一种混合优化算法，这种算法既能克服 模拟退火算法收敛慢的缺点，而且兼容了混沌优化算法遍历特性和模拟退火算法 全局收敛性。 关键词：混沌优化算法模拟退火算法地震反演 成都理工大学硕士学位论文 c h a o s s i m u l a t i o na l g o r i t h m f o ra p p l i c a t i o no f p a r a m e t e r i n v e r s eo fr e s e r v o i r a b s t r a c t t h es e i s m i cd a t ac a nb ea p p l i e dt or e s e r v o i rd e c r i p t i o na n dr o c kp r o p e r t y i n t e r p r e t a t i o nm o r et h a nt og e o l o g i c a l c o n s t r u c t i n t e r p r e t a t i o n i nt h es t a g eo f e x p l o r a t i o na n dd e v e l o p m e n t h o w e v e r , t h ec o n v e n t i o n a ls e i s m i cd a t ac a n o td i r e c t l y b ea p p l i e dt or c s e r v o l rd e s c r i p t i o na n db er e q u i r e ds e i s m i ci n v e r s i o na si tc a l lb eo n l y r e p r e s e n tt h er e f l e c t i o no ft h er e l a t i o no fr o c kp r o p e r t yu n d e r g r o u n d i nr e c e n ty e a r s ，n o n l i n e a rs e i s m i ci n v e r s eh a sm a d ea l le n c o u r a g i n gi m p r o v e m e n t i nb o t ht h et h e o r ya n dt h ea p p l i c a t i o n n o n l i n e a ri n v e r s eo fc h a o so p t i m i z a t i o ni s i m p o r t a n tp a r to fs e i s m i cn o n l i n e a ri n v e r s e b u tt h ep r o b l e m so fs e i s m i ci n v e r s e g e n e r a l l yh a v et h ec h a r a c t e r so fn o n l i n e a r , s t r o n g - c o n s t r a i n t , r a n d o m ，l a r g es c a l ee t c b e c a u s eo ft h el i m i t a t i o no fu n i t a r ya l g o r i t h m ，m o r ea n dm o r ed i f f i c u l t i e st h a tc a nn o t b es o l v e dc o m ef o r t hi ns o l v i n go p t i m a lp r o b l e m so fp r a c t i c a li n v e r s e f o re x a m p l e ， o p t i m a lp a r a m e t e r sg e ti n t o l o c a li n f i n i t e s i m a le a s i l y , o p t i m a lt i m ei st o ol o n ga n d o p t i m a le f f e c tc a nn o tr e a c ht h ep r e d i c a b l ep a r a m e t e r s s oah y b r i do p t i m a la l g o r i t h m i si n t r o d u c e db a s e do ns i m u l a t e da n n e a l i n ga l g o r i t h ma n dc h a o so p t i m i z a t i o ni nt h e d i s s e r t a t i o n t h eh y b r i do p t i m a la l g o r i t h mc a nn o to n l yc o n q u e rt h es l o wc o n v e r g e n c e r a t eo fs i m u l a t e da n n e a l i n ga l g o r i t h m , b u ta l s oh a st h et r a v e l s a lc h a r a c t e ro fc h a o s o p t i m i z a t i o na l g o r i t h ma n dt h eg l o b a l - c o n v e r g e n c eo f s i m u l a t e da n n e a f i n ga l g o r i t h m k e y w o r d s ：c h a o so p t i m i z a t i o na l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m ，s e i s m i c i n v e m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得盛赶堡王盔堂或其 他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 kl 学位论文作者导师签名：7 砂幺叉 学位论文作者签名霪凤交苛 z o o 年了月3 0 日 学位论文版权使用授权书 本学位论文作者完全了解盛都堡王太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授权盛整理王太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：霍凤文武 2 0 0 ? 年 与月3 0 日 第1 章引言 1 1 选题依据 第1 章引言 随着油气勘探和开发的不断进行，石油工业界对地震技术提出了越来越高的 要求，不仅希望从地震资料中了解地下构造的基本情况，还要求能从地震中确定 储层分布范围以及求得储层参数的准确情况。以前，地质学家和石油工程师们是 用钻井和测井资料来确定油气藏的分布范围、储层的厚度及其他储层参数，如孔 隙度和渗透率等，并用这些参数来计算储量和确定最佳开发方案。但是无论在油 气田开发的哪个阶段，井孔总是有限的，从钻井和测井中得到的地下信息总是不 连续的。因此，地质学家和油藏工程师们迫切希望能用地震资料来填补这个信息 缺口，综合利用地震、钻井和测井资料，更为准确地确定地下储层的细微特征， 准确的估计油藏储量，指定更为有效的开发方案。 地震处理得到的水平叠加剖面和偏移剖面反映的是地下不同岩性地层分界 面的空间变化情况。从这种剖面中能够很好地恢复地下构造的形态。由于这种地 震剖面没有直接反映地层的岩性，因此不能与钻井、测井资料进行直接对比。常 规的地震剖面更适合作构造解释，而不适合作岩性解释。 地震反演的目的就是要将反映地层界面( 反射系数) 的地震剖面转化为反映 地层岩性特征( 速度、密度、波阻抗) 的岩性参数剖面，这将大大增加井间地下 岩性信息，有利于对储层进行精细描述和开发方案的制定。 a v o 反演是提供更为全面的储层参数反演的有效途径。在有井资料控制的 情况下，传统的全波形a v o 反演是一项非常有用的技术( b u l a n d ，1 9 9 5 ，1 9 9 6 ， 2 0 0 3 ：m a h o b ，1 9 9 9 ) ，在没有井控制的情况下可优先选用遗传算法进行越，o 反 演( m a l l i c k ，1 9 9 5 ，1 9 9 9 ) 。c a s t a g n a ( 2 0 0 0 ) 曾指出：a v o 分析的目标不是试 图得到一个正确的答案，而是要认识和说明引起异常现象的原因，为减小风险提 供更多的信息。这充分说明了a v o 反演不能克服多解性问题，但是，一个好的 初始模型对反演结果是很有帮助的( d r u f u c a ，m a z z o t t i ，1 9 9 5 ) 。传统的a v o 反 演更多的是估算a v o 的各种属性，利用各种属性与岩石物理背景趋势的差异作 为检测烈，o 异常的一种有效手段，它忽视了岩石弹性参数的定量估算。因此， 我们将研究定量的多种弹性参数的a v o 反演。 地震资料的储层参数反演是一个非线性问题，这是因为地震反演中的目标函 数是一个非凸性的复杂的多峰函数。如果使用对初始模型有很大依赖性的线性优 化方法、最速下降法和共轭梯度法进行储层参数参数反演，则容易陷入局部极值 成都理工大学硕士学位论文 区而难以得到全局极值。并且当反演参数较多时，搜索空间急剧膨胀，计算量非常 大，导致搜索效率大大下降，其主要缺点如下： ( 1 ) 一般对目标函数都有较强的强制性限制，如连续、可微、单峰等。这 些对于地震资料的储层参数反演得目标函数的要求是非常苛刻的。 ( 2 ) 这些方法都有根据目标函数的局部展开性质来确定下一步搜索的方向， 这与搜索函数的整体最优解的目标在一定程度上是抵触的。 ( 3 ) 在实现算法之前，需要做大量准备的工作，如求函数的一阶和二阶导 数、某些矩阵的逆等。在目标函数复杂的情况下，这一项工作是很困难的，有时 甚至是不可能的。 ( 4 ) 算法结果一般与初值的选取有很大的关系，不同的初值导致不同的结 果。初始值的选取较大的依赖于优化者对问题背景的认识及所掌握的知识和经 验。 ( 5 ) 算法缺乏简单性与通用性。针对一个问题，优化方法的使用者需要有 相当的知识去判定使用哪一种优化方法较为合适。这一困难是优化设计更广泛应 用的主要障碍之一。 ( 6 ) 对有些约束问题较难处理，要求解空间为凸集。 因此，为了适应地球物理发展的需要，我们需要继续探讨更有效、更实用的 优化方法。近年来，出现了具有全局优化性能且通用性强的随机搜索算法，如混沌 优化算法和模拟退火算法等。混沌优化是利用混沌运动的随机性、遍历性和规律 性( 确定系统产生的运动) 寻求最优点，从而可用于系统的识别、最优参数设计 等方面。混沌搜索是利用混沌的遍历性进行搜索，即在改变初始值的同时，将要 搜索的数据和进入混沌状态的值相比较，检测出接近于待搜索数据的状态。这种 方法比随机搜索或遗传算法具有更高的检索速度。模拟退火算法只考虑目标函数， 对初始模型的要求不高，并且可以随机地在全局域内进行搜索这种具有较强搜索 能力的算法能够保证反演结果基本上为最优解。故我将使用混沌优化算法和模拟 退火算法相结合的方法来反演储层参数 针对上述问题，本文将利用a v o 技术和混沌模拟退火算法对储层参数反演 进行研究和实践。 1 2 叠前参数反演的研究历史和发展现状 叠前反演主要包括基于旅行时的c t 成像技术和基于振幅的a v o 分析技术 可以进行弹性参数的反演。 就利用a v o 技术进行岩性参数反演的发展过程方面，s i m m o n s b a c k u s ( 1 9 9 6 ) 提出基于波形的一步法线性反演，假设其具有岩石物理趋向的背景条件， 2 第1 章引言 利用a v o 预测误差作为检测a v o 异常的一种有效手段。为了有效的反演出更多 的岩性参数，m a i k i n ( 1 9 9 9 ) 在传统的稀疏脉冲反演的基础上，提出了 e i g e n v e c t o r - b a s i s e x p a n s i o n 波阻抗反演方法；w a n g ( 1 9 9 9 ) 在给出了射线参数表 示的反射系数公式的基础上，讨论了利用该公式同时反演三个岩性参数的可能性 和可靠性。由于传统的a v o 反演主要是利用p p 波a v o 来反演纵、横波速度、 密度及其它岩性信息，这样可能会带来比较大的误差。为了更可靠、更有效的对 油气储层参数进行反演，j i n ( 1 9 9 9 ，2 0 0 0 ) 利用实际数据的p p 波p - s v 波联合 反演讨论了多参数储层反演的多属性a v o 分析及弹性参数反演方法，并指出利 用这种方法可以有效地识别和区分孔隙流体。l a r s c n 等( 1 9 9 9 ) 利用p p 波p s v 波联合加权叠加理论讨论了同时反演纵、横波阻抗的方法。r o n e n ( 2 0 0 0 ) 在他 们的基础上，提出了多分量a v o 反演理论，并讨论了利用该方法同时反演纵、 横波阻抗、归一化密度、速度和拉梅参数的可行性。k e l l v ( 2 0 0 0 ) 提出了p p 波 p - s v 波角度叠加反演的理论，并指出这种角度叠加反演是最简单最有效的a v o 反演方法，如果借助于各种岩性参量之间的关系，利用该方法能够更多的岩性参 数。另外，h a m p s o n r u s c l l 公司和剑桥大学分别将神经网络应用于a v o 岩性参 数反演的研究( h a m p s o n ，1 9 9 0 ，r u s s e l l ，2 0 0 2 ，2 0 0 3 ) 。在国内，成都理工大 学、西南石油局也对线性、非线性a v o 反演理论进行了较深入的研究，同时也 将模拟退火反演应用于实际资料的反演( 许多，2 0 0 1 ；李正文，2 0 0 2 ；唐建明， 2 0 0 2 ) 。 目前油气勘探从构造勘探向岩性勘探转化，地震属性的提取和岩性的识别显 得尤为重要。在叠后地震资料中通常只能提取到波阻抗信息( 邹才能，2 0 0 2 ) ， 这种情况下从叠前地震资料中提取地震属性就显得尤为重要。在这方面，a v o ( a m p l i t u d ev e r s u so f f s c t ：振幅与偏移距关系) 技术经过二十几年的研究和应用 已经取得了很大进步，目前在油气勘探领域已经得到广泛的应用，并且在油气储 层检测等方面已经获得了很多成功的应用实例，已在油气检测和储层描述等领域 扮演着重要角色。但是，在二十几年的发展历程中a v o 技术也经历了很多失败 的教训( f r a s i e r , 1 9 8 8 ；j a m e s ，1 9 9 3 ；c a m b i o s ，1 9 9 8 ，2 0 0 0 ) ，也就是说还存在很多问 题需要深入研究。比如，反射系数同时受到多种弹性参数的综合影响，如果孤立 的用某一个或几个参数来定性表征反射系数随炮检距的变化规律势必会有一定 的片面性；另外，在a 、，o 分析过程中人为假定纵横波速度比近似为2 ，在很大 程度上限制了其应用范围，甚至还可能造成假象( 邹才能，2 0 0 2 ) 。a v o 数据 影响因素的复杂性与消除这些影响的困难，a v o 的定量反演仍然是a v o 应用 研究中最困难的问题。 3 成都理工大学硕七学位论文 1 3 混沌理论的研究历史和在地球物理中的应用现状 混沌学的研究热潮仅始于7 0 年代初期，但这门新学科的渊源却可以追溯到 上个世纪。1 9 世纪3 0 年代，英国数学物理学家w r h a m i l t o n 将动力学系统的能 量表示为广义动量和广义坐标的函数。这样，牛顿力学变成了相空间的几何学， 几何方法成了研究动力学系统的有力工具。按照h a m i l t o n 函数的数学形式，可 以把动力学系统划分为可积和不可积两大类。这一划分使人们逐步认识到，经典 牛顿理论实际上只是关于可积系统的理论，而一般的动力学系统，包括多体甚至 仅三体系统都是不可积的。这一认识是通向混沌学大门的重要一步，因为混沌正 是不可积系统的典型行为。 本世纪印年代以来，人们发现：即使对于典型的可用确定性方法描述的系 统来说，只要该系统稍微复杂一些( 通常是指含有非线性因素) ，在一定条件下 也会产生非周期性的、表面看起来很混乱的无规则运动。这种来自可用确定性方 法描述的系统中的无规则运动，特称为混沌或称为内在随机性。 e n l o r e n z 在1 9 6 3 年发表了著名论文确定性非周期流，1 9 7 2 年1 2 月2 9 日，在美国科学发展学会第1 3 9 次会议上发表了题为蝴蝶效应的论文，提出 一个貌似荒谬的论断：在巴西一只蝴蝶翅膀的拍打能在美国得克萨斯州产生一个 陆龙卷，并由此提出了天气的不可准确预报性。以后又陆续发表了三篇论文，这 组论文是混沌研究的第二大突破，成了后来研究耗散系统混沌现象的经典文献。 l o r e n z 揭示了一系列混沌运动的基本特征，如确定性非周期性、对初值的敏感依 赖性、长期行为的不可预测性等等，他还在混沌研究中发现了第一个奇怪吸引子 ( l o r e n z 吸引子) ，他为混沌研究提供了一个重要模型，并最先在计算机上采用数 值方法进行具体研究，为以后的混沌研究开辟了道路。 1 9 7 1 年，法国数学物理学家d r u o l l e 和荷兰的e t a k c n s 在学术界第一个提 出用混沌来描述湍流形成机理的新观点，独立地发现了奇异吸引子。此后，判别 是否存在奇异吸引予，刻划吸引子的特征，成了耗散系统混沌研究的基本课题。 1 9 7 5 年，正在美国马里兰大学攻读博士学位的华人李天岩和他的导师 j y o r k e 联名发表了一篇震动整个学术界的论文周期3 蕴含混沌，这是一个关 于混沌的数学定理，基本思想是y o r k c 受l o r e n z 的1 9 6 3 年的论文启发而得，李 天岩给出了具体证明，这就是著名的l i - - y o r k e 定理。定理描述了混沌的数学特 征，为以后的一系列研究开辟了方向。李天岩和y o r k c 在动力学研究中率先引入 “混淹”( c h a o s ) 一词，为这一新兴研究领域确立了一个中心概念，为各学科研 究混沌现象树起一面统一的旗帜。l i - - y o r k c 定理帮助r m a y 理解了他在l o g i s t i c 方程中发现的奇异现象，他认识到这是隐藏在生态系统中的具有普遍特征的混 4 第1 章引言 沌，从而撇开了各个具体领域的特殊性，总结和阐明了一个基本事实：简单的非 线性差分方程，可以产生出从平衡态到周期态再到混沌态的整个动力学行为。 1 9 7 6 年r m a y 发表了题为 r 。求目标函数最小值的问题 称为最小化问题，记为m i n f ( i ) ，i e s 。 显然，改变目标函数符号，最小化问题与最大化问题就可以等价相互转化。 1 9 8 2 年，k i r k p a t r i x 等将模拟退火思想引入组合优化领域，提出了一种求解大 规模组合优化问题的有效近似算法模拟退火算法。它源于对固体退火过程的 模拟；采用m e t r o p o l i s 接受准则；并用一组称为冷却进度表的参数控制算法进程， 使算法在多项式时间里给出一个近似最优解。 2 1 模拟退火理论的概述 2 1 1 固体退火过程中的物理现象 物理中的固体退火是先将固体加热至熔化，再徐徐冷却，使之凝固成规整 晶体的热力学过程，属于热力学与统计物理研究的的范畴。 热力学与统计物理学所研究的对象，通常称为热力学系统，是指在给定范 围内，由大量微观粒子所组成的宏观物体。如气体、液体、固体等离子体等。对 同一研究对象，热力学与统计力学从不同角度加以研究。熟力学从经验总结出的 定律出发，找出系统宏观量之问的联系以及宏观量变化的规律；统计物理学从物 质的微观结构出发，把宏观量作为相应微观量的统计平均值来计算，可以从理论 上计算某些宏观量及其涨落，因此更能反映热运动的本质。 在加热固体时，固体粒子的热运动不断增强，随着温度的升高，粒子与其 7 成都理工大学硕士学位论文 平衡位置的偏离越来越大，当温度升至熔解温度后，固体的规则性被彻底破坏， 固体熔解成液体，粒子排列从较有序的结晶态转为无序的液态，这个过程称为熔 解。熔解的目的是消除系统原先可能存在的非均匀状态，使随后进行的冷却的过 程以某一平衡态为始点。冷却时，液体粒子的热运动渐渐减弱，随着温度的徐徐 降低，粒子运动渐趋有序。当温度降至结晶温度后，粒子运动变成围绕晶体各点 的微小振动，液体凝固成固体的晶态，这个过程称为退火。退火过程之所以必须 徐徐进行，是为了使系统在每一温度下都达到平衡态，最终达到固体的基态。退 火过程中系统的熵值( 衡量不能利用的热能数量) 不断减小，系统能量也随着温 度降低趋于最小值。冷却时，若急剧降低温度，则将引起淬火效应，即固体只能 冷凝在非均匀的亚稳态，系统能量也不能达到最小值。 退火过程中系统在每一温度下达到平衡的过程，可以用封闭系统的等温过 程来描述。根据b o l t z m a n n 有序性原理，退火过程遵循应用热平衡封闭系统的热 力学定律自由能减少定律： “对于与周围环境交换热量而温度保持不变的封闭系统，系统的状态的自 发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡 态”。 系统的自由能f = e t * s ，其中e 是系统的内能，t 是系统的温度，s 是系统 的熵。设i 和j 是恒温系统的两个状态，即 f i = e i t s i 和f j = 马t s j 而 a f - - f i f i = ( r e j - e 0 - t ( s j s i ) = e t + a s 。 若系统状态由i 自发变化到j ，则应有a f 舢) 2 舢 ik 2 1 3 组合优化和物理退火的相似性 引用模拟退火算法( s a ) 的原动力是基于这样的模拟：具有大规模解空间 的组合优化问题和带多自由度的物理系统显示出类似的性质。该算法用于解决组 合优化问题的出发点是鉴于物理中晶体物质的退火过程与一般组合优化问题的 相似性。 在对固体物质进行退火处理时，通常是先对它加温，使其熔化，其中的粒子 可以自由运动，然后随着温度缓慢下降，粒子逐渐形成低能态的晶格。若在凝结 点附近的温度下降速率过快，则不能达到这个能量最低态，而是以一种多晶体的 或者以一种非晶的具有高能量的亚稳态结束。因此，这个过程的本质是慢速冷却， 让粒子有充分的时间失去可动性，进行重新分布，这是退火的技术定义，它能确 保粒子达到低能态势。 对组合优化问题来说，也有类似的过程，组合优化问题解空间的都代表一个 具有目标函数的解。所谓优化，就是在解空间寻找函数最小解的过程。若把目标 函数看成能量函数，把控制参数视为温度，解空间作为状态空间，那么模拟退火 算法( s a ) 寻找基态的过程就是求目标函数极小值的优化过程，因此，基于 m e t r o p o l i s 接受准则的最优化过程与物理退火过程存在一定的相似性。将这种相 似性归纳在下表2 1 中 表2 - 1 组合优化和物理退火的相似性 组合优化物理退火组合优化物理退火 解粒子状态 m e t r o p o l i s 抽样过程 等温过程 最优解能量晟低态控制参数的下降 冷却 设定初始温度熔解过程目标函数能量 众所周知，处于热平衡的物理系统的各种可能状态服从玻尔兹曼 ( b o l t z m a n n ) 概率分布，即如式( 2 1 ) 所示。 这里先研究由式( 2 1 ) 所确定的函数随t 的变化趋势，选定两个能量e l e 2 ， 在同一温度下，有 1 0 第2 章模拟退火算法理论 一赤c x p ( 一鲁) 【l 小产) 】q 5 式( 2 5 ) 恒存在c x “一兰生：b 0 ，因此式( 2 - 5 ) 大于零总成立。 基本相同，接近平均值i d i ，i d i 为状态空间d 中的状态的个数。结合( 2 5 ) 式， - 警二业止( 2 6 ) 。学吲沪掣， 所以，p es e ( r ) 关于温度t 是单调下降的。又有： p 西研肛去c x p ( 一警) ； 其中，d o 是具有最低能量的状态集合。 令丁一0 时，有 n 。，e x p ( 一业铲蚴_ 。 1 ld oi + 尺 ( 2 7 ) 亦有p 伍自e ( r ) 呻丽i t 。 可见。当温度趋于0 时，式( 2 1 ) 决定的概率渐进i d o 。据此可以得到， 在此温度趋于0 时，分子停留在最低能量状态的概率接近1 。综合上面的讨论， 分子在能量最低的状态的概率变化可以由图2 1 ( a ) 所示。 对于能量最小的状态，由式( 2 2 ) 和分子在能量最小状态的概率是单调减 小可知，在温度较高时，分子处于这些状态的概率在1 d 附近，依赖于状态的 1 1 字 成都理工大学硕士学位论文 不同，可能超过1 i d i 。由式( 2 6 ) 和( 2 7 ) 可知存在一个温度t ，使式( 2 6 ) 决定的概率在( o ，1 ) 上单调升的；再由式( 2 6 ) 可知，当温度趋于0 时，( 2 1 ) 定义的概率趋近予0 ，概率变化曲线图见图2 - 1 ( b ) 。 由上面的讨论可知，在温度很低时仁一o ) ，能量越低的状态的概率值越高。 在极限状况，只有能量最低点概率不为零。 e j ? e ( a ) 能量最低状态( b ) 非能量最低状态 图2 1 波尔兹曼函数曲线 2 1 4 模拟退火算法的特点 s a 算法在搜索策略上与传统的随机搜索算法不同，它不仅引入了适当的随 机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模 拟退火算法在迭代过程中不仅接受使目标函数变“好”的试探点，而且还能以一 定概率接受使目标函数值变“差”的试探点，接受概率随着温度的下降而逐渐减 小。s a 算法的这种搜索策略有利于避免搜索过程因陷入局部最优解而无法自拔 的弊端，有利于提高求得全局最优解的可靠性。s a 算法的上述特性不仅在理论 上能突破传统算法难以解决的难题，而且具有很强的科学和实际的工程应用价 值，因而被誉为解决许多高难度优化问题的救星。下面分析s a 算法和其它传统 搜索方法的对比： 解析法是常用的搜索方法之一它通常是通过求使目标函数梯度为零的一组 非线性方程来进行搜索的。一般而言，若目标函数连续可微，解的空间方程比较 简单，解析法还是可以用的。但是若方程的变量有几十或几百时，它就无能为力 了。爬山法也是常用的搜索方法，它和解析法一样都属于寻找局部最优解的方法。 对于爬山法，只有在更好的解位于当前解附近的前提下，才能继续向最优解搜索。 显然这种方法对于具有单峰分布性质的解空间才能进行行之有效的搜索，并得到 第2 章模拟退火算法理论 最优解。 另一种典型的搜索方法是穷举法。该方法简单易行，即在一个连续有限搜索 空间或离散无限搜索空间，计算空间中每个点的目标函数，且每次计算一次。显 然，这种方法效率太低而鲁棒性不强。许多实际问题所对应的搜索空间都很大， 不允许一点一点的慢慢求解。 随机搜索方法比起上述搜索方法有所改进，是一种常用的方法，但它的搜索 效率依然不高。一般而言，只有解在搜索空间中形成紧制分布时，它的搜索才有 效。但这一条件在实际应用中难以满足。这里必须把随机搜索( r a n d o m s e a r c h ) 方法和随机化技术( r a n d o m i z e dt e c h n i q u e ) 区分开来。s a 方法也是利用随机化 技术来指导对于最小能量状态的搜索。而另一种搜索方法遗传算法就是一个 利用随机化技术来指导对一个被编码的参数空间进行高效搜索的方法。因此，随 机化搜索技术并不意味着无方向搜索，这一点与随机搜索有所不同。 前述的几种传统的搜索方法虽然鲁棒性不强，但这些方法在一定的条件下， 尤其是将它们混合使用也是有效的。当面临更为复杂的问题时，必须采用像s a 算法这样更好的方法。s a 算法具有十分顽强的鲁棒性，这是因为比起普通的优 化优化搜索方法，它采用许多独特的方法和技术。主要有以下几个方面： ( 1 ) 能够以一定的概率接受劣解 s a 算法在搜索策略上与传统的随机搜索算法不同，它不仅引入了适当的随 机因素，而且还引入了物理系统退火过程的自然机理。这种自然机理的引入使模 拟退火算法在迭代过程中不仅接受使目标函数变“好”的试探点，而且还能以一 定概率接受使目标函数值变“差”的试探点，迭代中出现的状态是随机产生的， 并且不强求后一个状态一定由于前一个状态，即以一定的可能容忍的退化状态的 出现。接受概率随着温度的下降而逐渐减小。传统的方法往往是从解空间一个初 始点开始最优解的迭代搜索过程。如登山法，若一个细微变动能改善质量，则沿 该方向前进，否则取相反方向。然而复杂问题会使解空间中出现若干局部最优解， 传统的方法很容易限于局部最优解而停滞不前。很多传统的优化算法往往是确定 性的，即从一个搜索点到另一搜索点的转移有确定的转移方法和转移关系。这种 确定性往往可能使得搜索永远达不到最优点，因而限制了算法的应用范围。而 s a 算法是以一种概率的方式来进行的，使得算法进程具有跳跃性，可能跳出局 部最优的“陷阱”，化解了算法对初值的依赖性，从而增加了其搜索过程的灵活 性。 ( 2 ) 引进算法控制参数t 引进类似于退火温度的算法控制参数t ，它将优化过程分成各个阶段，并决 定各个阶段下随机状态的取舍标准，接受函数由m e t r o p o l i s 算法给出一个简单的 成都理工大学硕士学位论文 数学模型。s a 算法的两个重要步骤是：一是在每个控制参数t 下，由前迭代点 x ( i ) 出发，产生邻近的随机状态x ( “1 ) ，由t 确定的接受准则决定此新状态的取舍， 并由此形成一定长度的随机m a r k o v 链；二是缓慢降低控制参数t ，提高接受准 则，直至t 一0 ，状态链稳定于优化问题的最优状态，提高s a 算法获得全局最 优解的可靠性。 ( 3 ) 使用对象函数值( 即适应值) 进行搜索 传统搜索算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等 其它一些辅助信息才能确定搜索方向。当这些信息不存在时，算法就无效了。而 s a 算法仅使用由目标函数变换来的适应度函数值，就可确定进一步的搜索方向 和搜索范围，无需其它一些辅助信息。需要着重提出的是，s a 算法的适应度函 数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数唯一要 求是，对于输入可计算出加以比较的正的输出。这个特性对很多无法或很难求导 数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用s a 算 法就显得比较方便。另外，直接利用目标函数值或个体适应度，也可以把搜索范 围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。 ( 4 ) 隐含并行性 并行算法是6 0 年代发展起来的，发展迅速。有些专家甚至认为提高目前计 算机系统的性能的唯一方法是“选择大量的并行”。从目前情况看，并行算法的 设计主要采用两种：一是对现有的串行算法加工改造，使之成为好的并行算法； 二是结合所用并行计算机的结构特点，直接设计新的并行算法。对模拟退火算法 改造成并行算法还是比较容易的。目前常见的有以下几种并行策略，试演并行策 略，区域分裂策略，混乱分裂策略。这几种并行算法在不同程度上对解的质量、 收敛速度方面较模拟退火算法优。由此可以预见，大规模的并行设计模式将成为 研究全局优化问题的主流。即s a 算法隐含并行性( i m p l i c i tp a r a l l e l i s m ) ，它是 优于其它求解过程的关键所在。另外s a 算法的隐含并行性还有助于处理非线性 问题。 ( 5 ) 搜索复杂区域 s a 算法最善于搜索复杂地区，从中找出期望值高的区域。但在求解简单问 题时效率并不高。正如遗传算法创始人h o l l a n d h 所指出的“如果只对几个变量 作微小的改动就能进一步改进，则最好使用一些更普通的方法，为遗传算法助一 臂之力”。s a 算法字在这一点上与遗传算法类似，但比遗传算法更适合搜索复杂 区域。 上述具有特色的技术和方法使得s a 算法使用简单、解质量高、鲁棒性强、 易于并行化，从而应用范围甚广。 1 4 第2 章模拟退火算法理论 2 2 模拟退火算法的结构 模拟退火算法是根据优化问题的求解与固体退火过程的相似性为基础，把 物理系统的能量模拟成优化问题的目标函数，把固体退火过程模拟成对优化问题 搜寻全局极值，利用m e t r o p o l i s 算法，并用温度更新函数适当控制温度的下降过 程实现模拟退火，从而达到求解全局优化问题的目的，就实现了优化问题的模拟 退火算法 模拟退火算法的执行策略由如下步骤构成：从一个任意被选择的初始解开始 探测解空间，并且通过扰动产生一个新解，利用m e t r o p o l i s 准则判断是否接受新 解，相应的下降控制温度，基本模拟退火算法伪码描述 b e g i n ( 1 ) 初始化逐步冷却温度t e m p ，产生随机初始化配置x o ： ( 2 ) l o o p ：在温度t e m p 控制下，对于每一个温度t e m p ，重复执行如下操作， 直至系统冷却不再产生更好的配置为止。 ( 2 1 ) 在一个参数集所确定的配置中，随机选择一个新的配置x 1 ； ( 2 2 ) 计算新配置的目标函数c o s t ( x 1 ) 和旧配置的目标函数c o s t ( x o ) ： ( 2 - 3 ) 如果c o s t ( x 1 ) r a n d ( o ，1 ) ，接收该新的配置x 1 ， 其中r a n d ( o ，1 ) 是【o ，1 】区问的随机数； 否则仍保留原配置； e n d ( 2 4 ) 令t e m p i + l m a 4 t e m p i ，其中a e ( o 8 ，0 9 ) ，若满足收敛判据， 则退火过程结束；否则转( 2 ) e n d l o o p e n d 其中逐步冷却温度t e m p 控制着求解过程向最小值的优化方向进行，同时它 又以概率e x p 一a c o s t k t e m p 来接收劣质解，因此算法可以跳出局部极值点，只 要初始温度足够高，退火过程足够慢，算法就能收敛到全局最优解 上面的程序中，关键的是( 1 ) 新状态产生函数，( 2 ) 新状态接受函数，( 3 ) 抽样 成都理工大学硕士学位论文 稳定准则，( 4 ) 退温函数，( 5 ) 退火结束准则( 简称三函数两准则) 是直接影响优 化结果的主要环节。虽然实验结果证明初始值对于最后的结果没有影响，但是初 温越高，得到高质量解的概率越大。所以，应该尽量选取比较高的初温。 从上面程序还可以看出：模拟退火的典型特征是除了接受目标函数的改进 外，还接受一个衰减极限，当t 较大时，接受较大的衰减，当t 逐渐变小时， 接受较小的衰减，当t 为o 时，就不再接受衰减。这一特征意味着模拟退火与局 部搜索相反，它能避开局部极小，并且还保持了局部搜索的通用性和简单性。值 得注意的是，当t 为0 时，模拟退火就成为局部搜索的一个特例。 上面关键环节的选取策略： ( 1 ) 状态产生函数：又被称为邻域函数。状态产生函数的设计应该尽可能 保证产生的候选解遍布全部解空间。通常，状态产生函数由两部分组成，即产生 候选解的方式和候选解产生的概率分布。前者决定由当前解产生候选解的方式， 后者决定在当前解产生的候选解中选择不同状态的概率。候选解产生方式由问题 的性质决定，候选解通常在当前状态的领域结构内以一定的概率方式产生。候选 解由当前解的邻域函数决定，可以取互换，插入，逆序等操作产生，然后根据概 率分布方式选取新的解，概率可以取均匀分布、正态分布、高斯分布、柯西分布 等。故领域函数和概率方式可以多样化设计。 ( 2 ) 状态接受函数：这个环节最关键，但是，实验表明，何种接受函数对 于最后结果影响都不大。所以，一般选取m i n 【1 ，e x p ( - a c o s t x ) t ) 。 设计原则： 在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函 数值上升的候选解的概率； 随温度的下降，接受使目标函数值上升的解的概率要逐渐减小； 当温度趋于零时，只能接受使目标函数值下降的解。 ( 3 ) 抽样稳定准则：一般常用的有：检验目标函数的均值是否稳定；连续若 干步的目标值变化较小；规定一定的步数； ( 4 ) 退温函数：如果要求温度必须按照一定的比率下降，s a 算法可以采用， 但是温度下降很慢；快速s a 中，一般采用t 一瓦p 。”。目前，经常用的是 气+ ，= a t , ，t 是一个不断变化的值。 ( 5 ) 退火结束准则：一般有：设置终止温度；设置迭代次数；搜索到的最优 值连续多次保持不变；检验系统熵是否稳定。为了保证有比较优的解，算法往往 采取慢降温、多抽样、以及把“终止温度”设的比较低等方式，导致算法运行时 间比较长，这也是模拟退火的最大缺点。 以上的算法实际上是分两步交替进行的：第一，随机扰动产生新模型并计 1 6 第2 章模拟退火算法理论 算目标函数的变化；第二步，决定新模型是否被接收。故称为二步法。算法是在 高温条件下开始进行的，因此，使c o s t ( x ) 增大的模型可能被接收，因而能舍 去局部极值。显然通过缓慢地降低温度，算法能收敛到全局最优点。但是，当 a c o s t ( x 1 0 且t 值较小时，扰动被接收的概率较小，大部分扰动不被接收， 这样就有相当大的计算量被浪费了。 为了提高随机假设的“取舍比0r o t h m a n ( 1 9 8 5 ) 提出，用与变换在目标 函数上的效用成正比的概率去产生新解的无舍弃法。该方法在做出假设之前先算 出承认每次搜寻的相对概率，再从所得到的概率分布函数上获得一个随机数作为 某个参数的新解，并始终给予接收。而不是给出或者承认、或者舍弃的随机假设。 相对二步法，称这种改进的算法为一步法。r o t h m a n 也证明了模拟退火算法中新 模型的产生是对当前模型进行扰动得步法与二步法一样，都模拟了热平衡，因而 两种方法的本质是一样的。 2 3 冷却进度表的选取 冷却进度表是一组控制算法进程的参数，它的合理选取是保证算法在有限时 间内返回问题的近似最优解，即保