（计算机软件与理论专业论文）一种型材优化下料方法的研究与应用.pdf

分类号： udc 密级： 编号： 一种型材优化下料方法的研究与应用 ac u t t i n g0 p t i m i z i n gp r o f i l er e s e a r c ha n d a p p l i c a t l 0 n 学位授予单位及代码：篮蚕理王左堂f ! q ! 竖2 学科专业名称及代码：让簋扭挞性曼理i 垒l 盟1 2 丝2 研究方向；智能熬鲑申请学位级别：亟 指导教师： 董迸 研究 生：趋垂夔 论文起止时间：2 0 0 7 11 - - 2 0 q 壁。塑 摘要 随着国民经济的飞速发展，一维下料问题在建筑、电力、水利等领域获得了越来 越广泛的应用。寻找一种最优的下料方案，不仅可以节省原材料，降低生产成本，而 且能够为企业带来直接的经济效益，促进国民经济的健康发展。因此，开展对一维下 料问题的研究具有重要的理论意义和工程应用价值。 本文在对遗传算法进行分析和研究的基础上，把遗传算法用于一维下料问题的求 解。根据不同类型的下料问题设计了多种方案，并取得了较好的数值结果。 论文首先介绍了一维下料问题的研究概况，描述了遗传算法的基本原理和方法， 分析了遗传算法的编码、适应度函数、交叉和变异算子在整个遗传算法的运算过程中 的作用。对用遗传算法解下料阀题进行了系统研究。设计了一种新的改进的混合遗传 算法，针对库存材料种类的不同，提出了相应的遗传算法。本文采用了最优保存策略 来保持种群中的优良个体，使得产生的遗传算法更加有效。最后，本文对两种方案的 遗传算法进行了数值试验，结果表明新算法能更有效地求解一般下料问题。 关键词：一维下料问题遗传算法交叉算子变异算子 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn a t i o n a le c o n o m yi nr e c e n ty e a r s , t h eo n e - d i m e n s i o n a l c u t t i n gs t o c kp r o b l e mo c c u r si nm a n yi n d u s t r ya r e a s l o o k i n gf o ra l lo p t i m u mc u t t i n g s o l u t i o n nn o to n l ys a v er a wm a t e r i a l sa n dd e c r e a s ep r o d u c tc o s t , b u ta l s ob r i n gt 0 i m m e d i a t ee c o n o m i cb e n e f i t sf o re n t e r p r i s e sa n da c c e l e r a t et h ed e v e l o p m e n to fn a t i o n a l e c o n o m y s or e s e a r c ho nt h ep r o b l e mi so fi m p o r t a n c ei nt h e o r ya n d 删 i nt h i sp a p e ro nt h eg e n e t i ca l g o r i t h ma n a l y s i sa n dr e s e a r c ho nt h eb a s i so ft h eg e n e t i c a l g o r i t h mu s e df o rc u t t i n go n e - d i m e n s i o n a lp r o b l e ms o l v i n g a c c o r d i n gt ot h ed i f f e r e n tt y p e s o f c u t t i n gi s s u e sd e s i g nav a r i e t yo f p r o g r a m s ，a n da c h i e v e da b e t t e rn u m e r i c a lr e s u l t s t h i sa r t i c l ef i r s ti n t r o d u c e dt h eo n e - d i m e n s i o n a lc u t t i n gi s s u e sr e s e a r c h , d e s c r i b e dt h eb a s i c p r i n c i p l e so fg e n e t i ca l g o r i t h m sa n dm e t h o d so fa n a l y s i so ft h eg e n e t i ca l g o r i t h ma d d e ， f i t n e s sf u n c t i o n , a n dc r o s s - m u t a t i o ni nt h eg e n e t i ca l g o r i t h mo ft h ee n t i r eo p e r a t i o np r o c e s s i nt h i sp 乏i p e bt h e nu s et h eg e n e t i ca l g o r i t h mo f fm a t e r i a li s s u e so fs y s t e m an 伽i m p r o v e d h y b r i dg e n e t i ca l g o r i t h m , f o rd i f f e r e n tt y p e so fm a t e r i a l s ，i n v e n t o r y , t h ec o r r e s p o n d i n g g e n e t i ca l g o r i t h m i nt h i sp a p e r 9t h eo p t i m a lp r e s e r v a t i o ns t r a t e g yt ok e e pt h ep o p u l a t i o ni n t h e f i n ei n d i v i d u a l sh a v eag e n e t i ca l g o r i t h ma l l o w sm o r ee f f e c t i v e f i n a l l y , t w oo ft h e g e n e t i cp r o g r a mo ft h en u m e r i c a la l g o r i t h mt e s tr e s u l t ss h o wt h a tt h en e wa l g o r i t h mc a n e f f e c t i v e l ys o l v et h eg e n e r a lp r o b l e mo f c u t t i n g k e yw o r d s ：o n e - d i m e n s i o n a le u t t i n gs t o c kp r o b l e m , g e n e t i ea l g o r i t h m s ，c r o s s o v e r , m u t a t i o n l i 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，一种型材优化下料方法的研究与应用 是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用 的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本 声明的法律结果由本人承担。 作者签名：翅三鍪兰丝年二月丝日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版权使 用规定”，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕士学位论文 全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学位论文的复印件和 电子版，允许论文被查阅和借阅。本人授权长春理工大学可以将本学位论文的全部或 部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇 编学位论文。 作者签名：塑墨登丝2 年三月盟日 指导导师签名： 瞳月斗日 1 1 引言 第一章绪论 随着国民经济的飞速发展，下料问题在机械、电力、水利、航空航天、商业、国 防等领域获得了越来越广泛的应用。人们从不同的具体应用、不同的角度、采用不同 的方法对其进行了研究，提出了各种各样解的标准和算法。正是由于下料问题应用的 广泛性与其求解的难度，吸引了众多学者的研究。在1 9 8 8 年的e u r oi x t i m s ) ( ) ( c i i 国 际会议上，专门成立了下料问题兴趣小组s i c u p i ( s p e c i a li n t e r e s tg r o u po nc u t t i n g a n dp a c k i n gp r o b l e m ) 。 下料问题可以分为三大类：材料的切割问题( t r i ml o s sp r o b l e m 或c u t t i n gs t o c k p r o b l e m ) 、排样问题( a s s o r t m e n tp r o b l e m ) 和装箱问题( b i np a c k i n gp r o b l e m ) 。 材料的切割问题如型材、棒材的下料，建筑业中钢筋、铝合金的下料，家具制造 业中板材的下料；排样问题如印刷业中各种书刊、报纸的排版，微电子工业中集成电 路的排布；而物流业中的集装箱装货，即如何将货物优化地装入有限空闻的集装箱中 则属于装箱问题。 就材料的切割问题而言，根据原材料和零件的维数。又可以进一步划分为一维下 料问题、二维下料问题、三维下料问题等。一维下料问题指的是型材、棒材的下料， 二维下料问题则主要指板材的下料，三维下料问题是指原材料和所下零件的长、宽、 高均有特定要求的情况。 应该采取什么样的下料方案，使得既满足要求，又使下料后的剩余边料总长最小， 从而使材料利用率最大，达到减少材料损失，降低成本，提高经济效益的目的，这就 是所谓的一维最优下料闯题。 1 2 课题的目的和意义 i 2 1 课题研究的目的 近年由于消耗的型材数量巨大，涉及大量的一维优化下料问题。一维优化下料问 题一般描述为n 1 ：在一定数量的给定长度的原材和不定长的余料上，如何以最省料的方 式切割出所需数量的各种长度的成品。然而现行的解决方法主要为利用传统的人工经 验方法来处理此类问题，一般的人工下料法是在给定的原材上先切割出长度最大的零 件，然后在剩下的零件中切割出可能的最长零件，依次切割，直至最后无法切割出任 何一种规格零件为止，剩下的边角余料就当废料处理。这种人工下料方法除浪费十分 惊人外，下料计算复杂，耗费工程技术人员的大量精力，并且容易下料出错。即使是 由最有经验的工人师傅下料，材料的利用率也只能达到8 0 。也有一些应用行业采用计 算机辅助下料，但是所用的算法和人工下料法基本一样，原材料利用率并没有得到明 显改善，仅仅是提高了工作效率。 下料与排列问题对于切割制造工业而言是相当的重要的，一个好的下料算法，可 以增加原材料的使用率，降低材料的成本，当材料成本降低，相对的其价格的弹性空 间将变大，进而增加企业的市场竞争力。 论文的选题以企业的实际工作需要为背景，以降低企业原材料成本，提高生产效 率为主要研究内容。通过对一维线性材料切割下料问题的综合分析，利用科学的方式， 建立理想的下料计算模型，并使用遗传算法和启发式算法解决材料利用率优化问题。 当库存中有余料时先解决余料问题，以达到减少库存中余料的积压的效果。并期望最 终解能够达到使材料利用率最高、材料浪费量最小的目的，进而使本研究能够在生产 制造企业中得到实际应用。 1 2 2 课题研究的意义 下料问题之所以激起了许多研究者的兴趣，其中一个重要原因是他具有广泛应用， 并能直接产生经济效益。因为一种好的切割方法不仅可以节省原材料而且可以快切割 速度，直接给企业带来效益，促进国民经济的健康发展。 一维下料问题是组合优化中一个经典问题，从计算复杂性上看属于n p - h a r d 问题。 对小规模的下料问题，一般用线性规划、动态规划、分支定界法求解得到全局最优解。 而对于大规模的下料问题嘲嘲，不能找到全局最优解，一般用遗传算法，启发式算法 找到近似最优解。因此手工下料不能得到真正的最优解，即使采用计算机也必须开发 高效的算法才能实现利用率相对高的优化下料。目前的下料算法很多瑚伽，他们存在 的主要问题是计算时间和空间随下料品种数增加呈指数增长。 下料利用率的高低是影响企业经济效益的重要因素之一，这是由于下料的复杂性 决定的。决定材料利用率的主要因素有三个：( 1 ) 生产组织上由企业的管理水平决定 的；( 2 ) 技术上是由下料的科学性决定的；( 3 ) 生产上由加工工艺决定。所以提高原 材料利用率问题是一个系统工程问题，需要从生产管理、优化下料、决策支持等方面 提供完备的一体化解决方案。其中优化环节中，构造有效的优化算法是关键。 论文采用余料优先的算法，从宏观上来讲，是有效解决企业整体原材料利用率的 有效方式，能使企业在加工不同批次的产品的时候，达到使原材料整体利用率最优， 2 显著降低企业生产成本；从时间上，可以把需要加工的产品分成若干个批次，然后再 进行计算，能解决计算时间随下料品种数增加呈指数增长的问题。 1 3 国内外研究现状 l - 3 1 国外研究现状 二十世纪以来，随着工业技术突飞猛进的发展和资源的日趋紧张，各行业对节约 逐渐重视。人们开始考虑在“下料一这一环节尽可能地使能源得到充分的利用。第二 次世界大战以后，由于军事上的需要，使得运筹学和最优化的技术迅速发展和完善， 这给下料问题的研究提供了理论基础。 国外有关下料闯题的研究起步较早。第一个下料问题的著名模型是前苏联经济学 家k a n t o r o v i c h 于1 9 3 9 年提出用线性规划方法研究下料问题嗍，但采用解乘法来求解， 方法很不完善，得到的解不能保证为最优。 由于既是整数解又是最优解的答案在实践中很难得到，许多求解近似解的启发式 算法也被广泛应用嘲。h a e s s l e r 在1 9 7 1 年提出了顺序启发式方法，主要思想是：首先 计算剩余下料任务：寻求满足损耗小、下料模式少、耗材少等目标的下料方案：一旦找 到，按该方案尽可能多地完成剩余下料任务：并重复以上两个动作，直到下料任务全部 完成。这一方法的关键在于最初确定下料方案时，不仅要考虑降低材料损耗，提高原 材料用率，还要考虑如何使剩余下料任务有利于后期下料模式的生成。典型的s h p 方 法有，“最先适用一f f d ( t h ef i r s tf i td e c r e a s i n g ) 和“最好适用一b f d ( b e s tf i t d e c r e a s i n g ) 具有代表性的是h a e s s l e r 予1 9 7 5 年提出的“在一维切边问题中控制切 边方式的改变 的思想a b e a s l e y 于1 9 8 5 年通过一个启发式算法，依据一个复杂的切 割模式生成过程和线性规划，解决了侧刀切割问题中的多板片情况。 h a r l dd y c k h o f f e 5 ，于1 9 8 1 年指出，g i l m o r e 和g o m o r e y 给出的l p 模型并不适用 于所有的下料问题。针对母材与子材数量都很多的实际生产情形，他给出了一个新的 数学模型。这个模型同时适用于边角余料可以放入库存，再次利用的情况。并于对于 一维的下料问题提出了经典算法n 们，它将这类问题分为两类：项目导法( i t e m - o r i e n t e d ) 和式样导法( p a t t e r n - o r i e n t e d ) 。 f a r l e y 于1 9 8 8 年提出一个g i l m o r e - g o m o r y 延时模式生成方法的改进方法。另外， 还有随机搜索的启发式方法( j a n t o n i o ) ，包含两个目标函数在动态规划基础上产生 模拟退火启发式方法( c h u e n - l u n gs c h e n ) n 1 1 ，一种改进的启发式方法禁忌搜索。该方 法通过惩罚或禁止一些路径的搜索可以避免对解的重复枚举。 d a g l i 和c i h a n 于1 9 9 0 年采用模拟退火技术求解了排料问题他采用能量函数表达 了覆盖排料模式所需矩形面积，各模式之间的相似程度，和各模式之间的重叠面积u 幻。 w a e s h e r 于1 9 9 0 年对实际生产中的下料问题建立了数学模型n 小h 1 ，该模型同时考 虑了多个生产目标。他首先将这些目标公式化，然后指出该模型采用多准则决策机制 求解。 v a s k o 等于1 9 9 3 年给出了求解实际生产中下料问题的算法。该闯题产生于钢材工 业。原材料不能够直接用于子材的生产，而是需要在生产子材之前很短的时间内，在 另一个车间加工出来。因此母材的长度数据事先是未知的，只有在子材生产前的很短 的时闻内才能够得到。他们采用的算法是基于p c 机上的分支定界算法n 朝。 c h a u n y 和l o u l o u 于1 9 9 4 年给出了一个基于线性规划方法的多母材下料问题的求 解过程。他们首先采用一个特殊的启发式方法对问题的线性规划解进行舍入求整。然 后采用分支定界的办法对其整数解进行改进。v a n c e 等于又1 9 9 4 年采用列生成和分支 定界技术解决了一类二进制下料问题，得到问题最优整数解n 引。 c h e n 于1 9 9 6 年等采用模拟退火的技术求解一维下料的整数规划问题n 刀，r i c h a r d 对一维下料问题给出了一个随机的求解过程。首先在顺序启发式算法中，每次通过2 0 0 次随机实验生成下一个下料方案。生成一个下料方案后，给出该方案的适应度，采用 遗传算法中的交叉技术，保留较好的下料方案。 s c h o l l 予1 9 9 7 年结合了禁忌搜索和新的分支定界策略求解了著名的一维装箱问 题n 砌，该方法被称作b i s o n 方法。 1 9 9 9 年c h u 尝试着将动态规划方法运用到下料问题求解n 阳。并指出采用这种方法 只能对极小规模的下料问题精确求解。他同时给出了一个启发式动态规划方法对大规 模问题求近似解，其思想与s h p 有一定的相似之处，数值实验结果表明该算法实际运 行情况良好。有效解决了一类多目标多准则的一维下料问题。这表明，一些好的传统 优化算法，可以加以改进创造性地应用到下料问题的求解中去。 f r a n c o i s 于2 0 0 0 年给出了机器重设置时间最小问题的数学模型，该模型有多个变 量及相应数目的列。其中每个变量都对应着一个多背包限定问题。他采用分支定界的 方法给出问题的精确解嘲。 l e u n g 于2 0 0 1 年采用遗传算法与模拟退火相结合的技术解决了一类非闸刀式切割 的二维下料问题。并对给定的若干例子进行了数值实验。实验结果表明，与另外两个 启发式法方法相比较，该算法更为有效恤u 。 z a k 于2 0 0 2 年建立了线性规划数学模型求解多阶段下料问题，其中除了最后一个 阶段以外每一阶段都生成的是中间件，中间件的尺寸可以事先给定也可以随机产生。 闯题的目标是使完成生产任务所需中间件的数量最少。他采用了行列生成的技术求解 该问题嘲。 b e l o v 结合c h v a t a l - g o m o r y 的割平面方法与列生成技术对一维下料中多种原材料 4 长度问题进行了求解嘲。 l3 2 国内研究现状 近年来，随着计算机和优化技术的发展，人们对于一维下料问题的研究也在不断 深入。不少学者采用智能优化算法来解决下料问题，已经取得了初步的成果。针对不 同问题的特点，测试和分析算法的性能，研究如何利用多种算法成为下料问题研究的 一个重要方向。 国内对于排样问题的研究始于2 0 世纪8 0 年代，主要集中在高等院校和研究所。 对冲裁件排样从2 0 世纪8 0 年代开始研究，以华中科技大学、上海交通大学的工 作最有代表性，主要有人机交互法、边界加密方法和不相交判别法等，借助人机交互 方式进行图形的旋转和平移以达到优化排样的日的。围绕着冲裁件自动排样，采用将 零件处理为多边形的方法或采用碰撞算法直接对零件进行排样嘲。 对矩形件排样的研究始于2 0 世纪9 0 年代主要采用启发式算法，动态规划，整数 规划方法，g a ，s a 算法进行求解。 近几年来，国内学者开始对异形件排样问题进行研究。从算法看，主要是采用一 定规则将异形件处理为矩形，按矩形件排样方法进行排放；采用基于图形运算的移动 算法、碰撞算法，基于规则、样图的方法、神经网络方法基于学习的遗传算法等进行 求解嘲嘲嘲。 国内学者对于二维排样问题主要采用启发式算法及遗传算法进行求解例。以相同 尺寸的物体布局为研究对象，将约束处理加入启发式规则中，提出关于约束底盘装载 问题的启发式方法；采用遗传算法对装箱问题进行求解。 众多学者在研究排样算法的同时也开发了一些排样软件，从早期的交匀排样到自 动排样，排样系统也在随着排样算法研究的深入而发展。华中科技大学最早开发了冲 裁件排样系统；曹炬例推出了一维优化、矩形件排样、异形件排样的优化排样系统软 件，查建中对集装箱装运问题进行研究和开发。 与国外相比，国内关于排样问题的研究无论是在深度上和广度上都有差距，好在 很多学者己经意识到该问题的研究价值，日前排样问题已成为国内学者研究的一个热 点。 5 1 4 论文主要研究内容及结构安排 1 4 1 主要研究内容 根据原材料的供应情况，此类问题可简单归结为下列三种基本类型，其他情况一 般可看作这三种基本类型的复合和变型。 ( 1 ) 等长原料下料。即所有构件可通过一种规格的原料截得，原料数量无限制。 ( 2 ) 不等长原料下料。即构件可通过几种规格的原料截得，各种规格的原料均有 数量的限制洲。 ( 3 ) 随机长度原料下料。即原料长度分布无规律，边测长，边截切。 本文主要讨论第一种，第二种类型的一维下料问题，即等长原料下料和不等长原 材料下料的情况。 论文主要采用遗传算法与启发式算法相结合的方法，找出塑钢类型材的最佳下料 方案。首先，针对需要处理的型材和要制作的成品进行需求分析，根据需求情况进行 模块划分，需求分析按照面向对象的方式的方法来完成，模块划分要有针对性。其次， 在需求分析的基础上进行系统框架的搭建，即根据模块划分，确定系统流程，并协调 各模块之间的相互关系，以及主从情况，完善各模块的主要功能。第三，软件设计阶 段，其基本思想是利用遗传算法在全局寻优问题方面的优势，搜索塑类钢型材的原材 料可能下料方案，再用启发式思想对其个体进行编码和解码；根据材料利用率的信息， 来评价型材的下料方案的好坏；用遗传操作的进化能力搜索出更好的塑钢类型材的下 料方案；用自适应算子改进遗传操作的进化能力。按上述方法进行反复操作一定代数 后，找出塑钢类型材的最佳下料方案。根据前面的算法确定需要采用的软件技术，并 进行环境构建和程序设计，最终完成代码的编写。最后，对完成的软件进行相应的测 试，对不完善的地方加以修正和改进，并完成成品。 1 4 2 论文结构安捧 第一章：主要介绍本课题研究的目的、意义，国内外研究现状和主要内容以及论 文的结构。 第二章：主要介绍遗传算法的理论基础，包括遗传算法的生物学基础，遗传算法 简介，遗传算法的特点和遗传算法的应用。 第三章：介绍了启发式算法和混合遗传算法，并针对一维优化下料问题提出了一 种新型的改进的遗传算法。 第四章：对型材下料问题进行研究，分了两个部分，第一部分是对原材材料下料 6 问题的研究：第二部分是对余料优先下料问题的研究。 第五章：对型材优化下料方法的求解，包括程序流程图，讨论遗传算法中的各个 参数，以及实验数据。 第六章：总结与展望。 最后是参考文献和致谢。 第二章遗传算法理论基础 2 1 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启 发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设 计和开发提供了广阔的前景。遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 胁3 就是这种生 物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模 拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴 的生物学基础就是生物的遗传和进化。 2 1 1 遗传与变异 世间的生物从其亲代继承特性或性状，这种生命现象就称为遗传( h e r e d it y ) ，研 究这种生命现象的科学叫做遗传学( g e n e t i c s ) 。由于遗传的作用，使得人们可以种瓜 得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀游。 构成生物的基本结构和功能单位是细胞( c e l1 ) 。细胞中含有的一种微小的丝状化 合物称为染色体( c h r o m o s o m e ) ，生物的所有遗传信息都包含在这个复杂而又微小的染 色体中。遗传信息是由基因( g e n e ) 组成的，生物的各种性状由其相应的基因所控制， 基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细咆分裂的过程中， 其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。经过生物学家的 研究，现在人们已经明白控制并决定生物遗传性状的染色体主要是由一种叫做脱氧核 糖核酸( d e o x y r i b o n u c l e i ca c i d ，简称d n a ) 的物质所构成，除此之外，染色体中还含 有很多蛋白质。d n a 在染色体中有规则地排列着，它是个大分子的有机聚合物，其基本 结构单位是核苷酸。每个核苷酸由四种标为碱基的环状有机化合物中的一种一分子戊 糖和磷酸分子所组成。许多核苷酸通过磷酸二酯键相结合形成一个长长的链状结构， 两个链状结构再通过碱基间的氢键有规律地扭合在一起，相互卷曲起来形成一种双螺 旋结构。另外，低等生物中还含有一种叫做核糖核酸( r i b o n u c l e i ca c i d ，简称r n a ) 的物质，它的作用和结构与d n a 类似。基因就是m r 或m r 长链结构中占有一定位置 的基本遗传单位。生物的基因数量根据物种的不同也多少不一，小的病毒只含有几个 基因，而高等动植物的基因却以数万计。d n a 中，遗传信息在一条长链上按一定的模式 排列，亦即进行了遗传编码。一个基因或多个基因决定了组成蛋白质的2 0 种氨基酸的 8 组成比例及其排列顺序。遗传基因在染色体中所占据的位置称为基因座( l o c u s ) ，同一 基因座可能有的全部基因称为等位基因( a l l e l e ) 。某种生物所特有的基因及其构成形 式称为该生物的基因型( g e n o t y p e ) 。而该生物在环境中呈现出的相应的性状称为该生 物的表现型( p h e n o t y p e ) 。一个细咆核中所有染色体所携带的遗传信息的全体称为一个 基因组( g e n o r n e ) 。 细胞在分裂时，遗传物质d n a 遁过复制( r e p r o d u c t i o n o n ) 而转移到新产生的细胞 中，新细胞就继承了旧细胞的基因。有性生殖生物存繁殖下一代时，两个同源染色体 之间通过交叉( c r o s b o v e r ) 而重组，亦即在两个染色体的某一相同位置处d n a 被切断。 其前后两串分别交叉组合而形成两个新的染色体。另外，在进行细胞复制时，虽然概 率很小，但也有可能产生某些复制差错，从而使d n a 发生某种变异( m u t a ti o n ) ，产生 出新的染色体。这些新的染色体表现出新的性状。如此这般，遗传基因或染色体在遗 传的过程一中由于各种各样的原因而发生变化。 2 1 2 进化 生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改良， 这种生命现象称为进化( e v o i u t i o n ) 。生物的进化是以集团的形式共同进行的，这样的 一个团体称为群体( p o p u l a t i o n ) ，组成群体的单个生物称为个体( i n d i v i d u a l ) ，每一 个个体对其生存环境都有小同的适应能力，这种适应能力称为个体的适应度( f i t n e s s ) 。 达尔文( o a r w j n ) 的自然选择学说( n a t u r a ls e l e c t i o n ) 构成现代进化论的主体。自然选 择学说认为，通过不同生物闻的交配以及其他一些原因，生物的基因有可能发生变异 而形成一种新的生物基因，这部分变异了的基因也将遗传到下一代。虽然这种变化的 概率是可以预测的，但具体哪一个个体发生变化却是偶然的。这种新的基因依据其与 环境的适应程度决定其增殖能力，有利于生存环境的基因逐渐增多，而不利于生存环 境的基因逐渐减少。通过这种自然的选择，物种将逐渐地向适应于生存环境的方向进 化，从而产生出优良的物种。 2 1 3 遗传与进化的系统观 虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清 楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几 个特点却为人们所共识： ( 1 ) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。 ( 2 ) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体 上。 9 ( 3 ) 生物的繁殖过程是由其居因的复制过程来完成的。 ( 4 ) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新 的性状。 ( 5 ) 对环境适应性好的基凶或染色体经常比适应性差的基因或染色体有更多的机 会遗传到下一代。 2 2 遗传算法简介 遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优 化的概率搜索算法，它最早起源于6 0 年代对自然和人工自适应系统的研究。7 0 年代 d ej 0 n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在一 系列研究工作的基础上，美国密西根大学的h o l l a n d 教授在认真分析了生物进化发展 的规律之后，提出和发展这一算法的理论，形成了遗传算法的基本框架并得到了人们 的广泛承认，f r 0 1 l a n d 教授也因此被人们当作遗传算法的奠基人。 2 2 1 遗传算法概要 对于最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性 的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的 深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能也 不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。总的来说，求最 优解或近似最优解的方法主要有三种：枚举法、启发式算法和搜索算法。 ( 1 ) 枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续 函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到 最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最 先进的计算工具上都无法求解。 ( 2 ) 启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近 似最优解。该方法的求解效率虽然比较高，但对每一个需要求解的同题都必须找出其 特有的启发式规则这个启发式规则无通用性，不适合于其他问题。 ( 3 ) 搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索 操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的 最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到一种 较好的平衡。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来解 1 0 决最优化问题的通用方法仍是一个难题。而遗传算法却为我们解决这类问题提供了一 个有效的途径和通用框架，开创了一种新的全局优化搜索算法。 遗传算法中，将n 维决策向量x - x 。，x 。，x n 用n 个记号x 。( i = l ，2 ，o o o ，n ) 所组 成的符号串x 来表示： x = x 。x 2 墨= x = x ，x 2 ， oeo9 岛 7 把每一个x i 看作一个遗传基因，它的所有可能取值称为等位基因，这样，x 就可看做 是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长度n 是同定的，但 对一问题n 也可以足变化的。根据不司的情况，这里的等位基因可以是一组整数，也 可以是某一范围内的实数值，或者是纯粹的一个记号。最简单的等位基因是由o 和1 这两个整数组成的，相应的染色体就可表示为一个二进制符号串。这种编码所形成的 排列形式x 是个体的基因型，与它对应的x 值是个体的表现型。通常个体的表现型和 其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。染色体x 也 称为个体x ，对于每一个个体x ，要按照一定的规则确定出其适应度，个体的适应度与 其对应的个体表现型x 的目标函数值相关联，x 越接近于目标函数的最优点，其适应度 越大；反之，其适应度越小。 遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索是通过对染 色体x 的搜索过程来进行的从而由所有的染色体x 就组成了问题的搜索空间。 牛物的进化足以集团为主体的。与此相对应，遗传算法的运算对象是由m 个个体 所组成的集合，称为群体。与生物一代一代的自然进化过程相类似。遗传算法的运算 过程也是一个反复迭代过程、第t 代群体记做p ( t ) ，经过一代遗传和进化后，得到第 t + l 代群体，它们也是由多个个体组成的集合，记做p ( t + 1 ) 。这个群体不断地经过遗 传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下 一代，这样最终在群体中将会得到一个优良的个体x ，它所对应的表现型x 将达到或接 近于问题的最优解x 。 牛物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成的。与此相 对对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传 算子( g e ll e ti co p e r a l o r s ) 作用于群体p ( t ) 中，进行下述遗传操作。从而得到新一代 群体p ( t + 1 ) 。 ( 1 ) 选择( s e l e c t i o n ) ：根据各个个体的适应度，按照一一定的规则或方法，从 第t 代群体p ( t ) 中选择出一些优良的个体遗传到下一代群体p ( t + 1 ) 中。 ( 2 ) 交叉( c r o s s o v e r ) ：将群体p ( t ) 内的各个个体随机搭配成对，对每一对个体， 以某个概率( 称为交义概率，c f o s s o v e r r a t e ) 交换它们之间的部分染色体。 ( 3 ) 变异( m u t a t i o n ) ，对群体p ( t ) 中的每一个个体，以某一概率( 称为变异概率， m u t a t i o nr a t e ) 改变某一个或某一些基因座上的基因值为其他的等位基因。 2 2 2 遗传算法的运算过程 遗传算法的运算过程如图2 1 所示。 图2 1 遗传算法的运算过程示意 由该图可以看出，使用上述三种遗传算予( 选择算子、交叉算子、变异算子) 的遗 传算法的主要运算过程如下所述。 步骤一：初始化。设置进化代数计数器t t ，则进化过程 中所得到的具有最大适应度的个体作为最优解输出，终止计算。 2 3 遗传算法的特点 为解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、梯度 法、动态规划法、分枝定界法等。这些优化算法各有各的长处，各有各的适用范围， 1 2 也各有各的限制。遗传算法是一类可用于复杂系统优化计算的鲁棒搜索算法，与其他 一些优化算法相比，它主要有下述几个特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决 策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以 决策变量的某种形式的编码为运算对象4 这种对决策变量的编码处理方式，使得我们 在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的 遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特别是对一些无数值 概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独 特的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要利用目 标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。 而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向 和搜索范围，无需目标函数的导数值等其他一些辅助信息。这个特性对很多目标函数 是无法或很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等， 应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。再者，直接利用 目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜 索空间中，从而提高了搜索效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从解空间 中的一个初始点开始最优解的迭代搜索过程。单个搜索点所提供的搜索信息毕竟不多， 所以搜索效率不高，有时甚至使搜索过程陷于局部最优解而停滞不前。遗传算法从由 很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开 始搜索。对这个群体所进行的选择、交叉、变异等运算，产生出的乃是新一代的群体， 在这之中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，所以实际 卜相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定性的搜 索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定 性往往也有可能使得搜索永远达不到最优点，压而也限制了算法的应用范围。而遗传 算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方 式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生 一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多 优良的个体，实践和理论都已证明了在一定条件下遗传算法总是以概率l 收敛于问题 的最优解。当然，交叉概率和变异概率等参数也会影响算法的搜索效果和搜索效率， 所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。而另一方面，与其 他一些算法相比，遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能地低。 1 3 2 4 遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于同题的具体 领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的 一些主要应用领域： ( 1 ) 函数优化嘲。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性 能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也 有离散函数，有凸函数也有凹函数，有低维函数也有高维函数。有确定函数也有随机 函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传 算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数 优化闯题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。 ( 2 ) 组合优化侧。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大， 有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问 题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解 的最佳工具之一。实践证明，遗传算法对于组合优化中的n p 完全问题非常有效。例如， 遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成 功的应用。 ( 3 ) 生产调度问题伽。生产调度问题在很多情况下所建立起来的数学模型难以精 确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与 实际相差甚远。而目前在现实牛产中也主要是靠一些经验来进行调度。现在遗传算法 已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、 生产规划、任务分配等方面遗传算法都得到了有技的应用。 ( 4 ) 自动控制嘲嘲嘲。在自动控制领域中有很多与优化相关的问题需要求解，遗 传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航 空控制系统的优化、使用遗传算法设计宅问交会控制器、基于遗传算法的模糊控制器 的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用 遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这 些领域中应用的可能性。 ( 5 ) 机器入学侧。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的 起源就来自于对人工自适应系统的研究，所以机器凡学理所当然地成为遗传算法的一 十重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹 规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应 用。 ( 6 ) 图像处理侧。图像处理是计算机视觉中的一个重要研究领域。在图像处理过 1 4 程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影口 向图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗 传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式识别、图像 恢复、图像边缘特征提取等方面得到了应用。 ( 7 ) 人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自 然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特 征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命 现象的重要基础理