（船舶与海洋结构物设计制造专业论文）基于改进遗传算法的驳船配载方案优化研究.pdf

大连理工大学硕士学位论文 摘要 进入2 l 世纪，随着人类对海洋资源的开发利用，许多大型海洋结构物应运而生， 尤其是大型海洋平台。勘探和开采海底石油不能没有海洋平台，而大型海洋平台一般都 是利用驳船运输到作业地点然后下水作业。同时，驳船又是大型海洋结构物建造过程中 用来下水的实用工具。目前，国内外对驳船配载研究的不是很多，其相应技术发展还不 成熟，有待于对现有的成果进行改进。 大型海洋结构物在陆地上建造完工以后，其下水方式一般是通过驳船配载实现的。 其原理是通过不断调节驳船压载舱各舱的水量分布以改变驳船的浮态来实现驳船滑道 与码头滑道的对齐，从而把大型结构物拖拉上驳。海洋结构物上驳过程中的压载水调载 作业一般都是操作人员利用以往的经验完成，但是，这种方式对操作人员的依赖性很大， 作业过程效率不高，精确程度不够。 近年来大型海洋结构物不断增加，驳船配载的技术显得日益重要。为了更好地控制 产品上驳过程，一些基于驳船配载的优化方法相应诞生。本文便是在此工程背景下，利 用改进的遗传算法优化配载结果。研究内容中涉及到驳船浮态的计算、方案强度的校核、 遗传算法的改进及其效果的验证以及驳船配载方案的优选问题。驳船的配载主要是依据 静力学平衡原理和船舶基本知识对船舶浮态的调节。为了在较短时间内完成配载作业， 本文对遗传算法进行了改进，提出了种群全部交叉和分布式动态惩罚函数法等改进机 制，对驳船配载中的调载水量分布进行了优化。计算结果表明，改进遗传算法的配载方 案比基本配载方案时间更短、效率更高。运用本改进遗传算法对驳船配载进行方案优化， 能够满足工程要求、缩短上驳作业时间。 关键词：驳船；遗传算法；适应值；惩罚函数；配载 基于改进遗传算法的驳船配载方案优化研究 t h er e s e a r c ho fb a r g e sb a l l a s to p t i m i z a t i o nb a s e do ni m p r o v e dg e n e t i c a l g o r i t h m s a b s t r a c t w i t hm a r i n er e s o u r c e sb e i n ge x p l o i t e da n du t i l i z e d ，s o m el a r g em a r i n es t r u c t u r e s ， e s p e c i a l l yf o ro c e a np l a t f o r m s ，s t a r tt oc o m eo u ti nl a r g eq u a n t i t i e s e x p l o r a t i n gc r u d eo i lc a n n o td ow i t h o u to c e a np l a t f o r m g e n e r a l l y ，t h el a r g eo c e a np l a t f o r mi st r a n s p o r t e dt ot h ej o bs i t e a n dt h e nl a u n c h e do p e r a t i o nb yu s eo f b a r g e a tt h es a m et i m e ，t h eb a r g ei sau s e f u lt o o lw h i c hi s u s e dt ol a u n c ho c e a np l a t f o r m s a tp r e s e n t ，t h e r ea r el i t t l et h es t u d i e so nb a r g e sb a l l a s t ，a n di t s t e c h n o l o g i c a ld e v e l o p m e n t ，w h i c hi s n e e d e dt o i m p r o v e do nt h eb a s i so ft h e c u r r e n t a c h i e v e m e n t ，i ss t i l ln o tm a t u r e a r e rl a r g em a r i n es t r u c t u r ec o m p l e t i o n ，b a r g e sb a l l a s ti si t su s u a ll a u n c hw a y t h e p r i n c i p l eo fb a r g e sb a l l a s tc a nb ee x p r e s s e da sf o l l o w s ：i no r d e rt oa l i g nd o c k ss l i p w a ya n d b a r g e ss l i p w a y ，w em a yc h a n g eb a r g e sf l o a t i n gc o n d i t i o nb ym e a n so f r e g u l a t i o no f t h eb a l l a s t w a t e r u n d e rt h er e q u i r e df o a t i n gc o n d i t i o n ，o p e r a t o r sp u l lt h el a r g es t r u c t u r eo nt h eb a r g e f o r m e r l y ，b a r g e b a l l a s ti sc o m p l e t e dr e l yo no p e r a t o r s e x p e r i e n c e j u s tt h ed e p e n d e n c yr e s u l t s t oi n e f f i c i e n ta n di m p r e c i s e w i t ht h ei n c r e a s eo fl a r g em a r i n es t r u c t u r e si nr e c e n ty e a r s ，t h et e c h n o l o g yo fb a r g e s b a l l a s ti si n c r e a s i n g l yi m p o r t a n t f o rt h ep u r p o s eo fc o n t r o l l i n gt h ep r o c e s st h a tp r o d u c te n t e r o n t ob a r g e ，s o m eo p t i m i z a t i o na b o u tb a r g e sb a l l a s tc o m ei n t ob e i n g i nt h ec o n t e x to ft h i s p r o j e c t , t h i sp a p e rp r o p o s e san e ws o l u t i o nm e t h o dw h i c ho p t i m i z e st h er e s u l to fp r o g r a m t a k i n ga d v a n t a g eo fi m p r o v e dg e n e t i ca l g o r i t h m t h ec o n t e n to ft h i sp a p e rm a i n l yr e l a t e dt o f o l l o w i n ga s p e c t s ：t h e c a l c u l a t i o no fb a r g e s f l o a t i n gc o n d i t i o n ，s t r e n g t hv e r i f i c a t i o n ， i m p r o v e m e n to f g e n e t i ca l g o r i t h m ，a n dt h ep r o g r a mo p t i m i z a t i o na b o u tb a r g e sb a l l a s t b a r g e s s t o w a g ei sb a s e do na d j u s t i n gf l o a t a t i o nb ys t a t i c sa n db a s i ck n o w l e d g eo ft h es h i p i no r d e rt o c o m p l e t es t o w a g es o o n e r ，t h i sp a p e ra p p l y si m p r o v e dg a ，o p t i m i z i n gb a l l a s tw a t e r s d i s t r i b u t i o n ，w h i c hc o m e su pw i t ha l l - c r o s sa n dd i s t r i b u t e dd y n a m i cp e n a l t yf u n c t i o nm e t h o d a n ds oo n t h er e s u l t ss h o wt h a tp l a n sa p p l i e di m p r o v e dg aa r eb e t t e rt h a nb a s i cp l a n si nt i m e a n de f f i c i e n c y i m p r o v e dg at o o p t i m i z eb a r g e ss t o w a g e c a nm e e tt h ee n g i n e e r i n g r e q u i r e m e n t sa n d s a v et h ew o r kt i m e k e yw o r d s ：b a r g e ；g a ；f i t n e s sv a l u e ；p e n a l t yf u n c t i o n ；b a l l a s t i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 丝拿邀趁幽堡兰至塞巫至盗垒室鱼丝4 嘉 作者签名： 复缢塑 日期：兰型三年j 月一日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印，或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 大连理工大学硕士学位论文 1绪论 1 1 论文研究的意义和价值 随着国际形势的发展，能源已成了人们普遍关注的问题，陆地的能源有限，而海洋 中的能源还有待开采。近年来，国家站在长远发展的战略高度，对海洋资源的开发越来 越引起了重视并加大了力度对海洋石油进行钻探与开发，这就直接促进了对高科技的海 洋结构物的依赖和需求。关键的问题是，这些大型海洋结构物的建造过程一般都是在陆 地上完成，而其作业地点都是在海洋中。建造完工后，其面临的首要问题是如何托运到 海洋中的指定作业地点。一般来说，这些大型结构物本身没有漂浮能力，通常情况下， 如果结构物的重量比较轻，则可以采用浮吊的方法移运到船上。但是，对于重量较大结 构形式较复杂的大型海洋结构物，浮吊装运的方法则难以实现。因此，海洋平台组块等 大型海洋结构物施工过程的重要环节之一驳船配载技术日益收到人们的重视。该技术是 在驳船滑道与码头滑道对齐的情况下利用绞索车拖动大型海洋结构物使之平稳上驳的 方法。它取代了传统采用浮吊的施工方法，大幅度地降低了成本，但在驳船配载过程中， 随着结构物重心的移动和外界环境的变化，需要动态的测量、计算和调整控制驳船的压 载舱液位，计算过程涉及面广，该技术是一项作业难度较高的项目，直接关系到整个工 程的质量和成败。 一直以来，国内的大型结构物配载装船都是由技术人员依靠简单的工具现场检测潮 位变化以及结构物移动距离，通过这些参数计算出驳船的调载水量，指挥整个拖拉工程， 这种控制过程存在着多项的人为误差、测量误差以及不确定因素。一般来说，工程中是 测量驳船的六个角点的吃水或四个角点的吃水来估算目前驳船所处的漂浮状态，再根据 码头的高度计算出驳船能够进行上驳作业的相应浮态。由于在操作中，可能会产生驳船 的扭曲，所以估算出的平均吃水存在误差。本文认为，不管目前驳船吃水如何，只需知 道预配下一步时驳船能够作业的浮态即可，根据要达到的浮态与目前各舱的吃水以及驳 船和产品的参数就可以计算出下一步预配时各舱需要调节的压载水量。驳船配载的特点 是压载水调节量比较大，上驳的大型海洋结构物往往比较贵重，一旦发生事故就会造成 巨大经济损失。因此，保证驳船配载的安全是一项十分重要的工作。对于码头的潮水涨 落限制是本文工作考虑的重点，在工程项目中，有些码头的潮水涨落时间间隔较短，使 得结构物上驳作业的时间受到限制，也就是说必须在时间限制比较大的情况下完成驳船 的配载。如果配载作业时间内各舱配载方案不合理很有可能会导致作业时间较长而出现 驳船配载的危险情况。同时，如果配载方案不合理也会形成驳船的强度不满足要求，如 基于改进遗传算法的驳船配载方案优化研究 剪力弯矩过大、扭矩过大等等。另一方面，配载方案的制定是一项经验性很强的工作， 只有长期从事配载操作的人员才有可能快速地制定出令船方满意的配载方案。配载工程 中丰富经验的调度员很少，这势必影响驳船配载的质量。所以，科学地利用先进计算机 和传感器等技术进行调载水量计算、调节和实时测控，是十分有意义且必要的工作。这 可以有效地提高工程的质量以及可靠度，有利于提高驳船配载操作的科学性、安全性、 可靠性，对海洋工程有着重要的意义。 1 2 驳船配载现状及其发展趋势 驳船配载是大型海洋结构物施工过程的重要环节，该技术需考虑的因素很多，是一 项作业难度较高的项目，世界各国都对该操作的重要技术探索引起了重视。随着海洋石 油事业的蓬勃发展，海域开发己由浅海向深海迈进，海洋平台向着更高大的方向发展。 这些深海作业的大型海洋结构物的移运上驳对驳船配载技术的要求非常高。通常，海洋 结构物装船是采用浮吊吊装，但此方法只适应于中小型结构物，对于大型结构物，吊装 作业无法实施【l 】。为了解决大型海洋结构物的的配载装船问题，工程上专门提出了针对 这一现状的驳船配载技术。随着计算机技术在各行各业的发展与应用，基于计算机技术 的船舶配载系统产生了，目前，韩国、我国等一些掌握此技术的国家已在工程项目中应 用了。总的来说，该技术在工程作业上已取得初步成效，但其技术发展还有待完善，仍 有一些有待改进的地方。比如上文所说的作业时间受限的情况，就需要一个可靠实用的 配载算法。驳船配载作业主要利用上驳产品的信息以及驳船本身的信息和周边环境，通 过船舶静力学和船舶强度的基本原理进行计算，包括对船的浮态、稳性、强度的计算。 产品在配载过程中，一般是事先预测潮高以及上驳产品将要进入驳船的长度，然后 在理想状况下预算配载方案并按照预算方案对各舱进行调水操作，在极小的时间差之内 根据各舱调载水量的实际差别再进行人工干预配载。其中，产品上驳长度和各舱配载情 况应该是同步协调的。如果出现配载和上驳产品进入长度不协调，那么驳船的浮态将出 现变化，有可能会发生危险情况。所以，最理想的情况就是，结构物移运到驳船上的哪 一段，各舱配载量正好使得驳船的浮态满足能够进行上驳作业的要求。 由于结构物上驳作业过程是一个连续动态的过程，因此，配载过程中计算机系统会 实时记录并计算驳船的动态。根据测量的数据，时刻了解驳船的首尾吃水、纵倾、横倾 等浮态问题。关于浮态的计算，已经摒弃了传统的手工算法，而是根据船舶静力学原理， 利用曲线插值技术加密船体型线由计算机软件程序求解并输入到驳船舶配载的模块中。 这一方法解决了计算量大和难的问题，并且方便，基本满足了驳船配载工程的要求。 大连理工大学硕士学位论文 一般而言，驳船装载不需要进行强度校核，大部分情况下强度应该满足要求，但是 为了安全起见，最好也能够在计算浮态、稳性的同时，也实时地计算驳船的强度。强度 计算过去是传统的手工算法，速度慢，人为误差大。目前是应用船舶总纵强度计算原理 的知识采用计算机编写程序的方法，对驳船配载的过程中驳船状态进行总纵强度计算， 如果方案对应的强度太大，则取消该方案，对下一可行优选方案进行强度校核，直到找 到能够满足浮态和强度两方面的合理方案。在计算中，为了保证强度，一般会给出一个 强度储备系数，以保证船舶的安全。这种操作既提高了工作效率，又保证了方案的安全、 准确、合理。 国外的船舶配载研究的文献主要集中在集装箱船的配积载规划方面。从方法上讲， 可以归纳为六类：概率模拟方法、启发式方法、数学规划模型、专家系统、决策支持系 统和模拟进化算法【2 巧j 。 目前在国外，如挪威、美国、墨西哥等国家在驳船配载方面主要是通过不断地调节 驳船的压载水来实现海洋结构物的下水安装作业【6 。引。国外有芬兰的n a p al t d 公司开发的 o n b o a r d - n a p a 系统，瑞典的k o c k u ms o n i c s 公司开发的l o a d m a s t e r ，丹麦的m a r i n e a l i g n m e n t 公司开发的e a s e a c o n 系统等。国内如海洋石油工程股份有限公司的大型半潜式 驳船b h 3 0 8 先后成功地运用该技术根据及时潮汐完成了我国j z l 9 3 油田西区储油存箱、 s z 3 6 一l 海洋平台等的配载装船、海洋运输作业。国内外个人在配载的技术方面也对这一 问题进行了研究。y t y a n g 等i 别研究了一艘3 4 0 0 0 0 d w t 级f s o ( f l o a t i n gs t o r a g ea n d o f f l o a d i n gs y s t e m ) 的建造以及下水问题。采用“h y d r a u l i cj a c k i n gs y s t e m 对纵向强度 和挠度进行计算分析，确保操作过程中纵倾角不超过0 2 5 。，横倾角不超过0 2 。，有力 的保证了结构安全，为平地建造超大型海洋结构物提供了参考。a k u m i a w a n 等【lo j 以实 现导管架挠度和曲率最小而调水效率最高为要求，将导管架平台上驳看作是位于弹性基 础上的梁型，通过建立挠曲线方程，运用多目标的优化方法对平台上驳过程进行了方案 优化分析。在专家系统的研究方面，王照宁等【li 】对集装箱自动配载提出了将专家系统与 管理信息系统相结合，由低级向高级转化的方案。杨掣1 2 】联系实际情况给出了散货船配 载专家系统知识库、推理机的设计方案，同时提出了利用效用矩阵实现货物自动调整的 方法。简兆权【1 3 1 等将人工神经网络和专家系统结合探讨了神经网络专家系统在货船配载 系统中的应用。成鹏飞【1 4 】等针对宝钢水运业务人工配载的低效率问题，通过分析货物的 装船原则，并结合船舶对强度、稳性、装载量等的要求，开发了一套船舶配载专家系统， 取得了良好效果。刘勇 1 5 1 等运用模糊数学理论并结合专家系统理论开发出了一套船舶配 积载模糊优化专家系统，实现了货物的准确、快速和合理配载，并能快速绘出配积载图。 张维英【1 6 】以集装箱船全航线配载研究为主线，使用智能优化的算法与技术，提出了求解 基于改进遗传算法的驳船配载方案优化研究 配载问题的一些新方法。车鉴【l7 】等从提高设备效率出发，提出了新的思路和方法，即在 预配载图限制的基础上，建立了一个整数线性规划模型，将堆场上集装箱组最为合理地 分配到船上单元块。孙静【l8 】等从船舶最佳纵倾航行节能原理出发，进行了船舶最佳纵倾、 压载及其配载的定量计算，运用实船证明了该方法的节油率可达到2 3 。邱文昌i t 9 1 等将编制船舶最佳压载方案看作一个多目标决策问题，给出了编制最佳压载方案的基本 原理，提高了用户的操作效率。张权松【2 0 】利用船舶调载水舱的储水实时调驳来控制船舶 在航行途中配载变化引起的横向倾斜，从而保证了船舶的航行安全。在气囊移运方面， 冯章烈2 1 】等对气囊拖运技术在港口工程上的应用进行了研究。刘亚东【2 2 】等介绍了气囊搬 运沉箱的技术，给出了气囊牵引力的计算公式以及气囊型号和数量的选择方法，为配载 的施工提供了技术参考。胡恩纯【2 3 】等以“四航东南 浮船坞移运沉箱搭接上坞为例，运 用工程力学理论对出运过程中浮船坞的调水进行了量化分析，考虑了气囊移运时浮船坞 离散受力的特点和潮位变化的影响。另一方面，针对出运过程中的搭接头受力进行了定 量计算，降低了以往在搭接头安全上主要凭经验的定性分析的风险。杜嘉立【2 4 】等提出并 开发了船舶的自动配载程序，并给出了满足相关规范、公约要求的船舶稳性、浮态、强 度等指标的计算结果。杨久青【2 5 】论述了计算机辅助配载的方法，通过该配载系统可以对 手工油轮配载方案进行浮态、稳性及强度的计算和校核。郭昌捷【2 6 】等通过合理地控制油 船配载方案和配载顺序，预报可能的危险状态或配载禁区，有效地解决了油船由于老龄 化带来的剩余强度降低问题。周丰【27 】提出在船舶配载工作中，以按货票配载取代按货种 配载的观点，建立了货物配载的优化模型，并根据配载工作的特点，给出了改进的k o l e s a r 算法。章青及其学生么子云等【2 2 】对驳船配载进行深入的研究。通过自动化及优化技术， 对大型结构物滑移装船过程进行了优化控制。同时，还对滑移装船进行了技术仿真，很 好地实现了滑移装船过程中驳船稳性、浮态及压载水的调控。朱崇诚 3 3 】在强度计算方面 对总重超过8 0 0 0 t 的大型海上平台装船过程的几种危险状态进行了有限元分析，并提出 了多项符合工程实际的解决方案，从而保证上驳过程的结构安全性。 综上，国内外目前对驳船配载已经有了包括方案优化、强度考虑等在内的一些方面 的研究。不过，这些单位和个人都没能很好地解决驳船智能装载的问题，也没有考虑在 特定的作业要求下，对驳船配载的研究，比如，配载作业要在较短时间内进行、由于驳 船强度不是很好要求每一步配载都要对驳船方案进行强度优化等等。目前，大型结构物 的上驳速度是人为控制的，这存在很大的随机变动性，所以在程序控制中无法实现，如 果能够完全依靠自动装置控制大型结构物的上驳速度，将能够大大得有利于驳船配载的 自动控制。 大连理工大学硕士学位论文 1 3 论文研究目标 目前，国内外研究驳船配载的不是很多，一般所做的工作都是仅满足工程现状的要 求。而且，在现场复杂的情况下，面临多变的因素，工程中的解决方法有时候可能会面 临没有解决方案的情况，这不得不再次依赖工作人员的经验加以指导。所以编写一个好 的驳船配载的算法尤为关键，在各种方案中找出一个满足工程要求且合理的方案十分重 要。本论文研究的是应用改进遗传算法对驳船配载的方案进行优化，在众多的可行方案 中找到每次配载的最佳方案，以合理满足工程要求为目标。 1 4 本文研究内容和方法 为了保证驳船配载操作的安全和质量，实现上驳产品配载过程的稳定，提高驳船配 载的科学性、安全性、可靠性。本文研究的内容主要包括以下部分： ( 1 ) 驳船配载过程中，驳船的浮态是主要研究的内容。由于配载时驳船浮态属于小 倾角稳性，而且装载时都是选择比较好的气候环境，风浪流对驳船的影响很小。因此， 基于工程上可靠实用、计算方便的原则，使用静力学理论分析驳船的受力状况，使之满 足“双零原则，即力和力矩的合矢量都为零。 ( 2 ) 本文研究的驳船配载优化目标是在最少的时间内完成结构物的上驳作业。其优 化方法为改进的遗传算法，在对待约束的处理上本文提出了一些新的处理方法。遗传算 法中，本文除了利用已有的改进机制，还自行提出了一些经计算验证较好的遗传机制。 ( 3 ) 最终方案的确定是以程序模块的形式来完成，这就要求有一个良好的用户界面， 以便工作人员能够方便、灵活地应用，该部分主要用v i s u a lb a s i c6 0 程序语言作为基础 来实现。利用改进遗传算法机制在所有可行方案中找到一个最合适的方案作为最终配载 方案，如果不满足要求，就从次方案中选择，直到满足要求为止。 基于改进遗传算法的驳船配载方案优化研究 2 遗传算法原理 2 1 遗传算法概述 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 起源于对生物系统所进行的计算机模拟研究。 美国m i c h i g a n 大学的h o l l a n d 教授及其学生受到生物模拟技术的启发p 钔，创造了一种基 于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术遗传算法。后 人基于遗传算法的思想在计算机上进行了大量的优化计算实验，得到了一些重要且具有 指导意义的结论。经过遗传算法在科学计算、工程技术和社会经济中的反复实践，大量 的实例证明遗传算法是一个可靠有效的计算方法，有着传统方法不可比拟的优化特性。 特别是近年来，迅猛发展的遗传算法赢得了许多学者们的青睐，人们对遗传算法的应用 越来越多，也越来越广。 2 1 1 遗传算法特点 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优 化概率搜索算法，它与传统的优化方法不同，不依赖于梯度信息，能在搜索过程中自动 获取和积累有关搜索空间的知识。 ( 1 ) 遗传算法的优点 遗传算法以自变量的编码作为运算对象。传统算法往往直接利用自变量的实值 进行优化计算，而遗传算法以独特的方式，对自变量进行了编码处理，在计算过程中借 鉴生物学的遗传变异法则，使自变量自动朝着目标函数更好的方向发展。 不要求目标函数可导连续。有些优化方法，要求目标函数可导连续，但是有些 问题的目标函数没有这些特性，不利于求解，而遗传算法没有这些辅助信息的限制，所 以遗传算法的应用空间更为广阔。 遗传算法具有和其他技术兼容的特性，本文当中就采用了遗传算法和惩罚函数 法并用的混合算法。因此，它能够吸收其他一些算法的优点对自身算法加以补充完善。 能够多点搜索。传统的优化算法往往是逐点搜索，容易陷入局部极值。遗传算 法是多点并行搜索，一般不会陷入局部极值，有着很好的全局收敛性。 搜索方法的优越性。一般的优化方法搜索机制比较繁琐，有些还需要计算导数 值，每步搜索都有着复杂的函数判别，而遗传算法直接利用目标函数进行信息搜索，不 需要其他的辅助信息，有利于复杂问题求解，提高了搜索效率。 ( 2 ) 遗传算法的缺点 大连理工大学硕士学位论文 编码方法虽能解决自变量约束问题，但不能把等式约束和不等式约束表达出来， 对这两种约束的不可行解都采用阈值处理，这必然会增加搜索时间，降低搜索效率。 遗传算法中，如果算子处理不好容易过早收敛，而且往往是局部收敛。 2 1 2 遗传算法的应用领域 遗传算法在求解比较复杂问题有一定的优越性，且应用领域比较广泛。它虽是一门 比较前沿的技术，但发展却非常迅速。主要的应用领域有以下几个方面： ( 1 ) 函数优化 ( 2 ) 组合优化 ( 3 ) 生产调度问题 ( 4 ) 自动控制 ( 5 ) 机器人 ( 6 ) 图像处理 ( 7 ) 数据挖掘 ( 8 ) 信息战 ( 9 ) 生命工程 遗传算法在人们的应用研究中逐步趋于稳定，尤其是对于比较复杂的问题，使用遗 传算法运算的效果更能体现其优越性。 2 2 基本遗传算法 2 2 1 遗传算法术语 遗传算法是模拟遗传科学而形成的新的计算方法，所以，在遗传算法中会出现与生 物遗传相类似的遗传术语，现分别介绍如下： ( 1 ) 基因。基因是遗传的基本单位。 ( 2 ) 基因座。基因的位置称为基因座。在编码串中表现为每个码所在的位置。 ( 3 ) 等位基因。基因所取的值叫做等位基因。为编码串中每个基因的特性值。 ( 4 ) 染色体。染色体是遗传物质的载体，它决定了生物的性状。生物遗传中，染色 体一般都有两条链条，而在遗传算法中，每条链条就表示一个染色体。 ( 5 ) 种群。生物的进化是以集团的形式进行的，这样的进化团体称为种群。遗传操 作是以种群为作用对象，并按照遗传法则搜索出新的种群。种群的大小决定了生物进化 的规模，也影响了进化速度和进化精度。 ( 6 ) 个体。组成种群的单个解称之为个体。 基于改进遗传算法的驳船配载方案优化研究 ( 7 ) 适应度。每个个体对环境的适应能力称为个体的适应度。具体问题中表现为个 体目标函数的好与坏。 2 2 2 遗传算法模型 基本遗传算法只包括选择算子、交叉算子、变异算子3 个基本遗传算子，在选定了 初始种群后，按照3 个遗传算子和适应度的评价，不断地对种群进行进化计算。基本遗 传算法的数学模型可表达为式( 2 1 ) 所示： s g a = ( c o a e ，f i t n e s s ，p o p o ，p o p s i z e ，s e l ，c r o s s ，m u m ，刃( 2 1 ) 式中，o 比表示个体的编码方法，f i t n e s s 表示个体适应度评价函数，p o p o 表示初 始种群，p o p s i z e 表示种群规模，s e l 表示选择算子，c r o s s 表示交叉算子，m u t a 表示变 异算子，丁表示算法终止条件。该模型的执行流程图如图2 1 所示： 图2 1 遗传算法简单流程 f i g 2 1s i m p l eg e n e t i ca l g o r i t h mp r o c e s s 大连理工大学硕士学位论文 由上图可见，基本遗传算法程序简单，容易理解。对于一个求函数最大值的优化问 题，一般可描述为( 2 2 ) - - - ( 2 4 ) 所示的数学规划模型： m a x 似) s 1 x r 天u ( 2 2 ) ( 2 3 ) ( 2 4 ) 上式中，胙o l ，x 2 ，为决策变量，氕的为目标函数，式( 2 3 ) 、( 2 4 ) 为约束条 件，u 是基本空间，r 是u 的一个子集。满足约束条件的解x 称为可行解，集合r 表示 由所有满足约束条件的解组成的一个集合，叫做可行解集合【3 5 】。其中，对于约束条件仅f x 琅) 的一般表述为( 2 5 ) 和( 2 6 ) 所示【3 6 1 ： 晶b ) s 0f = 1 , 2 ，p( 2 5 ) 吃= 0 = 1 , 2 ，g ( 2 6 ) 式( 2 5 ) 统称为不等式约束，式( 2 6 ) 贝j j 统称为等式约束。对于式( 2 4 ) 的约束条件一般 表述为式( 2 7 ) ： 儿f t u 互 1 f s 刀 ( 2 7 ) 式( 2 7 ) 中，儿，为自变量的下限，u l ，为自变量的上限，刀为自变量个数。 对于约束条件下所求解的最大值( 最小值同理) 的优化问题按照等式约束、不等式约 束以及自变量范围的不同大致可以分为下面四种类型： ( 1 ) 所求问题中除了自变量范围的约束