（载运工具运用工程专业论文）基于改进蚁群算法求解fms工艺路线优化配置问题的研究.pdf

j j 交上謦硕l 学位沦文 基于改避蚁群算法求钟f m s 工艺路线优化d ! 置问题的研究 摘要 随着信息时代的来l 临，生产制造已经转向以多品种、中小批量 为主要模式。柔性制造系统( f m s ) 是为此而发展起来的一种自动化 生产方式。高度的生产柔性使得f m s 可以连续不断地以几种不同 的工艺路线加工各种零件，而如何安排各工艺路线在生产中所占份 额，最大限度地提高系设备的利用率和生产率就成为必须解决的问 题。本文以f m s 的工艺路线优化配置问题为对象进行了研究。 在对f m s 工艺路线优化配置的一般概念、相关理论、以及研 究现状进行了详细介绍和分析的基础上，提出了本文的研究方案。 为了得到较好的分析性和较快的求解速度，该方案使用闭环排队网 络( c q n ) 建立了f m s 的模型，以此模型来描述求解对象和求解 过程。c q n 优化模型具有多变量、非线性约束等特点，求解难度 高，计算量大。目前求解该问题比较有效的方法是t e t z l a f f 所提出 的解析算法，但确定搜索步长所带来的困难影响了该算法在工程上 的实际应用。 蚁群算法的特点表明它适合于求解f m s 工艺路线优化配置这 类非线性约束复杂优化问题。本文充分利用了蚁群算法在求解该类 问题方面的优势，通过融合了网格法的蚁群算法实现了将蚁群算法 用于求解多变量连续函数优化问题。针对蚁群算法自身存在的容易 陷入局部最优等问题，提出了引入交叉算子和变异算子来改进算法 的性能。此外，为了防止算法在实施过程中约束条件被破坏，本文 设计了一种新的边界收缩策略。为方便于验证与应用，根据本文的 研究方案，编写了相应的软件。最后，选用工程实践中的具体算例 来验证了将改进蚁群算法应用于求解f m s 工艺路线优化配置问题 的有效性。 关键词：柔性制造系统，工艺路线，闭环排队网络，蚁群算法，网 格法 a b s t r a c t w i t ht h ea d v e n to fi n f o r m a t i o ne p o c h ，t h em o s t l ym o d eo fm a n u f a c t u r i n g t u r n st om u l t i b r e e d ，m i d d l i n go rs m a l ll i t t l eb a t c hf m s ( f l e x i b l em a n u f a c t u r i n g s y s t e m ) i sad e v e l o p i n ga u t o m a t i cp r o d u c t i o nf a s h i o nf o ri t f m sc a np r o c e s s p a n st h r o u g hs e v e r a l d i f f e r e n tr o u t e sc o n t i n u o u s l y ，t h e nh o wt oo p t i m i z et h e a s s i g n m e n to fp r o d u c t i o nr e q u i r e m e n tt oa l t e m a f f v er o u t e s b e c o m e sap r o b l e m n e c e s s a r y f o r m a x i m i z i n g t h e t h r o u g h p u t o fa g i v e n f l e x i b l e m a n u f a c t u r i n g s y s t e m i nt h i sp a p e rw et a k e t h eo p t i m i z a t i o no ft h ea s s i g n m e n tt oa l t e r n a t i v e r o u t e sa st h er e s e a r c h i n go b j e c t g u i d e db yt h e o r yo fo p t i m i z a t i o no ft h ea s s i g n m e n tt oa l t e r n a t i v er o u t e s ，t h i s d i s s e r t a t i o ne s t a b l i s h e si t so w nt h e o r e t i c a lf l a m e f o rb e t t e ra n a l y t i c a lp r o p e r t y a n dl e s st i m ec o n s u m i n gf o rb e i n gs o l v e d ，c o ni sa p p l i e dt oe s t a b l i s ht h em o d e l o ff m s c o nh a sm u l t i v a r i a b l e sa n dn o n l i n e a rc o n s t r a i n ts e t s ；i ti sd i 筒c u l tt ob e s o l v e d u p t i l ln o w , r e p r e s e n t a t i v em e t h o di st h ea n a l y t i c a la l g o r i t h mp r o p o s e db y t e t z l a f f w h e r e a st h e d i f f i c u l t ya r i s i n g f r o m c o n f i r m i n g t h e s t e pl e n g t h o f s e a r c h i n g r e s t r i c t st h ea p p l i c a t i o no ft h i sa l g o r i t h mt op r a c t i c e c h a r a c t e r i s t i c so fa n tc o l o n ya l g o r i t h mi n d i c a t et h a ta n tc o l o n ya l g o r i t h m w i l lw o r kw e l li n s o l v i n gc o m p l i c a t eo p t i m i z a t i o np r o b l e m sw i t h n o n l i n e a r c o n s t r a i n ts e t sj u s tl i k et h eo p t i m i z a t i o no fa s s i g n m e n to fr o u t e s i n t e g r a t e dw i t h g r i d d i n g m e t h o da n t c o l o n ya l g o r i t h m c a nb eu s e dt os o l v ec o n t i n u o u s m u l t i - v a r i a b l e so p t i m i z a t i o np r o b l e m s a sa n tc o l o n ya l g o r i t h mi se a s yt of a l li n t o l o c a lb e s t ，i nt h i sp a p e ra ni m p r o v e da l g o r i t h mi sp r e s e n t e dt os o l v et h i sp r o b l e m ac r o s s o v e ro p e r a t o ra n dam u t a t i o no p e r a t o ra r ec o n t a i n e di nt h i sa l g o r i t h m i t c a n i m p r o v ea n tc o l o n y t om a k et h ec o r r e s p o n d i n gs o l u t i o nb e t t e r , m o r e o v e r , n e w m e t h o df o rc o n t r a c t i n gt h er a n g eo fv a r i a b l e si s a p p l i e dt oa v o i dc o n s t r a i n ts e t s b e i n gd e s t r o y e d b a s e d o nt h e r e s e a r c h i n gp r o j e c tc o r r e s p o n d i n g s o f t w a r ei s d e s i g n e d a tt h ee n d o ft h i sp a p e r ，w eg i v eo u ta ne x a m p l et ov a l i d a t et h et h e o r y a n dm e t h o d s k e y w o r d s ：f l e x i b l em a n u f a c t u r i n gs y s t e m ，r o u t e s ，c l o s e dq u e u i n g n e t w o r k s ，a n tc o l o n ya l g o r i t h m ，g r i d d i n gm e t h o d i i m 启主逼上擎硕士学位论文 基于敌进蚁群算法求解f m s 工艺蹄线优化配置坷题的研宄 第一章绪论 1 1 柔性制造系统及其性能特点 1 1 1 概论 随着经济的发展，生活水平的提高，追求多样化、新颖化成为 社会风尚，对消费品的要求更高，希望产品有自己的特色。目前， 每个制造商都必须迎合顾客的需求去开发新产品和组织生产。激烈 的竞争使传统的大规模生产环境发生了改变，要求对传统的零部件 生产工艺加以改进。 在激烈的市场竞争中，人们也认识到缩短从定货到交货的周期 是赢得竞争的主要手段。然而那种有着固定生产节拍，而且设计复 杂，投资巨大的刚性自动化生产线是无法满足不同顾客对产品的不 同要求，也无法在激烈的市场竞争中占据优势。 市场的变化与发展促使企业界寻求一条有效的途径，来解决多 品种、中小批量生产自动化问题。经过几十年不懈的努力，终于找 到了解决这个问题的金钥匙柔性制造系统。 柔性制造系统( f l e x i b l em a n u f a c t u r i n gs y s t e m ，f m s ) 的首创者是 美国的m a a l r s o s e 公司，它于1 9 6 3 年制造了世界上第一条加工 多种柴油机件的数控自动线。1 9 6 7 年英国m o l i n s 公司生产的制造 系统s y s t e m - 2 4 ，利用计算机分散控制加工设备，每天可连续工作 2 4 小时，使柔性制造系统的思想正式形成。自上世纪7 0 年代以来， 柔性制造系统得到了很大的发展。迄今为止，柔性制造系统除应用 于机械制造业以外，还在集成电路生产、服装等行业得到了广泛应 用。我国自上世纪8 0 年代中期开始发展柔性制造系统，经历了消 办毒置逦上莘硕士学位论文 基于馥进蚁群葬法求孵f m st 艺路线优化配置问罡l 的研究 化、国产化和自行设计开发三个阶段，目前我国己投入使用或正在 研制的柔性制造系统已逾2 0 多条【1 1 。 1 1 2 柔性制造系统的一般概念 由于柔性制造系统还在发展中，所以其概念尚无统一的定义， 但以下观点是被广泛接受的：柔性制造系统是在自动化技术、信息 技术和制造技术的基础上，通过计算机技术，把工厂生产活动中的 自动化设备有机的集成起来，打破设计和制造的界限，取消图纸、 工艺卡片，使产品设计、生产相互结合而成的，能根据制造任务和 生产品种的变化而迅速进行调整的，适用于中、小批量和较多品种 生产的高柔性、高效率的自动化制造系统1 2 - 5 】。 柔性制造系统一般由三部分组成： ( 1 ) 加工系统：f m s 采用的设备由待加工工件的类别决定，主 要有加工中心、车削中心或计算机数控( c n c ) 车、铣、磨及齿轮加 工机床等，用以自动地完成多种工序的加工。 ( 2 ) 物料系统：用以实现工件及工装夹具的自动供给和装卸， 以及完成工序间的自动传送、调运和存贮工作，包括各种传送带、 自动导引小车、工业机器人及专用起吊运送机等。 ( 3 ) 计算机控制系统：用以处理f m s 的各种信息，输出控制 c n c 机床和物料系统等自动操作所需的信息。通常采用三级f 设备 级、工作站级、单元级) 分布式计算机控制系统，其中单元级控制 系统( 单元控制器) 是f m s 的核心。 1 1 3 柔性制造系统的性能特点 f m s 的主要优点有： 高生产率； 高产品质量； 低劳动强度； 短生产周期； 办 i z 攀硕士学位论文 基于改进蚊群算法求解f m s 工艺路线优化配置问题的研究 高设备利用率： 高柔性制造能力。 柔性制造系统可根据需要加工多种工件，换言之，柔性制造系 统的主要特点之一是其具有柔性，主要表现在： ( 1 ) 加工柔性：可以加工给定的数种工件： ( 2 ) 产品柔性：可以经济的转向新种类工件的生产； ( 3 ) 操作柔性：具有改变工件加工工序次序的能力； ( 4 ) 工艺柔性：能以几种工艺路线来加工工件； ( 5 ) 容错柔性：在正常的生产加工情况下，可以处理设备故 障： ( 6 ) 批量柔性：能在不同的生产批量下经济有效的运行； ( 7 ) 扩充柔性：能方便地扩充系统规模。 尽管f m s 有许多优点，但是在工业实践中发展f m s 也存在一 些困难，或者说f m s 还存在着一些缺点。 f m s 的主要缺点为： ( 1 ) 高昂投资：f m s 的投资随f m s 的规模和自动化程度不同 而不同，一般需要几百万甚至上千万美元的投资，这还不包括支持 运行环境建设的费用。 ( 2 ) 建设周期长：f m s 技术复杂，开发、研制、调试一套f m s 系统需要较长的周期，从提出开发一个f m s 到将其具体实现，往 往需要几年的时间。 由于这些困难或缺点使得许多企业对现代化f m s 缺乏信心， 望而却步。也存在一些效果未达到预期的目的，甚至是失败的f m s 应用案例。 正是由于f m s 的实际应用效果与潜在优点之间存在较大差距， 合理地进行系统规划设计就成为了保证f m s 高效运行的重要前提。 资料表明，国外现已运行的f m s 中约有8 0 没有达到设计要 求，而其中6 0 是由于初期规划不全面或失误造成的。因此，寻找 如j 主逼上挚硕士学位论文 基下改进蚁群算法球解f m s 工艺路线优化配置闯韪的研究 先进有效的f m s 规划设计方面的理论和技术便成为克服f m s 的上 述缺点，改善f m s 性能而亟待研究的课题。 1 2f m s 工艺路线优化配置问题 f m s 本身是由多台加工中心、工件传送系统、控制系统等所组 成的一种高自动化的机械加工系统，但它通常是一个更大生产系统 ( 例如工厂) 的子系统。f m s 所属的大生产系统的生产计划决定了 f m s 所要加工工件的种类、数量、原材料供应日期以及完工产品的 交货日期。这样，f m s 的生产计划所涉及的问题就是如何有效地组 织生产，在满足大系统生产要求的同时，使f m s 自身所拥有的有限 资源( 机床、托具、夹具、刀具、小车等) 得到有效的利用，负荷 达到均衡”1 。 当把f m s 所属大系统的生产计划确定下来之后，f m s 生产调度 管理所要解决的第一个问题就是待加工零件的分批。3 。零件分批的 目的在于有限数量资源的条件下合理组织生产，使f m s 可以不停机 做任何调整，连续不断地加工完一批零件中的全部零件，并保证产 品能按时交货。在零件分批之后，所面临的问题就是如何去加工每 一批零件，才能使得各台设备负荷达到均筏并使机床利用率最高。 解决上述问题最重要的任务之一就是通过寻找最佳的工艺路 线混合比来保证零件的加工时间最短。零件不同的工艺路线的混合 增大了系统的柔性，同时也在产品需求和系统性能之间建立了联 系。只有对各种工艺路线进行合理的配置，才能有效地组织生产， 使各台设备的负荷达到均衡，从而令f m s 自身所拥有的有限资源 得到有效利用，这样才能使系统的性能在按时完成生产任务的前提 下得到最大限度的改善。工艺路线的配置不合理，不仅会导致制造 系统不良的运行性能，而且还会导致较差的经济性能，造成极大的 资源浪费。 ， 毒之z 挚碗士学位论文 辈 二盏进蚁群算法术解f m s 工艺路线优化配簧问题的研究 1 3f m s 工艺路线优化配置问题研究现状 由上节分析可知，为了能使柔性制造系统中有限的资源使用效 率最高，使得系统的生产率达到最大，零件的工艺路线优化配置是 必须要解决的问题。 零件工艺路线优化配置问题为复杂的非线性约束优化问题，属 n p - c o m p l e t e 问题，同时具有等式约束和不等式约束，因此其求解 难度和计算量非常大。尽管如此，由于该问题在工程实践中的重要 意义，国内外学者在此领域进行了大量的研究。 s e c c o s u a r d o 在“托盘无限”这一假设的基础上提出了解决该 问题的模型1 8 j 。在该模型中，决策变量为以每种可行工艺路线加工 各工件时的生产率，系统的总生产率等于所有工件以每种可行工艺 路线加工时的生产率之和，某一工件的生产率是系统的总生产率和 该产品所占产品总量的百分比的乘积。而为了保证由此求出的工艺 路线配置方案进行生产时，不会超出各工作站的加工能力，提出相 应的约束条件，即系统总生产率与某一工作站负荷的乘积不大于该 工作站中的机床数。k i m e m i a 和g e r s h w i n 提出的线性规划模型与 s e c c o s u a r d o 的模型非常相似。同样以最大产量为优化目标，不同 之处在于两者的决策变量。该模型的决策变量为某运行周期中工件 在某一类加工设备的生产量。该方法是通过优化运行过程中零件加 工设备的选取方案来最终产生最优的工艺路线的配置方案【9 1 。由 a v o n t s 所提出的另一种模型是以系统中设备利用率最大为优化目 标，该模型是以一定的比率采用每种可行的工艺路线加工某种工 件，并要保证产品不会超过预先制定的产量【1 。】。 以上三种模型都具有线性规划的结构，都可以用单纯形法来求 解。然而这三种模型都是描述系统的静态行为且假设托盘为无限， 可f m s 的生产是连续不断进行的，这就妨碍了这些模型在f m s 中 的应用；而当系统中具有大量托盘使得托盘的成本可以忽略不记 时，这些模型同样不适用。 # 毒交逼z 莘硕上学位论文 鉴于改进蚁群葬往求解f m s 工艺路线优化酝置问题的研究 为了解决上述问题，k i m e m i a 和g e r s h w i n 又提出了一种可以 描述系统动态行为的模型。该模型是他们之前所提出模型的拓展， 并借鉴了排队论的思想【1 1 】。该模型是通过使某一运行周期中各工件 在某类设备上的总的流量最大来得到整个系统的最大生产量，该模 型要求系统中在加工的工件平均数不大于预先给定的常数n ，并且 为了保证系统生产连续不断，必须服从在不同周期中各工件在所有 类型设备上的总流量相等的约束。该模型可以利用g e r l a 提出的 e f m e t h o d i ”j 和d a n t z i g 及w o l f e 提出的方法【1 3 j 来求解。通过对于 系统动态行为的描述使得该模型很适合用于f m s ，但是该模型假设 系统中存在数量足够大的托盘，这一点往往与实际情况不相符。 y a o 和s h a n t h i k u m a r 提出的模型是以工件进入某一加工单元的 输入率为决策变量，以最大生产率为优化目标。每一加工单元由若 干并行运行的设备构成，没有提供待加工零件等待的空间。当一个 工件到达时，若有空闲设备则对该工件进行加工，加工完毕工件离 开系统。如果没有空闲设备，则工件进入中央缓冲区【1 4 】。根据排队 论，该问题可以转化为一个求解凸函数最小值的问题。y a o 和 s h a n t h i k u m a r 提出了使用改进的f r a n k w o l f e 算法【1 5 】来求解此问题。 但是，由于进入系统的工件被输送至任一加工单元加工之后就离开 系统，因此，可以认为每个工件在整个系统中只完成一种操作。对 于进入不同加工单元打工件，只有加工时间会有所不同。这一点严 重制约了该模型在f m s 中的适用性。 在总结该领域已有成果并分析了各种研究方案不足的基础上 t e t z l a f f 提出了一种求解该问题的解析方法【1 6 】。在该方法中t e t z l a f f 定义了一个能够表示工件在系统中的平均通过时间d ( q ) 随q f 相对 变化的变量l g r ： f8 d ( q ) 1 粤。薹2 薹带 i 逼上莘硕士学位论文 基于改进蚁群算法求解f m s 工艺路线优化配置问题的研究 冥中， 引卟参却o ，咄v h 为系统中共有n 个托盘时，在m 工作站的平均托盘数， 薹既( ) = 。而p 如。= 女，) = 石高等击g 抑( 一，m ) 为系统中 q 。( ) = 。而p 如。= 七，) = 揣g 抑( 一七，m ) 为系统中 共n 个托盘时，m 工作站有k 个托盘的概率，并且： g 枷加，m ) = g ( 月，m ) 一荟l ( 七) g m 。- k , m ) m z 1 ，2 r ，m ；月_ 1 ，2 ，。v g “f o 州1 = 1 t e t z l a f f 在研究后发现，q ，的变化可引起1 。的同向变化，并且 在每种工件不同工艺路线的l 。相等时，d ( q ) 近似达到极小值。因此 可根据l ，来调整q f ，最终使同种工件的不同工艺路线的i ，近似相 等。调整过程中，若欲被减少的q 。已经为0 ，则不作调整，其1 。 也不参与终止规则评判。需要注意的是一个工件q 。的调整，可能 引起其它工件l ，的变化。因此每次调整一个q 。后，需先更新参与 后续计算的b ，再调整其它工件的l ，所有可调整q ，的工件均调 整一次后，即完成一个循环，每个循环完成后进行终止规则判断。 在该方法中，由于某一个的调整将影响整个系统的负荷分 配，从而引起所有b 的变化，因而降低了算法的效率。另外，搜索 步长系数的选取非常困难，而该系数的选取也直接影响到算法的收 敛状态。该算法的上述缺点影响了在工程上的实际应用。 从以上分析我们可以看出，尽管学术界和工业界对于f m s 工 艺路线优化配置这一问题已经进行了许多研究并已取得了一定的 成果，但遗憾的是这些成果总体上来说并不能让人满意，所存在的 问题还是很明显的，没有一个优化方案既能准确描述系统运行时各 部分之间的关系又能快速有效地求出问题的最优解。因此，有必要 办 主g 辟硕士学位论文 摹 = 改进蚁群算 盍求解f m s 工艺蹿线优化配置问题的研究 对在该领域进一步开展研究，寻求更加可行有效的求解方案。 1 4f m s 工艺路线优化配置问题相关理论简介 1 4 1f m s 建模方法 由1 3 节的文献综述可知，解决f m s 工艺路线优化配置问题首 先要建立相应的模型。由于f m s 属于离散事件动态系统( d e d s ) ， 高度的柔性使得由工件、机床、托具、夹具、刀具、传送装置及所 选择的工艺路线等构成的所有可能排列组合及其对应的运行结果 几乎是无穷的。而且，系统中的每一台机床、运料小车、换刀机器 人等本身就是一个自动控制系统，当把f m s 作为一个整体研究时， 这些单元不仅仅被看成一个简单实体，他们彼此之间相互影响、相 互制约，形成了错综复杂的联系。可见，要建立一个理想的f m s 模型并不容易。 随着有关d e d s 理论的迅速发展，一些理论工作者和实际工作 者在f m s 建模问题上作了许多工作，提出了一些方法，其中较为 典型的方法有以下几种： 1 极大代数法 此种方法是首先由g c o h e n 等人提出的，它以极大代数为工具， 将f m s 视为确定性系统。系统中各加工活动的开始时间看作是离 散事件系统的状态变量，工件和机床等资源投入时间看作是输入变 量，而资源从系统中释放即任务完成时间看成是输出变量，这样就 根据系统的运行关系建立起一系列事件发生时间的状态方程。通过 特征值分析可以求到f m s 的加工周期，各机床的利用率。由于此 种方法着眼于系统内部的运行关系，亦有人称之为运行分析法旧。 但是，由于将f m s 看作一个确定性系统，因而系统没有决策 能力，对系统中出现的各类随机情况也未加以考虑。而且，事件与 ；驺交逗z 乎硕士学位论文 基于教避蚁群算注采解f m s 工艺路线优化配置问题的研究 状态变量一一对应使得当系统规模增大时方程的维数也随之增大 这就会使模型的实用性受到影响。 2 扰动分析法 扰动分析法是1 9 7 9 年由哈佛大学y c 。h o 提出并领导发展起 来的【1 8 】。它兼容了仿真法与理论分析的长处，同时也避免了单纯用 仿真法的大量计算和用理论分析法研究复杂系统所遇到的困难。用 扰动分析法研究f m s 的主要内容是研究系统的性能指标( 如生产 率) 对参数变化的敏感性，并且以此为基础对系统的运行进行优化。 扰动分析对于多参数的扰动或较大扰动，很难用表或状态方 程表示仿真运行历程：再者，扰动较大时，这种方法近似程度差。 3 p e t r i 网 p e t r i 网( p e t f in e t ) 是德国科学家p e t r i 于1 9 6 2 年首先提出的 一种网络圈理论，适合于描述离散事件系统模型。它可以较好地描 述并发系统的结构，并能对系统的动态性质( 有界性、安全性、活 性、可达性、可逆性、不变量等) 进行分析，因而已被广泛地用于 f m s 的设计、分析和仿真中。 p e t f i 网方法的困难在于，当系统较为复杂时，建模和分析的难 度很大；并且网络描述基于确定性系统，系统扩充后的处理较烦琐： 计算机编程处理有一定难度。 4 计算机仿真 运用计算机仿真建立的模型通过计算机程序模拟了系统的详 细的运行，该程序有效的经历了系统中可能发生的每个事件。因 此，仿真便允许以对实际系统很小或无扰动的对复杂系统进行有控 制的实验研究。由于仿真分析可以在不同的改进水平上实现，因此 具有不同程度的精度和可信度。对此，要付出的代价则是建模的编 程时间、收集数据的时间和每次运行程序的计算机时间。在柔性制 造系统中，仿真可用于测试系统的规划和研究不同的控制战略、作 排毒主逼上擘硕士学位论文 基于改进蚁群算泣求解f m s 工艺路线优化配箕问韪的研究 业进度计划的优先规则、故障情况和生产维持图的效果。 5 排队网络 在f m s 优化配置的理论和方法中，基于闭排队网络( c l o s e d q u e u i n gn e t w o r k s ，c q n ) 的解析方法由于具有较好的分析性和较 快的求解速度而被广泛接受1 1 9 】。 最初将排队论用于f m s 建模的是s o l b e r g ，其模型假设服务台 ( 加工中心或机床) 具有指数型服务事件分布，顾客( 工件) 都是 同一类型。通过排队模型，可以分析系统生产率、平均生产时间、 工位的利用率、系统的极限生产率。 利用排队论中j a c k s o n 定理( j a c k s o n st h e o r e m ) 的特例一一 具有中央服务台的闭排队网络来建立描述f m s 运行属性的模型， 可以很快地获得有关柔性制造系统制造系统性能的大量信息，可以 详细研究系统稳态运行下的各项重要性能指标( 如系统生产率、平 均加工时间、设备利用率、排队长度等) ，从而为改进现有系统和 设计新系统提供方法和依据。 由于实际系统是相当复杂的，模型化的过程是以许多简化和假 定为前提的。只有忽略若干次要的细节，才有可能对某些主要的属 性给予定量的数学描述。如果模型过于复杂，则所要求的技术水平 和费用就会过高，而且过分严谨的数学推理和考虑众多复杂的因素 往往极不必要也不一定有效，因此从实用角度来讲，当前f m s 研 究中迫切需要解决的问题之一是如何建立一个简明、可信、易行的 系统模型。综合考虑前面谈到的各种f m s 建模方法，为了使本文 的研究工作更有针对性，作者决定选排队网络作为建模工具。 1 4 _ 2 主要优化算法 f m s 工艺路线优化配置问题是多变量复杂的非线性约束优化 问题，并且排队网络模型中的一些要素不能以显式形式给出，求解 如毒主逦z 挚硕士学位论文 基于改进蚁群算注求解f m s 工艺路线优化 e 置问题的研究 难度和计算量都非常大，属于n p 完全问题。对于此类问题，想以 常规方法来求出其最优解是非常困难的，即使能够求出，其计算时 间之长也往往令人难以接受，在绝大多数情况下，是通过某种启发 式算法求得问题的一个可行解。 可以用于求解该类问题的启发式算法有以下几种 1 模拟退火算法 模拟退火算法的思想最早由n m e t r o p o l i s 等人在1 9 5 3 年提出 1 2 。模拟退火算法是基于m o n t ec a r l o 迭代求解法的一种随机寻优 算法，其出发点是基于物理学中固体物质的退火过程与一般组合优 化问题之间的相似性。模拟退火法在某一初温下，经过不断地降温， 在全局解空间中随机寻找最优解，不但接受对目标函数有改善的状 态，还以某种概率接受使目标函数恶化的状态，即具有爬山功能， 能够爬出局部最优解。从而比较有效地进行全局搜索。 模拟退火算法运行速度很慢，为了获得较好的解，需要在每一 温度下达到平衡状态，而退火温度的变化般是相当缓慢的。此外， 并非所有的组合最优化问题都能利用模拟退火算法得到满意解，对 于那些梯度变化非常剧烈的问题模拟退火法很难得到满意解。而 且，在实际问题中模拟退火算法的收敛性无法保证。在实际应用中， 高效的退火策略很难设计。 2 遗传算法 遗传算法( o a ) 是模拟遗传选择和自然淘汰的生物进化过程的 计算模型，是由m i c h i g a n 大学h o l l a n d 教授于1 9 7 5 年首次提出的 肛“。这是一种新的全局优化搜索算法，因其简单通用，鲁棒性强， 适于并行处理，已广泛应用于计算机科学、优化调度、运输问题、 组合优化等领域。遗传算法的主要特点是群体搜索策略和个体之间 的信息交换，他实际上是模拟由个体组成的群体的整体学习过程， 其中每个个体表示给定问题搜索空间中的一个解点。遗传算法从任 意初始化的群体出发，通过随机选择( 使群体中优秀的个体有更多 办j i 逼卫事耐! 士学位论文 鉴于美进蚁群算法求解f m s _ t 艺路续优化配置问题的研究 的机会传给下代) 、交叉( 体现了自然界中群体之间的信息交换) 和变异( 在群体中引入新的变种确保群体中信息的多样性) 等遗传 操作，使群体一代一代地进化到搜索空间中越来越好的区域，直至 抵达最优解点。 遗传算法主要存在以下缺点： 编码不规范及编码存在不准确性：单一的遗传算法编码不能全 面地将优化问题的约束表示出来；是否能够收敛到全局最优解还有 待于验证。 3 禁忌搜索算法 禁忌搜索算法是局部邻域搜索算法的推广，是人工智能在组合 优化算法中的一个成功应用。g l o v e r 2 2 】在1 9 8 6 年首次提出了这一 概念，进而形成了一套完整算法。禁忌搜索算法的特点是采用了禁 忌技术。所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜 索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已 经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不 再有选择地搜索这些点，以此来跳出局部最优点。 禁忌算法的缺陷是对于初始解具有较强的依赖性【2 3 】，一个较好 的初始解可使禁忌搜索在解空间中搜索到更好的解，而一个较差的 初始解则会降低禁忌搜索的收敛速度，搜索到的解也相对较差；此 外，其搜索只是单。单操作，即在搜索过程中初始解只能有一个， 在每代也只是把一个解移动到另一个解。 4 蚁群算法 蚁群算法是一种新型的模拟进化算法。该算法是由意大利学者 m d o r i g o 、v m a n i e z z o 、a c o l o r i n i 等人首先提出的f 2 4 , 2 5 , 32 1 ，其原 理主要是利用了蚂蚁群体在搜索食物的过程中，通过个体在所经过 的路径上留下的信息素来引导整个蚁群找到离食物源最近的路径。 大量的蚂蚁进行信息交流表现出一种信息正反馈现象，某一路径上 经过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大。 排j 主工譬硕土学位论文 基于改进蚁群算法求解f m s 工艺路线优化配置问韪的研究 同以上三种算法相比，人们对蚁群算法的研究时间还不长，还 没有形成坚实的数学基础和系统的分析方法。但初步的应用已经显 示出其求解复杂优化问题方面的优势，并且潜力巨大。 该算法的优势主要体现在以下几个方面：较强的鲁棒性，分布 式计算，易于与其他算法结合。 1 5 课题的提出 1 5 1 课题的研究内容 本章的前面部分对f m s 工艺路线优化配置问题的研究现状和 存在问题进行了回顾与分析，在此基础上，本文提出了基于改进蚁 群算法求解f m s 工艺路线优化配置的思想，研究工作主要包括以 下内容： ( 1 ) 建立f m s 的c q n 模型：分析f m s 各组成部分之间的逻辑关 系，忽略系统的实际布置及一些不必要的细节，将系统简化为由若 干工位组成的排队模型。以此模型对f m s 的各种主要性能指标进行 分析并对本文的研究对象及求解过程进行描述。 ( 2 ) 应用蚁群算法求解连续优化问题：蚁群算法在解决组合优 化问题方面显示出了较好的性能，然而在解决连续优化问题方面却 应用甚少。本文将采用与网格法相融合的蚁群算法来实现将蚁群算 法应用于求解连续优化问题领域。考虑到该算法实施过程中可能会 破坏约束条件，本文将改进原有的边界收缩方法来避免这一现象的 发生。 ( 3 ) 改进蚁群算法：对蚁群算法存在的主要不足及其产生的原 因进行分析，引入变异算子和交叉算子来提高解的多样性和求解质 量，而且针对蚁群算法的特点，在改进过程中将采用双点交叉和基 本位变异。根据改进的蚁群算法绘制完整的算法流程框图。 # 毒主乏z 事硕士学位论文 蓼彳改进蚁群算法求舸f m s 工艺路线优化配箕问题的研咒 ( 4 ) 软件实现和算例验证：根据之前所提出的算法，利用m a t l a b 编写相应软件。对某一生产实际问题进行求解，将所得结果与目前 该领域内比较有代表性的t e t z l a f f 解析法作比较来验证本文所提出 的算法的有效性。 1 5 - 2 课题的工程及学术意义 工艺路线优化配置问题是在进行制造系统的规划设计或生产 组织时经常遇到的问题，其求解结果将直接影响到生产设备的工作 负荷，从而进一步影响制造系统的生产率等性能。在进行制造系统 的规划设计时，工艺路线优化配置问题是必须要解决的基本问题。 此时，如果工艺路线优化配置不合理，不仅会导致制造系统不良的 运行性能，而且还会导致较差的经济性能，造成极大的资源浪费。 因此，对柔性制造系统的各工件的工艺路线进行合理的配置，找出 使系统运行效率较好的配置方案，是在运行柔性制造系统前必须要 解决的问题，具有重要的工程意义。 利用基于c q n 模型的f m s 工艺路线配置问题的求解，可以迅 速地为f m s 的优化设计提供有价值的信息。但是该问题是多变量 的复杂约束优化问题，属于n p c o m p l e t e 问题，用常规方法求解存 在极大困难。本文首次将蚁群算法应用于f m s 规划设计领域，一 方面将对蚁群算法进行深入的研究，并进行相应的改进，扩大其应 用范围；另方面将完善f m s 工艺路线优化配置这一n p c o m p l e t e 问题的求解方法，提高其求解性能。因此，该研究也具有较高的学 术价值。 1 6 论文主要工作及组织结构 依据上述思想，本文针对f m s 的工艺路线优化配置的理论与 方法进行了的研究。各章主要内容简述如下： 第一章为绪论：首先简要介绍了柔性制造系统的一般概念、性 14 排毒主连上挚碗士学位 e 立 基于改进蚁群葬泣求角军f m s 工艺路线优化配芄问题的研究 能特点，指出f m s 是顺应社会发展的一种重要的现代化制造系统 形式。继而说明了f m s 工艺路线优化配置问题的内容和重要性。 介绍了f m s 工艺路线的研究现状和研究方法，并根据各自的特点 对各种方法进行了比较。最后提出了本文的研究内容基于改进 蚁群算法解决f m s 工艺路线优化配置问题，说明了全文的基本思想、 研究意义、内容安排及组织结构。 第二章为基于c q n 的f m s 的模型：首先简要介绍了排队网络 及其分类以及几种常见的排队网络模型，然后介绍了用排队网络的 方法进行建模所作的一些假设，针对本文所研究的问题，建立了基 于c q n 的f m s 的数学模型并对对系统的性能指标以及设计的目 标、已知条件、设计结果进行了详细说明。 第三章为蚁群算法的基础知识：首先根据蚁群算法产生的生物 学背景简要介绍了蚁群算法的基本思想原理，然后通过对t s p 问题 的求解描述了蚁群系统的模型及实现过程，并给出了计算过程的伪 代码。最后介绍了蚁群算法发展现状及其应用领域。 第四章为基于改进蚁群算法求解f m s 工艺路线优化问题：本 章一开始分析了将蚁群算法用于求解连续优化问题所需要做的改 进，然后根据本文所研究问题的特点确定了改进策略，继而给出了 基于蚁群算法求解该问题的优化模型并绘制出编程实现的流程图； 针对基本蚁群算法所存在的不足提出了结合遗传算法中的交叉算 子和变异算子的改进蚁群算法来提高原有算法的性能并对将会影 响求解算法精度的边界信息进行了处理。 第五章为软件实现与算例验证：根据本文的研究方案，编写相 应的软件。利用该软件求解一个生产实际中的具体算例，通过将所 求得的结果与用该领域中比较有代表性的t e t z l a f f 算法求得的结果 相比来说明本文所提出算法的有效性和可行性。 第六章为总结与展望：总结论文的工作，并且指出本论文的研 究工作的不足之处，提出未来此领域的研究方向和研究内容。 办毒主工挚硕士学位论文 基于改进蚁群葬洼求解f m s 工艺路线优化配置问题的研究 第二章基于c q n 的f m s 的模型 2 1 1 概述 2 1 排队网络方法 排队网络方法是d e d s 研究中应用最广泛且较为有效的一类 方法。此方法在其适用范围内具有较成熟的概率论和随机过程理论 方面的理论背景和良好的准确性，而且排队网络模型对于d e d s 中 各种复杂因素，一般具有较强的物理拟合能力，其输出结果与应用 专门仿真语言得出的结果相比误差小于3 。正是由于该模型在物 理概念上的直观性以及在满足系统参数和结构一定的假定条件时 可获得简洁、可靠的分析解，因此，特别适用于对f m s 进行分析 与设计。由于f m s 耗资巨大且有一定的风险性，在目前我国资金 比较紧张的情况下，就更有必要在f m s 建造前进行认真的研究与 设计，建立适宜的f m s 模型，用以分析f m s 的各种主要性能指标， 为f m s 的建立提供科学的依据，从这个意义上讲，研究排队网络 在f m s 中的应用是比较实用和有效的。 2 1 2 排队网络分类 排队网络一般分为开排队网络、闭排队网络和一般排队网络。 1 开排队网络 这类网络是指顾客( 工件) 按一定分布规律进入系统申请服务， 当得到满足后立即离开系统。其大致特征是：顾客按泊松分布，加 工时间按负指数分布，对顾客按先到先服务的规贝3 ( f c f s ) 进行服 务，系统缓冲器容量足够大，不会发生阻塞现象，系统中各服务中 心的队长分布是相互独立的，此类网络系统的稳态分布为： ， 主逼衅硕士学位论文 基于改进蚁群算注求解f m s 工艺路线优化配置问题的研究 p ( k ，k ：，k 。) z # ( k ，) 最( k ：) o ( k ，) 其中队长矢量( k 。，k ：，k 。) 为系统状态向量， 只c k 。，2 主 ：；善：；：；：；簧：。k ，一i 。；i ”：。，。 2 闭环排队网络 这类网络是指系统中顾客数量一定，即当有一个顾客离开系统 的时刻，必定有另一个顾客进入系统。其大致特征是：顾客数量不 变，加工时间按负指数分布，对顾客按f c f s 规则进行服务，缓冲 器容量足够大，且假定d h i 时间分布可与队长有关，即第i 服务中 心的服务速率为o i ( n 。) 。此类网络系统的稳态分布为： p ( ”，m ) = 而丽1 m 肛4 ( 一) 3 一般排队网络 这类网络是j a c k s o n g o r d o n 一一n e w e l l 网络的进一步推 广。其顾客可以分成r 类，不同类型顾客可以有其不同的路径，系 统不仅可以是开环的、闭环的，也可以是混合的。假定输入过程为 与系统内各服务中心队长有关的泊松分布过程，服务规则也扩展到 多于一种类型，如f c f s ，l c f s 等。 排队网络除了可以分为这三大类，还有一些其他的模型比如： 排队网络计算机分析模型：此模型是一个具有中心服务台的闭 环网络模型，其中m h s 被视为独立的服务台。由于工件在一个工 作站加工完毕后去另一个工作站时必须经过m h s 传送，因此m h s 起到了中心服务台的作用，此模型特别适合于m h s 是自动小车 ( a g v ) 的情形； i 主暮，哮硕士学位i 奁文 基于魏进蚁群算泣求解f m $ 工艺蹄线优化配置问题的研究 平均值分析网络模型：此模型即为平均值分析法所采用的模 型，它能方便地考虑多类工件同时加工的问题。此时假定服务规则 为f c f s 。推广的m v a 还可处理各类工件需求不同的加工时间和加 工时间服