（模式识别与智能系统专业论文）二维矩形件优化排样问题研究.pdf

山东大学硕士学位论文 摘要 二维矩形件优化排样问题普遍存在于玻璃、钢板、木材、纸张、制衣和船 舶等行业中。一个好的排样方案可以节省原材料，降低生产成本，直接给企业 带来经济效益，提高企业的核心竞争力。该问题在理论上是具有最高计算复杂 性的n p 完全问题，随着问题规模的扩大，将很难用精确算法求得最优解。因此， 开展对二维矩形件优化排样问题的研究具有重要的理论意义和工程应用价值。 本文在分析矩形件优化排样问题特点的基础上，建立了该问题的数学模型， 分别应用三种方法进行优化求解，对不同约束条件下的算例的求解结果进行了 比较和分析。 首先采用遗传算法对矩形件排样问题进行了求解。在求解过程中，给出了 遗传算法求解的编码方法、适应度函数的定义、遗传算子以及关键参数。经过 具体的算例求解，发现该算法在一般情况下可以求得较好的优化结果。 然后针对遗传算法在初始解群分布不均匀，容易陷入局部最小值而过早收 敛的缺点，提出一种免疫算法对矩形件排样问题进行了求解。算例求解的结果 表明，免疫算法中的基于浓度的群体更新策略可以有效地保持抗体的多样性， 改善早熟收敛现象，取得了比遗传算法更好的优化结果，但是存在算法运行时 间偏长的缺点。 最后在基本免疫算法的基础上，通过重新定义抗体间的相似度，改进抗体 浓度的计算方法，并加入接种疫苗操作，提出了一种改进的免疫算法。经过具 体算例的求解和比较分析，发现其求解结果在总体上优于遗传算法和免疫算法， 并且算法的运行速度比基本免疫算法有了明显的提高。 关键词：矩形件优化排样遗传算法免疫算法浓度疫苗 山东大学硕士学位论文 a b s t r a c t t h ep r o b l e mo ft w o 。d i m e n s i o n a lo p t i m a ll a y o u tf o rr e c t a n g u l a rp a r t sw i d e l y e x i s t si nm a n ym a n u f a c t u r i n gi n d u s t r i e s ，s u c ha sg l a s s w o r k ，s t e e lp l a t em a c h i n i n g ， l u m b e r i n g ，r a gt r a d e ，s h i p b u i l d i n ga n ds oo n ag o o dp a c k i n gs c h e m ec a nn o to n l y s a v er a wm a t e r i a la n dr e d u c et h ep r o d u c t i o nc o s t ，b u ta l s ob r i n ge c o n o m i cb e n e f i t s f o re n t e r p r i s e sa n de n h a n c et h ec o m p e t i t i v e n e s so fe n t e r p r i s e s t h ep r o b l e mw h o s e c o m p u t a t i o ni st h et h em o s tc o m p l e xi nt h e o r yb e l o n g st ot h en pc o m p l e t ep r o b l e m s t h eo p t i m a ls o l u t i o ni sv e r yd i f f i c u l tt oo b t a i nb yt h ee x a c ta l g o r i t h m sw h e nt h e s c a l eo ft h ep r o b l e me x p a n d sl a r g e l y t h e r e f o r e ，r e s e a r c ho nt h ep r o b l e mo f t w o d i m e n s i o n a lo p t i m a ll a y o u tf o rr e c t a n g u l a rp a r t si sv e r yi m p o r t a n ti nt h e o r ya n d a p p l i c a t i o n s i nt h i sp a p e r ，t h ef e a t u r e so f t h ep r o b l e ma r es t u d i e da n di t sm a t h e m a t i c a lm o d e l i se s t a b l i s h e d t h e nt h r e em e t h o d sa r ea p p l i e dt os o l v i n gt h ep r o b l e m t h er e s u l t so f f o u rn u m e r i c a le x a m p l e su n d e rd i f f e r e n tc o n s t r a i n t sa r ec o m p a r e dw i t he a c ho t h e r a n da n a l y z e di nd e t a i l f i r s t l y ，t h eg e n e t i ca l g o r i t h m ( g a ) i su s e dt os o l v et h ep r o b l e mo fr e c t a n g u l a r p a r t so p t i m a ll a y o u t i i lt h em e a n t i m e ，t h ec o d i n gm e t h o d ，f i t n e s sf u n c t i o nd e f i n i t i o n ， g ao p e r a t o r sa n ds o m ek e yp a r a m e t e r sa r eg i v e n t h er e s u l t so fn u m e r i c a le x a m p l e s s h o wt h a tg ac a ng e n e r a l l yo b t a i ng o o ds o l u t i o n s t h e nw ea t t e m p tt op u tf o r w a r do n ek i n do fi n 3 a n u n ea l g o r i t h m ( i a ) t os o l v et h e p r o b l e m ，b e c a u s eg aw i l lf a l li n t op r e m a t u r ec o n v e r g e n c ee a s i l yw h e nt h ei n i t i a l s o l u t i o n sa r e n td i s t r i b u t e de q u a b l y d u et ot h es t r a t e g yo ft h eg r o u pr e n e w a lb a s e d o nt h ed e n s i t yo fa n t i b o d i e s ，i ac a ne f f e c t i v e l ym a i n t a i nt h em u l t i p l i c i t ya m o n g a n t i b o d i e sa n do v e r c o m ep r e m a t u r ec o n v e r g e n c e i ti s p r o v e dt h a ti ac a no b t a i n b e t t e ro p t i m i z e ds o l u t i o n st h a ng a h o w e v e r , i ah a sad e f e c tt h a ti tr u n sm o r e s l o w l yt h a ng a f i n a l l y ，w er e d e f i n et h es i m i l a r i t yb e t w e e nt w oa n t i b o d i e s ，i m p r o v et h ew a yo f c a l c u l a t i n gt h ed e n s i t ya n da d dv a c c i n a t i o no p e r a t o rt ot h eb a s i ci m n l u n ea l g o r i t h m i t 山东大学硕士学位论文 a ni m p r o v e di m m u n ea l g o r i t h m ( i i a ) i sp r o p o s e dt os o l v et h ep r o b l e m t h e nt h e r e s u l t so ft h en u m e r i c a le x a m p l e sa l ec o m p a r e da n da n a l y z e dt os h o wt h a ti i ac a r l n o to i l l yo b t a i nb e t t e ro p t i m i z e ds o l u t i o n st h a ng aa n di a ，b u ta l s or u n sm u c hf a s t e r t h a n i a k e yw o r d s ：r e c t a n g u l a rp a r t so p t i m a ll a y o u t ，g e n e t i ca l g o r i t h m ，i m m u n ea l g o r i t h m ， d e n s i t y ，v a c c i n e u i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：叁垂 日期：鲨：! ：竺望 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：j 址导师签名：型日虮型坐! 山东大学硕士学位论文 1 1 问题的提出 1 绪论 在当前市场经济条件下，企业要想在激烈的竞争中求生存、谋发展并立于 不败之地，关键就是尽一切可能提高企业的经济效益。而提高效益的一个重要 环节就是降低生产成本。在玻璃、钢板、木材、纸张、制衣和船舶等行业中， 原材料费用在生产成本中所占的比重很大，这些企业要想降低生产成本，必须 优化下料，提高原材料利用率。因此，研究优化下料问胚就显得非常必要。在 下料生产中，优化排样是一个典型的智能决策任务，它要解决的问题就是在许 多排样方案中选择最优或接近最优的方案。 关于下料问题的研究始于2 0 世纪6 0 年代。至今已有许多学者从不同的领 域、不同的角度对其进行了研究并发表了大量论文，同时也对下料问题做出了 不同的命名。文献【l 】对下料问题的多种名称做了介绍： ( 1 ) 下料问题，减少废料问题( c u t t i n gs t o c ka n d t r i m l o s s p r o b l e m s ) ； ( 2 ) 排样，排料，布局，分类，划分问题( n e s t i n g ，l a y o u t ，a s s o r t m e n t ， p a r t i t i o n i n gp r o b l e m s ) ； ( 3 ) 装箱，条料排样，背包问题( b i np a c k i n g ，s t r i pp a c k i n g ，k n a p s a c k p r o b l e m s ) ； ( 4 ) 车辆装货，货盘装载，集装箱装货问题( v e h i c l el o a d i n g ，p a l l e tl o a d i n g ， c o n t a i n e rl o a d i n g ) 。 尽管上述这些问题的命名不尽相同，它们的基本逻辑结构是相近的，都可 以归属于下料问题。 下料问题按照原材料和零件的维数，可简单地分为一维、二维和三维下料 问题。一维下料问题指型材、棒材的下料；二维下料问题主要指板材的下料； 三维下料问题则是指原材料和所下零件的长、宽、高均有特定要求的情况。其 中，二维下料问题按照下料件的轮廓形状，又可进一步划分为矩形件和异形件 ( 不规则件) 的排样问题。本文主要研究矩形件的排样问题。 矩形件优化排样通常是指在给定的矩形板材上排放所需要的矩形件，使排 放区域的板材废料尽可能地少，以达到节省板材的目的。对于异形件的排样问 山东大学硕士学位论文 题，可以通过计算机的图形处理技术将一个或几个零件套排在一个包容矩形中， 然后对包容矩形进行下料排样，从而转化为矩形件排样问题圈，可见矩形件优 化排样问题的解决具有十分重要的意义。 1 2 矩形件排样问题的研究现状 1 2 1 国外研究现状 国外有关下料排样问题的研究起步比较早。下料问题最早由苏联人 k a n t o r o v i c h 于1 9 3 9 年提出，但其奠基性工作当属g i l m o r e 与g o m o r y 在6 0 年 代的工作。g i l m o r e 和g o m o r y 先后发表了四篇著名的论文，其中前两篇叫1 详 细阐述了一种用于一维下料问题的线性规划算法，后两斜孓国将该算法推广到了 二维和三维问题，第一次为解决实际生产中的下料问题提供了可行的技术手段。 从此众多学者针对下料问题的一个或几个方面，发表了大量的文献，对矩形件、 异形件排样及优化问题提出了多种算法。 国外早期对矩形件排样的求解主要采用数学规划方法和启发式算法。数学 规划这类方法具体的有线性规划m 、动态规划i s 、整数规划例以及整数线性规划 u o 】。但数学规划方法有一个主要缺陷，就是随着矩形件数量的增加，所需要的 计算时间和空间将呈指数级增长，不适用于求解大规模的矩形件优化排样问题。 启发式算法放弃了寻求最优解的想法，而是力图在人们可以接受的计算时间内 寻求近似最优解。d a g l i 1 l 】提出了一个基于图案子集的启发式算法，该算法适合 于图形组合的图案较少的情况。y a n a s e e 和z i n o b e r t l 提出依次序的启发式排样 算法，算法的主要思想是根据排样零件的物理属性( 长、宽和面积等) 给出一 定的优先级规则，零件按照这种优先级规则排序，从板材的左下角开始按次序 排放每一个零件。a l b a n o 和o r s i n i 1 司在树搜索的基础上加入了启发式的搜索技 术，解决了正交切割方式的矩形排样问题，并得出了近优的排样方案。启发式 算法因其易于融合各种限制条件和具体目标，在实际生产排样中起着重要的作 用。 2 0 世纪9 0 年代以后，随着禁忌搜索、模拟退火算法、遗传算法以及人工 神经网络算法等智能优化算法的日益成熟及其在t s p ( t r a v e l l i n gs a l e s m a n p r o b l e m ) 问题、空间分配、任务调度等组合优化问题方面的成功应用，这些算 山东大学硕士学位论文 法与排放算法相结合被广泛地应用于矩形件排样问题的求解。 、 f a i n a t “】运用模拟退火算法，分别解决了直线切割和非直线切割模式下的矩 形件排样问题。s e g e n r i e c h 和b r a g a c l m 运用遗传算法解决了零件多件多排问题， 即在定宽无限长的板材上正交排列给定的矩形件，将排样问题转化为排列问题， 把问题的解表示成数字串的形式，然后再对数字串进行选择，交叉和变异操作， 从而求得新的解。s r i r a m 和k a n g 【l 司利用改进的h o p f i e l d 人工神经网络解决了二 维模块的布线问题。该方法以总线长度为目标函数来构造模型。通过使网络的 连接权矩阵依赖于网络的状态，并且在能量函数中包含四次项来改进h o p f i e l d 神经网络。将原来的二维问题分解成两个一维问题。d a 9 1 i 和p i p a t p o n g 【1 7 1 结合 神经网络和遗传算法对排样问题提出了一种新的解决方法，解决了排样系统的 学习问题。同时文章采用了最小排样布局的分层方法，使网络的大小与规模的 数目呈线性关系。文献 1 8 】给出了模拟退火算法( s a ) 、遗传算法( g a ) 、随机搜 索法( r s ) 与不同排放算法结合，对不同问题实例的综合性能评价的结果，得出 两点主要结论：( 1 ) 复合算法的结果优于单纯排样算法的结果，并且排样算法 效果越好，复合算法在同等条件下的效果也越好；( 2 ) 任何算法都有效果不佳 的问题实例，即对矩形件排样目前还没有完全有效的方法。 1 2 2 国内研究现状 我国的计算机辅助排样研究工作开始地比较晚。开始时一般都集中在矩形 件的排样上，多用人机交互方法对图形进行平移、旋转达到优化的目的，对不 规则件涉及的较少。 对矩形件排样问题的求解，国内学者主要采用数学规划方法、启发式算法 以及智能优化算法。文献 1 9 1 对矩形件套裁排样问题建立了物理模型，引入了 人工智能的深度优先搜索策略和博弈树的a b 搜索方法。文献 2 】研究了矩形件 正交排样优化问题的遗传算法求解，其基本思想是将问题转化为一个排列问题。 该文献提出了下台阶算法( 改进的b l 算法) ，并将其与遗传算法相结合，用于求 解矩形件排样问题。通过试算表明该算法可获得比b l 算法更好的解，是一种 有效的算法。文献 2 0 】提出一种适用于矩形件优化排样的最小宽度算法，将其 与模拟退火算法相结合，能够跳出局部搜索，最终可获得近似总体最优的排样 结果。经过算例求解表明，该优化排样算法具有广泛的适应性，并可适合“一 山东大学硕士学位论文 刀切”的高效率下料工艺。 1 3 论文的主要研究工作 本文所讨论的二维矩形件优化排样问题是实际生产和理论研究中出现频率 最高的一类优化排样问题。论文在分析矩形件排样问题的基础上，建立了该问 题的数学模型，分别采用遗传算法、免疫算法和改进的免疫算法进行优化求解。 通过对不同约束条件下的算例进行求解和比较分析，从中找出一种适合求解此 类问题的较好方法。论文各章节的内容安排如下： 第二章：在分析矩形件排样问题的基础上，建立了该问题的数学模型。分 析了问题规模增大时用数学规划方法求解的难度，对几种矩形件启发式排放算 法做了介绍。 第三章：应用遗传算法对矩形件排样问题进行求解，给出了遗传算法的编 码方法、适应度函数的定义、遗传算子和关键参数，以及对具体算例求解的结 果。 第四章：首先介绍了免疫算法的生物学基础、基本步骤、收敛性以及相对 于遗传算法的优点，然后提出一种免疫算法来求解矩形件排样问题，给出了免 疫算法实现的具体步骤和算例求解的结果。 第五章：针对基本免疫算法的不足，通过重新定义抗体间的相似度，改进 抗体浓度的计算方法，并加入接种疫苗操作，提出了一种改进的免疫算法并应 用于矩形件件排样问题求解。最后对三种算法的求解结果进行了比较与分析。 第六章：总结与展望。、 4 山东大学硕士学位论文 2 矩形件排样问题的数学模型及排放算法 2 1 矩形件排样问题的数学模型 2 1 1 矩形件排样问题的描述 矩形件排样问题是指在给定的矩形板材上将一系列矩形件按最优方式排 布，即在长为l ，宽为的板材p 上，将给定的n 个零件 r i ，尼，r 在满足 一定的工艺要求下不重叠地全部排放上，使得板材的利用率最高。 2 1 2 数学模型 为了叙述及以后编程方便，我们将板材竖起放置，即已知板材宽度为， 高度为l 。定义以下变量：卢( 1 ，2 ，一 是给定的待排放的矩形件的一组编号； 是所需板料的最小高度；云是某个已知的l 一的上界；( 石j ，y j ) 是矩形件 是的左下角点坐标；( z ：，y ：) 是矩形件尼的右上角点坐标；厶，砒是矩形件 b 的高度和宽度。另外定义三个逻辑变量：r i c o 或1 ，当矩形件足横放时取1 ， 噩竖放时取o ；0 = o 或1 ，当风置于弓的左侧时取1 ，右侧时取o ；b f f = o 或1 ， 当愚置于而的下侧时取1 ，上侧时取o ； 矩形件的排样问题可表达为：求最优排放序列，使 厶m 峄州) 2 气r 2 1 其中：l i 彬为待排放矩形件的面积总和；m 为所有矩形件排放完毕后所 i = 1 占用的板材面积。 约束条件为： j ! y ：工m f ， f ， ( 2 2 ) ( 2 3 ) 山东大学硕士学位论文 工：= 爿+ ( 1 一) 形+ f y ：= y j + ( 1 一r i ) l l + 啊 # - 4 + w ( 1 - l o ) y ；s y + 三n 一) t q + l # + b u + b # 1i ，j l ， l m i a , 工，i ，y ：，工；y ；0 f j f j i - 1 i j i i t ，则 以进化过程中所得的具有最大适应度的个体最优解输出，中止计算。 遗传算法的运算过程如图3 1 所示。 山东大学硕士学位论文 吲 囱匝翮 一 jk 圃 匝蔓卜臣乎岖沿f 一 图3 1 遗传算法的运算过程示意图 3 1 2 遗传算法的特点 遗传算法的优越性可以简单地归结为以下几点： ( 1 ) 遗传算法是一种数值求解的方法，对目标函数的性质几乎没有要求， 甚至都不一定要显式地写出目标函数，因此应用范围较广。 ( 2 ) 遗传算法所具有的特点是记录一个群体，它可以记录多个解而不同于 局部搜索、禁忌搜索和模拟退火仅仅是一个解，这多个解的进化过程正好适合 于多参数、多变量、多目标优化问题的求解。 ，一 ( 3 ) 遗传算法在求解很多组合优化问题时，不需要有很强的技巧和对问题 有非常深入地了解。在对问题的决策变量编码后，其计算过程是比较简单的， 且可以较快得到一个满意解。 ( 4 ) 遗传算法同求解问题的其他启发式算法有较好的兼容性。如可以用其 他的算法求初始解。对每群体，可以用其他的方法求解下一代新群体。 ( 5 ) 遗传算法比传统的优化算法更容易在计算机上实现。 1 4 山东大学硕士学位论文 3 1 3 遗传算法的收敛性 以往对遗传算法的收敛性分析主要是根据h o l l a n d 的模式定理对简单的遗 传算法作定性分析，认为遗传算法是全局收敛的。但该结论一直受到怀疑和争 论。近年来，在遗传算法的全局收敛性分析上取得了重大突破，人们开始讨论 用m a r k o v 链对其进化过程进行理论分析。g o l d b c r g 和s e 孕e s t i 硎首先用m a r k o v 链对遗传算法进行分析。r u d o l p h 用齐次m a r k o v 理论证明标准遗传算法不能收 敛到全局最优解，不适于进行函数优化，应改变选择策略以实现全局收敛 2 7 1 。 g r c f e b s t e t t 2 s 和e i b e n t 2 9 1 证明了采用保留最佳个体策略的遗传算法能够以概率1 收敛到最优解。这些结论除了具有理论上的重要意义以外，在实际应用中也为 最优解的搜索提供了保证。 3 1 4 遗传算法实现的技术问题 在遗传算法中，正确选择和构造编码技术、适应度函数与遗传算子是非常 重要的，这些参数的选取不同构成不同的遗传算法。 1 初始种群的选取和计算中群体的大小 一般采用随机产生初始种群和通过其他的方法先构造一个初始种群。通过 其他方法构造的初始种群可能会节省进化的代数，但也可能过早地陷入局部最 优群体中，我们称这种现象为早熟( p r e m a t u r e ) 现象。群体中个体的个数称为 群体的维数。群体的维数越大，其代表性越广泛，最终进化到最优解的可能性 越大。但维数大的群体势必会造成计算时间的增加，这又是我们不希望的。群 体的维数常常采用一个不变的常数。在一些应用中，群体的维数可以采用同遗 传代数有关的变量。 2 编码方法和解码方法 编码是应用遗传算法时需要解决的首要问题，也是设计遗传算法的一个关 键步骤。编码方法不仅决定了个体的染色体排列形式，还决定个体从搜索空间 的基因型变换到解空间的表现型时的解码方法，以及遗传算法的运行效率。针 对具体的应用问题，如何设计一种完美的编码方案一直是遗传算法的应用难点， 也是遗传算法的一个重要的研究方向。 比较直观和常规的方法是0 ，1 二进制编码，我们称这一类码为常规码。这 山东大学硕士学位论文 同人类的染色体成对结构类似。这种编码方法使算法的三个算子构造比较简单。 对一些优化问题有其表示简单和直观的优越性，如o 一1 背包问题。除常规的0 1 编码外，其他的非o 一1 码称为非常规编码。非常规编码同问题联系紧密。 如t s p 旅行商问题。 编码和解码是相对应的。遗传算法的最后一个工作是通过解码得到问题的 一个解。 3 适应度函数 在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语 来衡量某个物种对于其生存环境的适应程度。在遗传算法中，这个概念用来衡 量群体中的每个个体有可能达到或接近于最优解的优良程度。适应度高的个体 遗传到下一代的概率就大，而适应度较低的个体遗传到下一代的概率就相对要 小。度量个体适应度的函数称为适应度函数。 简单的适应度函数是目标函数的简单变形。若，g ) 为目标函数，则适应度 函数f i t n e s s b ) 可以取 胁艄= 牌m m 砜。萋嚣亲凳蒜 - ， 此外，随着要解决问题的不同，出现了非线性加速适应度函数、线性加速 适应度函数、排序适应度函数等较为复杂的定义方法。 4 遗传算子 ( 1 ) 选择算子 遗传算法中的选择算子就是用来确定从父代群体中选取哪些个体作为下一 代群体进行交叉与变异运算的父代的方法。最常用的选择方法是比例选择 ( p r o p o r t i o n a lm o d e l ) 法，也叫做轮盘赌( r o u l e t t ew h e e l ) 法。其基本思想是 计算各个个体的相对适应度 p i = 1 争，i = 1 , 2 ，n ( 3 2 ) 乃 然后根据概率分布从初始种群中随机选一些染色体构成一个新的种群。显 而易见，这种选择方式非常类似于轮盘赌中的转盘，扇区的面积越大，骰子落 入其中的概率也就越大。即个体的适应度越大，它被选择到的机会也就越大。 山东大学硕士学位论一文 适应度高的个体有可能被重复地选到新的l 鼬群中去。 为了避免少数个体霸占整个群体而导致“早熟”的现象，可以考虑如下的 改进方法，在初始种群随机产生后，在随后的进化过程中，种群可以由5 秘策 略重新构成口0 1 ：全部替换上一代( n 方式) ；保留父代中最好的一个( e 方 式) ；按一定比例更新上一代( g 方式) ；从子代和父代中挑选最好的n 个 ( b 方式) ；变化种群规模( v 方式) 。一般地，n 方式的全局搜索性能最好， 但收敛速度最慢；b 方式收敛速度最快，但全局搜索能力最差；e 方式和、g 方 式介于两者之间。在实际问题的g a 算法中常将几种策略混合使用。本文所提 出的遗传算法的选择策略就采用了b 方式。 ( 2 ) 交叉算子 交叉运算在遗传算法中起着关键作用，它决定了遗传算法的全局搜索能力。 它是指两个相互配对的染色体按某种方式交换其部分基因，从而形成两个新的 个体。交叉算子的设计要与个体编码的设计统一考虑。 单点交叉和双点交叉是比较常用的交叉算子。 ( 3 ) 变异算子 “ 变异运算是指将个体染色体编码串中的某些基因用其他等位基因来替换， 从而形成一个新的个体。从遗传运算产生新个体的能力方面来说，交叉运算是 产生新个体的主要方法，它决定了遗传算法的全局搜索能力。而变异运算只是 产生新个体的辅助方法，但它也是必不可少的一个运算步骤，因为它决定了遗 传算法的局部搜索能力。交叉算子与变异算子的相互配合，共同完成对搜索空 间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优 化问题的寻优过程。 3 。2 矩形件排样问题的遗传算法求解 采用遗传算法对矩形件排样问题进行求解的基本思想是将该问题分解为两 个互相融合的部分：( 1 ) 将零件的排放序列作为排列组合问题；( 2 ) 按给定的 序列排放，获得捐 样图。即通过遗传算法获得最优的排入序列，按排放算法获 得排样图。 山东大学硕士学位论文 3 2 1 编码方法 根据矩形件排样的特点，本文采用十进制整数编码，对每一个矩形件进行 编号，i = 1 , 2 ，n ，零件编号构成的一个整数串l l = p 1 ，p 2 ，p 。 ，1si p , i 。， 就表示了种排样图( 一个解) ，即个个体j t 。其中，每一位整数都有正负之 分，为正表示将零件横放，为负表示将零件竖放。例如个体( 3 ，5 ，1 ，2 ，4 l 表示5 个零件这样排放：先横放3 号零件，竖放5 号零件，竖放1 ，横放2 ，最 后横放4 号零件。一个个体对应一种排样方案，m 个个体构成了一个群体。 当下料工艺要求是直线切割，并且下料零件规模较大时，为提高切割生产 率，应将同一类型的零件尽可能地相邻排列。所以在编码时不再对单个零件进 行编号，而是对每一种类零件进行编号，将种类号组成一个个体。例如个体f 1 ， 4 ，一3 ，2 ，5 l 表示一组零件这样排放：先横放第1 种零件，横放第4 种零件， 竖放第3 种，横放第2 种，最后横放第5 种零件。 3 2 2 适应度函数设计 设计适应度函数有两种方式可供选择：一种从排样图的最大高度方面考虑， 要求尽可能地使排样图的最大高度值小，一般用最大高度值的倒数来表示；另 一种是从废料再利用的角度出发进行考虑的，这种方法要求尽可能的提高可再 利用废料的再利用率( 此处所讲的可再利用废料是指处于排样图最高轮廓线和 排样图最大高度水平线之间的部分) 。针对板材的三种情况，我们分别定义了不 同的适应度函数。设要排a n 个矩形件，i = 1 , 2 ，n ，长、宽分别为厶，f ，a r e a o n 为排入的矩形件的总面积，贝l j a r e a o = y l ，形。 ( 1 ) 定宽无限长板材情况 对于定宽无限长板材，本文认为用排样高度来评价排样的优劣， 能地保持完整的板材，故采用如下的适应度函数： h i n e s s ( ，) ：翌 h ( ) w 其中，h 是排样图的最大高度，为板材的宽度。 ( 2 ) 多张同一规格板材情况 可以尽可 ( 3 3 ) 山东大学硕士学位论文 对这种情况 n t n e s s ( ，) = 采用如下的适应度函数 a r e a o a r e a l + h ( ，) w ( 3 4 ) 设n p l a t e s 是所用板材的数量，a r e a l 是前( n p l a t e s 1 ) 张板材的面积，h 是最 后一张板材排样图的最大高度，为板材的宽度。 ( 3 ) 多种不同规格的板材情况 将板材序列固定，采用和第2 种情况相似的评价策略： f i t n e s s ( ，1 ： ! 竺! ( 3 5 ) a r e a l + h ( j ) x 1 设n p l a t e s 是所用板材的数量，a r e a 是前( n p l a t e s 1 ) 张板材的面积，h ( d 是最 后一张板材排样图的最大高度，z 为最后一张板材的宽度。 显然，上述定义的适应度函数f i t n e s s ( ) 的物理意义就是板材的利用率。 3 2 3 遗传算子 1 交叉算子 染色体交叉的难点在于将两个染色体的部分基因片断互换后，会形成非法 基因，也就是在染色体中会有重复的基因。所以在染色体交叉的实现过程中， 既要使染色体发生交叉交换，又要保证交叉后的染色体没有重复的基因。 g r e f e n s t e t t e 等提出的基于剩余编号顺序的编码【3 ”，用剩余编号顺序的编码 进行交叉后，再用同样的方法翻译回顺序编码。这种交叉算法的优点是第一交 叉点前的部分不变，对于关心从前往后顺序而不只是组合顺序的情况有利，但 是实现过程较为复杂。因此本文采用文献 3 2 提出的交叉方法。这种方法的具 体实现过程如下：先选定一个固定的交叉位置，在该点以前的基因保持不变， 对该点以后的基因部分进行交叉；将两个染色体的不交叉的基因部分进行比较 ( 对于有符号的基因，只比较它们的绝对值) ，在剔除两个基因片断中相同的基 因后，将剩下的基因按原来的顺序分别放入两个数组p 和q 口电。在对交叉的 基因片断操作时，对不等于数组p 口和q 口中的基因直接进行交换。对于与数组 中的基因相同的基因，则先换成对应的数组加或q d 中的基因后再进行交换。 例如，有两个染色体为( 3 2459 87 610 ) 和 9 103 2 5 46 78 ，选 择第5 个位置为交叉点。先比较两个染色体不交叉部分，剔除相同基因后分别 放入两个数组，则p 】= 45 ，q 】= 一10 ) 。在交叉的基因片断( 87 610 中，将 山东大学硕士学位论文 1 换为4 ，0 换为5 ；在基因片断 546 78 中，将5 换为0 ，4 换为1 。最后将 变换后的基因片断进行交叉，交叉后的染色体变为1 3 245 90 16 78 l 和1 9 1 03 287 645 。 2 变异算子 变异算子使种群中比例很小的一部分染色体的结构发生变动，保证了染色 体在进化过程中能产生原先不存在的新特征，扩大了染色体的选择范围，是种 群跳出局部最优解的一种操作手段。本文采用的变异方法有两种，一种是位置 变异，另一种是旋转变异。 位置变异的内容如下：先设定一个变异概率p m j ，然后依次从1 到n ( 为 种群中染色体的个数) ，每次产生一个0 到1 的随机数r ，将r 与p m l 比较，若r 小于p m a ，则对第i 个染色体进行变异操作。否则就不进行变异。而变异的具体 方法是这样的：先产生两个不等的随机数量1 、恐，且应介于0 到n ( 为染色 体的基因长度) 之间。然后将置1 和钇之间的基因两两对换，以变异的方式形 成新的染色体。例如：有序列a = 98 垒56 7 羔3 2 ，产生的随机整数置1 3 ，k z = 7 ， 在序列中位于3 和7 之间的基因为 4567 1 ) ，则对应的4 和1 ，5 和7 相互交 换，基因6 保持不变，序列变为 98 176 5 432 。 旋转变异适用于允许矩形件旋转的情况，随机产生一个旋转位6 打，以概率 p m 2 对子代染色体中位于6 打之后的矩形进行旋转。例如序列b = 8945 量713 2 ) ，随机产生的旋转位是第5 位，则序列变为 89456 7 1 - 3 - 2 ) 。 3 选择算子 我们将简单遗传算法中的选择算子作了改进，较好地克服了轮盘赌法的缺 陷。采用了3 1 4 节中的b 方式，即：将子代和父代群体中各个个体的适应度 函数值从大到小排列，取排在前面的个个体作为下一代进化的父代种群。即 从子代与父代中挑选出最好的个个体，使收敛速度达到最快。 3 2 4 应用遗传算法求解的具体步骤 ( 1 ) 产生初始种群：给定 1 个零件的编号或n 种零件的编号，随机产生由 m 个编码 ，如，k 构成的初始种群。采用改进的最低水平线法进行解码， 根据板材情况从( 3 3 ) 、( 3 4 ) 、( 3 5 ) 式中选择相应公式计算当前群体中每个 个体的适应度。 山东大学硕士学位论文 ( 2 ) 交叉：将父辈群体中的个体随机两两配对，以交叉概率p 。进行交叉 操作，产生m 个个体构成子辈群体。本文采用单点交叉，即随机生成_ 个介于 o n 的交叉位b l ，将位于b l 以后的基因部分进行交叉。 ( 3 ) 变异：对进行了交叉操作的子辈个体，先以一定的变异概率p m l 对个 体进行位置变异，即随机生成两个不等的并介于0 n 的整数蜀、髟，将位于 置。和配之间的基因两两对换。然后以概率p 五对个体进行旋转变异，即随机产 生一个旋转位b z ，将位于b 2 之后的基因乘以1 。经过交叉操作和变异操作后得 到m 个个体构成的子辈群体。 ( 4 ) 选择：用改进的最低水平线法解码并计算变异后的n 个子辈个体的 适应度。将父辈个体与子辈个体的适应度函数值由大到小排序，取排在前面的 m 个个体作为下一代的父辈个体。记录最优个体及其适应度。 ( 5 ) 终止：判断当前最好解的适应度是否达到了要求或满足了预定的进化 代数。是，则停止并输出结果；否，则转去执行第( 2 ) 步。 3 3 计算实例 为了测试本章提出的遗传算法的性能，分别对四个不同约束条件下的算例 进行了求解，每个算例所需的矩形件和板材的己知数据参见附录1 。考虑到板 材的第三种情况与第二种情况的求解方法类似，故不再单独对第三种板材的下 料问题进行算例求解。其中，算例一是板材为定宽无限长、切割方式为正交切 割的情况；算例二是板材为定宽无限长、切割方式为直线切割的情况；算例三 是同一规格板材多张、切割方式为正交切割的情况；算例四是同一规格板材多 张、切割方式为直线切割的情况。 对四个算例，我们取种群规模m = 3 0 ，进化代数g e n = 2 0 0 ，交叉概率p 。= 0 9 ，变异概率p m l 印。2 _ o 1 。本章算法是在w i n 2 0 0 0 平台下，应用v c + + 6 0 编 程，在p e n t i u m4 、1 2 8 m 的p c 机上调试通过。矩形件和板材己知数据参见附 录l 。所设计的优化排样软件的输入、输出界面如附录2 所示。 由于遗传算法中初始种群的选取是随机的，并且交叉、变异操作都是以一 定的概率进行，也带有很大的随机性。所以对于同一个问题，每次运行均可出 现不同的结果。本文对每个算例各运算l o 次，给出算法运行结束时得到的其中 一个最优排样图，并给出适应度最大值、适应度最小值、适应度平均值及平均 2 1 山东大学硕士学位论文 运算时间。四个算例的最优排样图依次为图3 2 、图3 3 、图3 4 和图3 5 所示， 其中算例一子代群体的平均适应度的变化曲线如图3 6 所示。具体求解结果如 表3 2 所示。 图3 2 算例一g a 求得的最优排样图 图3 3 算例二g a 求得的最优排样图 图3 4 算例三g a 求得的最优排样图 山东大学硕士学位论文 图3 5 算例四g a 求得的最优排样图 图3 6 基于g a 的算例一子代群体的平均适应度的变化曲线 表3 2 g a 的求解结果 适应度平均适应度最小适应度最大平均时间 值值值( 秒) 算例一 0 8 9 9 20 8 8 6 00 9 1 3 4 1 7 5 算例二0 9 5 8 0 0 9 2 7 3o 9 6 4 17 6 7 算例三 0 8 9 5 10 8 8 1 70 9 0 3 21 3 1 算例四 0 9 5 9 3，o 9 5 1 40 9 7 3 38 5 2 山东大学硕士学位论文 3 4 本章小结 本章首先介绍了遗传算法的基本结构、特点和实现技术问题。然后针对矩 形件排样问题特点，提出了一种遗传算法对其进行求解，并给出了算法的具体 步骤。经过对不同约束条件下的算例进行求解，发现该算法所求得的优化结果 还是比较好的，即适应度较高，也就是板材利用率较高。 山东大学硕士学位论文 4 免疫算法求解矩形件优化排样问题 4 1 免疫算法的生物学基础 免疫系统是生物体的一个高度进化、复杂的功能系统。它能自适应地识别 和排除侵入机体的抗原性异物，并且具有学习、记忆和自适应调节能力，维护 机体内环境的稳定。 4 1 1 免疫学的基本概念 免疫系统是一个由众多组织、细胞与分子等构成的复杂系统，为了便于很 好地理解免疫系统的主要功能和作用机制，有必要先简单介绍一下免疫系统中 的一些基本概念和技术术语。这些概念主要包括【3 3 1 ： 1 抗原 抗原( a n t i g e n ) 是指能够刺激和诱导机体的免疫系统使其产生免疫应答， 并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。抗原具有两 种特性，其一为免疫原性( i m m u n o g e n i c i t y ) ，即抗原能刺激特定的免疫细胞， 使免疫细胞活化、增殖、分化，并最终产生免疫效应物质( 抗体和致敏淋巴细 胞) 的特性；其二为免疫反应性( i m m u n o r e a c t i v i t y ) ，即抗原与相应的免疫效 应物质在体内或体外相遇时，可发生特异性结合而产生免疫反应的特性。 2 自身抗原 自身抗原( a u t o a n t i g e n ) 是指能够引起自身免疫应答的自身组织成份。 3 抗体 抗体( a n t i b o d y ) 是指免疫系统受抗原刺激后，b 淋巴细胞转化为浆细胞 并产生能与抗原发生特异性结合的免疫球蛋白( i m m u n o g l o b u l i n ) ，该免疫球蛋 白即为抗体。 4 表位 表位( e p r o p e ) 即为抗原决定簇，它存在于抗原分子的表面，是决定抗原 特异性的特殊化学基团。抗原以此来与相应的淋巴细胞表面的抗原受体相结合， 激活淋巴细胞并引起免疫应答。另