（油气储运工程专业论文）塔河油田六区集输系统优化布站研究.pdf

英文摘要 s u b j e e r ： as t u d yo fg a t h e ra n dt r a n s p o r t a t i o ns y s t e m o p t i m i z a t i o nf o rt a h e o i l f i e l ds i xd i s t r i c td e p a r t m e n t s p e c i a l i t y ： o i l g a ss t o r a g ea n d t r a n s p o r t a t i o ne n g i n e e r i n g n a m e ： q i a nj u n( s i g n a t u r e 幺叠竺： 1 1 1 s 们c 衙：d 仰gz h e n g y u a n ( s i g n a t u nl 血扣垃手归 a b s t r a c t t h ec o m m o nm s ，m r sa n dm s tn e t w o r k si ns u r f a c e p i p e l i n e n e t w o r ka r e m a t h e m a t i c a l l ya n da c c u r a t e l yd e f i n e d ，b a s e do nc a r e 向la n dp r o f o u n da n a l y s i so ft h es t r u c t u r a l c h a r a c t e r i s t i c s ，r e l a t i o n s h i p sb e t w e e nl a y e r s ，c h a r a c t e r so fn e t w o r kv a r i a t i o na n d0 t 1 1 e rf a c t o r s o fo i l f i e l ds u r f a c ep i p e l i n en e t w o r k ，a n db yu s eo fg r a p ht h e o r ya n do t h e r c o r r e s p o n d i n g k n o w l e d g e t h e nt h r e em u l t i - o b j e c t i v em a t h e m a t i cm o d e l sa r ee s t a b l i s h e da c c o r d i n gt ot h e d e s i g no fn e t w o r k sm e n t i o n e da b o v e ，i nw h i c ht h em i n i m a ll e n g t ho fp i p e l i n ea l et a k e na st h e o b j e c t i v e s n ec a l c u l a t i o nd i f f i c u l t yo ft h em o d e l i sa n a l y z e db yc a l c u l a t i o nc o m p l e x i t y t h e o r y b a s e d o nt h es t r u c t u r a lc h a r a c t e r i s t i c so ft h em o d e la n d p r a c t i c a ld e s i g n p r o c e s s ，h i e r a r c h i co p t i m i z a t i o ns t r a t e g ya d o r e d ，t h er e s o l u t i o no ft h em o d e li sd e c o m p o s e d i n t ot w os u bp r o b l e m s ，t o p o l o g yl a y o u t o p t i m i z a t i o na n dp a r a m e t e r so p t i m i z a t i o n t h e i r c o o r d i n a t i o ni sa c h i e v e db yi t e r a t i o nc o m p u t a t i o n t o p o l o g yl a y o u to p t i m i z a t i o no fo i l f i e l d p i p e l i n en e t w o r k i ss t u d i e d t h e c o r r e s p o n d i n gm a t h e m a t i cm o d e lo ft o p o l o g yl a y o u t o p t i m i z a t i o n ，a c c o r d i n gt om s ，m r sa n dm s tn e t w o r k sm e n t i o n e da b o v e ，i se s t a b l i s h e d ，i n w h i c ht h em i n i m a ll e n g t ho fp i p e l i n ei st a k e na st h eo b j e c t i v e h i e r a r c h i c a lo p t i m i z a t i o ni s a d o p t e dt om e e tt h en e e do ft h es t r u c t u r a lc h a r a c t e r i s t i c so ft h em o d e l b e c a u s eo ft h e d e f i c i e n c yo ft h i sm e t h o d ，h i e r a r c h i c a lo p t i m i z a t i o n ，g e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n g a l g o r i t h ma r eo r g a n i c a l l yc o m b i n e dt of o r mar e s o l u t i o ns t r a t e g yo fh y b r i dg e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h m p r a c t i c a lc a s e s c a l c u l a t i o ni n d i c a t et h a tc o m p a r e dw i t hh i e r a r c h i c a l o p t i m i z a t i o n ，t h ea l g o r i t h mc a nb ei m p r o v e di no p t i m i z a t i o nc a p a c i t y ，r o b u s t n e s so fi n i t i a l v a l u e sa n do t h e ra s p e c t st os o m ee x t e n t k e yw o r d s ：p i p en e t w o r k ；o i l g a sg a t h e r i n ga n dt r a n s p o r t i n g ；t o p o l o g y o p t i m i z a t i o n ；g e n e t i ca l g o r i t h m i i i 学位论文创新性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他 人已经发表或撰写过的研究成果；也不包含为获得西安石油大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做 了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：j 耻 日期：驴六0 6 。口乎 学位论文使用授权的说明 本人完全了解西安石油大学有关保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属西安石油大学。学校享有以任何方法发表、复制、 公开阅览、借阅以及申请专利等权利，同时授权中国科学技术信息研究所将本论文收录 到中国学位论文全文数据库并通过网络向社会公众提供信息服务。本人离校后发表 或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为西安石油大 学。 论文作者签名： 雄 导师签名：蔓趁 日期：2 里哩。亟! 星 注：如本论文涉密，请在使用授权的说明中指出( 含解密年限等) 。 第一章绪论 弟一草绪论 1 1 课题研究的目的和意义 油田地面管网系统是由油气集输、注水、供水和采出水处理等管网分系统组成的一 个十分复杂的多级流体网络系统，肩负着油井产出液的收集、处理、储存、转运、采出 水处理和向油层注入介质( t g 、聚合物等) 的艰巨任务，对于保证油田正常开发生产起 着重要的作用。目前，该管网系统的规划方案主要是由人工凭经验进行，设计质量的好 坏直接受设计者经验和工作状态的影响，根本无法得到严格意义上的最优设计。 油田地面大型管网系统优化设计是一类复杂的大型混合优化问题，涉及离散拓扑优 化、非线性参数优化、选址优化、动态优化、多目标优化等。从计算复杂性角度分析， 有些子问题属于n p 类难题。目前对于这类问题的研究，大多数是对一个确定的网络提 出各种优化方法。但由于问题的复杂性和难度，以往的研究只局限于单一系统，所采用 的优化算法也只是近似解法，因此很容易形成设计和决策在局部是合理的，而在整体上 没有达到最优，甚至出现不协调，致使油田正式投入开发后被迫进行不断地调整改造， 这不仅影响油田的正常开发生产，同时也造成了人、财、物的巨大浪费。对于油田地面 管网这样一个大系统，传统的优化理论与方法存在建模难、优化模型求解难或无法满足 实际要求等问题。而以模拟退火、人工神经元网络和进化算法为主的智能计算由于具有 高度并行性、鲁棒性好、自适应自学习能力强等优点，在解决这类问题方面越来越发挥 更重要的作用。近年来智能计算在构造大系统整体递阶优化模型【1 】和解决油田多级站定 位优化 2 , 3 i 1 a - j 题方面取得了一些研究成果，但由于该系统网络结构规模大，涉及的关系复 杂，网络动态变化等特点，这些成果还很难应用于油田实际，有必要做进一步的研究。 因此，根据实际问题需求建立数学模型，通过设计适当的算法实现油田地面管网系统的 优化设计和动态设计，对于推动最优化技术在油田地面工程建设中的应用，提高油田开 发建设的经济效益具有重要的意义。 1 2 油( 气) 田地面管网综合优化技术研究概述 以优化设计为代表的c a d 技术，在我国油田建设设计中应用研究的迅猛发展是具 有中国特色的研究成果。油田地面管网系统高度分散，管网基本上埋地敷设，系统工艺 流程多变，造成难以研制出在国际上具有广泛适应能力的通用优化设计软件，市场狭窄， 国外公司研制积极性不高。而在国内，由于系统工艺流程相对一致，设计程序、设计采 用的规范和技术相同，因而研究成果具有较强的推广应用前景。近几十年来，随着计算 机技术的不断发展，国内多所高等院校、研究机构与石油企业合作，针对油田地面工程 中的管网系统规划设计方案优化开展了大量研究，初步编制了一些油气集输网络优化设 计【4 】、天然气长输管道设计【5 。、注水管网规划【6 】等方面的优化设计软件。油田地面管网实 质上是一个由点集和边集构成的网络系统【7 】。对油气集输管网而言，点集主要包括油井、 计量站、接转站、集中处理站等；边集是连接节点之间的集油管线和热水管线等。注水 管网的点集包括注水井、配水间、注水站等；边集指的是连接注水节点之间的注水管线。 西安石油大学硕士学位论文 对地面管网进行规划设计的目的主要是确定点集中的某些节点( 如计量站、接转站、集 中处理站、注水站等) 的位置、各节点之间的连接关系以及连接弧的属性( 如管径、壁 厚等) ，以实现油气集输、采出水处理和向油层注入介质的功能。规划设计的准则可以采 用经济最优化准则，如最大利润、最小总费用、最低成本等，也可以采用技术最优化准 则，如最大可靠性等。由此可见，油田地面管网的规划设计问题可以看作是求解满足某 种特定功能的网络最优化问题。 网络优化问题是一类广泛的实际优化问题，其涉及的范围很广，提法很多：目前对 于该问题的研究大致可以分成两大类：一类是对于一个确定的网络提出各种优化问题， 如最短路径问题、最短旅行商问题、最优生成树问题、网络最大流问题、最小费用流问 题等；另一类是求满足某种要求的最优网络，如城市供水管网和排水管网的优化设计、 油气集输管网、注水管网、天然气管网系统的优化设计等。对于第二类问题，目前常用 的策略是采用分级优化方法，根据设计阶段不同将问题划分为几个子问题分别进行求解。 文献 8 - 1 0 】以油田地面建设投资和生产运营费用之和最小为目标进行原油集输系统的规 划设计，根据设计阶段不同将优化过程划分为三个层次：( 1 ) 系统优化，主要是确定各 级站的规模和站数；( 2 ) 布局优化，以管线长度最小为目标优选井站之间的隶属关系和站 址；( 3 ) 工艺优化，优选各类管线规格和生产工艺参数。文献【l l 】将原油集输管网的优 化设计分解成井号集合最优划分、计量站站址优化、集输管网布局优化和参数优化四个 子问题分别进行分析和研究。 文献【1 2 】研究了海底油气集输管网的优化设计问题，以管网投资最小为目标函数， 管网可靠度指标等为约束条件建立了海底油气集输管网的0 1 规划数学模型，运用图论 和网络理论，将该优化问题转化为求可靠度至少为a 的网络图的最小生成树问题进行求 解。文献【1 3 】针对稠油油田注蒸汽管一站系统的优化设计，采用分级优化策略，将问题 分解为管网优化和管径优化。管网优化主要是确定管网的连接关系和各站的几何位置： 管径优化是在管网优化的基础上确定管径和保温层厚度。文献 1 4 】以复杂树枝状干线输 气管网系统为研究对象，在勘察设计定线后，采用分级优化策略，将整个输气管网优化 设计问题分解成布局优化、参数优化和方案优选三个子问题。文献【1 5 】将大型气田集输 管网规划问题划分为网络布局优化和管径组合优化两个子问题。网络布局优化的目标函 数为整个网络铺设的可行管线总长最短，管径组合优化的目标为管网投资最小。 文献【l 缸1 7 】采用分级优化的原则将注水系统的规划分解为注水支线管网的规划和 注水干线管网的规划两部分。在注水支线管网的规划中，优化原则为系统投资最省和可 靠性最高；注水干线的优化原则为管网投资最省，运行费用最少，其优化过程包括注水 站站址选择、主干线走向、干线与支线交点确定三个步骤。 大庆石油学院刘扬教授经过多年研究，根据管网形态不同将油气集输管网划分成多 级星形集输网络和多级环形集输网络两种，建立了相应的拓扑优化数学模型，并提出了 多级分解优化方法 1 8 2 1 】。在管网规划设计过程中，由于设计阶段和设计者偏好不同， 2 第一章绪论 设计所采用的目标函数和求解方法也互不相同。在前面所介绍的关于集输管网和注水管 网的优化设计中，设计主要考虑的目标包括系统投资最省、运行能耗晟低、管线长度最 短、系统安全运行可靠性最高、费用现值最小等，采用的算法主要有枚举法【2 2 1 、离散直 接搜索法【2 3 】、最小生成树算法【1 4 】、动态规划法【2 4 1 、s t e i n e r 算法【1 5 】、混合惩罚函数法【】、 蒙特卡罗方法【2 5 1 、单纯形加速法i 矧、序列二次规划法【2 7 】等。以上研究成果虽然在工程实 际规划设计过程中取得了一定的经济效益，但是在许多方面如模型的完整性、优化算法 的可靠性和通用性、软件研制等多个方面还需要开展进一步研究，以期获得更大的效益。 1 3 智能优化算法研究概述 1 3 1 最优化技术发展简介 最优化是应用数学中一个很强的分支，其研究的主要问题是在给定的条件下如何作 出最好的决策，达到预定的目的。研究的主要内容包括实际问题的模型化、寻求最好决 策的方法以及建立这些方法所依据的理论。最优化技术的发展与计算机技术进步是密切 相关的。在计算机技术尚不发达的时期，由于受到计算量和时间的限制，择优只能在有 限几个方案中进行。当问题复杂时，很难达到最优。5 0 年代以前，求解最优化问题的数 学方法只限于古典求导方法和变分法，或用拉格朗日乘子法求解等式约束条件下的条件 极值问题。用这类方法求函数的极值称为古典最优化方法。随着科学技术的发展，许多 优化问题已无法用古典方法来解决。5 0 年代初期，库恩( h w k u h n ) 和图克( a w t u c k e r ) 首先在理论上取得了突破性成果。他们推导了关于不等式约束条件下的非线性最优必要 条件，称为k u h n t u c k e r 条件，他构成了非线性最优化技术的理论基础。针对不同种类 的优化设计问题，人们发展了许多种不同类型的算法【2 8 3 。对于线性规划问题，常用算 法有单纯形法、k a r m a k a r 算法等；对于无约束极值问题，常用算法有最速下降法、牛顿 法、阻尼牛顿法、变尺度法、模式搜索法、p o w e l l 算法等；对于约束非线性规划问题， 常用算法有惩罚函数法、序列线性规划、序列二次规划、广义简约梯度法、复合形法等； 对于离散优化问题，常用的算法有枚举法、拟离散法、随机搜索法、离散复合形法等。 以上所提及的最优化算法习惯上称为传统优化方法，它们是相对于智能优化算法( 或现 代优化算法) 而言的。这类算法一般只适合于求解中小规模的优化设计问题，当问题规 模较大、非线性程度较高、计算复杂时容易陷入局部最优解。随着工程问题的日益扩大， 优化要面对的工程问题的规模逐渐增大，并且这类问题往往具有复杂性、约束性、非线 性、多极值、建模困难等特点，传统优化算法难以有效解决这类问题，因此寻求一种适 合于大规模并行且具有智能特征的算法己成为有关学科的一个主要研究目标和引人注目 的研究方向。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌算法、遗传算 法、进化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟或揭示某些自然现 象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经科 学和统计力学等方面，为解决复杂问题提供了新的思路和手段【3 0 1 。这些算法独特的优点 西安石油大学硕士学位论文 和机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在诸多领域得到 了成功应用。由于这些算法构造的直观性与自然机理，因而通常被称作智能优化算法或 现代优化算法。1 9 9 4 年，关于神经网络、演化程序设计、模糊系统的i e e e 国际学术会 议在美国o r l a n d o 市举行了首届计算智能世界大会( w c c i 9 4 ) ，进行了题为“计算智能： 模仿生命( c o m p u t a t i o n a li n t e l l i g e n c e ：i m i t a t i n gt h el i f e ) 的主题讨论会，取得了关于计算 智能的共识。继人工智能之后，计算智能异军突起，吸引着众多研究开发者投身于这一 新领域的开拓。w c c i 9 4 虽未界定计算智能的内容，更未讨论它的定义，但从实现计算 机智能化信息处理的方法论角度来看，可以说计算智能包含了一大类“软计算方法， 当前主要有神经计算、演化计算( 又包括遗传算法、演化程序设计、演化策略) 、模糊计 算等。计算智能一出现即受到世界各国科技界、企业界和政府决策机构的高度重视，被 认为是对今后人类社会有重大影响的关键技术。 值得提出的是，虽然由于计算机技术的进步，推动了最优化理论的发展，使其有可 能应用到各种数学、经济、工程设计等领域，并产生了大量的应用算法。但本质上讲， 之所以会有这样多的技术，主要是因为到目前为止还没有找到一种理论或技术可以应用 到所有的优化问题。总体上讲，每种理论或技术均在某些领域，在一定程度上解决所对应 的问题。所以，人们一直努力试图找到一种通用的算法。我们的目的是通过研究这些算 法和技术，找到解决我们所面临的工程问题的新途径、新思路。 1 3 2 模拟退火算法研究概述 模拟退火算法的物理学原理：模拟退火算法是一种亚启发式随机优化算法，其搜索策 略与传统的随机搜索方法不同，它不仅引入了适当的随机因素，而且还引入了物理系统 退火过程的自然机理。这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目 标函数值变好的试探点，而且还能够以一定的概率接受使目标函数值变差的试探点，接 受概率随温度的下降而逐渐减小。模拟退火算法的这种搜索策略有利于避免搜索过程因 陷入局部最优解而无法自拔的弊端，有利于提高求得全局最优解的可靠性。模拟退火算 法的核心思想与热力学原理很相似，而且尤其类似于液体凝固为结晶过程以及金属冷却 退火过程。当液体从高温缓慢的冷却到低温时，其流动性会逐渐丧失，最后形成稳定的 固体。从分子运动的角度来看，在液体冷却过程中，每个粒子都在进行着无序的随机运 动，任意一个粒子都可以沿任意一个方向移动任意的距离，这种移动每次都伴随着粒子 能量的变化。所有粒子运动状态的总体构成了体系的状态，粒子能量的总和构成了体系 的能量，所有粒子能量的变化决定了体系能量的变化。当物系的温度很高时，尽管体系 处在较低能量状态的可能性很大，但是它仍具有达到任何可能状态的能力。随着温度的 下降，系统可能达到的状态数目就逐渐减少。当冷却速度足够缓慢时，粒子的运动就会 从完全无序逐渐向有序的状态变化，最后会排列成为整齐的晶格，这种结构具有最低的 系统能量状态，是系统的稳定态。如果冷却速度过快或者初始温度不够高时，那么系统 就不可能在每个温度下都达到热力学平衡状态，此时形成的是有缺陷的晶格结构。这种 4 第一章绪论 结构在能量上不是最小的，是一种亚稳定态。系统能量的变化规律可以用波尔兹曼函数 来描述，其形式为： c = 2 e 蜀一岛7 灯( 1 1 ) 式中，磊为对应系统的最低能量状态；五为常数；k 为波尔兹曼常数；r 为系统的温度； 只为系统能量处于能量为e 状态的概率。由波尔兹曼函数可知，即使在很低的温度下， 系统状态仍能以一定的概率向能量增大的方向变化。这个特性使系统有可能摆脱能量局 部最小态，达到全局最小态。最优化问题的求解也可以看成上述冷却退火过程；需要优 化的变量构成的可行解集对应着退火过程中系统的众多可能状态，目标函数值对应着每 个可能状态下的能量值，问题的求解过程就是从所有的可能状态中找到使目标函数值最 小的状态。 模拟退火算法的发展及应用研究概况：模拟退火的思想最早是由m e t r o p o l i s 等于 1 9 5 3 年提出的，当时他提出了一种模拟固体在恒定温度下达到热平衡状态的重要性采样 方法，该方法是一种改进的m o n t ec a r l o 方法，称之为m e t r o p o l i s 算法【3 2 】。1 9 8 3 年， k i r k p a t r i c ks 等意识到固体退火过程与组合优化之间存在着相似性，于是提出了解决大 规模组合优化问题，特别是n p 难问题的一种有效近似算法一模拟退火s g 法( s a ) t 3 3 】。 从此，许多学者开始采用s a 算法进行各种组合优化问题的求解，并不断对该算法进行 改进。1 9 8 4 年，g e r m a n s 和g e r m a nd 给出了退火率和退火时间的对数成反比的模拟退 火算法【3 4 1 。1 9 8 5 年，c e m yv 运用模拟退火算法求解t s p 问题获得成功【3 5 】。1 9 8 6 年s z u h 提出了一种退火率和退火时间成反比的快速模拟退火算法( f s a ) 【3 6 , 3 7 1 。1 9 8 7 年，c o r a n a a 将s a 算法用于求解多目标连续变量优化问题【3 8 1 。同年，l a a r h o v e np 和a a r t se 出版 了模拟退火算法的理论和应用一书，对模拟退火算法作了比较系统的总结【3 9 1 。该书 的出版大大促进了s a 算法理论和应用研究的快速发展，并在生产调度、控制工程、机 器学习、神经网络等多个领域取得了较好的应用效果【删9 1 。 近年来，模拟退火算法在油气田开发工程领域的应用研究也比较广泛。文献【5 0 】采 用该算法解决了低渗透油田压注采系统的非线性全局优化问题，得出了不同条件下压、 注、采的最佳匹配关系，实现了压裂、注水和采油技术与经济的有效统一。文献【5 l 】采 用该算法对油田压裂施工过程中的多目标参数优化模型进行了求解，有效地提高了压裂 施工的经济效益。文献【5 2 】将该算法应用到油田压力监测系统的优化部署中，取得了较 好的效果。文献【5 3 】采用模拟退火组合优化算法进行储层随机精细建模，包括目标函数 的构造、选择初始状态、抽样和扰动机制、退火策略参数的选择以及多种类型资料的综 合等问题。文献【5 4 】用该方法预测气田产量、压力等参数的递减规律。 模拟退火算法的实现方式和关键技术：模拟退火算法是基于m o n t ec a r l o 迭代求解策 略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，它是 由某一较高温度开始，利用具有概率突变特性的m e t r o p o l i s 抽样策略在解空间中进行随 机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。其计算过程 西安石油大学硕士学位论文 是由初始解和温度初值f n 开始，然后对当前解重复“产生新解一计算目标函数差一判断 是否接受新解一接受或舍弃”的迭代过程，并逐渐衰减t 值，算法终止时的当前解即为 所得到的近似最优解。从模拟退火算法的计算过程可知，初始温度选择、新状态产生函 数、新状态接受函数、温度衰减函数、内循环终止准则和外循环终止准则是影响算法优 化性能的主要环节，在设计时应予以重点考虑。计算过程如下： ( 1 ) 初始温度f n 的选择 经验法则要求算法进程在合理的时间里搜索尽可能大的解空间范围，只有足够大的 f 0 才能返回一个高质量的最终解，而过大的f 0 值又可能导致过长的执行时间，使模拟退 火算法丧失可行性。因此，初温的确定应折衷考虑优化质量和优化效率，常用的方法包 括：利用经验公式确定初温；均匀抽样一组状态，以各状态目标值的方差作为初温； 随机产生一组状态，确定两两状态间的最大目标值差i 一i ，然后依据差值利用一定的 函数确定初温。 ( 2 ) 状态产生函数 设计状态产生函数的出发点应该是尽可能保证产生的候选解遍布全部解空间。通常， 状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。前者决定 由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。 候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产 生，而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、指数分布、 正态分布等。 ( 3 ) 状态接受函数 状态接受函数一般以概率方式给出，不同接受函数的差别主要在于接受概率的形式 不同。设计状态接受概率应遵循以下原则：在固定温度下，接受使目标函数值下降的 候选解的概率要大于使目标函数值上升的候选解的概率；随温度的下降，接受使目标 函数值上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。 ( 4 ) 温度衰减函数 由固体退火过程可知，控制温度参数的衰减必须缓慢。“以小为宜是控制温度衰减 函数的选取原则。在控制参数缓慢衰减的情况下，相邻的两个温度值气和f 是平稳分布 且相互逼近。因此，一方面，如果在气值上己经达到准平衡，则可以期望在厶值衰减为f 值时，只需要进行少量的变换就足以在o 。值上恢复准平衡，因而可以选取较短长度的 m a r k o v 链来缩减执行时间。另一方面，控制参数小衰减量，可能导致算法进程迭代次数 增加，则可以期望算法进程接受更多的变换，搜索更大范围的解空间，从而返回更高质 量的最终解。目前，最常用的一个非常直观的温度衰减函数是丘+ 。= a t k ，其中0 口 l 且 大小可以不断变化。 ( 5 ) 内循环终止准则 内循环终止准则，或称m e t r o p o l i s 抽样稳定准则，用于决定在各温度下产生候选解 6 第一章绪论 的数目。在s a 算法理论中，收敛性条件要求在每一温度下产生候选解数目趋于无穷大， 这在实际应用时是无法实现的。常用的抽样稳定准则包括：检验目标函数的均值是否 稳定；连续若干步的目标值变化较小；按一定的步数抽样。 ( 6 ) 外循环终止准则 外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值f 。是一 种简单的方法，s a 算法的收敛性理论中要求t 趋于零，这显然是不实际的。通常的做法 包括i 设置终止温度的阀值；设置外循环的迭代次数：算法搜索到的最优值连续 若干步保持不变。 1 3 3 遗传算法研究概述 遗传算法是基于达尔文的进化论和孟德尔的遗传学说，模拟自然选择和有性生殖过 程的一种全局优化搜索算法。达尔文的进化论认为物竞天择，适者生存。孟德尔的遗传 学说也就是染色体遗传学说，又称基因学说。自然界的生物类型遵循着从低级、简单到 高级、复杂的进化过程。在这一过程中，遗传和变异起着重要作用，是决定生物进化的 内在因素。其中遗传是指父代与子代之间，在性状上存在的相似现象。变异是指父代与 子代之间，以及予代的个体之间，在性状上或多或少地存在的差异现象。遗传能使生物 的性状不断地传送给后代，因此保持了物种的特性，使生物界的物种能够保持相对稳定。 变异能够使生物的性状发生改变，使生物个体产生新的性状，以至于形成新的物种，从 而适应新的环境而得以生存。根据现代细胞学和遗传学的研究得知，进化是发生在作为 生物体结构编码的染色体上，染色体是生物遗传物质的主要载体。染色体由多个基因组 成，基因是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变， 并可通过控制蛋白质的合成而控制生物的形状。生物体自身通过对基因的复制和交叉操 作来选择和控制其性状的遗传。同时，通过基因重组、基因变异和染色体在结构和数目 上的变异产生丰富多彩的变异现象，决定着生物个体的性状。根据达尔文的进化论，多 种多样的生物之所以能够适应新的环境而得以生存进化，是与上述的遗传和变异现象分 不开的。那些适应性好的个体比差的个体得到更多的繁殖机会。从自然界生物体的演化 过程来看，大多数生物体是通过自然选择和有性生殖这两种基本过程进化演变的。自然 选择决定了群体中哪些个体可以存活并繁殖；有性繁殖保证了后代基因中的混合和重组。 自然界中的生物体就是通过自身演化这种非定向机制不断地向前发展。遗传算法解决优 化问题的过程就是模拟生物种群的进化过程。首先，建立一个初始群体，用类似于染色 体的编码( 如二进制数串) 表示给定寻优问题的一个可能解，即代表种群的一员。类比生 物的适应性，建立适应值函数以确定种群成员的“好与“坏。按与适应值成比例的概 率选择适应性好的个体进行复制，淘汰适应性差的个体；然后，按照一定的概率对种群 成员进行交叉和变异，产生出新的一代更适应环境的种群。这样一代代地不断进化，最 后收敛到适应性最强的群体，历代种群中最好的个体即为优化问题的最优解。 遗传算法的最早雏形源于f r a s e r 的论文，它是一位生物学家，试图仿真突出突变和 7 西安石油大学硕士学位论文 选择交互作用的进化过程【5 5 】。2 0 世纪6 0 年代，美国m i c h i g a n 大学的h o l l a n d 教授开展 自然和人工自适应系统的研究。在研究过程中，他试图发展一种用于创造具有适应任意 环境能力的通用程序和机器的理论，并意识到用群体方法搜索以及选择、交叉等操作策 略的重要性睇】。1 9 6 7 年，h o l l a n d 教授的学生b a g l e y 发表了第一篇有关遗传算法应用的 论文，并首次提出了“遗传算法”这一名词。在该论文中，提出了与目前复制、交叉、 变异等类似的基因操作，并对遗传算法的早熟机理进行了研究，提出了自组织遗传算法 的概念1 57 1 。1 9 7 0 年，c a v i c c h i o 研究了基于遗传算法的子程序选择和模式识别问题。在 模式识别问题上，采用整数编码，检索空间很大，他提出了以预选择策略保证群体多样 性，对遗传算法参数进行中心控制的方法【5 引。1 9 7 5 年是遗传算法发展史上最重要的一年。 在这一年发生了两个被认为是具有里程碑意义的重要事件。一是h o l l a n d 教授出版了经 典著作“a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m s ，【5 9 】。该书是作者多年理论研究及实 践的结晶，特别是给出了奠定遗传算法理论基础的模式定理。另一个是d e j o n g 完成了 对遗传算法研究具有指导意义的博士论文“a na n a l y s i so ft h eb e h a v i o ro fac l a s so f g e n e t i ca d a p t i v es y s t e m ”唧j 。他深入领会了模式定理并做了大量严格的计算实验，给出 了明确的结论，并建立了著名的d e j o n g 五函数测试平台，定义了性能评价标准，并以 函数优化为例，对遗传算法六种方案的性能及机理进行了详细实验和分析，他的工作成 为后继者的范例并为以后的广泛应用奠定了坚实的基础。 g o l d b e r g 在遗传算法研究中起着继往开来的作用，他在1 9 8 3 年的博士论文中第一次 把遗传算法应用到实际的工程系统，也即煤气管道优化【6 。g o l d b e r g 的系统不仅用与实 际系统相当的成本满足了供气要求，而且也发展了一套分层容错规则，它能够对管道漏 洞采取适当的反应。从此，遗传算法在理论研究方面更加深入，并在函数优化、工程设 计、神经网络、机器学习、系统辨识等领域获得了广泛的应用。近年来，遗传算法在油 气田开发工程领域也有一些成功的应用。文献 6 2 6 4 1 应用遗传算法确定油气田产量预报 模型中的参数最优估计值，有效地提高了产量预报的准确性，改善了开发生产效果和措 旋作业效益。文献 6 5 1 采用该算法求解油田措施的目标随机动态规划模型，为开发方案 地有效调整、确保油田稳产起到了积极作用。文献 6 6 】应用遗传算法对压裂井产量生产 动态资料进行解释，确定地层参数( 渗透率、表皮系数、地层平均压力和井筒储存系数等 参数) 和损害程度，为气田开发监测提供了较为经济的途径。文献 6 7 】以获得最大利润为 目标，根据油田开发的实际情况，综合考虑了成本、投资等约束，建立了油田开发非线 性规划数学模型，并采用遗传算法进行了有效求解。在油田地面工程方面也有一些文献 报道。文献【6 8 】将灰色理论和遗传算法结合起来预测注水管道腐蚀速率，有效地提高预 测精度。文献【6 9 】采用遗传算法进行油田地面多相混输管网结构参数优化，文献【7 0 】用该 算法对油田注水系统并联注水泵运行优化调度数学模型进行了求解，在实际应用中均取 得了一定的经济效益。 遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体 8 第一章绪论 的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量 的状态。标准遗传算法的主要步骤为： ( 1 ) 随机产生一组初始个体构成的初始群体，并评价每一个个体的适应值。 ( 2 ) 判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤。 ( 3 ) 根据适应值大小以一定的方式执行复制操作。 ( 4 ) 按照一定的交叉概率执行交叉操作。 ( 5 ) 按照一定的变异概率执行变异操作。 ( 6 ) 返回步骤( 2 ) 。 根据遗传算法的计算过程可知，问题的编码方案、适应值函数设计、基因操作、算 法参数选取以及算法终止条件是影响算法优化性能的主要环节，在设计算法时应根据问 题的特点进行设计【7 1 1 。现简要介绍如下： ( 1 ) 问题编码方案 遗传操作不对解空间的决策变量直接进行操作，而是对表示可行解的个体编码施加 选择、交叉、变异等操作。这种将可行解从其解空间转换到遗传算法所能处理的搜索空 间的转换操作或方法称为编码。编码的好坏直接影响了遗传算子的设计，进而影响到算 法的性能和效率。根据问题不同，人们提出了许多种不同的编码方法，这些编码方法大 致可以分为三大类：二迸制编码、实数编码和符号编码。二进制编码和解码方法操作简 单易行，交叉、变异等遗传操作容易实现。但二进制编码存在连续变量离散化带来的映 射误差，以及符号串的长度对问题的求解精度和算法运行效率有很大的影响等问题，尤 其在求解高维优化问题时，二进制编码串非常长，扩大了算法的搜索空间，因而大大降 低了算法的搜索效率。实数编码适合于精度要求较高、搜索空间较大、高维复杂约束问 题，但实数编码要求保证交叉、变异等操作的结果必须在基因值给定的区间内，而且交 叉运算不能在基因的中间字节分隔处进行。符号编码是指个体染色体编码串中的基因值 取自一个无数值含义、而只有代码含义的符号集。该编码方法便于在遗传算法中结合所 求问题的专门知识，而且利于与相关近似算法混合使用，但该编码方法需要对交叉、变 异等遗传算子认真设计，以满足问题的各种约束条件，提高算法的搜索性能。 ( 2 ) 适应值函数+ 适应函数值是遗传操作中用来度量个体能达到或接近于最优解的优良程度，是遗传 算法优化过程发展的依据。适应度较高的个体遗传到下一代的概率较大，而适应度较低 的个体遗传到下一代的概率较小。适应函数的选取至关重要，直接影响到遗传算法的收 敛速度以及能否找到最优解。一般而言，适应值函数是由目标函数变换而成的。对于简 单的优化问题，一般可以直接利用目标函数转换成适应值函数；对于复杂的优化问题， 往往需要将目标函数值域进行某种映射变换，这种变换称为适应函数的尺度变换。常用 的适应函数尺度变换方法有线性尺度变换、指数尺度变换、乘幂尺度变换等。 ( 3 ) 遗传算子 9 西安石油大学硕士学位论文 遗传算子主要包括复制、交叉和变异等算子。算子设计一般因问题的编码方式不同 而有所不同，算子设计的好坏将直接影响到算法的收敛性和收敛速度。复制操作的目的 是为了避免有效基因的缺失，使高性能的个体得以更大的概率生存，从而提高全局收敛 性和计算效率。复制操作策略对算法性能的影响会起到举足轻重的作用。不同的复制策 略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。较大的选 择压力使最优个体具有较高的复制数目，从而使得算法收敛速度较快，但也较容易出现 过早收敛现象。相对而言，较小的选择压力一般能使群体保持足够的多样性，从而增大 了算法收敛到全局最优的概率，但算法的收敛速度一般较慢。常用的复制策略大致可以 分为基于适应值比例的复制( 如轮盘赌选择、繁殖池选择等) 、基于排名的复制、基于局 部竞争机制的复制( 如锦标赛选择等) 。交叉是指两个相互配对的染色体按某种方式相互 交换其部分基因，从而形成两个新的个体。在交叉运算之前，常用随机配对策略先对群 体中的个体进行配对。交叉算子的设计和实现与所研究的问题密切相关，其作用是组合 出新的个体，以便在解空间中进行有效搜索，同时降低对有效模式的破坏概率。交叉算 子的设计主要考虑如何确定交叉点的位置及如何进行部分基因的交换，常用的交叉算子 有单点交叉、双点交叉、算术交叉等。变异是指个体编码串中某些基因座上的基因值， 以一定的概率用其他等位基因来替换从而形成一个新的个体。变异操作可以改善遗传算 法的局部搜索能力，维持群体的多样性，防止出现早熟收敛。变异算子的选择与问题的 编码方式有很大关系。二进制编码中通常采用替换式变异，如基本位变异等：实数编码 中通常采用扰动式变异，即对原先个体附加一定机制的扰动来实现变异；组合优化问题 通常采用互换式、逆序式、插入式变异等。 ( 4 ) 算法参数选取 遗传算法中需要选择的参数包括群体规模、交叉概率只和变异概率只等，这些参 数的选取对遗传算法的性能有很大的影响。在求解实际问题时，这些参数主要是凭经验 值给出，其范围一般为：n = 2 0 1 0 0 ，= 0 5 1 0 己= 0 0 0 1 0 0 5 。在简单遗传算法中， 这些参数是不变的。目前许多学者认识到这些参数需要随着遗传进程而自适应变化，这 种有自组织性能的遗传算法具有更高的鲁棒性、全局最优性和效率。d a v i s 提出一种只、 只随基因操作的在线性能自适应变化的有效方法，性能提高则增加，反之则己增加 1 7 2 1 。f o g a r t y 研究了己随遗传代数变化的效果，结果显示己随指数下降有较好性能【7 3 1 。 恽为民，席裕庚的自适应有效基因突变也有类似效果【7 引。s r i n i v a s 和p a t n a i k 提出一种只、 只随父串的适应度自适应变化的新方法，计算实例显示该法在非线性优化问题中性能优 异。 ( 5 ) 算法终止条件 遗传算法是一种反复迭代的搜索方法，它通过多次进化逐渐逼近最优解而不是恰好 等于最优解，因此需要确定其终止条件。最常用的终止方法是规定遗传的代次。当目标 函数是方差这一类有最优目标值的问题时，可采用控制偏差的方法实现终止。一旦遗传 1 0 第一章绪论 算法得出的目标函数值与实际目标函数值之差小于允许值后，算法终止。终止条件也可 通过检查适应函数值的变化来实现，如果群体平均适应函数值变化率和最优个体适应函 数值变化率小于许可精度，则可以认为群体处于稳定状态，群体进化基本收敛，可结束 群体进化过程，否则继续群体的进化过程。 1 4 论文主要研究内容 本论文研究的主要任务是：在对油田地面管网的网络形态，层次关系，动态变化特 征等相关因素进行分析研究的基础上，建立系统拓扑布局优化的数学模型；通过计算复 杂性分析说明所建立模型的计算难度；根据模型