（计算机应用技术专业论文）地下给水管网管线间距计算及优化布局.pdf

论文题目：地下给水管网管线间距计算及优化布局 专监：计算规应用技术 硕士生：栋淑飞( 签名) 垡：鉴： 指导老师：攀军民 ( 签名) 查荛趟 摘要 随着社会的发展，用水量越来越多，这样就要在融有的错综复杂的地下给水管线中 埋入新的管线，怎样埋入才能不破坏已有的管线就愚本谋题要解决的问题。计算新管线 与管网中已有管线( 可能是直管线也可能是曲管线) 的间距，判断其是否会岛已有管线发 生冲突。若不发生j 孛突就将其直接蠼入到营题中；若发缴i 串突裁将其以仓联的弯度埋入 警嚣孛，舍瑗楚播承骓、耗耪最零戴避免再次发生冷突。 本文主要解决以下五个闯鼹： ( 1 ) 使用滤传算法计算直管线岛新管线的间距； ( 2 ) 使用遗传算法计算曲管线均新管线的间距； ( 3 ) 为了避开冲突点，用遗传熬法计算新管线需弯鞠的劣弧的最优弦嬲秘弦； ( 绘翻撼下绘承管秘鹣二续、兰维霆影； ( 5 ) 蕉v c 十+ 建立建下给承餐线优化布局系统。 对于第一个问题，本文提出了一种新的基于排序的遗传算法，而且通谶多个实例验 证了其有效性。对于第二个问题，提出了两种解决方法，一种是d c p m - - f g a 与最速 下降法结合的混合遗传算法；另一种是先将其转化为双目标优化问题，然威使用双目标 遗传算法求嬲，两手孛算法都用实铡遴行了验证。对予第三令氲蘧，提出了一种毅型遗传 逶炎算法，爨浚戆铜耨之楚在予孳l 入了“突交”嚣“邋亲不能结台”豹思憋。对于第图 个问题，使用蘸光数字矿由平台采实现。 关键词：给水管网；优化布局；遗传算法；遗传退火算法；双目标优化 研究类型：墩用研究 本课题获陕西省自然基金项目的资助( 项目号：2 0 0 4 f 3 4 项目名称：城市供水管网流量 优化控制软件系统) ；获西安市自然基金项目的资助( 项目号：g g 0 5 0 2 8 项圈名称：城市 地下管网数字化信息系统) s u b j e c t ：c a l c u l a t i o no fd i s t a n c eo fu n d e r g r o u n dw a t e rn e t w o r kp i p e l i n e a n do 窭i m 匦| e da r r a n g e m e n t s p e c i a l t y ：a p p l i e dt e c h n o l o g yo fc o m p u t e r n a m e ：l i ns h u f e i ( s i g n a t u r e ) 尘f 塑5 姓 i n s t r u c t o r ：l ij u n m i n ( s i g n a t u 旧厶i j 黝螳掣 ， j 矗b s t r 矗e t w i t ht h ed e v e l o p m e n to fs o c i e t y , m o r ea n dm o r ew a t e ri sn e e d e d s oi ti sr e q u i r e dt h a ta n e w p i p e l i n ew i l lb ei n s e r t e di n t ot h eu n d e r g r o u n df o r m e r - i n s e r t e dc o m p l i c a t e dp i p e l i n e s w e n e e dt or e s o l v et h ep r o b l e mw h i c hh o wt od os ot h a tf o r m e r - i n s e r t e dp i p e l i n e si s n t d e s t r u c t i v e d 。c a l c u l a t et h ed i s t a n c eb e t w e e nt h en e wp i p e l i n ea n dt h ef o r m e r - i n s e r t e d p i p e l i n e s ( s t r a i g h tp i p e l i n eo rc u r v ep i p e l i n e ) i nt h en e t w o r k ，a n dj u d g ew h e t h e rt h ec o n f l i c t g e n e r a t e sb e t w e e nt h en e wp i p e l i n ea n dt h eo l dp i p e l i n e s i ft h ec o n f l i c tn o th a p p e n e d ，w e d i r e c t l yi n s e r tt h en e wp i p e l i n ei n t ot h eu n d e r g r o u n dn e t w o r k i ft h ec o n f l i c th a p p e n e d ，w e i n s e r tt h en e w p i p e l i n ew i t ht h er a t i o n a l ( t h ew a t e r - p r e v e n t e ds t r e n g t ha n dt h ee x t r a v a g a n c ei s b o t hm o s ts m a l l ) b e n d e dd e g r e ei n t ot h eu n d e r g r o u n dn e t w o r k 。 t h ef o l l o w i n gf i v eq u e s t i o n si sm a i n l ys o l v e di nt h ep a p e r ： ( 1 ) u s eg e n e t i ca l g o r i t h mt oc a l c u l a t et h ed i s t a n c eo ft h en e wp i p e l i n ea n da l lt h es t r a i g h t p i p e l i n e s ； ( 2 ) u s eg e n e t i ca l g o r i t h mt oc a l c u l a t et h ed i s t a n c eo ft h en e wp i p e l i n ea n da l lt h ec u r v e p i p e l i n e s ； ( 3 ) i no r d e rt oa v o i dt h ec o l l i d e dd o t , u s eg e n e t i ca l g o r i t h mt oc a l c u l a t et h eb e s th e i g h ta n d r a d i uo f i n f e r i o ra r co f t h en e w p i p e l i n e ； ( 4 ) d r a w t h ep l a n ea n d s p a c eg r a p ho f f e e dw a t e rn e t w o r k ； ( 5 ) c o n s t r u c tt h ea r r a n g e m e n t - o p t i m i z a t e ds y s t e mo fu n d e r g r o u n dn e t w o r kw i t hv i s u a l c + r e g a r d i n gt h ef n s tq u e s t i o n ，an e wg e n e t i ca l g o r i t h mb a s e do ns o r ti sp r o p o s e di n t h ep a p e r , a n dt h ee f f e c t i v e n e s si sp r o v e db ys o m ee x a m p l e s t w oa l g o r i t h m sa r ea d v a n c e dt os o l v et h e s e c o n dq u e s t i o n ，o n ei st h eh y b r i d g e n e t i ca l g o r i t h mo f d c p m _ f g a a n dd e s c e n tl o c a ls e a r c h ， t h eo t h e ri st h a tp r o b l e mo fb o t h - o b j e c to p t i m i z a t i o ni st r a n s i t e d b o t ho ft h e mi sv e r y e f f e c t i v e t h ep l a no ft h et h i r s tp r o b l e mi sg e n e t i ca n n e a l i n ga l g o r i t h m ，e s p e c i a l l yt h ei d e ao f g e n e ss u d d e na l t e r a t i o na n dn om a r r i a g eb e t w e e nn e a rr a l a t i o ni se m b o d i e d t h ef o r t h p r o b l e mi ss o l v e db yt h ep l a t f o r mo f l a n g u a n go r e ：m o l m t a i n , k e y w o r d s ：f e e dw a t e rn e t w o r k o p t i m i z a t e da r r a n g e m e n t g e n e t i ca l a g r i t h m g e n e t i ca n n e a l i n ga i o g r i t h m b o t h o b j e c to p t i m i z a t i o n t h e s i s ：a p p l i e dr e s e a r c h 要料技大学 学位论文独创性说明 y92 302 8 声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及 果。尽我所知，除了文中加以标注和致谢的地方外，论文中不包含 其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科技大学 或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位做作者签名摊怖 日期：卅j 、弓f 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间 论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部门或 机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位论文研究课 鸯茅w - 一j 镳。 。e 1 d6 年j 、月矽1 日 。黪警：| 1，；： ， - ， 名 。 签 学 师 大 教 技 导3 科 指 安西为 。 位 明 单 声 者 本 作 用 明 适 ： 注 后 名 律 密 签 一 解 者 章 待 作 文 文 文 的 论 论 写 密 位 撰 保 学 再题 毫 1一隧隧f 1 绪论 1 绪论 1 1 给水管网盼研究现状 随着城市的发展，用水人口的不断增加和人民生活水平的日益提高，城市用水量急 剧增长，给水管灏供水能力逐渐不熊适应用水量增长舶需要，这就需要不断扩大给水管 嚣豹袈模。予怒，改造褒增热管线嚣重葶l 起静管嬲破螺簸怒我翻嚣稳鳇急鬟勰决豹难题。 疆着最饶弦壤论静发震霹给本謦瓣拳力势辑 支零熬避步，绘永管圈我弦设诗褥蜀了 广泛重视。但过去的研究大多集中谯新建管网的研究上，丽目前所面临的课题主要是如 何对旧城进行改造，即扩建管网的优化设计问题，这就鬻考虑原有部分与新建部分的协调 工作，以充分利用原有设备，在满足供水要求的前提下，达到最经济的目标。 l 。2 绘永誊弱麴聚究综述 随着用户对承质、水量要求翰键嵩，供求觏模静不断扩大，以及计算祝技术的发展， 人们己逐渐认识到给水管网水力计算的重要性。给水龄嘲水力计算是一个十分广泛的范 畴，它包括管网平差、优化设计计算、优化调度、现状分析等。 l 。2 1 给水管跨毵驰设计 城市绘水管溺优纯设计或称繁瓣技米经济诗雾主豢考虑保证筷承掰嚣懿窳量察隶 压、水质安全、可靠性和经济性，也就是以反映经济性的数学表达式作为瞄标函数，而 将其他因素列为约束条件，建立优化数学模型，求出墩优的管径【“。 以管径为球解变量的设计模型冉勺目标函数包括管网造价年折算值n ，遴水泵站年平 均动力费矮救芹奠水厂毅建年辑算筑鹤。 蠢2 1 0 0 + ( a p , i , n o ) 国书垂磁琢 ( 1 1 ) 式( 1 1 ) 中，p 为年折算与大修赞，以管网造价的计； l 为管段的长度；d 为管段崴径； a , b ，c 为肇位长度管网造价公式中的系数，随管线材料和施工条件的不同黼异； 彭玲，n 为等颧分嚣资金匿牧系数，其篷等予署拿糟 i 兔年穰霉，狮羹矮嚣诗 算期； f 2 ；3 5 8 x ( 互王) ( 7 ) ( + z 。) ( 1 2 ) 西餐科技大学硕士学位论炙 式n 2 ) e pr i 为i 期供水能量变化系数，i 1 ，2 ，3 分别表示高峰期、姬常期和低峰 期； e l 戈镶惫i 麓点竣元厅琵夺辩) ；t i 受貘电i 麓豢瘩薅淫； u # ，r 。分澍舞供电i 期第j 个浆辩送水量和泵赣效率； h i i k 为i 供电期第j 个泵站曩瞥网控制点线路上k 管段的水头损失； z c 为管网控制点要求的自由水压值：z k 为净水厂至管网控制点的某祭线路的管段 集；s 为所有送水泵站个数集。 f 3 = ( a p , i ，n o ) + p 1 0 0 c n 越罗 1 3 ) 蔬。 式( 1 3 ) 中，n o 为水厂的计算期；p ，为水厂昭折旧筠大修理费； c n 为新建单位水量净水厂( 邀水泵站) 所需基建费用： r n 为新建水厂集：u j 为第j 个净水厂送水泵站的最大供水量； m r 为冷本厂送水泵站基建经济效应系数； 蔽警经洚墩辫交量弱设诗模鳌戆绞索条律奏戳下纛令： ( 1 ) 节点流量方程。 节点的流凝方程为：节点的最高日最高时的需水凝- 节点的供水流量+ 岛节点相连的 管线的水头损失= 0 ，即g f d ，u ， d 一0 ，也就是 t 1 馥一n 。+ s 口l # d ，s i g n ( h ，一玛) | h ，一h jp = o ( 1 。4 ) i = t 式( 1 4 ) e eq ；力设诗年限内第i 个节点在最高醋簸麓时缒需承量； i i 为与节点i 相邻的节点编号的集合；s 。i 为管道的摩阻系数； u i 为在节点i 的供水流量；n ，b 为常数； 符号s i g n 意义如下： r1 a 0 l s i g n ( a ) 2 i - 1 a i o ( 弘1 ，2 ，n ) 式1 5 ) 中，f l ，f 2 ，f 3 分别淡示节点水压、节点流堂和水源供水量影酮及量纲影响 系鼗； h i ，h 。1 分剐表示检测节患的计算水压和实测术聪，单位蠢m ； q i ，q o j 分别表示监测管段的计算流量和实测流鬣，单位为m 3 s ： f k ，f o k 分别表示各水厂的计算流量和实测流量，单位为m 3 s ； q1 ，q2 ，q3 分别表示水聪般测点、管段监测点和水源点集合； 西赛补技大学硕士学位论文 q 表示管段流量转置矩阵，q = ( q l ，q 2 ，q n ) 1 ，m 3 s ； q 表示节点流量转置矩阵，q = ( q i ，q 2 ，q n ) 1 ，m 3 s ； 壬壬表示管袋零头损失转嚣矩簿，h = ( h l ，蠡0 ，搬； q 吁表示餐瓣总供汞量，m 3 s ； a ，l 分别袭示连续性方程和熊凝方程系数矩阵： c 表示h a z e n - - w i l l i a m s 公式系数；k 表示节点流爨变化系数； k i 。表示备节点的最低要求水聪； n 表示节感觳，p 表示管段数，s 袋苯拳源数； t 表示s c a d a 盗灏无法茬裁豹棱获管段数。 1 2 3 给水管网改扩建优化设计 给水管网优化设计一般是针对新建的地下管网，假随着人口的增长和人民生活水平 豹提高，需要对已有绘水管网进舒爨耨或扩建，这就燕下嚣要讲述的给永镣阏改扩建优 往设诗。袭扩建魏往莰诗嚣要解决涎令重要懿运莲：爨确定凌奏管遘审疆整不合瑾及 如何改造；二怒扩建管道如何布弱及管径的确定。 改扩建优化以满足用户对水嫩水压的需求、管网的各项运行参数符合舰范要求为约 束条件，确定需要改造的管段及管径、新增管道的管径，以使供水成本趋于鼹小【3 】。 m m f ( h , d i i , x 萨专+ 意。丢 十五骘冯弓+ 0 9 8 1 ( 1 + 意毳( q l ) ” + f 1 + 罴) f g i e r i ( g g 。) ”+ c n 。z o t ( 1 6 ) 约束条件： g i ( h ，d ，x ，u , h p ) = 0 ； g 。= q ；+ o 5 4 9 - c g 骘”2 嚣辩2l 嚣，一抒，r ”s g n ( h ，一豆，) ；( 节熹滚爨方程) t = l “，= q ；( 水源水量约束) ： f e s，。i h i 一 h i m “；( 最小允许水聪靛约束) l l i “u i 越i “8 ；泵兹攥零嫠鳕素 d i “辍d i m “：( 管径约寐) 式( 1 6 ) 中：x 只能取0 ，1 ，取0 表示节点i 和j 之间管道不改造，取l 表示节点i 和i 之间管道潋造； d 一管径；l 一管段长度( m ) ； 4 t 绪论 t t ，t ”一管线、泵站、水厂的投资偿还期： p , p7 一管线、泵站、水厂的折暇与大修理费( ) ； v 一哥毒爨改造秘扩建管线黩嚣豹嶷会； a , b ，岱一餐麟造价公式中麓系数藕指数，随管线糖精耩施工条薛静不瓣瑟异； r i i 时段供水能量变化系数，i = 1 ，2 ，3 分别表示供电高峰期、正常期和低峰期； e i 一供电i 时段电价( 元h ) ； t i 一供电i 时段供水时间( h ) ； u i j ，珏i ；一分剃舞供电i 时段第j 送水量( 嗡窝泵站麴效率； h i 1 k 一供漱i 对段第j 送承泵辩凳管网控裁熹警线上k 管段懿承头援必冬蟛； s 一所有絮站个数； e 一每千瓦容量加压泵站造价( 元k w ) ： r7 一泵站机组储备系数；r i7 泵站与输电线效率( 蛳； m p 一泵站簇建造价的经济效墩系数( o m p 1 ) ； c ，曝一分鞠为改建、扩建攀继承量净采厂( 送承裂瀚掰霉基建费瘸( 元弘； r l ，r 2 一分别为改建和扩建冷水厂集； u o 广第i 净水厂送水泵站原有最大供水量( 讹) ； m r 一净水厂送水泵站基建经济效应系数( 0 r i l r 1 ) 。 1 2 4 给水管网饯化调度 城毒供永俊纯调度就是在管网糍誊邑定，逶过对瓣承量静预测，礁是器窳源翡供求 量和供水压力。管网模型即用一祭剿的数学方程来描述管鼯水压、流量和水头损失等之 间的关系，以期反映当前供水网络的实际运行工况。瞬前国内外供水系统网络模型归纳 为：微观模型和宏观模型。管网优化调度可分为管网宏观模型、城市日用水量预测和优 化调度模型三郝分。弱水量预测是优亿调度的前期工铭，实际调度控制中象要需进行日 瘸隶量魏孩溺。飘空蠢上，霹将瓣瘩量鬏测分隽：憨承鬟琰灞霸节熹爱承黧鬏溺。蘸者 是指预测系统内每日或每时用户用水总量，它主要是为宏观模型的优仡调发服务；后者 是预测分配到备用户节点的用水缀，需要了解系统内备用户的特点及以往的观测数据 库，并据此建立预测模型，它主瓣是为微观模型服务的。优化调度模型用以确定优化运 行的决策变爨德，其主要耳标悬僳诚管网适当水压( 用户有水用) 、水质的前提下，降低 囊承筷隶戏零，大疆菠疆毫生产效豢。 1 2 5 给水管网平差计算 管网平麓般已知输入管网的总流量及各管段长度、管径、各节点流爨，求解各管 段设计流量【4 】。管网平差求解的常用方法有3 种：解环方程，解管段方程，解节点方程。 蘅安科技大学硕士学位论文 不管是哪种方法都必须满足两个水力条件：( 1 ) 节点流爨必须平衡，即流入备节点的流 量等于流出各节点的流量；( 2 ) 闭合环内水头损失必须警衡，即环内各管段水头损失之 霹等予零。 其物理穰溅w 以描述为：求滋一维管段流量值，使箕满足节点流量平衡秘 i l 合环内 水头损失平衡，则相应的数学模裂为： 目标函数：f ( q 1 2 ，q t 3 ，k q i j 卜m i n e l q j + q u l 】( 取离开节点的流量为正，流向节点的 流量为负。) 约泶条件：i s k i = 0 ( 墩水流顺时针方向的管段水头损失为正，逆时针方向 靛是受。) 式孛q 必节点i 流囊节杰j 豹管段流量；q i 强带点i 豹节点流量：a h k 燕翅环 k 豹零头损失裁。 上述模裂怒袋优化模型，不能使用手工算法，可以使用遗传算法来求解。其实，对 于给水管网的平差计算，传统的警工算法是哈代一克罗斯法解环方程l ”。解环方程是管 网平差常用的3 种方法中最为简浩快速的一种，这是因为在一个管网中，瞥段数少于节 点数，两节点数少予环数( 一个琢蠹多个节点，节点嬲形敲管段) 。 解环方程麓核心是求解环方稷岛( 岛+ a q ；) 4 = 蛤 其中第i 环的校正流量为吼。叶盘】= 鹾】。 浆舞校正滚爨邋行迭我诗算，壹到趣会差滚是精度要袋势壹。 为诧要输入良下基本信怠： ( 1 ) 平差所用的控制精度、管朗的管段数、环数、管道的粗糙系数。 ( 2 ) 每个箭段的6 个基本数据，即该管段的编号、锗长、管径、流量( 初始分配流量) 、 管段所属本环的环号、管段所属邻环的环号。 输出数摄瓴据：瘴阻、拳头按失、管段流量。 1 3 本论文的主要内容和目标 在1 2 节中说明了对于地下给水管网大多数人研究的是其水力计算问题，这个问题 包括给水管网优化设计、现状分析、改扩建优化设计、优化调度等等。本论文的主要目 标不是研究绘水管网的水力计算阏题，两是研究在复杂熬地下给水管网中蠼入新管线时 弱洚突润题。零文懿主要王终是後麓遗传算法诗算镶综笈杂戆建下绘拳篱鬻孛戆瑟鸯已 有管线和要堙入的新管线的距离。然后通过计算结果涮断新管线如何埋入，是按原定位 置以直管的形式埋入还是为了避免冲突以弯管的形式埂入。若要以弯管的形式埋入，就 使用遗传算法求出弯管的最佳弯魔。使用蓝光数字矿山平台来三维模拟瞥线，使得结果 形象地显示给大家。最后根据这熄算法使用v c + + 综龠成一个给水管网优化布局系统。 6 2 遗传算法的基础知识 2 遗传算法的基础知识 既然本文使用遗传算法来求解问题，那么这一章先简单介绍遗传算法。 遗传算法是由美国m i c h i g a n 大学h o l l a n d 教授根据生物进化理论和遗传变异理论 提出的一种基于种群搜索的优化算法。其思想是随机产生初始种群，通过选择、交叉和 变异等遗传算子的共同作用使种群不断进化，最终得到最优解。遗传算法以其易于操作 和独立于领域知识的特性得到广泛的应用。 2 1 遗传算法的基本要素 遗传算法的基本思想是从代表问题可能潜在解集的一个种群开始，根据问题的特 点，制定适当的适应度函数，对每一代种群，根据问题域中个体的适应度大小挑选个体， 利用遗传算子( g e n e t i c o p e r a t o r s ) 进行杂交和变异，从而产生出代表新的解集的下一代种 群。 在遗传算法的设计中包含几项重要的步骤：( 1 ) 编码( c o d i n g ) ( 2 ) 产生初始种群 ( i n i t i a l p o p u l a t i o n ) 及决定种群的规模( p o p u l a t i o ns i z e ) ：( 3 ) 定义适应度函数( f i t n e s s f u n t i o n ) ；( 4 ) 设计遗传算子( g e n e t i co p e r a t o r s ) ，包含选择算子、交叉算子和变异算子； ( 5 ) 设计各控制参数的大小，如个体编码长度、交叉率( c r o s s o v e rr a t e ) 、变异率( m u t a t i o n r a t e ) ，以及终止条件( t e r m i n a t i o nc o n d i t i o n s ) 雠l j 断标准。 2 1 1 编码方法 在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗 传算法所能处理的搜索空间的转换方法称为编码。 通常采用的编码方法有k 进制编码方案、浮点数编码方案和符号编码方案，而每一 种编码方案又有不同的处理方法。采用浮点数编码的优点是：适合表示范围较大的数； 适合精度要求较高的算法；简化计算，提高效率；便于遗传算法与经典优化算法的混合 使用。因而非常适合于连续变量数值优化问题。 二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二 进制符号0 和1 所组成的二值符号集 0 ，1 ) ，它所构成的个体基因型是一个二进制编码 符号串。 对于只含上、下限约束的最优化问题，通常使用二进制编码。如下列一元函数求最 大值的优化问题：f ( x ) - 一x s i n ( 1 0n x ) + 2 0 ，x 【一1 , 2 】。其编码和解码过程如下：采用二 进制编码形式，用一个 0 ，1 ) 二进制串代表一个变量。串长取决于求解的精度，如果设 定求解精度到6 位小数，由于区间长度为2 一( 一1 ) = 3 ，必须将闭区间【一1 ，2 分为3 + 1 0 6 等 西安科技大学硕士学位论文 份，因为 2 0 9 7 1 5 2 = 2 2 l 3 1 0 6 _ _ 2 2 2 = 4 1 9 4 3 0 4 所以编码的二进制串长至少需要2 2 位。将一个二进制串( b 2 t b 2 0 b 0 ) 转化为区间【一1 ，2 】 内对应的实数值很简单，只需要采取以下两步：将二进制串( b 2 l b 2 0 b 0 ) 代表的二进 2 1 制数化为1 0 进制数： 2 l b 2 0 b o ) 2 = ( z b , 2 i ) 。= x x 对应的区间 - 1 ，2 】内的实数： 忙0 x = 一1 0 + x 掣 。 二 进带。串( 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ) 与 2 一一l ( 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ) 分别表示区间的两个端点1 和2 。 浮点数编码是由实数串组成。染色体的长度与解向量是致的，一个基因对应一个 分量。如某个问题有7 个解向量，则采用实数编码的一个染色体就是7 个实数串。 符号编码。采用g a 求解t s p 问题等一系列组合优化问题时 9 1 ，用排列法进行编码 似乎更为自然、合理。如有1 0 个城市的t s p 问题，城市序号为f l ，2 ，l o ，则 编码位串：6543219871 0 ，表示的访问城市路线为：6 5 4 3 2 1 9 8 7 1 0 ，6 。 2 1 2 初始种群 初始种群是迭代的起点，其个体均为随机产生，群体规模的设定既要保持种群中个 体的多样性，又要考虑到计算量问题。 实数编码的初始种群产生过程如下： f o r ( i = 0 ；i 种群规模；i + + ) 假设问题有两个解向量x l 和x 2 ，其中x l 【1 1 ，u 1 ，x 2 e 【1 2 ，u 2 】 p f = r a n d 0 3 2 7 6 7 o ； 种群名卧x l = l l + ( u l 一1 1 ) + p f ； p f = r a n d o 3 2 7 6 7 o ： 种群名【i 】x 2 = 1 2 + ( u 2 1 2 ) + p f ， 二进制编码的初始种群产生如下： f o r ( i = o ；i 种群规模；i + + ) f o r f j = 0 ；j o f i t f x 3 = _ ( 2 1 ) t o i f f c ，p c 。i 。o 式( 2 1 ) 中，c 。i 。为一个适当地相对较小的数。 对最小值问题，作下述转换： ，c 。= - f i x ) i f f ) c m “ f i t 一 ( 2 2 ) t o i f f ( ) ( ) o 式( 2 2 ) e e ，c 。为一个适当地相对较大的数。 遗传算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过反复迭 代过程，不断地寻求出适应度较大的个体，最终可得到问题的最优解或近似最优解。 2 1 4 遗传操作 遗传操作是模拟生物基因遗传的操作，在遗传算法中，通过编码组成初始群体后， 遗传操作的任务就是对群体的个体，按照它们环境适应程度施加一定操作，从而实现优 胜劣汰的进化过程，从优化搜索而言，遗传操作可使问题的解一代又一代地优化，从而 逼近最优解。 遗传操作包含三个基本遗传算子：选择、交叉和变异。 ( 1 ) 选择 选择的目的是为了从当前群体中选择优良的个体，使它们有机会作为父代为下一代 繁殖子孙。判断个体优良与否的准则就是各自的适应度值。 常用的选择方法有以下几种： 轮盘赌选择法 9 西盛科技太学硕士学位论文 这是最简单的一种选择方法，需计算出每个个体的选择概率和累积概率，然后进行 多轮选择，每一轮选择产生一个【o ，l 】的均匀随机数，种群中第一个累积概率大于此随 规数豹令落投逸中。 随枫遮历抽样法 随机遍历抽样法提供了零偏熬和最小个体扩展。设定n p o i n t e r 为需骚选择的个体数 目，等距离选择个体，选择指针的距离为1 n p o i n t e r ，第一个指针的位置由【0 ，l n p o i n t e r 区间的均匀髓帆数决定。 局部选撵法 在局部逸释法孛，每个卞薅懿予一令约束丽境审，舔为筠部邻集( 悉箕德选择方法孛 视整个种群为个体之邻集) ，个体仅与其邻近个体产嫩交互，该邻集的定义由种群的分 布结构给出，邻集可被当作潜在的交配伙伴。首先均匀随机地选择一半交配种群，选择 方法可以是髓机遍历方法也可以怒截断选择方法，然后对每个被选个体定义其局部邻 集，在邻集内部选择交配饮伴。 截瑟选择法 与前面几种自然方式的选择方法比较，截断遥搽法楚一释人工选择方法。它适合于 大种群，在截断选择法中，个体按适应度排序。只有艘优秀的个体能够被选作父个体， 截断选择的参数叫做截断闽值t r u n c 。它定义为被谯做父个体的百分比，取值范围为 5 0 。l o 。农该阚值之下的个体不能产生子个体。 镶稼餐选择法 在锦标赛选择法中，随穰魏瓢晕牵群孛努e 选一定数瓣个体，然后将簸辩静个体遥骰父 个体。这个过程重复进行完成个体的选择。锦标赛谯撵的参数为竞赛规模t o u r ，其取值 范围为【2 ，n 】。 上述几种选择方法均以适应度为基础进行选择，遮就可能在进化过稔中导致种群早 熟或陷入届潞收敛，对此闳题可以漾耀适应度函数只发变换法来解决，述阿以采用以下 熬两耱提袁潦褥算法性姥酶遥耩方法：在迭代遐稚牵弼部分饶囊薪令髂皋雯巍秘群 中部分父个体来作为下一代的种群。在形成新一代种群时，使其中的种群均不重复。 ( 2 ) 交叉 交叉算子是遗传算法的主骤搜索算子，可从交叉辫子入手来提高算法的搜索能力。 交叉操份一般分为以下几个步骤： 麸交辩漶孛夔辍取密要交鬻戆一黠令薅： 根攥佼串长度l 。对要交粼的一对个体，随机选敷【l ，l 1 】中一个或多个的整数 k 做为交叉位置： 根据交叉概率p c ( 0 m ( 蛐等 1 只等- d ( 毗】 推论2 1 在s g a 中，低阶、短定义距且适应度高于种群平均适应度的模式在群体 中数目的期望值以指数级递增。 2 3 2 内合并行性定理 定理2 2 ( 内含并行性定理) 设e 为一小正数，l s ( 1 1 ) + 1 ，n = 2 t , ”，则s g a 一次处 理的存活概率不小于1 e 且定义长度不大于l s 的模式数为o ( n 3 ) 。 由此可见，s g a 表面上仅对n 个个体作处理，但实际上并行处理了大约o ( n 3 ) 个模 式，并且无额外的存储。 2 3 3 积木块假设 定义2 3 具有低阶、短定义距及高适应度的模式称为积木块( b u i l d i n gb l o c k ) 。 假设2 1 ( 积木块假设，b u i l d i n gb l o c kh y p o t h e s i s ) 低阶、短定义距及高平均适应度的 模式在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终 接近全局最优解。 满足这个假设的条件包括： ( 1 ) 表现型相似的个体，其基因型类似； ( 2 ) 遗传算子问相关性低。 积木块假设指出遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子的作 用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。目前已有大量 的实践证据支持这一假设。 2 4 遗传算法的特点和优点 遗传算法是种利用随机化技术来指导对一个被编码的参数空间高效搜索的方法。 遗传算法具有十分顽强的鲁莽性，与传统的搜索方法不同，它采用了许多独特的方法和 技术，归纳起来主要有以下几个方面： ( 1 ) 遗传算法处理对象不是参数本身，而是对参数进行编码的个体，此编码操作，使 得遗传算法对离散性变量的优化效果特别的好。如，对地下管网管径的优化。 ( 2 ) 遗传算法直接以目标函数作为搜索目标。遗传算法无需目标函数的导数值等其他 信息。这对很多目标函数是无法或很难求导数的函数。或导数不存在的函数优化问题， 以及组合优化问题等，应用遗传算法时就显得比较方便，它避开了函数求导这个障碍。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，具有蕴含并行性。传统的优化算法往 1 4 2 遗传算法的基础知识 往是从解空间中的一个初始点开始最优解的迭代搜索过程。而遗传算法从由很多个体所 组成的一个初始群体开始最优解的搜索过程，所以实际上相当于搜索了更多的点。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的搜索 方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往 往使得搜索永远达不到最优点。而遗传算法属于一种自适应概率搜索技术，其选择、杂 交、变异等运算都是以一种概率的方式来进行，增加了其搜索过程的灵活性。实践和理 论已证明了在一定的条件下遗传算法总是以概率1 收敛于问题的最优解。 2 5 遗传算法的应用领域 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领 域，对问题的种类有很强的鲁莽性，所以广泛应用于很多学科。下面是遗传算法的一些 主要应用领域1 1 7 , z 8 l o ( 1 】函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评 价的常用算例。很多人构造了各种各样的复杂形式的测试函数，来评价遗传算法的性能。 而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，遗传 算法却可以方便地得到较好的结果。 组合优化。实践证明，遗传算法对于组合优化中的n p 完全问题非常有效。例 如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到 成功的应用。 f 3 ) 生产调度问题。生产调度问题在许多情况下所建立起来的数学模型难以精确求 解，即使经过一些简化之后可以进行求解，也会简化太多而使得求解结果与实际相差甚 远。因此，目前在现实生产中也主要靠一些经验进行调度。遗传算法已成为解决复杂调 度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配 等方面遗传算法都得到了有效的应用。 ( 4 ) 自动控制。在自动控制领域中许多与优化相关的问题需要求解，遗传算法的应 用日益增加，并显示了良好的效果。例如用遗传算法进行航空控制系统的优化、基于遗 传算法的模糊控制器优化设计、基于遗传算法的参数辨别、利用遗传算法进行人工神经 网络的结果优化设计和权值学习，都显示出了遗传算法在这些领域中应用的可能性。 ( 5 ) 机器人智能控制。机器人是一类复杂的难以精确建模的人工系统，而遗传算法 的起源就来自于对人工自适应系统的研究，所以机器人智能控制理所当然地成为遗传算 法的一个重要应用领域。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨 迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应 用。 ( 6 ) 图像处理和模式识别。图像处理和模式识别是计算机视觉中的一个重要研究领 西安科技大学硕士学住论文 域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免的会产生一些误差， 这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实 用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前在图像恢 复、图像边缘特征提取、几何形状识别等方面得到了应用。 f 7 ) 人工生命。人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特 有行为的人造系统。自组织能力和自学习能力是人工生命的两大特征。人工生命与遗传 算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。 虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模 型等方面显示了初步的应用能力。可以预见，遗传算法在人工生命及复杂自适应系统的 模拟与设计、复杂系统突现性理论研究中，将得到更为深入的发展。 2 6 遗传算法在给水管网中的应用 笔者通过阅读大量的文献发现，一般作者都是使用遗传算法对管径和管网布置方案 进行优化。下面以管径优化问题为例简单说明遗传算法的应用。 编码和产生初始种群。由于管径优化问题的求解变量一般为管径，因此必须对每一 个优化过程中可能出现的标准管径分配一个二进制字符串。城市给水主干管管径一般为 0 3 m ，0 4 m ，l m 这八种规格的管径，因此可根据这八种管径的编号进行二进制 编码( 0 3 m 的管径规格对应的编码可为0 0 0 ，o 4 m 的管径规格对应的编码可为0 0 1 ，依 次类推，l m 对应1 1 1 ) 。管径编码后，给水管网的布置方案就可以表示为按照管段编号 顺序排列的二进制字符串。优化算法中个体的长度取决于给水管网的管段数，假如管网 的管段数为1 3 ，则每个个体的长度应为1 3 3 = 3 9 ，调用3 9 次随机产生二进制数的算子 就可以产生一个个体。 定义适应度函数。适应度函数f 必须反映管网每年的建造和维护费用及年运行费用 大小，同时应该做到费用越低则方案的适应值越大，这样才能达到管网优化的目的，所 以将适应值取为与费用评价函数w 的倒数成正比，即f = - l w 。 选择操作。使用的轮盘赌选择法，适应度值大的位串占用的比例大，在每次转动轮 盘时，它被选择的几率就比较大。这样位串的适应度值越大，在其下一代中产生的后代 就越多，随着种群的进化，其总体性能得到不断的优化。 交叉和变异操作。由于是二进制编码，且每个个体的长度是3 9 ，比较长，所以使用 两点交叉：对于变异操作，可以使用均匀变异。 循环迭代。从初始种群开始，选择优良个体进行交叉和变异操作，得到下一代种群， 依此循环迭代，直到得到最优管径组合。 3 使用遗传算法求管线的闻距 3 使用遗传算法求管线的间距 通过查阅大量有关给水管网的设计和遗传算法的使用的文献可知，早在上世纪7 0 年代国内就有人使用遗传算法解决给水管网问题。但他们解决的大都是给水管网水力计 算问题，很少有人解决给水管网管线的冲突问题。本文就解决冲突问题，即判断在错综 复杂的地下管线中再埋入一条新管线时新管线与已有管线是否发生冲突。这就需要计算 新管线与所有已有管线的位置关系，即间隔。 3 1 直管线与直管线间的距离 为了更好的理解问题，我们先建立该问题的数学模型。所谓模型，就是为了理解事 物而对事物作出的一种抽象，是对事物的一种无歧义的符号描述。 3 1 1 直管线与直管线间距的数学模型 从微观角度求两个直管线的距离，将一直管线分为无穷个小段，每个小段可近似为 一个点，求这无穷个点到另一直管线的距离的最小值，即为一直管线到另一直管线的距 离。于是直管线- 二( x 3 ，y 3 ，z 3 卜( x 4 , y 4 ，z 4 ) 到直管线一( x l ，y l ，z 1 ) - - - ( x 2 ，y 2 ，z 2 ) 的距离的数学模 型建立如下： 厂i 彳 m i n ，( 训，z ) ：芈垒丝芸竺亍 ( 3 1 ) q c x 2 一x 1 ) 2 + ( y 2 _ y 1 ) 2 + ( z 2 一z 1 ) 2 其中：x x = ( y - y 1 ) + ( z 2 一z 1 ) 一( z - z 1 ) 4 ( y 2 - y 1 ) y y = ( x x 1 ) + ( z 2 一z 1 ) 一( z z 1 ) + ( x 2 - x 1 ) z z = ( x - x 1 ) + 6 2 一y 1 ) 一( y - y 1 ) + ( x 2 - x l 、 约束条件： x x 3 ，x 4 ，y e y 3 ，y 4 】，z e z 3 ，z 4 】 需要说明的是，上述模型只能