（轮机工程专业论文）基于协同进化的船舶分支管路空间布局优化.pdf

大连理工大学硕士学位论文 摘要 管路设计是船舶设计中重要的设计步骤之一，在总体设计中占有很大的比重。管路 设计的好坏直接关系到一条船的质量性能和经济成本，如何缩短管系设计时间，提高管r 系设计质量，对于缩短整个造船周期，提高经济效盏，有着不可估量的意义。但是，由 于管路布局问题的困难性和船舶本身的复杂性，使得管路布局设计的自动化和优化的解 决既具有理论上的开拓性和艰难性，又具有工程实践上的复杂性。 管路三维布局优化问题由简单到复杂分别为单管路布局，多管路布局和分支管路布 局。分支管路普遍存在，但布局十分复杂，它是一对多的布局问题，即管路有一个起点， 多个终点。分支管路系统包括主管路、分支管路和嵌套分支管路。分支管路的路径寻优， 属于n - p - h a r d 问题，近年来，国内外有一些学者对其进行了研究探讨。他们虽然采用了 不同的优化方法，但都必须先选择分支管路的敷设顺序，再确定分支点，然后以分支点 为起点和其它终点相连寻找路径。由于分支管路敷设顺序和分支点位置的不确定性，使 得以上方法在空间较大，障碍物较多，分支较多且包含嵌套分支时，需要很大存储空间， 时间效率低，甚至会引起组合爆炸。协同进化算法是在传统进化算法的基础上引入生态 系统的概念，将待求解的问题映射为相互作用的各物种组成的生态系统，以生态系统的 进化来达到问题求解的目的。本文运用协同进化的思想，提出一种对分支管路布局进行 优化的新方法，打破了先前分支管路布局优化研究中必须首先确定管路敷设顺序和分支 点位置的一贯做法。该方法将分支管路系统分解为多个单独的管路，每个单独的管路代 表一个种群，种群间相互影响适应度的评价以使分支管路系统布局达到最优。另外，本 文还分别讨论了比较先进的单管路布局优化方法遗传算法和蚁群算法，并将其嵌入 到基于协同进化的分支管路布局优化方法中来，通过仿真实验验证，本文的思想和方法 不会受某一种单管路布局优化方法的限制，可以广泛应用。 关键词：船舶设计；分支管路系统；布局优化；协同进化 基于协同进化的船舶分支管路空间布局优化 c o e v o l u t i o n a r yo p t i m i z a t i o na l g o r i t h mf o rs h i p b r a n c hp i p er o u t i n g a b s t r a c t t h em a i np u r p o s eo fs h i pp i p er o u t i n gd e s i g ni st of i n dar a p i da n de f f e c t i v em e t h o df o r s o l v i n gp i p er o u t i n go p t i m i z a t i o na u t o m a t i c a l l y 髓er e s e a r c ho nt h r e ed i m e n s i o n a lp i p e r o u t i n go p t i m i z a t i o nh a si m p o r t a n ts i g n i f i c a n c ef o rr e d u c i n gt h ed e s i g n e r sb u r d e n , i m p r o v i n g t h ed e s i g ne f f i c i e n c ya n dq u a l i t ya n dr e d u c i n gt h es h i p b u i l d i n gc o s t a tp r e s e n t ，t h es h i pp i p e r o u t i n gd e s i g nm a i n l y r e l i e so nh u m a ne x p e r t sa n dt h e i rr e l a t e de x p e r i e n c ei np r a c t i c eb e c a u s e t h en u m b e ro fs h i pp i p ei sv e r yl a r g e ，t h ec o n s t r a i n ti sm i s c e l l a n e o u sa n dt h el a y o u ts p a c ei s l a r g e t h e r ei sas t r i k i n gc o n t r a c tb e t w e e nt h er e s e a r c ho ns h i pp i p er o u t i n gd e s i g na n dt h e l e v e lo fs h i pc a d s u c hs i t u a t i o nb e c o m e sab o t t l e n e c ki nt h ep r o c e s so fs h i pd e s i g na n di t r e s t r i c t st oi m p r o v et h es h i pd e s i g nv e l o c i t ya n dq u a l i t y t h es o l v i n go ft h ea u t o m a t i ca n d o p t i m i z a t i o no f s h i pp i p er o u t i n gd e s i g nn o to n yh a s t h e o r e t i c a lp i o n e e r i n ga n dd i f f i c u l t y , b u t a l s oh a sc o m p l e x i t yi nt h ee n g i n e e r i n gp r a c t i c ef o rt h es a k eo ft h ed i f f i c u l t yo fp i p er o u t i n g a n dt h ec o m p l e x i t yo f s h i pd e s i g n t h et h r e e - d i m e n s i o n a lp i p er o u t i n go p t i m i z a t i o np r o b l e mc a nb ed i v i d e di n t os i n g l ep i p e r o u t i n g ，m u l t i p l ep i p em u t i n ga n db r a n c hp i p er o u t i n g t h eb r a n c h e dp i p ei su b i q u i t y , a n di ti s ao n e t o - m a n yp r o b l e m ，n a m e l y , i th a so n es t a r t i n gp o i ma n dm a n ye n dp o i n t s ，s oi t sr o u t i n g i sv e r yc o m p l e x t h eb r a n c hp i p es y s t e mi n c l u d e sm a i np i p e ，b r a n c hp i p ea n dn e s t e db r a n c h p i p e t h eo p t i m u mp a t hs e a r c ho f t h eb r a n c hp i p eb e l o n g st on ph a r dp r o b l e m s o m es c h o l a r s a th o m ea n da b r o a ds t u d i e da n dd i s c u s s e dt h i sp r o b l e mi nr e c 冶n ty e a r s a l t h o u g ht h e yu s e d d i f f e r e n to p t i m i z a t i o nm e t h o d s ，t h e ym u s tc h o o s et h er o u t i n gs e q u e n c eo fb r a n c hp i p ef i r s t l y a n dt h e nd e t e r m i n et h eb r a n c hp o i n t ，f i n a l l yt h eb r a n c hp o i n ta ss t a r t i n gp o i n tw a sj o i n e db y o t h e re n dp o i n t st of i n dr o u t e b e c a u s eo f t h eu n c e r t a i n t yo f t h eb r a n c hp i p er o u t i n gs e q u e n c e a n dt h eb r a n c hp o i n t sp o s i t i o n , a l la b o v em e t h o d sh a v em a n yp r o b l e m s ，s u c ha sl a r g es p a c e ， m a n yo b s t a c l e s m a n yb r a n c h e sa n dw h e ni ti n d u d e sn e s t e db r a n c h e si tn e e d sv e r yl a r g e s t o r a g es p a c e , w h i c hl e a d s t ol o wt i m ee f f i c i e n c ya n de v e nc o m b i n a t i o ne x p l o s i o n c o e v o l u t i o n a r ya l g o r i t h mi st oi n t r o d u c et h ec o n c e p to fe c o s y s t e mo nt h eb a s i so f t r a d i t i o n a l c o e v o l u t i o n a r ya l g o r i t h m , t h ea p p l i c a t i o nd o m a i np r o b l e mi sm a p p e di n t o t h ee v o l v i n g e c o s y s t e mc o n s t i t u t e db yv a r i o u ss p e c i e s ，s ot h ep r o b l e mc a l lb er e s o l v e db yt h ee c o s y s t e m e v o l v e m e n t i nt h i sp a p e l an e wm e t h o di sp u tf o r w a r dt os o l v et h ep r o b l e mo fb r a n c hp i p e r o u t i n go p t i m i z a t i o nb a s e do ut h ei d e ao fe o e v o l u t i o n a r ya l g o r i t h m t h i sm e t h o db r e a k st h e i i 大连理工大学硕士学位论文 t r a d i t i o n a lm e t h o d sn e e d e dt od e t e r m i n et h ep i p er o u t i n gs e q u e n c ea n dt h eb r a n c hp o i n t s p o s i t i o n i nt h em e t h o d ，t h eb r a n c hp i p es y s t e mi sd i v i d e di n t om a n ys i n g l ep i p e s ，a n de a c h p i p ei s 姐i n d i v i d u a la n di so p t i m i z e dw i t ha k i n do fp o p u l a t i o n , t h ef i t n e s so fi n d i v i d u a li s d e t e r m i n e db yt h ed i s t a n c ef r o mt h eo p t i m a li n d i v i d u a l si no t h e rp o p u l a t i o n ha d d i t i o n , t h i s p a p e rd i s c u s s e sg e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h ma p p l i e dt oo p t i m i z e ds i n g l ep i p e r o u t i n g , a n dt h e s et w oa l g o r i t h m sc o u l db ee m b e d d e dt ob r a n c hp i p er o u t i n go p t i m i z a t i o n m e t h o d t h r o u g ht h es i m u l a t i o ne x p e r i m e n t a lv e r i f i c a t i o n ，t h ei d e aa n dm e t h o dp u tf o r w a r di n t h i sp a p e ra l en o tl i m i t e do n es i n g l ep i p er o u t i n go p t i m i z a t i o nm e t h o da n dc a nb ea p p l i e d w i d e l ya n de a s i l y k e yw o r d s ：s h i pd e s i g n ；b r a n c hp i p e l i n es y s t e m ：r o u t i n go p t i r a i z a f i o mc o e v o h i t i o n a r y a l g o r i t h m i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 验盈日期：兰望：丝 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：鲤歪 导师签名：主奎兰丝二 2 竺璺午上月) - 日 大连理工大学硕士学位论文 1 绪论 1 1 船舶管路设计概况 在现代船舶设计中，管路设计是船舶设计中重要的设计步骤之一，在总体设计中占 有很大的比重。管路设计的好坏直接关系到一条船的质量性能和经济成本，如何缩短管 路设计时间，提高管路设计质量，对于缩短整个造船周期，提高经济效益，有着不可估 量的意义。 船舶管路系统不仅担负着船舶不沉性、安全性、防火、防污等任务，同时又要满足 安全、可靠、方便地操作、维修以及保证船舶各种机械正常运转和船员舒适生活等需要。 然而，若船上管子的数量和规格过多，不仅会延长管系的设计与施工周期，还会增加船 舶排水量，增加造价，降低航速，影响船舶航行的经济性。当今世界正在走向多极化， 和平与发展成为时代的主题，各国之间的竞争主要表现为以经济实力为主的综合国力的 较量。产品的设计是制造业的灵魂，如何最大限度的整合现有设计资源，以最低的开发 成本、在最短的设计周期内、提供最大限度满足需要的产品，是竞争中制胜的关键。随 着市场竞争的激烈，低成本，高性能，以及满足制造、安装、维护的生产产品已成为各 大船厂和船舶设计研究单位努力追求的目标。 船舶设计过程一般分为三个阶段，初步设计，详细设计和生产设计。管系设计在这 三个阶段的主要内容分别为： 初步设计阶段进行管系原理设计，提供管系原理图； 详细设计阶段进行管路的布局设计，提供管系布置图； 生产设计阶段进行管路干涉检验，提供管系安装图、零件图和材料统计表等。 管路布局设计是管系详细设计阶段的重要组成部分，其决定着管系详细设计中及其 后的设计步骤，因此，可以说管路布局设计是管系设计的重要内容 1 】。船舶管路布局要 求获得性能、成本、可靠性、可维护性等各方面综合平衡的设计，应以总布置图和船体 结构为背景，满足相应的标准、规则、规范、规格书、建造计划书、系统原理图的要求， 同时要考虑船厂的管子加工与安装工艺水平。 管路布置要尽量简单、合理、美观。管子与管子、设备、附件之间要以最短距离连 接，确保拆装方便，并尽量使之形成管束，管子的排列应避免交叉布置，应与船首、尾 方向，左右舷方向平行1 2 】。按照先布置大管后布置小管、先布置特殊要求管后布置一般 要求管的原则进行【”。布管空间应根据通道空间、入孔空间以及设备必须的拆检、维修 空间来确定。在机舱通道及工作区，根据人体最适宜的操作位置范围( 正常行走高度、 基于协同进化的船舶分支管路空间布局优化 横向进出的最小间距以及下蹲行走的最小高度等) 定出通道空间、通道高度。还应考虑 舱、柜人孔前必须的人孔空间等等。避开了这些才能进行布管，在布管时还应确保管与 管之间留有间隙，管子与甲板、外板、扶梯等都应留有标准距离。 一般管路的设计要点：( 1 ) 管路的布置应具有合理性，如所有燃油舱柜的空气管、 溢流管和测量管，都应避免通过居住舱室、精密仪器舱、粮库等贮藏舱室。淡水管路不 得通过油舱，以免管子破损或渗漏污染水质。同样，油管路也不得通过淡水舱。如不可 避免时，应加设油密隧道或套管，让管路通过。其他管路通过油舱时，应遵照规范要求 加厚管壁，并在舱内不得有可拆接头。( 2 ) 管路的布置应具有安全性，如蒸汽管、油 管、水管和柴油机排气管等，应避免布置在配电板及其他电器设备的上方及后面，并尽 量远离配电板周围。油管路还应避免在锅炉、烟道、蒸汽管、废气管及消音器的上方通 过。凡通过防火区域的管路，应采用满足船级社认可的节点形式。管子穿过水密或气密 结构处，应采用贯通件或座板。( 3 ) 管路的布置应具有可操作性，要为建造和维修阶 段所用的吊车、绞车和移动设备提供操作空间，阀及控制装置应避开障碍物并处在易维 护的范围内，如装在花钢板以下的阀件，其手轮应能方便操作，不便于操作的阀件，应 将阀杆接长或配各便于操作的工具。( 4 ) 管路的布置应具有可维护性，如在管子、附 件、滤器等设备上设有放泄装置，以放泄管子内的空气及存液。( 5 ) 管路的布置尽量 满足美观性、简化支撑、节省空间，如管路应尽量沿着舱壁、设备及管路支架正交并成 束敷设，管路排列整齐，对各个系统的每个阀门需要做有规则的整齐布置。( 6 ) 管路 的布置同时应满足管系的力学要求，防止因船舶振动，温度变化引起的热胀冷缩等因素 出现管子断裂、变形等安全问题。 良好的管路布局设计，不仅需要对系统工艺、设备情况、有关标准规范、操作维修 方式、船舶安全防火、各种配管材料性能价格、以及结构、振动、支撑、绝缘等多方面 情况的透彻了解和实际经验，而且需要各种方案的反复比较，并非只是简单遵循规范就 能解决的问题。再有，许多实际管路设计中所需的知识经验和技巧不可能由现成的标准 规范所涵盖，需设计人员反复思考才能逐步积累。管路的布局结果是因人而异的，不同 的设计人员做出的设计方案是非常不同的。而一些宝贵的设计经验有可能会随着有经验 的管路设计专业人员的逐年离退而丢失，这就使得管路设计的任务十分繁重。 1 2 管路布局优化研究的意义 管路三维布局优化方法的研究对减轻设计师负担，提高设计效率和质量，缩短设计 周期，降低造船成本均有重要意义。船舶工程领域中有关空间三维布局设计的研究与船 大连理工大学硕士学位论文 舶c a d 已经达到的水平相比形成了强烈的反差，是船舶设计过程中的瓶颈，它制约着 船舶设计速度和质量的提高。 在船舶设计的各阶段，管路设计工作存在各部门之间沟通困难，设计信息脱节，重 复工作量大等问题。 在初步设计和详细设计阶段，船舶管系设计工作在二维图纸上完成，通常使用的设 计软件是a u t o c a d 。设计人员要花费大量的时间去考虑如何绘制、如何表达各种管路 的相对空间位置，陷于繁重的绘图工作中。为了将设计方案表达清楚，常常要出大量的 剖面图，制图工作量很大。即使如此，在与甲方、工程审批人员、施工人员沟通时仍比 较困难。 在生产设计阶段，国内大部分中小型船厂主要采用平面设计方法进行舰船管路的布 置设计【3 4 1 。它是在船体和动力装置设计完成后，在平面上( 过去用样台或图纸，现在 主要用a u t o c a d ) 按一定比例画好船体型线和有关结构图，正确绘制出各种机械设备 的安装位置，用投影法绘制出全部管系的实际布置位置赦样图。由放样总图拆制各 管系的放样图，根据图中管子的几何形状及具体尺寸绘制管子零件图，按图纸在内场加 工管子，最后按图安装管子。这种传统的平面设计方法有着许多弊端，一方面平面设计 无法表示管路错综复杂的三维关系，只有在船体和各舱室建造完毕后才能进行实际布 置，易造成工时浪费和建造周期延长：另一方面，平面设计无法确定管路在船体中的精 确位置，势必导致管路安装过程中出现误差过大，返工率高等问题。随着计算机软硬件 技术的发展，针对中小型船厂的经济实力和这种放样困难，国内许多学者在研究开发价 格相对适中的软件系统，探索利用计算机在三维空间内对船舶管系进行放样的研究 4 ，5 】， 这种放样技术的优点：可以确保管系舾装的精度，降低材耗，减轻劳动强度，提高设计 质量，缩短设计周期和建造周期。另外，在一些有条件的大型船厂，现已开始应用三维 软件( 如：n o n 、c a d d s 5 等) 进行船舶管路的布局设计，设计过程就是建造三维 设计模型的过程，三维建模时与详细设计阶段的设计信息脱节，需要重新输入船舶设计 院的详细设计的信息，工作量很大。 可以看到这种三维化的管系布局将是解决目前管路布置设计问题的唯一途径和发 展趋势。尽管从平面到三维，管路布局的设计质量和效率等都有了很大的提高，但无论 是平面设计还是三维设计，管路布局设计通常采用复杂的交互式输入和修改来完成，从 某种意义上说这只是一个完成图纸的过程，简单地归属于计算机绘图领域，并没有从真 正意义上支持船舶管路布置设计的全过程，设计的本质并没有发生根本的变化，即都需 要经验丰富的专家或管道工程师去完成，也就是说它主要依靠的是设计人员的专业知识 基于协同进化的船舶分支管路空间布局优化 和经验，还未完全实现管路布局设计的自动化和优化。改变传统的船舶布置设计状况， 提高布局设计的自动化和优化程度，已成为当前急需要解决的问题。 管路布局属于复杂方案设计问题，由于船舶上管子及其附件的数量和种类较多，约 束条件纷繁复杂，不同种类的管子约束条件不同，同种管子在不同的布局环境中，约束 条件也不一样。并且通常需要同时优化多个性能指标，并带有复杂的约束，即属于带约 束的多目标优化问题。这类问题具有计算复杂性、工程复杂性以及工程实用化难等三重 难度，也给相应的求解方法的研究提出了更高的要求。 设计理论的研究中一个很重要的研究方向是【6 】：把智能科学引入设计领域，通过对 设计过程和任务建模，用计算机逐步代替人进行设计，如：进化计算啊，人机结合嘲， 多a g e n t 思想 9 】等等。这些智能方法与以往的传统方法相比，无论在适用问题的范围、 求解方法的灵活性，还是求解问题的能力、质量和效率上。都有大幅度的提高。 船舶管路布局设计的主要目的是利用当前先进的计算机技术，寻找一种自动化地解 决管路优化布局问题的快速而有效的方法。其类似于三维空间的机器人路径寻优【l o 】，从 理论上讲属于组合优化n p - h a r d 问题 1 1 ，1 2 i 。用经典优化方法去解决这类复杂的组合优化 闯题可能会花费很多时间去寻找最优解，有时甚至花费很多时间也难以找到最优解，并 且随着问题规模的增加，其计算时间将会以指数速度延长。因此，对于这类问题，最合 理的方法是那些可以在较短的时间内发现质量较高解的启发式算法。近年来，一类基于 生物学、物理学和人工智能的具有全局优化性能、鲁棒性强、通用性强且适于并行处理 的现代启发式( m e t a - h e u r i s t i c ) 算法得到了很大的发展。这些启发式算法可分为模拟退 火算法( s a ) 、禁忌搜索算法( t s ) 、遗传算法( g a ) 和蚁群优化( a c o ) 算法等。 由于其高效的优化性能、无需问题特殊信息等优点，已广泛用于计算机科学、优化调度、 运输问题、组合优化、工程优化设计等领域，并取得了一系列较好的实验效果，它们的 出现为解决n p h a r d 组合优化问题提供了崭新的途径。 从管路布局优化设计的国内外研究概况看，虽然已经取得了一定的研究成果，但目 前所研究的解决方法或算法还存在着问题，还没有最终形成一套可以用于实际的自动化 管路优化布置系统。由于布局问题的n p 困难性和船舶本身的巨大复杂性，使得该问题 的解决既具有理论上的开拓性和艰难性，又具有工程实践上的复杂性。 1 3 管路布局优化国内外研究概况 自二十世纪7 0 年代起，国内外学者就开始对管路布局设计问题进行研究，先后经 历了从二维空间的简单约束发展到在三维空间内的多目标、多约束【1 3 】。所使用的方法在 一4 - 大连理工大学硕士学位论文 总体上可分类为：单元分解法、智能法及单元生成法。它们是试凑法【1 4 】、动态规划法【1 5 1 、 迷宫法【1 0 1 、逃逸法【2 1 - 2 4 、网络优化法【2 t2 5 也8 1 、z h u 方法【2 9 1 、遗传算法3 0 3 3 1 、专家系 统和模糊集理论 3 4 - 3 6 及蚁群算法 3 7 , 5 0 ，见表1 1 和表1 2 。由于管路敷设约束的复杂性， 到目前为止，管路布局设计还没有形成一套成熟的理论和理想的方法 3 7 】，其仍然是一个 有待于彻底解决的智能问题。下面简要介绍一些应用在管路布局中的主要方法。 表1 1 管路布局实际国内研究概况 t a b 1 1t h eo u t l i n eo f d o m e s t i cs t u d i e so f p i p er o u t i n gd e s i g n 表1 2 管路布局实际国外研究概况 t a b 1 2t h eo u t l i n eo f a b r o a ds t u d i e so f p i p er o u t i n gd e s i g n 基于协同进化的船舶分支管路空间布局优化 1 3 1 迷宫法 为解决像电子线路图这样的逻辑图的最短连接路径问题，l e d l 司于1 9 6 1 年首次提出 了迷宫算法( m a z ea l g o r i t h m ) 。迷宫法主要是基于波的连续扩散原理，如图1 1 所示， 图1 1 迷宫法 f i g 1 1 m a z ea l g o r i t h m 本质上是一种遍历性质的逐点查找法。首先，将布局空间划分为单元网格，带阴影的单 元表示障碍物；其次，路径从起点单元s 开始向外扩散，扩散的方法是把与s 单元在正 交方向邻接的单元标为l ，再把与1 单元在正交方向邻接的单元标为2 ，以此类推，直 到到达目标单元t 为止；最后，按数字递增的顺序顺次从起点连接到终点就形成了一条 最短可行路径。 r o u r k e ”】首次将解决线路问题的迷宫算法应用到管路布置上，于1 9 7 5 年提出了应 用迷宫算法解决管路布置的三个主要步骤，并为解决干涉检查问题，使用了一种矩形框 包围障碍物的屏蔽技术。m i t s u t a 1 8 1 等在1 9 8 6 年采用最优( b e s t f i r s t ) 搜索技术改进了迷 宫算法，他们按障碍物的大小和形状将布局空间划分为大小不等的单元格障碍物敏 感单元格，并用“i f - t h e n ”规则和“框架”理论来表达布置约束知识。陈鹰 1 9 9 8 u9 j 等 应用该算法解决液压管道的布置问题，在姿态空间内连接给定的起点和终点之间的空单 元用以产生免于碰撞的管路路径。樊江 2 0 0 3 】【2 0 】等应用改进的迷宫法以及最小斯坦纳树 生成法，进行飞机发动机外部管路的敷设研究，并开发出航空发动机网络敷管系统 a e g r s ( a e r o - e n g i n e g r i db a s e d r o u t i n gs y s t e m ) ，其方法的主要特点是采用三维加权 大连理工大学硕士学位论文 网格对发动机复杂三维模型进行网格划分，描述敷管的自由空间，以产生满足更多约束 的管路路径。 迷宫法的布通率高、适应性强，但所需容量大【3 8 】、操作速度慢，尤其当障碍物增加 时，其复杂性会成倍增长。另外，迷宫算法在一次布管时只考虑一条线路，而不考虑其 它管线对它所造成的影响，这与包含多条管路的管路系统的布置目标并不一致。因此， 在复杂的布管问题中，迷宫算法的直接应用受到了一定的限制。 1 3 2 逃逸法 为了克服迷宫法的缺陷，h i g h t o w e r 2 1 l 于1 9 6 9 年提出了逃逸算法( 向量搜索法) 。 这种方法始于起点位置上相互垂直相交的两条直线上，如图1 2 所示，这两条直线叫做 逃逸线；根据预先确定的规则，分别在两条逃逸线上选择逃逸点，设定逃逸点为新的起 始点，重复以上过程直到到达目标点为止。 图1 2 逃逸算法 f i g 1 2 e s c a p ea l g o n t h m 由于逃逸算法的搜索速度快、所需存储空间少，所以在印刷电路板( p c b ) 上得到 了广泛的应用。但是，这种方法并不总能找到最短路径，有时甚至在最短路径存在的情 况下，算法却搜索不到。因此，在实际应用中，为了减少计算的复杂性及操作所需的资 源和时间9 常将其和迷宫算法联合起来使用。例如：s c h m i d t - t m u b z 2 和b u r d o r f 2 3 1 分别 于1 9 9 8 年和2 0 0 4 年在厂房的布局中用这两种方法敷设最优管路。k n i a t 2 0 0 0 2 4 在三维 空间内延伸了这两种方法并且形成了一种混合方法。这种混合方法可充分利用迷宫法和 逃逸算法的优点，当布局空间的障碍物较多且路径较短时，应用迷宫算法；相反，当布 局空间障碍物较少且路径相对较长时，用逃逸算法，但研究中发现很难划分两种方法的 分界线。 基于协同进化的船舶分支管路空间布局优化 1 3 3 网络优化算法 网络优化算法亦可被用在管线布局上。给定一个有向图g = - ( 玎e ) ，这里v 是顶 点集 v 1 ，th ) ，e 是边集，在边集e 中只存在一条从顶点v f 到吁的边时，8 f 是 该边集中的一个元素。给边集中的每一条边赋予一个权重g ，所讨论的问题是在有向图 g 中确定一条连接给定原点，和目标点的最优路径，如图1 3 所示。 图1 3 网络优化法 f i g 1 3n e t w o r ko p t i m i z a t i o n m a n d l e 2 5 】在1 9 7 9 年提出可以用线性优化模型来表示这种网络优化问题，即： m i i l 吒嘞 ( 1 1 ) 。vl j ：e # 其中： f l t 而2 伍 如果k 是原点 如果七是目标点 ( 1 2 ) 如果七是中间节点 如果f 的下一个节点是， 其它 。 ( 1 3 ) 在早期解决这种线性优化模型的方法主要有两种算法，即d i j k s t r 算法和n i c h 0 1 s o n 【3 9 】 方法。w a n g d a h l 2 1 在1 9 7 4 年用d i j k s t m 算法计算最优路径，并且通过定义“通视点” ( i n t e r v i s i b l ep o i n t ) 建立“通视线”的方式来避开障碍物。同时，n e w e l l 1 9 7 2 t 2 6 1 采纳 n i c h o l s o n 方法寻找最短路径。g u i r a r d e l l o 1 9 9 3 【2 7 】在工艺车间的布局中应用了d i j k s 衄 “乩n i | 稚 俨 一 砀 俨 老 ， 点节个一 每 于砒对 大连理工大学硕士学位论文 算法和l i n d o 方法搜寻最短路径。y a m a d a 1 9 9 8 t z 8 1 在三维空间中应用网络优化法完成了 电厂的管路敷设，他用已存在的管路分割布局空间，通过基于距离矩阵的幂乘法获得最 短路径。 网络优化算法需要事先确定一系列用来交叉、连接和转弯的中间节点，这些工作要 靠有经验的专家才能完成，工作量仍然很大。同时这种方法一次只能建立一条路径而不 考虑其它管线，每一条管路的布置都是独立进行的。 1 3 4 z h u 算法 1 9 9 1 年d a v i d z h u 提出一种以他自己命名的z h u 算法1 2 9 佣来解决管路布局问题，在 他看来管路敷设相当于具有约束条件的路径规划，虽然他的思想是基于机器人的路径寻 优，但其方法本质是一种通道搜索算法。在这种方法中，管路路径被当作是运动的机器 人( 在2 d 中用圆盘表示，在3 d 中用球表示) 所走过的路径。首先，他把障碍物和已 敷设的管路分别转化为姿态障碍( 所谓姿态障碍，即是根据管道的口径和即将延伸的方 向，将障碍物和己敷设的管路向外扩展一定的距离，同时则可将要敷设的管道缩成一个 点，形成姿态障碍) ，把自由空间划分为矩形单元；然后，用自由空间的矩形单元构造 连通图，从而形成一个连通初始点单元和目标点单元的单元“通道”，如图1 4 所示； 最后，在“通道”中连接起点和终点并用a 算法寻找一条合适的路径。a 算法的公式 如下： f ( ) - - g ( ) + ( ) ( 1 4 ) 公式中g ( ) 是一个带有权重的表示路径总长和转弯个数的和函数，h ( ) 是节点 所在单元的中心点到目标点之间的m a n h a t t a n 距离函数。 f c 7 c 6 劂c 1 c 2 c 5 幽c 3 ic 8i 图1 4 单元分解和连通图 f i g 1 4 c e l ld e c o m p o s i t i o na n dc o n n e c t i v i t yg r a p h 基于协同进化的船舶分支管路空间布局优化 这种方法的最大缺点是，当找不到某一条管路的连通通道时，必须采用回溯的方法 从第一条管路重新开始规划，显然，这种方法在管路数量庞大的情况下不太实用。 1 3 5 遗传算法 遗传算法是由美国密歇根( u n i v e r s i t yo f m i c h i g a n ) 大学教授j o h nh o l l a n d 4 0 和他的 学生于1 9 7 5 年创立的，它是一种借鉴生物界自然选择和进化机制而发展的启发式优化 算法。遗传算法自其问世到被应用到管路布局上大概经历了有2 0 年的时间，最典型的 应用是日本的i t o 3 0 - 3 h ，他在1 9 9 8 年和1 9 9 9 年应用遗传算法在二维平面内搜索管路的 最优路径，取得了突破性的进展，但他在处理遗传算法的编码方式和遗传算子上不太理 想。在他的管路敷设工作中，一条管路路径由连接起点和目标点的一串由字符串代表的 单元格组成，它构成算法的一个解( 染色体) ，如图1 5 所示；杂交算子采用两点和单 点的杂交方式。这种编码方式和遗传操作算子，导致在杂交和变异操作中产生了大量的 非法解，引起十分繁琐的修补工作，影响了算法的收敛性能。 黼 囫路径c i 3 。一4 i c i = 2 ，2 ，2 ，2 , 4 ，4 4 ，4 ，2 ，2 ，2 ，2 ，4 ，4 ，4 ) 图i 5 管路路径和它的染色体 f i g 1 5p i p er o u t ep a t hm a di t sc b x o m o s o m e 另一个具有代表性的应用是由国内樊江【1 0 1 等为解决航空发动机的多管路布置问题， 在平面内建立的基于遗传算法的多管路智能寻径算法，取得了较好的实验效果。其算法 的主要思想是：每一条管路对应一个种群，这样多管路的协同布置设计相当于由多种群 组成的生态系统的协同进化；其个体协作度的评价也即算法的协作机制，采用对种群中 的每一个个体构造一个协作种群的方式，即对规模为n 1 的种群1 的每一个个体，如果 大连理工大学硕士学位论文 其协作种群2 的规模为n 2 ，那么需要对种群1 构造n 1 个规模为n 2 的协作种群2 。他 为多管路的协同敷设开辟了一条崭新的思路。 此外，还有一些学者也用遗传算法在管路布局方面作了一些研究工作。k i m 1 9 9 7 3 2 j 3 埔遗传算法并结合最小斯坦纳树( m i n i m a lr e c t i l i n e a rs t e i n e rt r e e ) 生成法在 平面内研究了流体管路的自动布置问题；s a n d l l k a r 和c h e r t 1 3 】提出了应用棋盘式对象来 表达障碍物的遗传算法，开发了g a p r u s ( g a - b a s e dp i p er o u t i n gu s i n gt e s s e l l a t e d o b j e c t s ) 管路敷设系统，其算法的主要特色在于，合成了一个由实数、整形和离散形变 量的变量集，它们在遗传算法中对应的变量是：管路长度、连续管路间的的弯头角度和 弯头数。范小宁和林焰【4 1 】对遗传算法的固有缺陷进行了改进，提出自适应退火遗传算法 对船舶管路布局进行了优化，与传统遗传算法相比，加快了收敛速度，提高了全局收敛 性。 遗传算法的鲁棒性、强有力的随机性和并行性，决定了它在解决类似组合优化问题 上的高效性，因而在管路布局优化问题上，它是一个非常值得深入探讨的优化方法。 1 3 6 专家系统和模糊集理论 管路布局设计，需要满足很多约束，而约束的大部分是以规则的形式出现的f 1 2 】。有 些约束很容易用数学函数表达，并可在编程过程中直接使用；但有些描述性模糊约束却 很难直接用数学函数公式化。针对这种情况，研究者提出采用模糊集理论来构建这类目 标和约束的方法。w u 1 9 9 8 1 3 4 等使用这种方法对船舶机舱设备和管路的布置进行了尝 试性的研究，他们在管路布局中用隶属度表示类似较大( 小) 空间、较高( 低) 温度、 操作频率较高( 低) 这样的模糊约束，取得了较成功的布局效果。另外，在他的研究中， 还考虑了设备布局和管路敷设之间的相互协调性，管路敷设的性能依赖于设备布局的结 果，只有设备布局合理，才能在管路敷设时获得较好的效果。由于管路敷设约束的多描 述性和模糊性的特点，因而，模糊集理论在管路敷设上的应用具有很大的优越性和灵活 性。 近二十年来，c a d 技术对设计生产产生了强大的推动力，但是，随着时间的推移， 也越来越暴露出它所具有的局限性，如前所述。鉴于此，为适应船舶及其管路布局设计 的特点，自然需要寻找新的技术，这就是专家系统，它具有克服c a d 系统限制的能力。 所以，k a n g 1 9 9 6 口卸基于c a d d s 5 运用专家系统进行了船舶机舱管路的自动敷设研究。 张大船 2 0 0 1 1 3 6 1 采用专家系统的功能结构模式联合开发并建立了配管工程专家数据库。 专家系统为管路布局问题提供了一条非常合理的解决途径，但目前这方面的研究还不是 很多。 基于协同进化的船舶分支管路空间布局优化 1 3 7 蚁群算法 蚁群算法( a n tc o l o n ya l g o d t h m ) 是意大利学者m d o r i g o 4 2 1 在1 9 9 1 年提出的一种 受自然界生物的行为启发而产生的进化算法。主要特征是采用正反馈机制，分布式计算 方法，用来解决各种分布式环境下的组合优化问题【4 3 】。在自然界中蚂蚁几乎是瞎子，却 能发现食物与蚁穴之间最短的距离。生态学家的研究表明，蚂蚁是借助信息素 ( p h e r o m o n e ) 来实现这一点的。信息素是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物 过程中会分泌这种物质。蚁群在寻找食物时，会有一些蚂蚁四处游荡，当蚂蚁发现食物 并返回巢穴过程中会在途中留下信息素。如果假定所有蚂蚁以相同的速度前进的话，则 第一只返回巢穴的蚂蚁发现的路径是当前所有蚂蚁发现的路径中最好的。较短路径上信 息素会比较浓一些，而较浓的信息素能吸引更多的蚂蚁走这条路径，这种强化过程使蚁 群发现最短路径。迄今为止，蚁群算法己成功地解决了许多实际问趔卅，如旅行商 4 5 - 6 】 问题，平方分配问题，工作进度安排h 8 ，4 观问题等。 2 0 0 6 年，范小宁【5 0 等将蚁群算