（机械制造及其自动化专业论文）船舶管系路径优化算法研究.pdf

r e s e a r c h e so np a t ho p t i m i z a t i o n a l g o r i t h mo fs h i pp i p es y s t e m c a n d i d a t e ：b a im i n g s u p e r v i s o r ：p r o f q i uc h a n g h u a a c a d e m i cd e g r e ea p p ll e df o r ：m a s t e ro fe n g i n e e r i n g s p e ci a l t y ：m e c h a n i c a lm a n u f a c t u r ea n da u t o m a ti o n d a t eo fs u b m i s s i o n ：d e c e m b e r ，2 8 ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，1 3 ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y tv 卜 “ 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：匀训 日期：年岁月蝈 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 曰在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( - 签- 7 - ) ：匆明 日期：爻，年岁月广日 导竺凳黧及午 参o | 年其? 姐 i f 厶 哈尔滨t 程大学硕l 学位论文 于葡要 随着科学技术的进步和船舶工业的发展，船舶产品升级换代的速度大大 加快。在现代船舶工业中，管路系统的布局设计在船舶总体设计中占有很重 要的地位。目前，在实际工作中管路系统设计主要依赖于设计者的经验来完 成，由于在设计过程中管子数量十分庞大，约束条件很复杂，管路布线设计 耗时费力，与船舶其它部分设计技术相比有很大差距，严重制约了整个船舶 的设计周期。国内外的研究者进行了大量的相关研究工作，试图找到解决办 法。但目前为止，还没有可以实际应用的成熟方法。因此，在船舶管路布局 领域寻求新的、实用的设计方法和设计手段就成为急需解决的问题。本文参 考三维布局领域的研究成果，结合人工智能技术、船舶c a d 技术进行船舶 管路布线问题的研究，为实现船舶管路的智能化设计做基础准备。 本文基于标准遗传算法的主体思想，结合船舶管路布线的具体问题，对 遗传算法进行了一些改进工作，得到了应用于船舶管路布线优化的遗传算法。 该遗传算法在解决管路布线问题时表现出更好的适应性，使管路布线设计结 果更合理。这些改进主要包括：对适应度函数的改进，对遗传算子的改进和 对管路布线流程的改进等。实验证明，这些改进对克服遗传算法进化过程中 的“早熟”现象和“产生局部最优解”现象有很大的帮助，使由遗传算法进 化得到的最优管路布线路径具有很高的实用性。本文还对应用于船舶管路布 线优化的遗传算法的各构成要素对算法的影响作了分析介绍，并对各参数和 系数取值的规律性和内在联系性作出总结。此外，本文还针对布线结果，设 计了路径在c a t i a 软件平台上实现可视化显示的“宏”程序，为实现船舶管 路系统的虚拟装配工作做基础研究。 实验结果表明，本文利用经过改进的遗传算法实现船舶管路布线和运用 c a t i a 软件实现管路布线显示的工作是成功的，对解决管路布线设计的实际 问题是很有帮助的。 卜 飞 卜 ? 每 哈尔滨工程大学硕 学位论文 关键词：遗传算法；管路；布线 ! 二 哈尔滨工程大学硕 学位论文 a bs t r a c t w i t hd e v e l o p m e n to ft e c h n o l o g i e sa n ds h i p b u i l d i n gi n d u s t r y , t h e p a c eo f u p g r a d i n gm a r i n ep r o d u c t sh a sb e e ng r e a t l ya c c e l e r a t e d i nt h em o d e r n s h i p b u i l d i n gi n d u s t r y , t h el a y o u td e s i g no fp i p e l i n es y s t e mp l a y sa l li m p o r t a n tr o l e i nt h eo v e r a l ll a y o u td e s i g no ft h es h i pp i p es y s t e m c u r r e n t l y , s y s t e md e s i g ni n p r a c t i c a lw o r km a i n l yd e p e n d so nt h ee x p e r i e n c eo fd e s i g n e r s ，b e c a u s eo fl a r g e r n u m b e r so f p i p e s a n dt h e c o m p l e xc o n s t r a i n t s ，p i p el a y o u td e s i g n i s t i m e c o n s u m i n g ，a n dt h e r ei sab i gg a pi nt h et e c h n o l o g i e sb e t w e e nl a y o u td e s i g n o ft h ep i p es y s t e ma n do t h e rp a r t so ft h es h i p ，w h i c hs e r i o u s l yi n f l u e n c es h i p d e s i g nl i f ec y c l e f o rt r y i n gt o f r e d s o l u t i o n s ，al a r g en u m b e ro fr e l e v a n t r e s e a r c h e sh a v eb e e nc a r r i e do u t b u ts of a r , t h e r ei sn op r a c t i c a lm a t u r em e t h o d s c a nb ea p p l i e dd i r e c t l y s oi th a sb e e nu r g e n ti s s u e st os e e kn e w , p r a c t i c a ld e s i g n m e t h o d sa n dd e s i g nt o o l si nt h ef i e l do fs h i pp i p i n gl a y o u t t h i sp a p e rt a k e s r e s e a r c ha c h i e v e m e n t si nt h ef i e l do ft h r e e d i m e n s i o n a ll a y o u ta s r e f e r e n c e s ， c o m b i n e dw i t ha r t i f i c i a l i n t e l l i g e n c et e c h n o l o g y , s h i p b u i l d i n gc a dt e c h n o l o g y , o f f e raf o u n d m i o nf o ri n t e l l i g e n td e s i g no ft h es h i pp i p e l i n e b a s e do nt h em a i ni d e ao fb a s i cg e n e t i ca l g o r i t h m ，c o m b i n e dw i t ht h e s p e c i f i cp r o b l e m so fs h i pp i p i n gl a y o u t ，an u m b e ro fi m p r o v e m e n t sh a v eb e e n m a d et om a k et h eg e n e t i ca l g o r i t h ms h o w sb e r e ra d a p t a b i l i t yw h e ns o l v i n gt h e p i p er o u t i n gp r o b l e m ，c o n s e q u e n t l yp i p el a y o u td e s i g nr e s u k sa r em o r er e a s o n a b l e t h e s ei m p r o v e m e n t s i n c l u d e ：i m p r o v e m e n t st ot h ef i t n e s sf u n c t i o n ，g e n e t i c h o p e r a t o r a 1 1 dt h e p i p e l i n e r o u t e p r o c e s s e x p e r i m e n t s s h 。wt h a tt h e s e i m p r o v e m e n t s c a no v e r c o m e p r e c o c i t yp h e n o m e n o na n dp h e n o m e n o no f g e n e r a t i o nl o c a lo p t i m a ls o l u t i o ni ne v o l u t i o n a r yp r o c e s so ft h eg e n e t i ca l g o r i t h m ， w h i c hm e a n si tc a ni m p r o v ep r a c t i c a b i l i t yo fo p t i m i z e dl a y o u td e s i g no ft h es h i p p i p eu s i n gi m p r o v e dg e n e t i ca l g o r i t h m t h ep a p e rh a sa n a l y s i s e da n di n t r o d u c e d 哈尔滨- 下程大学硕十学位论文 i i i i i i ；毒。m l t lm li t h ei n f l u e n c eo fi n s c a p eo fg e n e t i ca l g o r i t h mt h a ta p p l i e dt ot h es h i pp i p el a y o u t o p t i m i z a t i o n t o a l g o r i t h m ，a n ds u m m a r i z e dt h e l a w s a n di n t e r n a lr e l a t i o n s b e t w e e np a r a m e t e rv a l u ea n dc o e f f i c i e n tv a l u e i na d d i t i o n ，t h i sp a p e rd e s i g n s m a c r o - p r o g r a mt oa c h i e v ep a t h sv i s u l i z a t i o ni nt h ec a t i ap l a t f o r m a l lo ft h e s e h a sd o n ef u n d a m e n t a lw o r kf o rv i r t u a la s s e m b l yd e s i g no fs h i pp i p es y s t e m e x p e r i m e n t a lr e s u l t ss h o wt h a tl a y o u td e s i g no fp i p eu s i n gi m p r o v e dg e n e t i c a l g o r i t h ma n dd i s p l a yw o r ki nt h ee n v i r o n m e n to fs o f t w a r ec a t i aa r es u c c e s s f u l ， w h i c hi sh e l p f u lt os o l v ep r a c t i c a lp r o b l e m si nt h el a y o u td e s i g no fp i p es y s t e m k e y w o r d s ：g e n e t i ca l g o r i t h m ；p i p e l i n e ；l a y o u t 卜 哈尔滨工程大学硕士学位论文 目录 第1 章绪论l 1 1 引言1 1 2 管路布局问题国内外研究现状2 1 2 1 布局问题的建模方法研究3 1 2 2 布局问题的求解算法研究4 1 3 船舶工程领域人工智能技术研究现状6 1 4 船舶c a d 技术发展现状7 1 5 遗传算法概述8 1 5 1 遗传算法的提出及发展8 1 5 2 遗传算法的基本思想9 1 5 3 遗传算法的特点1 0 1 5 4 遗传算法的构成要素1 0 1 6 论文的意义及主要研究内容1 2 1 6 1 论文的意义“1 3 1 6 2 论文的主要研究内容”1 3 第2 章管路布局领域中遗传算法存在的问题”1 4 2 1 引言”1 4 2 2 标准遗传算法及其在应用中的存在的问题1 4 2 3 自适应遗传算法及其在应用中的存在的问题1 7 2 4 模拟退火遗传算法及其在应用中的存在的问题1 8 2 5 各种遗传算法的仿真实验结果分析2 0 2 6 本章小结2 3 第3 章船舶管路布局领域中对遗传算法的改进“2 4 3 1 编码2 4 3 2 对目标函数与适应度函数的改进2 6 卜 哈尔滨工程大学硕士学位论文 3 3 初始种群的生成3 0 3 4 选择算子3 2 3 5 对交叉算子和变异算子的改进3 2 3 6 算法的进化流程图3 5 3 7 本章小结3 6 第4 章改进的算法中各构成要素选取规则研究。3 8 4 1 仿真计算方法3 8 4 2 仿真计算结果统计及结果分析3 9 4 3 各构成要素对算法性能影响的规律性分析4 4 4 4 本章小结4 5 第5 章管路布线算法仿真计算与对比分析4 6 5 1 仿真计算演示4 6 5 1 1 准备工作4 6 5 1 2 仿真计算过程4 6 5 1 3 仿真结果及结果分析4 9 5 2 船舶管路布线优化设计结果的三维c a d 实现5 2 5 2 1 三维c a d 转换的实现步骤。5 2 5 2 2 三维c a d 转换仿真演示。5 2 5 3 管路布线优化的遗传算法的仿真对比分析5 4 5 3 1 准备工作5 4 5 3 2 仿真结果分析5 5 5 3 3 仿真示例对比5 6 5 4 本章小结5 8 结论5 9 参考文献6 1 攻读硕士学位期间发表的论文和取得的科研成果6 5 致j 射6 6 p 哈尔溟工程大学硕士学位论文 第1 章绪论 1 1 引言 我国改革开放三十多年来，在工业发展方面的伟大成就之一就是造船业 取得了世界瞩目的巨大发展。目前，我国造船业的年度造船能力( 总吨位) 已经排名世界的第一位。随着全球科技水平的不断提高，在全球造船业中， 新工艺、新技术不断出现并应用，造船模式正在向深度和广度两个方向不断 发展，计算机技术已经成为世界各国发展现代造船工业必不可少的重要技术 手段，船舶c a d 技术已经在世界各大造船厂及船舶相关企业中得到普及和 发展。 船舶管路系统设计是船舶设计的重要内容之一，也是船舶设计中工作量 最大、过程最繁琐、周期最长、设计改动最多的部分。由于我国在造船业中 的传统观念是重视船体设计，忽视船舶管路系统设计，因此我国船厂管路系 统的设计水平普遍不高，管路系统设计成为我国造船业的一大技术瓶颈。船 舶管路系统是船舶动力系统的重要组成部分，船舶管路系统设计的优劣不仅 关系到动力系统和船舶的性能，而且直接影响到船舶建造的周期和成本，还 将影响到以后船舶运行的安全性、操作的方便性、维修的简便性等各个方面。 因此，寻求设计船舶管路系统的新方法、新理论、新工具就成为我国造船业 发展的当务之急。 使用人工智能技术和虚拟装配技术进行船舶管路系统设计可以大大的提 高管路系统设计的速度和质量，从而大大节约船舶设计的时间和成本，是船 舶设计技术未来的重要发展方向之一。管路系统的布线设计是管路系统设计 的重要组成部分，研究如何利用现代计算机系统进行船舶管路系统自动布线 设计，是船舶管路系统智能化设计研究的重要组成部分。船舶管路系统布线 设计的可视化是实现管路系统虚拟装配的前提条件，布线设计的可视化研究 是管路系统虚拟装配研究的重要内容之一。 卜 哈尔滨工程大学硕士学位论文 1 2 管路布局问题国内外研究现状 船舶管路布线设计是一种典型的三维布局问题，其问题实质上是一种具 有性能约束的组合优化问题。 布局问题主要可以分为两类：一类是将一些给定形状和大小的区域分割 成若干所需要的形状及大小的几何体，使该区域所限定空间的利用率最高， 这类问题通常称为切割问题；另一类是在空间内互不重叠的放置一些已知形 状和大小的几何体，使得所有几何体所形成的外包络区域的测度( 即长度，面 积或体积) 最小，这类问题称为填装问题。 除了这种分类方法之外，布局问题按照分布领域和研究角度的不同，还 可以有以下几种不同的分类方法n 1 ： ( 1 ) 按照布局物体的布局空间维数分类，可分为一维布局问题、二维布 局问题和三维布局问题等三种类型。 ( 2 ) 按照布局物体的形状分类，可分为规则物体的布局和不规则物体的 布局两种类型。 ( 3 ) 按照布局问题的约束条件和约束性质分类，可分为无性能约束布局 问题和带性能约束布局问题两种类型。 迄今为止，有关布局问题的理论研究绝大多数属于二维和三维规则物体 的布局范围。这两类问题中，只有一些个别的问题( 如装盘问题和一刀切问 题) 附加有特殊条件，其问题本身可以抽象为纯数学模型的表达形式，利用 数学规划和启发式方法求解，理论上已经获得解决，实践应用中也得到了较 成功的应用；其它这类问题却随着布局物体数量的增加，解空间呈指数倍扩 大，出现组合爆炸现象，用动态规划、分支定界等基于穷举思想的算法都无 法解决。因此，关于这两类问题的所有算法都是基于特定应用领域的启发式 算法，它们的效果随着具体问题的不同有很大的差别，且只能找到近似可行 解嘲。 关于二维和三维不规则物体的布局问题，由于布局对象形态的任意性， 使问题变得非常复杂，目前这两类问题的研究成果还十分有限。 2 声 囊 哈尔滨工程大学硕士学位论文 布局问题的建模和求解是非常复杂的。首先，布局空间和布局物体的建 模要适合布局过程的计算和决策。其次，布局过程中涉及到大量人类专家的 认知活动，包括求解和决策活动。其中一部分具有规律性的认知活动可以表 示为知识并用一定形式化的方法加以描述( 例如规则集合) ，还有另外一部分 不具有规律性的人类专家的认知活动无法用模型来表示。再次，布局问题属 组合最优化问题，用数学优化模型描述的布局问题存在计算的复杂性，在有 限时间内得不到精确解。而且，不同领域的布局问题有着不同的功能，不同 的任务，因而有着不同的描述和表达形式，其求解方法也大不相同。目前， 对布局问题的研究主要集中在布局的建模方法和求解算法方面。 1 2 1 布局问题的建模方法研究 布局问题的提出和研究其实已有几百年的时间了。早期的布局问题是一 类寻求空间中几何体合理摆放的离散组合最优化问题。早在1 6 1 1 年著名天文 学家j o h a n n e sk e p l e r 就提出了等尺寸球体布局问题的“k e p l e r 猜想”。到目 前为止，大多数研究还是局限在规则物体( 形体) 的布局研究。原因是不规 则物体( 形体) 的形状很复杂，建模很困难。因此，对不规则物体的布局问 题，人们往往是将不规则物体( 形体) 简化为容易建模的规则的几何形体， 然后再进行布局研究，其本质上已经转化为规则物体( 形体) 的布局问题。 如唐飞等人p 1 将航天器中一种复杂插座板上进行插孔的布局设计问题简化为 二维圆形装填问题。 随着人们对布局问题及其求解理论和方法的认识不断深入，以及实际工 程应用中对不规则物体布局问题求解理论和方法需求的不断增加，人们对不 规则物体的布局问题越来越重视，从事这类问题研究的学者也越来越多口1 。 戴佐、查建中等将八叉树数据结构应用到三维优化布局问题领域来表 示任意形状的三维实体及三维布局空间。他们在文献 7 和文献 8 中给出了三 维实体的造型和干涉检验的八叉树方法，利用八叉树数据结构将三维实体布 局对象及三维空间的分布状态表达出来，为三维布局问题提供了一种很好的 卜 一 哈尔滨工程大学硕士学位论文 解决途径。 王金敏、查建中等限m 1 提出了一种新的三维实体八叉树模型的生成算法， 并基于该算法较好地解决了计算复杂物体之间距离的问题。 c a g a n 等1 提出了表达实体的一种改进的八叉树方法及相应的干涉检验 算法。 王爱虎、查建中n 射3 1 提出了一种利用- - y , 树结构表达矩形物体布局状态空 间的方法，还提出了一种解决简单多边形裁剪和交并计算的算法。 陆一平等u 川对八叉树理论进行了扩展，提出了2 n 叉树方法，从而为研究 和解决多维布局问题和抽象布局问题提供了一种研究的通用方法，2 n 叉树方 法的提出对八叉树理论的应用也很有启发意义。 1 2 2 布局问题的求解算法研究 布局问题涉及到计算几何、计算机图形学、运筹学、逻辑推理等多学科、 多领域的知识，通常都会抽象为一个复杂的组合最优化问题。复杂布局问题 的求解速度和求解精度成为一对矛盾，因此，求解算法选择的好坏直接影响 布局问题求解的速度和质量。近些年，在优化布局领域常用的算法主要有： 迷宫法、逃逸法、遗传算法及蚁群算法等，如表1 1 和表1 2 所示。除了表中 统计的方法和应用领域之外，2 0 0 5 年至2 0 0 9 年这5 年中还有很多学者进行 这方面的研究，并取得一些研究成果。 冯军弘1 于2 0 0 5 年提出三维管路空间距离矩阵表示方法，并在货船机舱管 路布置设计中利用遗传算法实现了管路布局。 范小宁【”1 在2 0 0 6 年分别采用自适应退火遗传算法、蚁群算法和多蚁群协 作式互利共生类协同进化算法进行管路布局研究，比对各种算法的布局效果 进行了比对分析。 曹战q 于2 0 0 7 年利用遗传算法解决车间设备的布局问题。 刘斌，蒋丹，齐恩伍1 在2 0 0 8 年将蚁群算法引入到凝汽器接颈部分的管 路路径规划领域，并取得了较好的效果。 4 簟 哈尔滨- t 程大学硕士学位论文 表1 1管路布局设计国内研究概况n 5 1 方法报道时间作者应用领域 c a d 试探法1 9 9 7 年王志红 试验台 1 9 9 7 ，1 9 9 8 年陈鹰液压 迷宫法 2 0 0 3 年 樊江航空发动机 遗传算法2 0 0 4 年樊江航空发动机 专家系统方法 2 0 0 1 年 张大船 工厂 表1 2 管路布局设计国外研究概况1 方法报道时间作者应用领域 1 9 7 5 年r o u k e p w一般 迷宫法 1 9 8 6 盔m i t s u t a t 一般 1 9 9 8 焦s c h m i d t t r a u b工厂 迷宫法和逃逸法 2 0 0 0 年a l e k s a u d e r 船舶 2 0 0 4 年b u r d o r f a工厂 1 9 7 2 笠n e w e l l工厂 1 9 7 4 年 w a n g d a h l g e 船舶 网络优化算法 1 9 9 3 年g u i r a d e l l o r工厂 1 9 9 8 年g u i r a d e l l o r工厂 z h u 算法 1 9 9 1 笠d a v i dz h u 一般 1 9 9 7 ，1 9 9 8 年 d a e g y u k i m 工厂 遗传算法 1 9 9 8 年w | e ic ：h e n 汽车 1 9 9 9 年i t o t一般 1 9 9 8 年，u b c g s 船舶 专家系统方法 1 9 9 9 年 k a n g s 船舶 单元生成方法 2 0 0 2 年 j i n h y u n gp a r k 船舶 从表1 1 、表1 2 和近几年布局问题领域的研究中可以看出：布局问题的 研究虽然已经有很长时间了，但目前并没有可以运用到实际工程设计中的成 熟方法，几乎所有研究都还处于理论研究阶段或实际应用的初步探索试验阶 段。由于实际工程设计中的急迫需求，目前布局问题依然是十分热门的研究 领域。而且，从表1 1 、表1 2 和近几年布局问题领域的研究中还可以看出： 迷宫法、逃逸法、遗传算法及蚁群算法是布局问题领域中比较热门的研究对 象。除此之外，像专家系统方法虽然方法思想很前卫，也符合目前专家系统、 智能设计等技术的研究潮流，但由于该技术领域涉及的知识太多，技术太复 哈尔滨丁程大学硕士学位论文 杂，甚至有些关键技术尚处于刚起步阶段或研究探索的初步阶段，技术很不 成熟，因此运用到实际工程问题中会遇到很多问题( 例如：知识表达方法问 题等) ，导致近几年在布局领域该方法的研究成果较少。 利用遗传算法和蚁群算法研究布局问题的研究者逐年增多。研究者对遗 传算法和蚁群算法进行了很多改进，还出现了基于这两种算法的混合算法或 这两种算法与其他算法的混合算法。从而使布局问题研究领域出现了“百家 争鸣，百花齐放”的可喜局面。 1 3 船舶工程领域人工智能技术研究现状 人工智能( a r t i f i c i a li n t e l l i g e n c e ，缩写为a i ) 是用计算机来完成或模拟人 脑的思维和推理过程的学科，是一门综合了计算机科学、生理学、哲学的交 叉学科。人工智能的研究课题涵盖面很广，从机器视觉到专家系统，包括了 许多不同的领域，这其中共同的基本特点是让机器学会“思考”。 人工智能始终处于计算机发展的最前沿，人工智能技术的研究为计算技 术的发展指引了方向。高级计算机语言、计算机界面及文字处理器的存在或 多或少都得归功于人工智能技术的研究。 人工智能技术在现代化船舶的控制和管理领域也得到了应用。上世纪8 0 年代以来，国外航运业对专家系统给予很大的关注，并先后开发出许多实用 的商品化专家系统u 引。例如：“双底双壳油轮中横剖面结构优化设计专家系 统”、“油船主船体隔舱划分的神经专家系统”、“内河排水型高速船稳性计算 专家系统”、“船舶设计咨询专家系统d e c e s 、“集装箱船中横剖面设计专家 系统”、“船舶动力装置c a d 智能化子系统 、“用于舰船推进装置方案设计 的c a d 系统”掣2 1 。 人工智能和专家系统在船舶设计领域的应用前景也很光明。目前，国内 外有很多专家学者都在进行这方面的研究工作。船舶管路系统的自动化布局 研究就属于船舶设计人工智能研究工作的一部分。人工智能技术的应用特别 是一些优化方法和一些启发式算法在船舶设计领域也进行了大量的研究n 蝴1 ， 6 哈尔滨工程大学硕上学位论文 推动了船舶设计中人工智能技术的向前发展，使计算机辅助船舶设计从数学 计算进入到知识信息处理和智能模拟的更高层次阶段嘲。 1 4 船舶c a d 技术发展现状 船舶c a d 技术的广泛应用与迅速发展对船舶设计n 造带来了巨大的影 响，逐渐改变了传统的船舶设计和制造方式，它是当前国际造船市场激烈竞 争的必要关键技术，在社会效益和经济效益上具有极大影响，它的发展水平 也代表了一个国家造船技术的发展水平和现代化程度圆。 随着经济全球化的发展，近年来世界货运和客运船舶的需求不断扩大， 世界的造船能力不断扩大，造船技术不断提高。从造船工业的未来发展方向 来看，现代造船技术正朝着机械化、自动化、集成化、模块化、智能化方向 发展。 上世纪9 0 年代以来，随着计算机硬件技术的迅猛发展，国际上各种先进 的船舶c a d c a m 系统取得了迅速的发展。到目前为止，世界著名的国外船 舶c a d c a m 软件主要有以下几款：( 1 ) 瑞典的k c s ( k o c k u m s c o m p u t e r s y s t e ma s ) 公司研发的一款辅助船舶设计、建造及信息集成的计算 机软件集成系统一r i b o n 软件系统；( 2 ) 西班牙s e n e r 公司开发的一款 针对船舶设计和建造的计算机软件系统f o r a n 软件系统；( 3 ) 法国 d a s s a u l ts y s t e m 公司开发的c a d c a e c a m 一体化软件c a t i a 软件系 统；( 4 ) 美国p t c 公司开发的一款功能齐全的通用机械三维c a d c a m 软件 叫a d d s 5 软件系统。 目前我国造船业在技术水平方面与日本和西欧还有很大差距。现阶段我 国造船业正处于产业结构调整期，各大船厂及相关单位正在大力开展技术创 新，加快提高船舶及船用装备的设计制造技术水平，我国造船业正在向开发 高技术、高附加值的船舶产品方向不断努力。计算机辅助设计( c a d ) 技术 可以有效地提高船舶设计的效率和质量，已经成为国内造船行业的共识，目 前国内大多数研究所和造船厂已经较大范围地应用了国际先进水平的3 d 造 7 哈尔滨1 = 程大学硕十学位论文 船软件。 我国造船行业自上世纪6 0 年代中、后期就开始了船舶c a d c a m 技术 的研究开发与应用工作，到现在，取得了一些重要研究成果，其中以中船总 公司组织开发的计算机辅助造船工程c a s i s i 系统和c a s i s i i 系统为主要 代表性成果。 在自行研制开发船舶c a d c a m 软件系统的同时，我国许多企、事业单 位也先后引进了t 砌b o n ，f o r a n ，c a t i a ，c a d d s 5 等先进的国外造船 c a d c a m 软件系统。这些软件系统的引进对促进我国船舶工业的发展、推 动我国船舶c a d c a m 技术的发展都起到了积极的作用。 1 5 遗传算法概述 1 5 1 遗传算法的提出及发展 遗传算法( g e n e t i ca l g o r i t h m ) 是模拟达尔文生物进化论的自然选择和遗 传学机理的生物进化过程发展起来的一种通用的问题求解的计算模型，是一 种通过模拟自然进化过程搜索最优解的方法，它最初是由美国m i c h i g a n 大学 j h o l l a n d 教授于1 9 7 5 年首先提出来的，并出版了颇有影响的专著( ( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) 2 4 oh o l l a n d 教授不仅提出了遗传算法的操作 原理，还运用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了 著名的s c h e m a 定理和隐含并行性( i m p l i c i tp a r a l l e l i s m ) 原理，为遗传算法的 发展奠定了基础口5 1 。d ej o n g 最早将遗传算法应用于函数优化问题，并对遗传 算法的性能做了大量的分析工作。 1 9 8 9 年，美国伊利诺大学的g o l d b e r g 在他的著作( g e n e t i c a l g o r i t h m s i n s e a r c h ，o p t i m i z a t i o n ，a n dm a c h i n el e a r n i n g ) ) 中对遗传算法理论及遗传算法 在各领域中的应用展开了较为全面的分析和例证。在这一时期，以遗传算法 为主题的多个国际会议在世界各地定期召开，有关遗传算法的学术活动、期 刊杂志纷纷出现，在机器学习、人工智能、神经元网络等学术会议上也都有 遗传算法专题，有关遗传算法的文章在国内外的各种期刊上频频出现，国际 8 哈尔滨工程大学硕卜学位论文 互联网上也出现多种相关的网页”。 随着遗传算法的应用领域不断扩大，对遗传算法的研究也出现了一些新 的动向凹：一是基于遗传算法的机器学习，这把遗传算法从以往离散的搜索 空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算 法。这一崭新的学习机制为解决人工智能中知识获取和知识优化精炼的瓶颈 难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论 等其它智能计算方法相互渗透和相互结合，这对开拓2 1 世纪新的智能计算技 术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究 不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都 是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断 渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生 物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在 这方面将会发挥一定的作用，五是遗传算法和进化规划( e v o l u t i o n p r o g r a m m i n g ，e p ) 以及进化策略( e v o l u t i o ns t r a t e g y ，e s ) 等进化计算理论 日益结合。进化规划和进化策略几乎是和遗传算法同时独立发展起来的，同 遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗 传算法具有相同之处，也有各自的特点。目前，它们之间的比较研究和彼此 结合的探讨正形成热点。 1 5 2 遗传算法的基本思想 遗传算法是一种随机搜索算法。与传统的搜索算法不同，遗传算法的优 化开始于一组随机产生的初始解，称为“初始种群”。种群中的每个个体是所 求问题的一个解，称为“染色体 。染色体作为遗传物质的主要载体，是多个 基因的集合，其内部表现( 即基因型) 是某些基因的组合，染色体决定了个 体的特性，这些染色体在后续迭代过程中不断进化，称为“遗传 。因此，在 一开始就需要实现从表现型到基因型的映射，即进行“编码”工作。由于仿 照基因编码的工作很复杂j 因此我们往往采取简化的方式，比如采用二进制 9 哈尔滨工程大学硕士学位论文 编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生 出越来越好的近似解，在每一代中，根据问题域中个体适应度的大小选择个 体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的 解集的种群。这个过程将导致种群如同自然进化一样，使其后代种群比前代 种群更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似 最优解。 1 5 3 遗传算法的特点 遗传算法是一种可应用于复杂系统优化计算的具有较好鲁棒性的搜索算 法，与其它传统的优化算法相比，主要具有以下特点1 ： ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直 接利用决策变量的实际值本身进行优化计算，而遗传算法是以决策变量的某 种编码形式作为运算对象。从而使得我们可以借鉴生物学中的染色体和基因 等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们能够方便 地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有 代码概念的优化问题，编码处理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数值或适应度值作为搜索信息，无需目标函 数的导数等其它辅助信息。这一特点使得对目标函数是无法或很难求导的函 数、以及导数不存在的函数的优化问题，应用遗传算法就显得很方便了。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息，具有隐含并行性。遗传 算法从初始种群开始最优解的搜索过程，后代群体包含了很多群体信息，相 当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。 ( 4 ) 遗传算法使用概率搜索技术，而非确定性搜索规则。遗传算法属于 一种自适应概率搜索技术，其选择、交叉、变异等运算都以一种概率的方式 进行，增加了搜索过程的灵活性。 1 5 4 遗传算法的构成要素 遗传算法一般由四部分组成口曰： 1 0 哈尔滨工程大学硕十学位论文 ( 1 ) 染色体编码方法：在遗传算法中需要将问题的可行解从其解空间转 化到遗传算法所能处理的搜索空间，这种空间转换的方法称为编码方法。编 码是应用遗传算法要解决的首要问题，也是应用遗传算法的关键操作步骤。 编码方法的优劣对遗传算法计算过程及运算效率的影响是非常大的，一种好 的编码方式会使算法操作简单可靠，并高效的完成运算过程；而较差的编码 方式可能会使遗传操作难以实现，也可能会在计算过程中产生各种无效的解， 当然，这些无效的解对计算并非都是无益的，但大部分情况下，这些无效解 会在很大程度上影响遗传算法的运行效率。 ( 2 ) 个体适应度评价：遗传算法采用“适应度”这个概念来度量种群中 每个个体在所求问题的解空间中的“适应程度”。度量个体适应度的函数称为 适应度函数。适应度高的个体遗传到下一代的概率就大，反之，适应度低的 个体遗传到下一代的概率就小。因此，必须首先确定好由目标函数值到个体 适应度函数值之间的转换规则。 评价种群中个体适应度的一般过程为p 6 1 ： 第一步：对个体编码串进行解码处理后，可以得到个体的表现型； 第二步：由个体的表现型可以计算出对应个体的目标函数值； 第三步：根据最优化问题的类型，由目标函数值按一定的转换规则求出 个体的适应度值。 以种群中个体的适应度值为遗传操作的依据，反复进行遗传操作的迭代 过程，不断地寻求适应度较大的个体，直到得到所求问题的最优解或近似最 优解，这就是遗传算法中种群的进化过程。 ( 3 ) 遗传算子：遗传算法的遗传算子包括三种基本类型：选择算子、交 叉算子和变异算子。它们构成了遗传算法计算功能的核心，是模拟自然界物 种进化过程中发生的繁衍、杂交、基因突变现象的主要载体。 选择算子：遗传算法以种群中个体的适应度函数值为依据，使用选择算 子对种群中的个体进行优胜劣汰的操作。选择算子的功能就是用来确定种群 中的个体是否能被遗传到下一代群体中以及在下一代群体中存在的比率。避 哈尔滨t 程大学硕士学位论文 免基因缺失、提高全局收敛性和提高遗传算法的计算效率是选择操作的主要 目的。 交叉算子：交叉运算是指将相互配对的两个染色体个体按照某种规则相