（运筹学与控制论专业论文）二维矩形切割问题的研究与实现.pdf

辽宁科技大学硕士论文 摘要 摘要 二维矩形切割问题广泛存在于各种工业部门中，如生产钢铁制品、纸张、木 材、皮革、玻璃等行业。在所有这些应用中，通常都是先生产出少数几种标准规 格的大件产品，然后再切割成用户所要求规格的成品，这样往往比直接生产用户 所需规格成品要经济的多。然而，切割过程对于生产过程乃至企业效益有着重要 影响，特别是切割贵重材料时。同时，切割问题是一类组合问题和调度问题紧密 结合的复杂问题。由于组合爆炸，这类问题往往描述成大规模整数规划，已被证 明为是n p 难问题。因此，对于切割问题的研究无论是在理论价值上还是在实际生 产当中都具有重要意义。 本文研究的是矩形材料的切割问题，即二维矩形切割这一类问题。在对已有 的二维切割问题分析的基础上，考虑了几种研究较少的特殊情形。 其一、考虑了现有文献中极少考虑的1 5 维切割问题，即待切割零件具有固定 的维数和一个变量，这样的切割是介于一维和二维之间的。本文针对1 5 维切割的 特殊性，提出一种两阶段求解方法，并采用混合粒子群算法进行求解。实验结果 表明，该两阶段方法对解决1 5 维切割问题是行之有效的。 其二、对于可进一步减少切割损耗的切割路径优化问题进行讨论。通过对切 割路径优化问题和旅行商问题的比较，发现二者有着很多相似点。采用解决旅行 商问题的方法来解决一个路径优化问题，并采用遗传算法求解。 其三、为了迸一步减少浪费，对排样切割所剩下的废料进行进一步的优化利 用。由于所剩余的废料大小、数量不等，针对此问题建立多目标二维切割模型， 并采用启发式贪心算法求解。实验表明，该算法能够在很短的时间内得到近优解。 关键词：切割问题，粒子群算法，逮传算法，贪心算法，切割路径优化 辽宁科技大学硕士论文 a b s l r a c t a b s t r a c t t w od i m e n s i o n a lr e c t a n g l ec u t t i n gs t o c kp r o b l e m sc a nb ef o u n di nv a r i o u s i n d u s t r i e s t h e ya r i s e ，f o re x a m p l e ，w i t ht h ep r o d u c t i o no fs t e e lp r o d u c t s ，p a p e r ，w o o d ， l e a t h e r ，g l a s s ，e t c i na l lt h e s ec t t s c $ i ti su s u a l l ym o r ee c o n o m i c a lt op r o d u c el a r g e o b j e c t si no r d yaf e ws t a n d a r ds i z e sa tf i r s ta n dc u tt h e mi n t ot h es i z e sd e m a n d e db yt h e c ：u s t o ! r l e f sl a t e rt h a nt op r o d u c et h er e q u i r e ds i z e sd i r e c t l y h o w e v e r , t h ec u t t i n gp r o c e s s i t s e l f c a nh a v es e v e r ei m p a c t so nt h ec o m p a n y sp r o f i t ，e s p e c i a l l yw h e nm a t e r i a lo f h i g h v a l u ei si n v o l v e d a tt h es a m et i m e ，c u t t i n gs t o c kp r o b l e m sc a l lb ev e r yc o m p l i c a t e d ，f o r t h e yc o n c e r nc o m b i n a t o r i a lp r o b l e m sc l o s e l yi n t e g r a t e d 谢ms c h e d u l i n gp r o b l e m s t h e y t e n dt ob ep r e s e n t e da sl a r g e s c a l ei n t e g e rp r o g r a m m i n gd u et oc o m b i n a t o r i a le x p l o s i o n a n dh a v ea l s op r o v e dt ob en p - h a r d t h e r e f o r e ，t h es t u d yo fc u t t i n gs t o c kp r o b l e m sc ：a r t b eo f g r e a ts i g n i f i c a n c ei nt h e o r ya sw e l la si np r a c t i c e i nt h i st h e s i sw ec o r l c l 。r l lo i lt h et w o - d i m e n s i o n a lc u t t i n g b a s eo i lt h ea n a l y z i n g a b o u tt w o d i m e n s i o n a lc u t t i n gs t o c kp r o b l e m ，s e v e r a ls p e c i a li n s t a n c e sf i r ed i s c u s s e d f i r s t ，w es t u d yt h e1 5 d i m e n s i o n a lp r o b l e mw h i c hh a sb e e nd i s c u s s e dr a r e l y 1 5 d i m e n s i o n a lc u t t i n gp r o b l e m si sp a r t i c u l a rc a s eo ft h et w o - d i m e n s i o n a lp r o b l e m si n w h i c ht h el e n g t ho fas h e e ti si n f i n i t e i nt h i ss t u d y , at w o s t a g ea p p r o a c hi sd e v e l o p e d f o r1 5 一d i m e n s i o n a lc u t t i n gp r o b l e m a n dt h e nw eg o tt h es o l u t i o nb yu s i n gp a r t i c l e s w a r ma l g o r i t h m t h ee x p e r i m e n tr e s u l t si n d i c a t et h a tt h em e t h o di sa v a i l a b l ei n 1 5 - d i m e n s i o n a lc u t t i n gs t o c kp r o b l e m s s e c o n d ，w eo p t i m i z et h ec u t t i n gp a t hp r o b l e mo ft w o d i m e n s i o n a lr e c t a n g l es t o c k b a s e do i lc o m p a r e dt h ec u t t i n gp a t hp r o b l e ma n dt h et r a v e l i n gs a l e s m a np r o b l e m ，w e c h o o s et h em e t h o dw h i c hs o l v et h et s pp r o b l e mo r d i n a r i l y a n dw es o l v et h ec u t t i n g p a t hp r o b l e mb yu s i n gg e n e d ca l g o r i t h m t h i r d f o rm i n i m i z et h ec u t t i n gw a s t e s 、阳o p t i m i z et h ec u t t i n gf l o t s a m so v e l a g a i n b e c a u s eo ft h ec u t t i n gt l o t s a m sa r cd i f f e r e n ti nf i g u r ea n ds i z e ，w es e tu pam u l t i o b j e c t st w o - d i m e n s i o n a lc u t t i n gm o d e l a n dw es o l v et h ec u t t i n gp r o b l e mb yu s i n g g r e e d ya l g o r i t h m t h ee x p e r i m e n tr e s u l t si n d i c a t et h a tt h ea l g o r i t h mw i l lg e tt h e a n t i e i p a t i v es o l u t i 0 1 3 i nas h o r tt i m e k e yw o r d s ：c u t t i n gs t o c kp r o b l e m s ，p a r t i c l es w a r mo p t i m i z a t i o n ，g e n e t i c a l g o r i t h m ，g r e e d ya l g o r i t h m ，c u t t i n gp a t hp r o b l e m i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得辽宁科技大学或其它教育机构的学位或证书而使用过 的材料，与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 签名：玺：耋! 日期：递z 。i ：! 关于论文使用授权的说明 本人完全了解辽宁科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学 校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 螽。爨 导师签名：笪型 佥 辽宁科技大学硕士论文 第一章绪论 第一章绪论 本章首先介绍切割问题的来源、研究目的、背景和意义。对切割问题的分类 及研究现状进行了综述，并指出了现有文献中存在的问题及进一步研究的方向， 最后概括介绍了本文的主要工作。 1 1 背景及研究意义 1 。1 1 问题的产生 切割问题是在现实生活中经常能够遇到的一类问题，从古代开始人们对木材 等原料的简单切割，到现在型材、棒材和管材、金属结构材料、建筑材料甚至布 料切割，这个问题已有上百年的历史。随着经济的迅速发展，竞争越来越激烈， 效益显的尤为重要。 切割问题属于切割装箱问题的一个具体部分，是运筹学的一个分支，它是组 合问题和生产调度问题交叉的一个混合问题。由于组合问题的爆炸性，使它成为 大规模问题，这主要体现在对一个问题的所有切割方案的选择上，可能的合同切 割方案的各种组合方式，即切割方案的数目将是极其庞大的，已被证明为是n p 一 难问题。其主要目的是满足一定合同需求及某些特定工艺的约束下，通过确定切 割模式和执行次数，使某个预定目标达到最优或近优。 切割问题之所以激起了许多研究者的兴趣，其中一个重要原因是它具有广泛 的应用，并能直接产生经济效益。因为一种好的切割方法不仅可以节省原材料而 且可以加快切割速度，直接给企业带来益处。目前切割问题在许多方面的应用已 经取得成功，如运输装配问题( t r a n s p o r t 1 0 a d i n gp r o b l e m ) 、箱堆问题 f c o n t a i n e r - l o a d i n g p r o b l e m s ) 、背包问题( k n a p s a c k p r o b l e m ) 、切边问题( t r i m p r o b l e m ) 等方面都有一些较好的算法。对于一个加工型企业来说，要想降低成本提高效益， 很重要的一条就是合理使用原材料，用尽可能少的原材料规划出尽可能多的产品， 使不可能再用的余料最少，从而降低生产成本。本文研究的切割问题就根据生产 中抽象出来的，随着国民经济的蓬勃发展，切割问题的解决将日趋完善，其应用 领域将愈来愈广阔。 辽宁科技大学硕士论文 第一章绪论 1 1 2 相关概念 切割问题是满足一定的需求要求和在特定工艺条件约束下，选择一组切割方 案，使某个预定的目标最优或是近优。为了更好的说明问题，先介绍几个相关概 念： 切割方法用一根原材切割各种不同规格的成材，当改变一种成材切割数量 时，其他成材切割的数量也要相应改变，我们把每一种改变所对应的切割称作一 种切割方法。例如，一根原材料长l = 2 0 ，要切割的一种零件长= 4 ，另一种长 = 3 ，则用此根原材料切割3 根零件、2 根l 零件是一种切割方法，而切割成2 根零件4 根l 零件就是另一种切割方法。 切割方案用一根原材切割各种不同的规格成材的种类不变，只改变切割数 量，即改变切割方法，这时所采用的所有各种切割方法组合成的方案称为切割方 案。如上面举的两种切割方法都属于同一种切割方案。用一根原材料进行切割除 了只有一种规格的零件时切割方案只有一种切割方法以外，其余的每一种切割方 案都包含多种切割方法。 切割模型从每一种切割方案中各选一种切割方法，合理分配每种切割方法 切割的原材根数，使切割的不同规格成材的数量满足要求，则由这些切割方法所 组成的模型称为切割模型。 目标对于不同类型的切割问题，所要求的目标也不是完全相同的，如原材 料消耗最少、原材料剩余最少、最大的产出率等。 1 2 切割问题及其特征曙1 切割问题，国外称之为“c u t t i n gs t o c kp r o b l e m - - - c s p ”。该问题在不同的刊 物上有不同的提法，如。d i ml o s sp r o b l e m ”， b i np i c k i n gp r o b l e m ”， a s s o r a n e n t p r o b l e m ”，“l a y o u tp r o b l e m ”等。国内外学者从事这方面的研究主要因为：一方面 由于二维切割在计算机辅助设计和自动化设计应用中所起着较重要的作用，二维 切割研究具有诱人的经济前景，好的二维切割方案每年可以为制造业节约巨额资 金，而且很容易比较出运用合理的切割方法所带来的经济效益；另一方面由于它 涉及面很广，涉及机械、建筑、钢铁、船舶、车辆、玻璃、造纸、皮革等制造业。 最早关于c s p 的研究见于1 9 3 9 年，俄国经济学家k a n t o r o v i c h 建立了第一个一维 切割模型。1 ，尽管他的这种切割模型在1 9 6 0 年才以英文形式出版。但在这个领域首 辽宁科技大学硕士论文第一章绪论 先取得较重要进展的启发性工作则由g i l m o r e 和g o m o 喊成“。“，在他们的文献中， 他们提出用列生成技术求解一维c s p ，并对二维c s p 闷题进行了开创性探讨。由于 当时计算工具的限制，并未引起人们足够的重视。直至7 0 年代，由于高速计算机 的出现以及借助于计算机的现代化技术诸如线性规划、运筹学理论的发展，使得 c s p 问题的研究有可能付诸于生产实践，二维切割问题重新引起国内外学者的兴 趣，这个领域的研究日趋活跃，己取得了不少研究结论和成果。从那以后，这个 领域不同应用研究的文章数量迅速增长，涉及面不断拓宽，不断在代表不同学科 的杂志期刊上发表。涉及学科有管理科学( m a n a g e m e n ts c i e n c e ) 、工程科学 ( e n g i n e e r i n gs c i e n c e s ) 、信息和计算机科学( i n f o r m a t i o na n dc o m p e e rs c i e n c e s ) 、 数学( m a t h e m a t i c s ) 等。也是从那时起，各种切割模式及其各种求解方法迅速出现 并蓬勃发展。 切割问题的分类，可以从图1 1 看出： 图1 1 切割问题的具体分类 二维c s p 中，二维g u i l l o t i n e 切割是应用最为广泛的下料形式之一。g u i l l o t i n e 切割可简单的定义为：在板材上的每次切割轨迹是一条边到边的连通直线。又称 为“e d g et oe d g e ”的切割( 图1 2 ) 。例如，玻璃零件的切割。而n o n g u i l l o t i n e 切 割就没有这个边到边的限制( 图1 3 ) ，因此适应于矩形件的冲裁下料。 辽宁稃技大学硕士论文 第一章绪论 图1 2g u i l l o t i n e 切割 图1 3n o n g u i l l o t i n e 切割 切害0 实际上是切割及装箱问题的一种具体形式，是运筹学的一个分支。从七 十年代开始，有一些研究女l l b r o w n 、g o l d e r 等已经注意n c s p 问题与装箱问题的密 切关系，但此时并没有一种系统全面的总结此类问题的方法论。随着日后研究工 作的深入，切割与装箱问题存在着很强烈的对偶关系。也就是，在一定程度上切 割可以看作是将小条块所占的空间组装到大物体所占的空间里去，而装箱可以看 作是将大物体所占的空间切割成由小物体所占用的空间。切割问题的主要目的是 在满足一定合同要求及某些特定工艺约束下，通过确定的切割模式及执行次数， 使某些预定目标达到最优或近优。切割问题是一类组合问题和调度问题紧密结合 的复杂问题。这类问题往往是大规模问题，即切割模式的数目将是及其庞大，已 被证明是n p - 难问题，即非多项式时间可解问题。 虽然现实生活中存在着大量的各种各样的切割及装箱问题的应用，但基于它 们共同的逻辑结构，d y c k h o f f 提出可一种系统地分析切割及装箱问题( c & p ) 的类 型学方法。根据他的类型学方法，下面将从以下四个内在特征来分析这类问题， 通过以上的描述，对切割问题有了一个基本的了解，见表1 1 。 4 辽宁科技大学硕士论文第一章绪论 表1 1 切割问题特征分析 特征分类 1 、一维 2 、二维 维数 3 、三维 n 、n 维( n 3 ) ( b ) 所有大件与一系列所选小件匹配 分配种类 ( v ) 一系列所选大件与所有小件匹配 ( o ) 一个大件 大物体的分类( i ) 许多相同大件 ( d ) 不同大件 ( f ) 少量不同形状的小件 ( m ) 大量不同形状的小件 小物体的分类 ( r ) 大量相同形状( 但大小不一致) 的小件 ( c ) 一致小件 在这里，最重要的特征是维数。维数起着非常重要的作用，一维是维数的最 小数量。d y c k h o f f 列举了维数的一些类型，有一维、二维、三维和多维。然而， 还有一些问题介于一维和二维之间，即1 5 维。 最简单的情况就是一维。对一维c s p 问题的典型例子就是对长度固定的钢条进 行切割。在1 5 维问题中，此时材料有个固定的维数和一个变量。举个例子来说， 在一个钢板切割问题中，当钢板的宽度为变量，而钢板的长度固定时即为1 5 维切 割。二维就是有两个自由维数的情况，也就是，原材料板和所要求的小条块都为 长方形。 由于即使最简单的c s p 问题也已被证明是n p c o m p l e t e ，因此对于更加复杂的 c s p i h 题同样是n p c o m p l e t e 。这就意味着不存在解决此类问题的多项式时间算法。 由于c s p 问题的复杂性，在钢铁业中被认为是最需要优化的问题。在现实问题中， 不同的启发式算法得到广泛的应用。然而，由于启发式使用了代解决问题的特定 信息，因此不能用于解决其它类似问题。 c s p 问题的另一个重要特征即是分配种类。它至少可分为两类：第一类，使用 了所有的原材料，但并未满足所有的种类要求；第二类，所有的种类要求都得到 5 辽宁科技大学硕士论文 第一章绪论 了满足，但此时只使用了一部分原材料板。 c s p 问题的第三种特征可以被分为三类： ( 1 ) 只需要切割一个大物体； ( 2 ) 有许多相同维的大物体； ( 3 ) 有许多不同维的大物体； 当原材料包含有一次切割后剩余的小片时，就为最后一种情况。同样，按同 样方式也可以对小物体进行分类：第一类，只有少数不同维的小条块；第二类， 有许多小条块，其中的大多数都有不同的维；第三类，有许多小条块，其中的大 多数都有相同的维；第四类，所有的小条块都有统一的维。 c s p 问题的最基本目标就是使锯切损失最小，然而也存在其它一些重要的目 标。s t a i n t o n 列举了五十种影响效益的因素。实际上，影响锯切损失的最基本的因 素是某种切割模式的使用费用以及从一种切割模式到另一种切割模式的转换费 用。 切割模式可以简单定义为在一块库存板上切割成合同板的顺序，也就是合同 板在库存板上的布置。在大多数情况下，还会考虑方向和，或g u n l 娟n e 切割的约束。 1 3 目标和主要工作 下面，主要叙述本文的研究目标以及主要工作。 1 3 1 目标 ( 1 ) 本文最主要的目标是找到解决1 5 维、二维c s p 问题的有效方法。一些方法 被应用到特定的问题中，用程序实现并同文献的结果加以比较。 ( 2 ) 第二个目标就是根据解的质量来判断所提出的算法的质量。本文主要将精 力集中在将本算法结果与文献结果以及实际情况进行比较。 ( 3 ) 第三个目标就是在一个c s p 问题建立模型并通过计算得到最优解后，考 虑如何进行切割才能够使切割路径最优，进一步的提高生产效率。 1 。3 2 主要工作 ( 1 ) 对c s p 问题特点和性质进行了总结，对其各种应用领域和现象进行了分 类，综述了一维c s p i 司题的研究历史和现状，指出了存在的问题，指明了本文的研 究方向和创新点。 6 辽宁科技大学硕士论文 第一章绪论 ( 2 ) 针对1 5 维切割问题的特殊性，建立数学模型，采用两阶段法进行求解。结 合模型进行特点分析，并用程序实现。 ( 3 ) 在一个二维切割问题建立模型并通过计算得到最优解后，考虑如何进行切 割才能够使切割路径最优，进一步的提高生产效率。 ( 4 ) 在切割问题完成后，产生一些大小不等的废料，以它们为原材料，根据需 要切割一些长、宽均完全相同的小矩形件，建立模型，并通过程序求解，通过对 废料的再次利用，进一步减少浪费。 1 4 技术路线 首先，通过参阅文献，尽量了解c s p 问题的历史及研究现状。在钢铁业、造纸 业以及其它行业的c s p 问题十分相似，因此，我们在参阅文献时侧重了解不同文献 对于问题的不同数学模型描述和应用不同的算法求解。 其次，我们通过了解经典二维切割问题的特点和数学模型，进一步建立其它 现有文献考虑较少的情况，并建立数学模型。 最后，通过仿真实验。同现有的文献所提供的同规模问题的性能指标进行比 较。 辽宁科技大学硕士论文 第二章矩形件切割问题的模型及方法 第二章矩形件切割问题的模型及方法 二维c s p 问题是切割闯题的一个重要组成部分，它广泛应用于各个生产部门， 如钢铁、冶金、造纸、木材等，因此它也是c s p 问题领域开展研究较早，研究较 深入广泛的一个分支。本章先分析经典二维c s p 问题的数学模型，通过研究一些 特定工业背景下具有代表性的二维c s p 问题，来分析它们的共同特点和类别，从 而为矩形件切割问题的建模分析提供一些参考和借鉴之处。 2 1 二维切割问题的模型分析 2 1 1 切割模式 二维n o n - g u i l l o t i n e 优化切割问题描述为：已知库存板的长，宽为、矿，待 下零件即合同板共有聊种，其长宽分别为“，) ，i - - 1 ，2 ，m ，需求量分别为自， f = 1 ，2 ，m ，问如何切割最节约原材料，且切割模式为n o n - g u i l l o t i n e 切割。正如 在第一章所述，我们可以把切割模式简单定义为在一块库存板上切割成合同板的 顺序，即合同板在库存板上的布置。 2 1 2 切割问题的数学模型 c s p 问题的数学模型主要由密切相关的两部分组成：第一部分为切割模式的 优化选取模型；第二部分为切割方案的优化模型。 切割模式的优化选取模型主要解决巨大数量初始可行切割模式的优化选取问 题，切割方案的优化模型则是对所选取的切割模式进行优化组合，从而最终选取 切割模式的最优组合。目前大量研究文献已建立了各种各样的数学模型，这些模 型归纳起来主要有两类：一类是以原材料消耗的总张数最少为目标函数”_ ”；另一 类是以锯切损失总和最少为目标函数。”。 ( 1 ) 原材料消耗的总张数最少的数学模型： m i l l x j j - 1 s t 9 辽宁科技大学硕士论文第二章矩形件切割问题的模型及方法 口p _ 岛，i = l ，2 , - - - , m x 。0 ，且为整数 ( 2 ) 切割损失总和最少的数学模型： m i n 罗, il x w 一w 勺 - 弓 j = l i - i t 岛，i = 1 ，2 ，m z ；0 ，且为整数 其中： _ 在原材料上下料的第，种下料方式的使用次数，即第，种下料方式切割 原材料的张数； 口。原材料对应的第门冲下料方式下第f 种零件的数量： 矗第i 种待下零件的需求量。 对于以上数学模型，有的文献中的约束条件是等式约束，即： ( 3 ) 等式约束型切割损失总和最少的数学模型： m i n il x w - y l , w , a fh j l f = l 一= 岛，i = 1 ，2 ，m x ；0 ，且为整数 2 2 本章小结 对于以上所提到的决策变量个数未知而且数目及其庞大的整数规划问题，基 于数学规划的解法通常是先得到问题的线性规划解，然后通过某种约整策略来获 得问题的最后整数解。然而，此类大规模问题不同于一般整数规划问题，常规的 用来求解相应线性规划的单纯形算法此时就显得无能为力了，而基于列生成技术 的线性规划算法就很好的弥补了常规算法的不足，已成为求解此类大规模整数规 划问题的首选。 1 0 辽宁科技大学硕士论文 第三章凡种常见的智能侥化算法 第三章几种常见的智能优化算法 3 1 粒子群算法 粒子群优化算法( p a r t i c l es w a l 1o p t i m i z a t i o n - - p s o ) 的基本概念源于对鸟捕食 行为的研究“。设想这样的一个场景：一群鸟在随即搜索事物。在这个区域里只 有一块事物，所有的鸟都不知道事物在哪里，但是他们知道当前的位置离事物还 有多远，那么找到事物的最优策略是什么呢? 最简单有效的就是搜索目前离事物 最近的鸟的周围区域。这是一种信息共享机制，在心理学中对应的是在寻求一致 的认知过程中，个体往往记住它们的信念，同时考虑其它个体的信念。当个体察 觉其它个体的信念较好的时候，它将进行适应性地调整。p s o 从这种模型中得到 启示并用于解决优化问题，p s o 中每个优化问题的可行解都是搜索空间中的一只 鸟，称之为“粒子”，每个粒子都有一个由被优化问题决定的适应度，每个粒子还 有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解 空间搜索。p s o 初始化为一群随机粒子( 随机解) ，然后通过迭代的方式寻找最优解， 在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第一个是粒子本身所 找到的最优解，此极值称为个体极值即p 。，；另一个极值是整个种群目前找到的最 优解，这个极值就是全局极值岛。，。另外也可以不用整个种群而是只用其中一部分 作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 p s o 算法与遗传算法类似，它也是一种基于群体的优化工具，但与遗传算法 相比，p s o 算法具有收敛速度快，容易实现，而且又具有深刻智能背景的优点因 此它既适于科学研究，又适于工程应用，在短短几年时间里便成为国际演化计算 界研究的热点。目前，它已被国际进化计算会议列为讨论的专题。人们已提出了 多种p s o 算法，广泛应用于函数优化，神经网络训练，模式分类，模糊系统控制 等多个领域。 3 1 1 粒子群算法简介 p s o 是受鸟群觅食行为启发提出的，算法采用速度一位置搜索模型，每个粒 子代表解空间的一个候选解，解的优劣程度根据优化目标由适应函数决定。粒子 群算法随机初始化为一群粒子，第i 个粒子在d 维解空间中的位置表示为 = ( 而。，玉：，嘞) ，粒子的飞行速度v = ( v i 】，y j ：，) ，决定粒子在搜索空间迭代 时的位移。每一次迭代，粒子通过动态跟踪2 个极值来更新其速度和位置。第1 辽宁科技大学硕士论文 第三章几种常见的智能优化算法 个极值是个体极值p 。，= ( p t ，a ：，如) ，是粒子从初始到当前迭代次数搜索产生 的最优解；第2 个极值是群体极值g o = ( g l ，g 2 ，岛) ，是粒子种群目前能够达 到的最优解。粒子根据式( 3 1 ) 、式( 3 2 ) 来更新其速度和位置： e + 1 = w q + 陀嚣d ( a 一而) + c 2 r a 树x ( g 一) ( 3 1 ) k l = 五十i ( 3 2 ) 式中：w 称为惯性权重，是与前一次速度有关的比例因子；c l ，岛是常数，称 为学习因子，一般取c f = 岛= 2 ；r a n d 是随机数。粒子群优化算法是基于群体智 能理论的优化算法，它利用群体中粒子间的合作与竞争产生的群体智能指导优化 搜索。与进化算法比较，( a ) 粒子群算法保留了基于种群的全局搜索策略，而采用 的速度位置模型操作较为简单，避免了复杂的遗传操作，它特有的记忆功能使其 可以动态跟踪当前的搜索，并能根据搜索情况调整搜索策略；( b ) 粒子群优化算法 是一种更高效的并行搜索算法，其概念简明清晰，容易实现，代码简短，优点显 著。 p s o 的基本算法步骤描述如下： 步骤l 采用随机产生的位置和速度在整个解空间中初始化粒子群。 步骤2 对于每个粒子，根据适应度函数计算其适应度函数值。 步骤3 比较每个粒子的适应度函数值和个体极值。如果当前值优于。， 就设置当前值为新的，粒子当前的位置勃为新的的位置磁。比较适应度 函数值时，需根据具体的优化问题确定，可能数值越大越优，也可能恰恰相反。 步骤4 比较所有粒子的适应度函数值和全局极值鼋。如果当前值优于g 。， 就设置当前值为新的，粒子当前的位置为新的的位置苟。 步骤5 改变每个粒子的速度和位置。 步骤6 如果满足了停止循环的准则，就可终止计算；否则转到步骤2 继续循 环。 基本粒子群流程图如图3 1 所示： 1 2 辽宁科技大学硕士论文 第三章几种常见的智能优化算法 图3 1 基本粒子群流程图 下图显示了粒子在解空间中的寻优过程： l 0 。 i 曩 ： i j 潼o 嘲焉絮量 喇i ? 一静孵l j ，曼i 娑篱掣媲 ? 薅羽 图3 2 粒子在解空间中的迁移方式 其中：玉，( t ) ：粒子在解空间中的当前位置； 薯，0 + 1 ) ：粒子在解空间中的下一更优位置； v ( f ) ：粒子当前飞行速度： v ( t + 1 1 ：粒子的改进飞行速度。 * ，鳓 二r 辽宁科技大学硕士论文第三章几种常见的智能优化算法 3 1 2 粒子群优化算法的参数选择 粒子数：一般取2 0 4 0 。其实对于大部分的问题1 0 个粒子已经足够可以取得 好的结果，不过对于比较难的问题或者特定类别的问题，粒子数可以取到1 0 0 或 2 0 0 。 粒子的长度：这是由优化问题决定，就是问题解的长度。 粒子的范围：由优化问题决定，每一维可设定不同的范围。 、k ：最大速度，决定粒子在一个循环中最大的移动距离，通常设定为粒子的 范围宽度，例如粒子( 西，而，而) ，五属于【- 1 0 ，1 0 ，那么k 的大小就是2 0 。 惯性权重：它的大小决定了搜索的步伐大小，通常是希望在开始时能搜索的 步伐大些这样可以加快速度，但随着叠代次数增加应该让步伐逐渐变小这样可以 避免错过最优解。 学习因子：自身因素参数q 和社会因素参数岛般要根据经验值来定。在函数 优化问题中通常等于2 。不过在文献中也有其他的取值，但是一般c 1 等于岛并且范 围在0 和4 之间。 中止条件：最大循环数亦或得到最小误差要求。这个中止条件通常要由具体 的问题确定。 p s o 算法分为普通的全局p s o 和局部p s o ( 不用整个种群而是只用其中一部分 作为粒子的邻居) ，前者速度快不过有时会陷入局部最优，后者收敛速度慢一点不 过很难陷入局部最优。在实际应用中，可以先用全局p s o 找到大致的结果，再用 局部p s o 进行搜索。 3 1 3 粒子群算法的典型特征 1 、它有一个初始化过程，在这个过程中，群体中的个体被赋值为一些随机产 生的初始解； 2 、它通过产生更好的新一代群体来搜索解空间； 3 、新一代群体产生在前一代的基础之上。 3 1 4 粒子群优化算法的总结和展望 p s o 在理论上并不能保证能够得到最优解。p s o 算法在进行优化问题的求解 1 4 辽宁科技大学硕士论文第三章几种常见的智能优化算法 时应用范围有限，尤其对离散的组合优化问题，其理论建模还处于起步阶段。p s o 算 法中的一些参数如学习因子c l ，c ：惯性权重w 以及粒子个数往往根据有限的应用经 验确定，并不具有广泛的适应性。因此将p s o 与进化算法、模糊系统、神经网络以 及一些优化技术结合，根据不同的优化问题建立相应的p s o 模型是p s o 算法当前的 研究重点。 p s o 算法的思想是跟踪最好点，并逐步向最好点靠近。在应用中表现为收敛 速度快，但与其它全局优化算法( 如遗传算法) 一样，该算法同样存在早熟收敛现象， 尤其是对复杂的多峰搜索问题，这一现象更为突出。因此出现了众多的对其进行 改进的研究工作。对此虽然已有很多研究工作，但是各有其优缺点。一些改进的 p s o 算法，如模糊p s o 算法“”、杂交p s o 算法“、智能p s o 算法“”存在着较复 杂、不便使用的缺点，而另一些改进的p s o 算法存在计算复杂度高、收敛速度慢 的缺点“”，如协同p s o 算法等“。 在应用领域，应该将p s o 算法在应用的广度和深度进行拓展。以制造业自动化 领域为例，制造企业中的工艺路径规划问题是企业自动化的瓶颈问题之一，直接影 响c a p p 与c a d ，c a m 系统的集成。究其原因是工艺路径规划问题的特殊性决定 其对生产经验的严重依赖。可以考虑将大量的工艺规划经验组成专家系统，根据不 同的工艺问题制定相应的模糊控制规则并利用p s o 算法训练人工神经网络自动生 成工艺路径。 3 。2 基本遗传算法 遗传算法( g e n e t i ca l g o r i t h m s ) 是模拟生物在自然界中的遗传和进化过程而形 成的一种自适应全局优化搜索算法“”。它最早由美国密执安大学的h o l l a n d 教授提 出，起源于上世纪6 0 年代对自然和人工自适应系统的研究。遗传算法产生的开始 阶段并没有引起人们的关注，一方面是因为它本身还不成熟；另一方面，当时的 计算机容量小，计算速度慢，也使得需要较大计算量的遗传算法难以实际应用。 上世纪7 0 年代d ej o n g 基于遗传的思想在计算机上进行了大量的纯数值函数优化 计算实验。在一系列研究工作的基础上，上世纪8 0 年代由g o l d b e r g 进行归纳总结， 形成了遗传算法的基本框架，遗传算法也迎来了兴盛发展时期。这包括对“早熟” 现象的研究和对“收敛”的证明 1 8 , 1 9 同时针对遗传算法的不足提出了改进方法， 取得了一定的成绩。 丑宁科技大学硕士论文第三章几种常见的智能优化算法 3 2 1 基本遗传算法概述 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受 其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应 系统的设计和开发提供了广阔的前景。遗传算法就是这种生物行为的计算机模拟 中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使 得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基 础就是生物的遗传和进化。 生物的遗传物质的主要载体是染色体( c h r o m o s o m e ) ，脱氧核糖核酸是( d n a ) 其中最主要的遗传物质，而基因( g e n e ) 又是控制生物性状的遗传物质的功能单位和 结构单位。复数个基因组成染色体，染色体中基因的位置称作基因座( 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 ) 。所谓表现型是指生物个体所表现出来的性 状，而基因型指与表现型密切相关的基因组成。同一种基因型的生物个体在不同 的环境条件下可以有不同的表现型，因此表现型是基因型与环境条件相互作用的 结果。在遗传算法中，染色体对应的是数据或数组，在标准的遗传算法中，这通 常是由一维的串结构数据来表现的。串上各个位置对应上述的基因座，而各位置 上所取的值对应上述的等位基因。遗传算法处理的是染色体，或者叫基因型个体 ( i n d i v i d u a l ) 。一定数量的个体组成了群体口o p u l a t i o n ) 。群体中个体的数目称为群体 的大小f p o p u l a t i o n s i z e ) ，也q 群体规模。而各个体对环境的适应程度叫做适应度 ( f i t n e s s ) 。 此外，执行遗传算法时包含两个必需的数据转换操作，一个是表现型到基因 型的转换，另一个是基因型到表现型的转换。前者是把搜索空闻中的参数或解转 换成遗传空间中的染色体或个体，此过程又叫做编码( c o d i n g ) 操作；后者是前者的 一个相反操作，叫做解码( d e c o d i n g ) 操作。 尽管遗传算法本身在理论和应用方法上仍有许多待进一步研究的问题o “2 “，由 于它具有简单、通用、鲁棒性强，适用于并行分布处理等特点，遗传算法在下面 领域的应用中己展现了其特色和魅力：函数优化、组合优化问题、生产调度问题、 自适应控制、结构性优化、图象处理、军事应用、规划设计、遗传编程、机器学 习和人工生命等。 辽宁科技大学硕士论文第三章几种常见的智能优化算法 3 2 2 基本遗传算法的构成要素 ( 1 ) 染色体编码方法。基本遗传算法使用固定长度的二进制符号串来表示群体 中的个体，其等位基因是由二值符号集f o ，l 所组成的。初始群体中各个个体的基 因值可用均匀分布的随机数来生成。如 x = 1 1 0 l o l l 0 1 1 1 0 1 1 0 0 0 1 就可表示一个个体，该个体的染色体长度是1 8 。 ( 2 ) 个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前 群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要 求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确 定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当前目标 函数值为负数时的处理方法。 ( 3 ) 遗传算子。基本遗传算法使用下述三种遗传算子： 选择运算使用比例选择算子； 交叉运算使用单点交叉算子； 变异运算使用基本位变异算子或均匀变异算子。 ( 4 ) 基本遗传算法的运行参数。基本遗传算法有下述4 个运行参数需要提前设 定： 吖：群体大小，即群体中所含个体的数量，一般取为2 0 1 0 0 ； 丁：遗传运算的终止进化代数，一般取为1 0 0 5 0 0 ； 以：交叉概率，一般取为0 4 o 9 9 ； 以：变异概率，一般取为0 0 0 0 1 0 1 。 3 2 2 1 基本遗传算法的描述 下面我们给出基本遗传算法的伪代码描述 b e g i n i n i t i a l i z ep ( 0 ) ； 仁o ： w h i l e ( t = t ) d o f o r i = lt o m d o e v a l u a t ef i t n e s so f p ( t ) ； e n d f o r 辽宁科技大学硕士论文 第三章几种常见的智能优化算法 f o r i - 1t o m d o s e l e c to p e r a t i o nt op ( t ) ； e n d f o r f o r i _ 1t o m 陀d o c r o s s o v e ro p e r a t i o nt op ( t ) ； e n d f o r f o r i = lt o m d o m u t a t i o no p e r a t i o nt op ( t ) ； e n d f o r f o r i