（市政工程专业论文）给水管网优化设计及其CAD的研究.pdf

y 57 a 2 0 摘要 随着城市现代化建设的加快，配水管网建设在市政工程中占有了越来越重要 的地位。由于给水管网优化技术的运用能够产生巨大的经济效益和社会效益，不 仅可以节省大量的资金，而且还能改善整个管网的水力条件，因此具有很好的工 程前景；然而目前管网优化技术缺乏工程实用功能，而且计算机作为种强大的 现代工具，并没能得到充分的应用。本文根据以往的文献资料及相关工程经验， 针对给水管网优化设计这一课题做了深入的研究，提出利用分层分解协调算法将 管网优化设计问题分解成流量优化、管径优化及管径取整三个子课题的思想，并 分别采用广义简约梯度法、遗传算法与广义简约梯度法相结合的混合遗传算法及 简单遗传算法来求解三个课题。本文对遗传算法作了很多的改进，采用了自然数 编码技术、扩大采样空间技术、惩罚策略、算术交叉和动态变异技术，并将遗传 算法与g r g 法有机地结合起来，改善了遗传算法的性能，充分地提高了搜索的效 率和精度。本文还开发了以优化技术为核心的给水管网c a d ，实现了在c a d 中 自动搜索并提取管网的拓扑信息及节点流量的自动预分配，建立了管网信息的 a c c e s s 数据库，从而能更为方便地进行管网优化设计。此外，本文以s u a lc + + 作为管网数据库开发平台，实现了对数据库数据的提取，优化计算以及数据反馈。 最后，本文结合工程实例验证了算法以及管网c a d 的实用性。 关键词：给水管网优化设计，分层分解算法，遗传算法，g r g 法，混合遗传算法 c a d a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec i t ym o d e r n i z a t i o n ，m u n i c i p a lw a t e rs u p p l ys y s t e m b e c o m e sm o r ea n dm o r ei m p o r t a n ti nt h em u n i c i p a le n g i n e e r i n g b e c a u s eo p t i m a l t e c h n o l o g yo f t h ew a t e rs u p p l yn e t w o r k sc a nn o to n l ys a v eag r e a td e a lo ff u n d sb u t a l s oi m p r o v et h eh y d r a u l i cc o n d i t i o no ft h ew h o l en e t w o r k ，i th a sb e r e rp r a c t i c a lv a l u e a l t h o u g hu s i n go p t i m a lt e c h n o l o g yc a nm a k eg r e a te c o n o m i c e f f e c t i v e n e s sa n ds o c i a l e f f e c t i v e n e s s ，i tl a c k so fp r a c t i c a lf i m c f i o n m o r e o v e r , t h ec o m p u t e rt h a ti sam o d e r n t o o lh a sn o tb e e n w i d e l yu s e di nt h ef i e l d u s i n gt h el i t e r a t u r em a t e r i a l sa n de x p e r i e n c e b e f o r e ，t h i sp a p e rm a k e s a t h o r o u g hs t u d y o n o p t i m a ld e s i g no f w a t e rs u p p l yn e t w o r k s a na l g o r i t h mo fd e c o m p o s i n ga n dc o o r d i n a t i o no fs y s t e me n g i n e e r i n gw h i c hd i v i d e s t h eo p t i m i z a t i o no ft h ew h o l en e t w o r k si n t ot h r e ep a r t s ，i e o p t i m i z a t i o no fw a t e r r e s o u r c ef l o w , a n d p i p e - d i a m e t e r a n ds t a n d a r d i z a t i o no f p i p e d i a m e t e ri sp r o p o s e d t h e t h r e ep a r t sc a nb er e s o l v e db yg e n e r a l i z e dc o n t r a c t e dg r a d sm e t h o d ，h y b r i dg e n e t i c a l g o r i t h mw h i c h i st h ec o m b i n a t i o no f g e n e t i ca l g o r i t h ma n dg r g m e t h o ds e p a r a t e l y t h i sp a p e ra l s om a k e sm a n yr e f o r m so ng e n e t i ca l g o r i t h m ，w h i c hi n c l u d eu s i n gt h e t e c h n o l o g yo f t h er e a ln u m b e r c o d e ，b r o a d e n i n g t h es e l e c t i n g s p a c e ，p u n i s h m e n tt a c t i c s a r i t h m e t i c a lc r o s s o v e r , d y n a m i cm u t a t i o na n dc o m b i n i n gg e n e t i ca l g o r i t h mw i t hg r g m e t h o d ，s o i t b r i n g s f a s t e r s e a r c h i n gv e l o c i t y a n db e t t e r a c c u r a c y n e x tt h r o u g h p r o g r a mg r a p h i c d a t a b a s e sa n dd a t a b a s e so fw a t e r s u p p l yp i p e l i n en e t w o r ka r ec r e a t e d b y m e a n so f a u t o s e a r c h i n g t h e t o p o l o g i c a l i n f o r m a t i o no f p i p e l i n en e t w o r k ， a u t o n u m b e r i n gt h ep i p e l i n e sa n d t h ej o i n t s ，a n dm e a s u r i n gt h e l e n g t ho fp i p e l i n e sa n d t h ef l o wd i s t r i b u t i o no fi n i t i a lp i p e l i n e sf r o mc a d w h a t s m o r e ，t h r o u g h v i s u a lc + + ， g e t t i n gd a t af r o md a t a b a s e s ，o p t i m a ld e s i g na n dr e t u r n i n gd a t ab a c kt od a t a b a s e sa r e a c h i e v e d a tl a s t ，t h ew a t e rs u p p l yn e t w o r k sc a d s y s t e ma n do p t i m a lm e t h o d i st e s t e d a n dv e r i f i e di na n e x a m p l e k e yw o r d s ：o p t i m a ld e s i g n o fw a t e r s u p p l yn e t w o r k s ，c a d ，a l g o r i t h m o f d e c o m p o s i n g a n dc o o r d i n a t i o no f s y s t e m e n g i n e e r i n g ，g e n e t i ca l g o r i t h m ，g r gm e t h o d ， h y b r i dg e n e t i ca l g o r i t h m 主要符号及意义 管线造价年折算费用 p 年折算与大修费 0 管段长度 d 。，管径 a , b ，c 单位长度管网造价公式中的系数 矿管网节点集合 口值”o ) 等额分付资金回收系数 f 年利率 n o 项目计算期 正送水泵站年平均动力费用 ，供水能量变化系数 占电价 丁供水时间 “，第f 个泵站送水量 功第f 个泵站效率 f 第f 个泵站至管网控制点线路上，管段的水头损失 z c 管网控制点要求的自由水压值 z b 第f 个泵站至管网控制点的某条线路的管段集 s 所有送水泵站合集 五新建水厂的年折算费用 h ：水厂的计算期 p 水厂的折旧与大修理费 c n 新建单位水量净水厂( 送水泵站) 所需基建费用 r , v 新建水厂集 聊净水厂送水泵站基建经济效应系数 q ，设计年限内第f 个节点在最高日最高时的需水量 五与节点f 相邻的节点编号的集合 鼢管道的摩阻系数 塌在节点f 的总水压 氆常数 v m 节点总数 h ，系统服务质量所要求的第f 个节点压力的下限值 日系统服务质量所要求的第i 个节点压力的上限值 “? 节点i 的供水泵站可能的最小供水量 “? “节点i 的供水泵站可能的最大供水量 所有可选用管径的集合 d 岫允许的最小管径 d 。允许的最大管径 d 。优化结果d ，下档的标准管径 d 。优化结果巩上档的标准管径 第一章绪论 随着城市现代化建设的加快，配水管网建设在市政工程中占有了越来越重要 的地位。一般来讲，给水管网占整个给水系统投资的6 0 8 0 ，而且还涉及每年 庞大的能量消耗，其设计的结果直接关系到二级泵站电耗的大小，而在自来水公 司中二级泵站的运转费用又占全部管理费的l 3 左右【l i 。因此，一个好的管网设 计方案，不但要考虑基建投资的经济性，还要考虑运行期管理费用的经济性，所 以城市管网的优化设计具有极为重要的意义。 给水管网的设计计算经过了从手算到电算，从凭经验设计到优化设计阶段， 这一过程是与计算方法和计算工具的发展相适应的。传统方法是凭经验查阅大量 表格进行设计的，过程繁琐，计算结果不准确。随着优化理论的发展，管网的优 化设计也相应的发展起来。起初，研究人员总是用一些确定性优化方法来解决管 网优化问题。2 0 世纪8 0 年代初，一些启发式模拟算法迅速发展起来，如遗传算 法、神经网络、模拟退火法等方法。这些方法超越了传统的设计思想，鲁棒性强， 己成功地解决了许多组合优化问题，现在也被引入到管网优化设计中来，并取得 了高质量的解答。 优化算法上的革命影响着管网模型的发展。由于计算机的广泛应用以及应用 软件的发展，目前，管网模型正向智能化、图形化方向发展，并为用户提供了方 便的界面和强大的功能。管网模型的发展趋势是如何利用计算机强大的功能来实 现更加快速、精确的设计分析。 计算机在给水排水工程中的应用主要表现在1 2 】：c a d ( c o m p u t e r a i d e dd e s i g n 一一计算机辅助设计) 、a m ( a u t o m a t e dm a p p i n g 自动成图) 、f m ( f a c i l i t i e s m a n a g e m e n t 设施管理) 、g i s ( g e o g r a p h i c i n f o r m a t i o ns y s t e m 地理信息系 统) 。其中c a d 和a m 可用来作为企划设计和设施成图等的图形生成环境的工具： 在没有图形显示能力时，f m 可以提供有效的工程设施的统计、管理和分析：而 g i s 能够在很大限度内支持a m f m 在诸如管网模拟、空间分析和事故模拟等方 面的应用。 a u t o c a d 是目前我国给水排水工程领域应用最普遍的c a d 平台之一，目前 国内编写的给水排水工程c a d 设计软件，都是以此为平台进行二次开发的。在 以前的a u t o c a d 版本中，大多是以a u t o l i s p 作为开发语言，后来扩展到a d s 系统。现在的a u t o c a d 2 0 0 0 提供了更多、更方便的二次开发工具，如v i s u a ll i s p 、 a c t i v e x 、v b a 、a d s 、a s i 等。 1 1 给水管网c a d 软件的概况 为了让优化方法在实际的工程设计中能够方便地运用，不仅需要把它们转化 为计算机语言，而且还需要把它们制成软件包。这样不仅能够克服使用上的不便， 同时还能够解决不可视的感觉缺陷。目前在国内外己有以下一些给水工程软件， 这些软件大部分都是以a u t o d e s k 公司的a u t o c a d 为操作平台。 1 1 市政管线设计软件h y s z g xv 4 0软件内容包括：地形处理、道路平 面、给水设计、管网平差、污水设计、雨水设计和管线综合等。h y s z g xv 4 0 的c a d 操作平台为美国a u t o d e s k 公司的a u t o c a d r 2 0 0 0 2 0 0 2 。软件根据给水、 污水、雨水管道各自的特点，结合道路的特征采用自动定线和交互定线相结合的 方式，快速得到管道平面布置图。对于布置好的管道，可以使用c a d 命令或软 件提供的专用命令进行编辑。使用专用工具对图面进行重合线检查、重合节点检 查和节点连接管线修正。对管道直径、标高进行修改时，程序会自动对上下游相 关管道进行修正。平差计算时，水源可以是定压力，也可以是水泵组合。可以计 算任意多个水源，可以对最不利点校核、消防校核、反算水源点压力、事故校核 等多种工况进行计算。计算原始数据可以直接输入也可以从图面自动提取。计算 规模达到千级管段，计算结果可以标注到图面上，也可以形成完整的平差计算书。 2 ) w a t e r c a d由世界上最大的给排水专业软件开发与研究公司海思德工程 软件公司( h a e s t a dm e t h o d s ，i n c ) 开发。w a t e r c a d 软件可对给水管网系统进行 静态分析和设计；可对给水管网系统进行动态模拟分析和设计，即分析和设计给 水管网系统在不同供水状态下随时间的响应。模拟分析和设计含有水泵、水塔、 水库和控制阀门的给水管网系统；进行消防用水流量和平差分析，分析给水管网 系统在极端用水条件下的表现；可对给水管网系统进行各种方案下的水文水力学 计算和成本分析比较，并为用户产生各种图表、曲线和报告。 3 ) w a d s o p ( 给水系统优化程序)一种典型的决策支持系统，该系统为承 担给水工程规划设计提供了一种灵活且有价值的工具。其中用非线性规划技术作 管网解算器，比传统方法( h a r d y c r o s s 、n e w t o n r a p h s o n 等) 具有明显的收敛 速度快的优点。 4 ) 理正给排水设计软件理正给排水、设备绘图软件包，是理正软件研究院 开发的一套智能化绘图软件，主要进行室内给排水管网设计。 5 ) 天正给排水t w t 方便灵活的室内给排水设计软件。平面图直接生成系 统图时，采用多视窗技术，即可生成大样系统图，也可生成完整的系统图或高层 立管图( 展开图) ，同时也提供直接绘制系统图的功能。最新版的给排水将使用户 在a u t o c a dr 1 4 平台及a u t o c a d2 0 0 0 平台上的转换极为方便。 6 ) i n t e r g p v 4 0 给排水c a d 软件由北京皓辰思达科技发展有限公司开发 主要进行室内外水、暖、电管网c a d 设计。 1 2 给水管网优化设计的算法概况 已定管线的配水管网的优化设计是n p 类的组合优化设计问题，情况复杂。近 年来，国内外学者在此领域作了大量研究。优化方法主要有两类：传统的是一些 确定性优化方法，主要有枚举法、线性规划法、非线性规划法：还有一类是近几 年才发展起来的一种随机性优化方法，主要是遗传算法和模拟退火方法等。 在五十年初，管网的技术经济计算是在新建管网流量分配已知的条件下进行 的。苏联学者把古典拉格朗日条件极值理论引入到管网优化设计中来，通过拉格 朗日把有约束非线性规划问题变换为无约束非线性规划问题。可它忽略了流速和 管径的不等式约束条件，且没有节点水压的极值限制，同时其目标函数是管段流 量和节点水压的费用函数，需进行流量初始分配，但环状管网的管段流量优化分 配是一凹规划课题，没有最优解，许多学者对这一问题作了大量的研究。2 0 世纪 8 0 年代初，俞国平提出了经验确定流量初始分配的方法，但这种半经验性的设计 降低了优化结果的可信度。欧美的一些学者把管网优化问题描述成一类非线性规 划问题。其中，j a c o b y 运用了梯度搜索技术；w a t a n a t a d a 采用的是罚函数法：s h a m i r 采用广义简约梯度法和罚函数法的结合。非线性规划的数学模型比较真实、完整 的表达了管网优化的实质，但这类课题的求解非常复杂困难，特别是在大型问题 中变量很多，得到的一般都是局部最优解。q u i n d r y 在梯度搜索技术基础上，把 线性规划运算得到的节点压力固定起来，再对流量q 进行梯度搜索，但很难找到 一个初始的基本可行解。 在流量分配和水头损失均未知的条件下，管网优化的课题是一个凹规划课题， 它的最优解出现在约束域的边界上，而且有非常多的局部最优解。当环状管网对 管段的流量及管径没有下限约束时，流量分配的结果是某些管段的流量为零，从 而使环状网变成树状网。b h z v e 提出用线性规划中运输理论观点来描述流量分配 课题；杨钦教授利用梯度搜索技术讨论最优流量分配；r o w e l l 和b a r n e s 把选择连 枝的优化问题描述为o 一1 整数规划问题，但都有一定的局限性。 在管网优化设计中，还存在理论管径园整为标准管径的问题，它是一个非线 性的整数规划问题，一般是根据某一原则就近园整。l a i n 提出了离散梯度的方法， 仍无法使园整后得到的目标函数为理论上求得的最优解。俞国平提出将每一根管 段分成两段，再上下取整的方法，这种方法增加了管网的管段数和节点数。 1 2 1 确定性优化方法 1 2 1 1 枚举法 枚举法需要存储每一管段所有可能用到的标准管径，形成标准管径解空间， 再进行逐个试算。此方法所需存储的空间大，计算效率很低，只能解决管段数量 很少的管网优化问题。1 9 8 5 年，g e s s l e r 依据一定的经验提出缩小管径解空间的 方法，这样虽相对降低了计算量，但不能保证最优解就在缩减后的解空间内。1 9 9 0 年，l o u b s e r 等又提出了缩减解空间的一些原则，计算量仍很大，优化结果不很 理想。 1 2 1 2 线性规划法 2 0 世纪7 0 年代末，a l p e r o v i t s 和s h a m i r ，q u i n d r y 相继提出线性规划模型， 至今仍有广泛的影响，但管网的规模受到了限制。后来，俞国平教授提出了以管 长为决策变量的线性规划模型【3 1 。用这一模型可以解决树状管网的优化设计问题。 由于树状管网管段流量分配的唯一性，管段流量分配的优化分配问题可以避免， 可以很容易的通过流速约束条件找出每一管段可能用到的标准管径解集。但对环 状管网，若管段流量分配未知，如何确定管段可行管径组就成为一新的问题。 1 2 ，13 非线性规划法 非线性规划模型比较真实地反映了管网优化设计问题的实质，但求解的难度 也大大增加。目前非线性规划模型一般都为复杂的不等式约束非线性问题，常用 的计算方法有广义简约梯度法( g r g ) 。该法应用范围广，收敛速度较快，是目前 解决一般不等式约束非线性规划问题最有效的方法之- - 4 1 。其缺点是计算结果常 常陷入局部最优，且计算程序复杂，占用内存大，难于解决大中型管网优化问题。 1 9 8 9 年，l a n s e y 等用拉格朗日罚函数法将水压约束变为目标函数中的罚函数项， 后来在此基础上采用数学变换方法将不等式约束的非线性问题转换为无约束非线 性规划问题，用p r p 共轭梯度法求解变换后的模型，运算结果表明其求解速度比 现有同类型非线性规划模型快1 0 倍【”。 1 2 2 随机优化方法 122 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是随机优化方法的一个新的正在发展 的领域。遗传算法模拟的机制是一切生命与职能的产生与进化过程。它通过模拟 达尔文“优胜劣汰、适者生存”的原理激励好的结构；通过模拟孟德尔遗传变异 理论的迭代过程中保持已有的结构，同时寻找更好的结构【5 l 。1 9 8 7 年，g o l d b e r g 等将这一理论应用于管网优化设计中来。遗传算法在有向网络、给排水管网等系 统的优化设计中，己成为较为可行的方法之一。虽然g a 的搜索方法具有很大的 随机性，可实践已证明对于任何管网系统的优化设计，都能得到全局最优解或趋 于全局最优的解。国内外的学者们对g a 的各种变异形式进行了研究和探讨，他 们各自的优缺点将在后面几章中详细介绍。 1 2 2 2 模拟退火法 模拟退火法( s i m u l a t e da n n e a l i n g ，简称s a ) 是由s k i n p a t r i k 于2 0 世纪8 0 年 代初提出的一种模拟金属退火的全局优化随机方法。它结合了统计物理学和局部 搜索的方法和原理求问题的全局解。它从任一标准管径初始可行解出发，并用某 一机制( 交换、查找、逆转) 产生邻域解，用水力约束条件控制计算流程是否由 m e t r o p o l i s 准则判定，如此迭代下去直到得出一满意解。s a 算法以离散的标准管 径为空间搜索点，管径不需调整，其次，随即产生邻域解及m e t r o p o l i s 准则的引 入，都避免了陷入局部最优解的发生。 1 3 本课题的来源和研究内容 给水管网系统投资大，投资偿还期长，有很大的可塑性，通过优化设计可以 节省大量工程投资。但历史上人们的大部分兴趣都集中在流量分配高效算法的研 究上，较少研究开发管网优化设计的方法，且目前的给水计算软件包极少采用先 进的优化设计技术。基于这些现实，本课题的研究旨在c a d 平台上实现管网拓 扑信息的自动提取，在建立管网优化设计模型的基础上，研究并采用新的理论和 方法，进一步发展给水管网优化技术。其研究内容包括： 1 ) 建立管网优化设计的数学模型并研究相应的优化算法。根据系统工程的分 解分层思想，整个大系统采用分解协调法来完成给水管网的优化。 管网优化问题分解为3 个子课题：管径优化、水源流量优化和管径取整。水 源优化问题采用对初值要求不高、优化效果明显的广_ 义简约梯度方法；管径优化 问题采用遗传算法求解，为了提高遗传算法的寻优效率，将广义简约梯度方法与 遗传算法相结合，实际工程应用结果验证了这种混合优化算法的有效性和可行性： 管径优化的结果并不符合标准管径的要求，需要进行管径取整，本文采用二进制 编码的简单遗传算法来实现管径的取整。 2 ) 给水管网c a d 的开发。进行管网设计需要大量的管网数据，例如管段编 号、节点编号、管长、上下游节点编号等，通常管网图形的拓扑关系都是由人工 完成，对于大型管网，这种方法效率低且容易出错，更不易于对管网进行修改。 为了克服这些缺点，本课题的另一个内容就开发以优化技术为核心的给水管网 c a d ，要借助计算机来自动完成管网拓扑信息的提取工作，实现管段、节点自动 编号，寻找管段上、下游节点，量取管长，初始管段流量分配，并建立数据库， 当设计者对管网进行修改时，数据库同步修改。数据库采用的是a c c e s s 数据库， 设计开发的平台采用的是a u t o c a d ，运用v b a 进行二次开发。 3 ) 以长沙县榔梨镇的新建管网工程为实际算例，验证优化算法的有效性和可 行性，以及给水管网c a d 的实用性。 第二章给水管网优化设计数学模型和算法 2 1 给水管网优化设计模型 给水管网的设计必须满足三个条件：一是水力条件( 即节点方程和环方程) ： 二是可靠性( 即用户对流量和水压的要求) ；三是经济性( 费用最省) 【6 】。由于经 济性以外的其他因素较难定量评价，因此优化设计的数学模型常以经济性为目标 函数，将其余的作为约束条件，据此建立目标函数和约束条件表达式，以求出最 优的管径和水头损失。 给水管网优化设计问题包含了水源、管线和泵站等组成部分。为了充分发挥 整个系统的功能，优化设计模型一般以年折算费用值最小为目标函数，在水力与 可靠性等约束条件下，求出送水泵站的最优流量分配及扬程、最优管径。这些约 束条件可表达为： 1 ) 水力约束：满足节点流量方程和能量方程。 2 ) 节点压力和节点流量必须满足用户的需求。 3 ) 管段流速( v ) 和管径( d ) 也要满足约束条件： v m m v v m 践 r ，1 、 d 。 0 时， 甜p “：+ 弛( ) 恒成立。所以球解如下： 最大允许步长k = m i n ，旯：) 。 在区间【o ， 。】内作步长九的维最优搜索 m i n f ( u + 妒 2 ) ，日) 由搜索方向和步长五可得新的流量为： ”) _ “；”+ 舻( “；”)i = 1 , 2 ，s 一1 3 4 流量优化分配的电算流程 ( 31 8 ) ( 31 9 ) ( 3 2 0 ) 多水源管网流量的优化分配子课题解法的步骤归纳为： 1 1o 一七，给定迭代精度s ，设定初始可行的”( ) ； 2 ) 对给定的”= ( “，求解子问题( 2 1 2 ) 的最优解d 肚； 3 ) 对给定的d ，按式( 3 1 5 ) 、( 3 1 7 ) 和( 3 1 9 ) 分别计算简约梯度、搜索方向和 最优步长； 4 ) 代入步长a 计算新的分配流量”( “。) = i t ( 。+ a p ( u ( ) ； 5 ) 对给定的 = “( “”，求解子问题( 2 1 2 ) 的最优解d ( “1 和目标函数值 “1 饵，u ) ； 6 ) 若，“”( 日，) f ( h ，u ) 则转入步骤6 ，否则转入步骤2 ； 6 ) 令s 为- - d , 的正数，如果m a 皿一- 7 “1 1 ) 占，1 , 2 ，s l 成立，则迭 s 幢 卢一 曲曲 一 只防 酬旧肥 也叫 陋” m m i | j i 如 代终止得最优解“”，否则令“a “”，针l 一i ，转入步骤3 。 优化分配的流程图如图3 1 所示。 输入初始数据 分配一 管径优化得和目标函数值f 求搜索方向和步长 i一 一”冉x p ( u ) l 管径优化得扩”和目标函数值f y 输出优化结果u ，d 图3 1 多水源管网流量优化分配流程图 患 第四章管网管径优化的混合遗传算法 4 1 管网管径优化的数学模型 4 1 1 管径优化的数学模型 管径优化是在供水水源供水量给定情况下的优化问题，其数学模型为： o b ) n f i nf ( h ，d ) f = l o l i o o + ( a i p ，n 。) 】+ 6 瑶) 勺 j ，r + 3 5 8 厄r ( 。r ，) ( f + z 。) ( 4 1 c t ) l e s 胙z + 【( 4 p ，f ，l ：) + p 1 0 0 c 。z 7 7 r s f g 。( 日，d ) = 0i = 1 , 2 ，m l 舅= q ，- - u i + 1 1j 口岛d ? 5 f g n ( h 一，) 1 - ，一h s i “。= 0 ( 4 ，1 6 ) j = l i 日。m a x 。h 。n u n j - l ，2 ，m ( 4 1 c ) d 。d ；d 。l d u w i ，j v( 4 1 d ) 4 1 2 管径取整的数学模型 管径取整是在优化管径( 非标准管径) 的情况下进行的，“为定值，其数学模 型为： o b j m i n f ( d ) f = p l i o o + ( a i p ) 】( + 6 ) 一 i ，r + 3 5 8 x r e t ( “，吼) ( 由，+ z c ) ( 4 2 a ) i s j z 月 + 眙p ，f ，n ；) + p 1 0 0 c 。“? j e r ” s f g 。( 日，d ) = 0 i = 1 , 2 ，埘一1 g ，= q ，一”：+ l ls q d ? s g n ( h ，一h s ) 1 - 。一h s l l “= 0 ( 4 2 b ) 日严2 日，i - ) i r m n f 1 ，2 ，m d 口一 d u 。，d ) d v l f ，u ，矿 4 2 遗传算法简介 ( 4 2 c ) r 4 2 d ) 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是模拟自然界生物进化过程的 类自组织、自适应人工智能技术。因为模拟达尔文的自然进化论与孟德尔的遗传 变异理论，所以遗传算法具有坚实的生物学基础。遗传算法的思想由来己久，早 在2 0 世纪5 0 年代，一些生物学家就着手于计算机模拟生物的遗传系统。1 9 6 7 年， 美国芝加哥大学h o l l a n d ，j h 教授在研究适应系统时，进一步涉及进化演算的思 考，并于1 9 6 8 年提出模式理论。1 9 7 5 年，h o l l a n d 教授的专著自然界和人工系 统的适应性( a d a p t a t i o ni n n a t u r ea n d a r t i f i c i a ls y s t e m s ) 问世，全面的介绍了遗 传算法，为遗传算法奠定了基础。此后，遗传算法无论在理论研究，还是在实际 应用方面都有了长足的发展。由于遗传算法采用种群的方式组织寻优，这使得它 可以同时搜索解空间的多个区域，同时优胜劣汰的自然选择和简单的遗传操作使 得遗传算法具有不受其搜索空间的限制条件( 如可微、连续、单峰等) 的约束及 不需要其它辅助信息( 如导数) 的特点，正是这些特点使得遗传算法使用简单、 易于操作且通用性强，这正是遗传算法受到人们青睐的主要原因【1 8 1 。最近十几年， 遗传算法在国内备受重视。 4 2 1 遗传算法的一般结构 遗传算法的常用形式是g o l d b e r g 提出的【1 9 1 。和传统搜索算法不同，遗传算法 从一组随机产生的初始解，称为“种群( p o p u l a t i o n ) ”，开始搜索过程。种群中的 每个个体是问题的一个解，称为“染色体( c h r o m o s o m e ) ”。染色体是一串符号， 比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一 代中用“适值( f i t n e s s ) ”来测量染色体的好坏1 2 “。生成的下一代染色体称为“后 代( o f f s p r i n g ) ”。后代是由前一代染色体通过交叉( c r o s s o v e r ) 或者变异( m u t a t i o n ) 运算形成。新一代形式中，根据适值的大小选择部分后代，淘汰部分后代，从而 保持种群大小是常数。适值高的染色体被选中的概率较高。这样经过若干代之后， 算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。设p f f ) 和c ( t 1 分别表示第t 代的双亲和后代，遗传算法的一般结构可描述如下 b e g i n t o ： 2 0 初始化j d ( f ) ； 评估p ( f ) w h i l e 不满足终止条件d o b e g i n 重组p ( 0 获得c ( f ) ； 评估c ( t ) ； 从p ( f ) 和c ( f ) 中选择尸( 什1 ) ； f 一r + 1 ： e n d ； e n d ； 、 n _ k 是g r e f e n s t e t t e 和b a k e r 描述的改进的算法步骤【2 0 】【2 l 】。通常初始化是随机 产生的。重组包括交叉和变异来获得后代。实际上，遗传算法中有两类运算： ( 1 ) 遗传运算：交叉和变异； ( 2 ) 进化运算：选择。 遗传运算模拟了基因在每一代中创造新后代的繁殖过程，进化运算则是种群 逐代更新的过程。以上描述和h o l l a n d 的原始描述有一些不同，原始描述是选择 双亲来进行重组【2 2 1 。 交叉是最重要的遗传操作，它同时对两个染色体进行操作，组合二者的特性 产生新的后代。交叉的最简单方法是在双亲( 两个父代的个体) 的染色体上随机 的选一个断点，将断点的右段互相交换，从而形成两个新的后代。这种方法对于 二进制表示最为合适。遗传算法在很大的程度上取决于采用的交叉运算的性能。 变异则是一种基本运算，它在染色体上自发的产生随机的变化。一种简单的 变异方法是替换一个或多个基因。在遗传算法中，变异可以提供初始种群中不含 有的基因或找回选择过程中丢失的基因，为种群提供新的内容。 遗传算法在几个基本方面不同于传统优化方法。g o l d b e r g 总结为如下几点 1 9 1 ： ( 1 ) 遗传算法运算的是解集的编码，而不是鹪集本身。 ( 2 ) 遗传算法的搜索始于解的一个种群，而不是单个解。 ( 3 ) 遗传算法只使用报酬信息( 适值函数) ，而不使用导数或其他辅助知识。 ( 4 ) 遗传算法采用的是概率的，而不是确定的状态转移规则。 4 2 2 遗传算法词汇 由于遗传算法起源于自然遗传学和计算机科学，因此遗传算法文献中的术语 是自然与人工系统语言的混合。 在生物学中把表明生物体构成的编码结构称为染色体，表述一个完整的生物 体可能需要一种或多种染色体。一套完整的染色体称为基因型( g e n o t y p e ) ，而生 成的生物体称为表现型( p h e n o t y p c ) 。每个染色体由一些称为基因的个体结构组 成，每个基因表达了生物体的一个特性，基因在染色体结构中的分布，或称为位 置，决定了基因表达的特性，在各个特殊位置上一个基因可能具有几个表达不同 特征的特殊值，基因的这些不同的值称为基因位值( a l l e l e s ) 。 遗传算法的术语和最优化术语的对应关系如表4 1 所示。 表4 1 遗传算法术语的说明 遗传算法说明 染色体( 位串，个体)解【编码) 基因( 位)解的部分 位置基因的分布 基因位值基因的取值 表现型解码后的解 基因型编码表示的解 4 2 3 遗传算法的运行参数 遗传算法中需要选择的运行参数主要有个体编码串长度，、群体大小m 、交 叉概率p 。、变异概率p 。、终止代数丁、代沟g 等。这些参数对遗传算法的运行 性能影响较大，需认真选取。 ( 1 ) 编码串长度，使用二进制编码来表示个体时，编码串长度，的选择与问 题所要求的求解精度有关；使用浮点数编码来表示个体时，编码串长度，与决策 变量的个体肝相等；使用符号编码来表示个体时，编码串长度，由问题的编码方 式来确定；另外，也可使用变长度的编码来表示个体。 ( 2 ) 群体大小m 群体大小m 表示群体中所含个体的数量。当m 取值较小时， 每次迭代需要的时间相对较短，提高了遗传算法的运算速度，但由于群体规模小， 群体包含的模式总数也相对较小，降低了群体的多样性，所以需要较多的迭代代 数才能搜索到较好的解或最优解，有时可能会引起遗传算法的早熟现象；而当m 较大时，算法可同时处理更多的解，因而容易找到全局最优解，但其缺点是增加 了每次迭代所需要的时间，影响算法的搜索时间，使得遗传算法的运行效率降低。 g o l d b e r 9 1 2 3 证明了当染色体是使用二进制编码时，最优群体规模与染色体长度之 问存在着某种关系。李大卫【2 4 1 对可重复自然数编码遗传算法的最优群体规模也作 了研究。因此对群体规模m 存在着权衡问题，一般建议的种群大小取值范围是 2 0 - l o o 。 ( 3 ) 交叉概率只交叉操作是遗传算法中产生新个体的主要方法，所以交叉概 率一般应取较大的值。但若取值过大的话，它又会破坏群体中的优良模式，对进 化运算反而产生不利的影响；若取值过小的话，产生新个体的速度又较慢。一般 建议的取值范围是o4 - 0 9 9 。另外，也可使用自适应的思想来确定交叉概率p ， 如d a v i s 2 5 1 提出，随着遗传算法在线性能的提高，可以增大交叉概率p ，的取