（机械电子工程专业论文）基于蚁群优化算法的柔性制造系统加工路径流量规划优化设计研究.pdf

基于蚁群优化算法的柔性制造系统加工路径流量规划优化设 计研究 摘要 柔性制造系统工件加工路径流量的优化分配是系统规划设计和生产管理调 度所需面对的重要问题，而此问题的n p c o m p l e t e 特性使最优解不能用多项式精 确求得。本文采用结合网格法的蚁群优化算法来求解此问题近似最优解。 ( 1 ) 阐述了柔性制造系统的基本概念，指出系统资源优化配置的重要性， 概括了在此领域的国内外研究现状。 ( 2 ) 介绍了蚁群优化算法的生物学基础、原理、特点和各种改进方法，确 定理论相对成熟的蚁周系统做为求解柔性制造系统流量优化分配问题的应用算 法。 ( 3 ) 应用闭环排队网络模型对柔性制造系统建模，分析系统各部分的逻辑 关系，提取求解所需的系统变量和已知条件。 ( 4 ) 使用网格法将系统变量离散化，达到可用蚁群优化算法来进行搜索求 解的目的，推导出蚁周系统算法的具体实现过程。 ( 5 ) 结合柔性制造系统的具体实例，给出蚁周系统的计算结果并与模拟 退火算法进行比较，得出蚁群优化算法能够很好得解决柔性制造系统工件加工 路径流量的优化分配问题。 关键词：柔性制造系统、蚁群优化算法、网格法、闭环排队网络、流量分配 t h er e s e a r c ho nt h eo p t i m i z e dd e s i g no fm a n u f a c t u r i n gf l u x p l a no ff m sb a s e do na c oa l g o r i t h m a b s t r a c t t h eo p t i m i z e da s s i g n m e n to ft h em f l n u f a c t u r er o u t e so fw o r k p i e c e si nf m si s t h ec r u c i a li s s u ef o l l o w i n gt h es y s t e mp l a n n i n ga n dd e s i g n ，a sw e l la st h e m a n u f a c t u r em a n a g e m e n ta n ds c h e d u l i n g i nt h i si s s u e ，t h ec h a r a c t e r i s t i c so f n p - c o m p l e t em a k et h em o s to p t i m i z e ds o l u t i o n si n a c c e s s i b l ev i am u l t i n o m i a l i nt h i s p a p e r , a c oa l g o r i t h mc o m b i n e dw i t hg r i d i n gm e t h o d i sp r o p o s e dt od e r i v et h e a p p r o x i m a t e l yo p t i m i z e ds o l u t i o no f t h i sp r o b l e m ( 1 ) t h eb a s i cc o n c e p t so ff l e x i b l em a n u f a c t u r es y s t e m ，t h es i g n i f i c a n c eo ft h eo p t i m i z e d c o n f i g u r a t i o no fs y s t e mr e s o u i 佗e sa n dt h er e e e n tr a s e a r e hs t a t u sa t ee x p o u n d e di nt h i sp a p e r ( 2 ) t h eb i o l o g i c a l f o u n d a t i o n s ，p r i n c i p l e s ，c h a r a c t e r i s t i c sa n dam u l t i t u d eo f i m p r o v e dm e t h o d sa r ei n t r o d u c e d ，a n da n t - c y c l es y s t e mw h i c hi sr e l a t i v e l y d e f i n i t i v ei nt h e o r yi se s t a b l i s h e dt os o l v et h ep r o b l e mo ft h eo p t i m i z e da s s i g n m e n t o f f l u xi nf m s ， ( 3 ) n l em o d e lo fc l o s e dq u e u i n gn e t w o r k si sa p p l i e dt oe s t a b l i s hf m s ，a n a l y z e t h el o g i cr e l a t i o n s h i po fa l lp a r t s ，a n dd i s t i l lt h es y s t e mv a r i a n c ea n dk n o w n c o n d i t i o n sn e e d e df o rt h es o l u t i o n ( 4 ) g r i d i n gm e t h o di su t i l i z e dt om a k es y s t e mv a r i a n c ed i s c r e t ei no r d e rt ou s e a c o a l g o r i t h m 幻s e a r c h ，a n dd e r i v et h ec o l l e r e t ep r o g r e s so f r e a l i z i n gt h ea l g o r i t h m o f a n t c y c l es y s t e m ( 5 ) c o m b i n e d 谢t 1 1ac o n c r e t ee x a m p l eo ff m s ，t h ec o m p u t e r i z e dr e s u l to f a n t - c y c l es y s t e mi sp r o v i d e da n dc o m p a r e dw i ms i m u l a t e da n n e a l i n ga l g o r i t h m a r l dt h ef i n a ic o n c l u s i o ni sd r a w nt h a ta c 0i sap e r f e c tt os o l v et h ep r o b l e mo f 也e o p t i m i z e da s s i g n m e n to ft h em a n u f a c t u r er o u t e so fw o r k p i e c e si nf m s k e yw o r d ：f l e x i b l em a n u f a c t u r es y s t e m ( f m s ) ， a n tc o l o n yo p t i m i z a t i o n ( a c o ) a l g o r i t h m ， g r i d i n gm e t h o d ，c l o s e dq u e u i n gn e t w o r k s ，f l u xa s s i g n m e n t 插图清单 图1 一i 柔性制造系统的构成框图2 图2 1 搜索技术的分类i 3 图2 2 蚁群优化算法原理1 7 图3 1 排队系统基本结构” 图3 2 多服务台排队方式一 图3 3 柔性制造系统闭环排队网络模型示意图- 图3 4 状态空间图一 图3 5 柔性制造系统工件加工路径流量优化分配流程 图3 6 算例结果界面一 盯粥凹船弘如 致谢 值此论文完成之际，我要向我的导师韩江教授和夏链副教授致以最诚挚的 敬意和最衷心的感谢! 在近三年的研究生学习期间，无论是在科研工作中，还是在生活q j ，韩老 师和夏老师都给予我悉心的指导和的照顾。韩老师和夏老师严谨认真的治学态 度和对学术孜孜追求的精神深深影响了我。他们渊博的学识和对学术问题的独 到见解，对研究课题的敏锐发现和研究方向的准确把握，都体现了很高的学术 素养。 从开始收集与本论文相关资料，一直到论文的完成，韩老师和夏老师都给 予了我无私的指导和帮助。在选题、开题及至完成论文的每一个阶段，韩老师 和夏老师都严格把关，并在课题的研究思路上给以具有建设性的意见。对论文 的审阅也同样耐心细致，大到论文的框架，小到一个知识点，韩老师和夏老师 都是一样细心批阅纠正。同时韩老师和夏老师也是我生活中的老师，他们对人 的平和、亲切，对学生的关心爱护，教会了我坦诚热情的待人处事方式。 感谢王治森教授、祖垣老师、何高清老师、余道洋老师在我的课题研究过 程中对我的帮助和指导! 感谢王建兵、郭建强、姜晓林、程治、潘斌、陆荣峰等同学在我的论文撰 写过程中给予的帮助。 感谢师弟张栋栋、刘向前、陆青松、苏志远、张国权、胡静和师妹李晓伟 给予我的帮助。 最后还要特别感谢我的父母，是他们不辞劳苦、任老任怨的辛勤付出给予 了我精神和物质上的支持，使我最终得以完成学业。 作者：成勇 2 0 0 6 年4 月 第一章绪论 1 1 柔性制造系统概述 1 1 1 柔性制造系统的定义 柔性制造系统( f l e x i b l em a n u f a c t u r e i n gs y s t e mf m s ) “”作为一种新 的制造技术，在零件加工业以及加工和装配相关的领域得到了广泛的应用。在 我国有关标准中，柔性制造系统被定义为：柔性制造系统是由数控d h i 设备、 物料贮运装置和计算机控制系统组成的自动化制造系统，它包括多个柔性制造 单元，能根据制造任务或生产环境的变化迅速进行调整，适用于多品种、中小 批量生产。 美国制造工程师协会的计算机辅助系统和应用协会把柔性制造系统定义 为：使用计算机控制、柔性工作站和集成物料运贮装置来控制，并完成工件族 某一工序或一系列工序的一种集成制造系统。 还有一种更直观的定义是：柔性制造系统是至少由两台机床，一套物料运 输系统( 从装载到卸载具有高度自动化) 和一套计算机控制系统所组成的制造 系统，它采用简单地改变软件的方法便能制造出某些部件中的任何工件。 综合起来可以认为：柔性制造系统是在自动化技术、信患技术和制造技术 的基础上，通过计算机软件科学，把工厂生产活动中的自动化设备有机地集成 起来，打破设计和制造的界限，取消图纸，工艺卡片，使产品设计、生产相互 结合而成的，适用于中、小批量和较多品种生产地高柔性、高效率地制造系统。 1 1 2 柔性制造系统的一般组成 柔性制造系统可概括为由下列三部分组成：多工位的数控加工系统，自动 化的物料贮运系统和计算机控制的信息系统，其构成如图1 1 所示。 1 、加工系统 加工系统的功能是以任意顺序自动加工各种工件，并能自动地更换工件和 刀具。通常由若干台对工件进行加工的c n c 机床和所使用的刀具构成。 以加工箱体类工件为主的柔性制造系统配备数控加工中心( 有时也有 c n c 铣床) ：以加工回转体工件为主的柔性制造系统多数配各c n c 车削中心 和c n c 车床( 有时也有c n c 磨床) ；能混合加工箱体形工件和回转体工件柔 性制造系统既配备有c n c 加工中心，也配备有c n c 车削中心和c n c 车床： 专门进行齿轮加工的柔性制造系统除配备c n c 车床外还配备有c n c 齿轮加 工机床。 柔性制造系统的加工能力由它所拥有的加工设备决定；柔性制造系统里的 加工中心所需的功率、加工尺寸范围和精度则由待加工的工件族决定。 图1 1 柔性制造系统的构成框图 2 、物流系统 在柔性制造系统中工件、刀具流统称为物流，物流系统即物料贮运系统， 是柔性制造系统中的一个重要组成部分。一个工件从毛坯到成品的整个生产过 程中，只有相当小的一部分时间在机床上进行切削加工，大部分时间消耗于物 料的贮运过程中。合理地选择柔性制造系统地物料运贮系统，可以大大减少物 料地运输时间，提高整个系统地柔性和效率。 物流系统一般由三个部分组成： ( 1 ) 输送系统：建立各加工设备之间的自动化联系。 r 2 ) 贮存系统：具有自动存取机能，用以调节加工节拍的差异。 f 3 ) 操作系统：建立加工系统同物流系统和贮存系统之间的自动化联系。 3 、信息系统 信息系统包括过程控制及过程监控两个系统。其功能分别为：过程控制系 统进行加工系统及物流系统的自动控制；过程监控进行在线状态数据自动采集 和处理。信息系统的核心是一个分布式数据库管理系统和控制系统，整个系统 采用分级控制结构，即柔性制造系统中的信息由多级计算机进行处理和控制， 其主要任务是：组织和指挥制造流程，并对制造流程进行控制和监视；向柔性 制造系统的加工系统、物流系统( 贮存系统、输送系统及操作系统) 提供全部 控制信息并进行过程监视，反馈各种在线检测数掘，以便修正控制信息，保证 安全运行。 1 1 3 柔性制造系统的工作原理 柔性制造系统的工作过程可以描述为：制造系统接到上一级控制系统的有 关生产计划信息和技术信息后，由其信息流系统进行数据信息的处理、分配， 并按照所给的程序对物流系统进行控制。料库和夹具库根据生产的品种及计划 调度信息供给相应品种的毛坯，选出加工所需要的夹具。物流系统按照信息系 统的指令，自动识别和选择所装卸的工件及夹具，并装载到相应的机床上。机 床的加工程序根据送来的工件选择加工所需的加工工序、刀具及加工参数，对 工件进行加工。加工完毕，按照信息系统的控制信息转换工序，并进行检验。 全部加工完成后，由装卸及运输系统送入成品库，同时把加工质量、数量信息 送达信息系统。 当需要变更产品工件时，只要改变输送给信息系统的生产计划信息、技术 信息和加工程序，整个系统就能迅速、自动地按照新要求来完成新产品的加工。 计算机控制着系统中物料的循环，执行进度安排、调度和传送协调的功能。它 不断收集每个工位上的统计数据和其他制造信息，以便汇总报告。 1 1 4 柔性制造系统的特点 1 、柔性制造系统的柔性 柔性制造系统的主要目标是通过机床、传送系统和控制系统的协调配合， 在不降低灵活性的情况下提高生产率和生产利用率。 柔性制造系统的柔性体现在以下几点： ( 1 ) 能在同一时间内加工多种零件。可以根据市场的需要及当前生产需要 安排各种零件之间的比例。 ( 2 ) 能在系统中个别机床发生故障的情况下，保持生产。此时系统通过控 制系统的调度，用其它机床取代故障机床，使系统生产能力接近正常状态。 f 3 ) 具有无人照管自动运行的能力。维护工作和装卡工作可在第一班里进 行，第二、第三班则可以无人化的方式运行。 2 、柔性制造系统的优点 ( 1 ) 设备利用率高：一组机床编入柔性制造系统后的产量，一般可达这组 机床在单机作业的2 3 倍。柔性制造系统能获得高效率的原因，一是计算机 把每个零件都提前安排了机床。一等机床空闲，马上将零件送去加工。同时将 相应的数控加工程序输入这台机床。二是由于送上机床的零件早已装卡在托盘 上，因而机床不用等待零件的装夹。 ( 2 ) 减少设备投资：由于设备的利用率高，柔性制造系统能以较少的设备 来完成同样的工作量。把车间采用的多台加工中心换成柔性制造系统，其投资 一般可减少三分之二。 f 3 ) 减少直接工时费用：由于机床是在计算机控制下进行工作，不需工人 去操纵。唯用人的工位是装卸站，只需低级技工装卸零件。当然，还需要一 名系统管理员，这就减少了工时费用。 ( 4 ) 减少了工序中在制品量、缩短了生产准各时间：跟一般加工相比柔性 制造系统在减少工序中零件积存数量上有惊人的效果。这是因为缩短了等待加 工时间。促成等待时间缩短的因素很多，例如：a ) 在柔性制造系统中，把加工 零件用的全部机床集中在一个很小的场地；b ) 由于各工序集中在加工中心进 行，因而减少了零件装卡的次数和零件需经过的机床数，c 1 计算机按制订的计 划，高效率地把零件分批送入柔性制造系统进行加工。 ( 5 ) 改变生产要求时有快速应变能力：柔性制造系统有其内在的灵活性， 能适应由于市场需求变化和工程设计变更所出现的变动，进行多品种生产。而 且还能在不明显打乱正常生产计划的情况下，插入备件制造任务。 ( 6 ) 维持生产的能力：许多柔性制造系统设计成当一台或几台机床发生故 障时，仍有降级运转的能力、即采用了加工能力有冗余度的设计，并使物料传 送系统有自行绕过故障机床的能力：此时虽然生产率要降低些，但全系统仍能 维持生产。 f 7 ) 产品质量高：柔性制造系统还有一条易被忽略的优点，就是提高了产 品质量，特别是与未联成系统的数控机床相比，此优点更为明显。高度的自动 化、减少零件装卡次数，一个零件可以少上几种机床加工：设计得更好的专用 夹具，更加注意机床和零件的对中定位等因素。都有利于提高单个零件的质量， 使各零件之间有良好的一致性，因而也大大减少了返工费用。 3 、柔性制造系统的缺点”1 ( 1 ) 投资高昂：柔性制造系统价值昂贵。视其构成规模的大小，一般需要 5 0 0 7 0 0 0 万美元的投资，这还不包括支持它运行环境建设的费用。 ( 2 ) 建设周期长：柔性制造系统系统技术复杂，丌发、研制、调试一套柔性 制造系统系统需要较长的周期，从提出开发一个系统的概念到具体实现，往往 需要5 6 年的时间，有时甚至更长。若要完全满足用户的要求则需更长的时间。 典型的柔性制造系统，仅调试周期通常就需要半年，有的甚至一年后还不一定 能完全正常运行。调试一套大型的柔性制造系统可能需要1 s o - 月，而使系统在 良好的性能状态下运行可能再需要】8 个月。 由于这些困难或缺点使得许多企业对现代化柔性制造系统缺乏信心，望而 却步。同时也确实存在一些效果未达到预期的目的，甚至是失败的柔性制造系 统应用案例。正是由于柔性制造系统的实际应用效果与潜在优点之间存在较大 差距，合理地进行资源地优化分配就成为了保证柔性制造系统高效运行的重要 前提。资料表明，国外现己运行的柔性制造系统中约有8 0 没有达到设计要求， 而其中6 0 是由于初期规划不全面或失误造成的。因此，完善柔性制造系统的 先期规划设计，使系统的资源分配达到最合理得程度，提高柔性制造系统性能 成为急待研究的课题。 4 1 1 5 柔性制造系统资源优化配置的研究内容 一般性认为：柔性制造系统资源优化配置主要是指根据所加工产品的信息 和制造系统的各种约束和要求来确定加工设备、工件运送系统、刀具交换及运 送系统以及各种必需的辅助台站的种类和数量。优化配置问题是一个在受约束 的求解空间中找到一个资源分配的可行的解决方案，使得系统的性能指标达到 要求。 一个柔性制造系统的基本结构是由一系列的工作站组成，每一个工作站包 括有：一台或者几台相同的数控机床( c n c ) 、装卸载站、个含有一个或者几 个运载工具的传送系统以及其他的辅助加工设备。既然投资费用主要来源于这 些系统的建造费用，那么找到个合理的方案优化配置这些基本的加工设备就 具有非常重要的设计和生产意义。这样不仅能够降低系统的投资建造成本，还 能够避免系统由于建造资源不足，而长期工作于一种超负荷的状态下，也能够 避免系统长期工作于非饱和的状态下，而造成系统资源的浪费。 柔性制造系统资源优化配置任务的完成将为所设计的系统构造出初步的 框架，同时这一部分工作涉及到柔性制造系统中最多的投资额，风险较大，是 系统规划设计中最重要也是难度最大的任务之一。 本文主要研究的是柔性制造系统加工路径流量的规划的优化设计问题，其 主要目的是在某恰当的工件加工路径流量比例下使各工位的设备工作负荷达 到均衡，从而使柔性制造系统资源的配置达到最优化，避免系统设备资源的浪 费。 1 2 国内外研究的现状 1 2 1 柔性制造系统资源优化配置的研究现状 关于柔性制造系统资源优化配置的研究，直到1 9 7 7 年，离散事件仿真还是 唯能够评价系统性能的工具，这时候利用离散事件仿真解决柔性制造系统资 源优化配置主要是在参考仿真程序提供结果的基础上对系统的各种决策变量 进行人为的调整，由于受当时计算机仿真技术水平的限制，这只能是一种相对 粗略的设计方法，它大量地依赖于人的经验和直觉判断。 离散事件仿真对于系统评价的不精确促使人们去寻求系统的更准确的描 述方法，1 9 7 7 年j j s o l b e r g 利用c a n q 模型来对柔性制造系统的性能进行评 价，从而开始了如何利用排队网络的方法来建立描述系统解析模型的探索。 相对于仿真模型，解析模型具有良好的分析性能，从而使得对于系统优化配置 成为可能。解析模型的建立大大地方便了设计者的工作，因为在一定的程度上， 这种模型使得设计者对于其所描述的制造系统的性能有了一个比较直观地认 识。另外，解析模型分析的快速性使得针对于制造系统大量的假设分析研究 ( w h a t i fs t u d y ) 变得非常的容易，而这些都是以前的离散事件仿真模型所无 法比拟的。 大量的研究使得利用排队网络的解析方法研究制造系统优化配置问题产 生了一系列的成果，建立了用于表征制造系统性能的各种模型，提出了一些有 效的算法。 r a j a ns u r i 和r i c h a r dr h i l d e b r a n t ( 1 9 8 3 年) 最早对柔性制造系统的优 化配置问题进行了论述“1 他们给出了一个用排队网络方法建立系统解析模型 的一个例子在这个模型中，被定义的系统配置变量有机床数量、托盘的数量 以及物料传送系统设备的数量，被评价的性能指标包括生产量和机床利用率。 为了配置一个合理的系统，他们对模型进行了多次反复的迭代分析，每一次的 迭代结果都是对上一次系统配置的一次改进，直至得到满意的优化结果。 v i n o d b 和j j s o l b e r g ( 1 9 8 5 年) 也较早地对柔性制造系统的优化配置问 题进行了研究“1 。他们利用闭环排队网络( c l o s e dq u e u e i n gn e t w o r k s 。c q n ) 模型对每个系统工作站( w o r k s t a t i o n ) 中的服务器数量和系统的托盘总量( j o b p o p u l a t i o n ) 进行了优化研究，其目标是在满足一定的生产率要求下，使各服 务器运行费用的总量和托盘总量达到最小。由于非线性生产率约束不能以显式 形式给出，他们提出了解决此问题的隐枚举法( i m p li c i te n u m e r a t i o n ) ，并给 出了计算结果。 s h a n t h i k u m a 和y a o ( 1 9 8 7 年，1 9 8 8 年) 也给出了他们描述制造系统性能的 g o r d o n n e w e l 网络模型。在他们建立的第一个模型( 1 9 8 7 年) 中，系统每个工 作站含有的缓冲站( b u f f e r ) 数量是有限制的，并且每一种工件只要在一个工作 站上加工就能够完成。而在第二个模型( 1 9 8 8 年) 中，系统的工作站含有的缓冲 站数量则是没有限制，每一种工件也至少要在两个工作站上加工刁能完成，也 就是说每种工件至少有两道加工工序。并且，在论文中他们提出了一种边缘分 析算法( m a r g i n a la n a l y s i sa l g o r i t h m ) ，这种算法被证明当制造系统的机床 加工率( p r o c e s s i n gr a t e ) 是队列长度递增的凹函数时，它是有效的，能够得 到系统优化配置结果。 随后，y v e sd a l l e r y 和y a n n i c kf r i e n ( 1 9 8 6 年) ，v a nv l i e t 和r i n n o o yk a n ( 1 9 9 1 年) “1 ，k o u v e li sp 和l e eh l ( 1 9 9 5 年) 1 都对排队网络用于柔性制造系 统的性能评价作了大量的研究。他们改进了以前的算法，将边缘分析法进行改 进，利用渐进边界分析法( a s y m p t o t i cb o u n da n a l y s i s ) 寻求初解和边界；同 时也提出了一些新的算法，例如将分支定界法与c q n 模型结合起来，等等。并 且他们所分析系统规模变得复杂，考察的系统变量也越来越多。 a n d r e ad a n g e l o 和m a s s i m og a s t a l d i ( 2 0 0 0 年) 利用特定的软件工具 w i t n e s s7 o x 寸制造系统进行建模。分析了三种系统布置方式：加工车间、 柔性单元和流水生产线以及市场产品需求变化对系统性能的影响。在论文中， 6 他们独立考察的系统性能参数有平均交货时间( a v e r a g el e a dt i m e ，l t ) 、平 均在制品数量( a v e r a g ew o r ki np r o c e s s ，w i p ) 以及平均缓冲站容量( a v e r a g e b u f e rs i z e ) ，文中成功地回答了其所列出的三个考察问题：不同的系统布置 方式是否对系统上述性能有显著的影响? 市场需求的变化是否与系统性能有 冲突? 以及市场的变化是怎样影响系统性能的? 我国在制造系统设计方面的研究与国外先进水平相比有很大的差距。只是 到最近十几年，才陆续有关于制造系统设计的文章发表，1 9 9 5 年同济大学的张 浩“”定性的、原则性地讨论了柔性制造系统规划设计的整体过程及其主意点， 1 9 9 7 年清华大学的吴柞宝“2 1 用p e t r i 网研究了一具体的叶片f m s 的规划设计， 提出了一较完整的f m s 评价体系，并用该体系对叶片f m s 的总体方案进行了评 审，1 9 9 8 年大连理工大学的明亮“”概述了计算机仿真在f m s 规划设计中的应用 及在我国制造业中的发展前景。2 0 0 0 年华中理工大学的赵天奇“”提出了一种 层次递阶的f m s 建模方式来描述f m s 的规划设计。 1 2 2 蚁群优化算法研究现状 蚁群优化( a n tc o l o n yo p t i m i z a t j o n a c o ) 算法是由意大利学者o o r i g o m ， c o l o r n i a n m a n i e z o v “”1 等人于1 9 9 1 年首先提出的一种模拟进化算法。蚁群 优化算法首先应用于解决旅行商问题( t s p ) ，然后m a n i e z o v 年n c o l o n i a ( 1 9 9 9 ) 把蚁群优化算法应用与解决二次分配问题( q a p ) 。 d o r i g o m 和lmg a m b a r d e l l a ( 1 9 9 6 年) 提出了a c s 算法，它在原系统的基础 上做了三方面的改进：a ) 状态转移规则为更好更合理地利用新路径和利用关于 问题的先验知识提供了方法；b ) 全局更新规则只应用于最优的蚂蚁路径上；c ) 在建立问题解决方案的过程中，应用局部信息素更新规则。 s t u t z l e t 和h o o s h ( 1 9 9 7 年) 提出了一种称为m a x m i n 蚁群优化算法，并与 邻域搜索算法相结合来解决t s p i 司题，算法采用了用当前找到的最好解更新信 息素来指引蚂蚁向更高质量的解空间搜索的贪婪策略，并对信息素设立h 下限 来避免算法的早熟。s t u t z l e t 矛n h o o s h ( 2 0 0 0 年) 应用m a x m i n 算法对t s p 问 题，a t s p 问题( 不对称t s p ) 以及q a p 问题作了仿真和对比研究，取得了很好的结 果。 g u t j a b r ( 2 0 0 0 年) 提出了一个基于图的蚁群优化算法- - g b a s ( g r a p h b a s e d a n ts y s t e m ) ，并证明了算法将以概率卜l 收敛于最优解，其中e 可以通过选 择足够大的蚂蚁数量y 或足够小的信息素挥发系数p 来获得任意小的值。b 1 n m 等( 2 0 0 1 年) 针对可转换为0 1 整数规划问题的组合优化问题，提出了一种 h c a c o 算法。这类组合优化问题的解可描述为个0 1 值的二进制向量，解构 成元素可定义为二进制向量中的每一位上的二进制数。 在国内，一些研究者也对蚁群优化算法作了一些研究，从公开发表的论文 7 看，最先研究蚁群优化算法的是东北大学张纪会博士和徐心和教授。1 9 9 9 年， 东北大学的吴庆洪等设计了具有变异特征的蚁群优化算法，2 0 0 2 年清华大学 的覃刚力和杨家本提出了一种基于自适应调整信息素的改进蚁群优化算法。 2 0 0 2 年上海交通大学的谢剑英和王颖通过自适应地改变算法的挥发度等系数 以克服蚂蚁算法易限于局部最优点的缺陷，并能够在保证收敛速度的条件下提 高解的全局性。 蚁群优化算法在组合优化问题上已体现出比较明显的优势，但对于连续空 间优化问题的研究却较少。从发表的文献看，只有同济大学的汪镭，吴启迪 ( 2 0 0 1 年) 和华东船舶工业学院的高尚等( 2 0 0 2 年) 分别提出了应用蚁群优化思 想来求解连续空间的优化问题。 1 3 课题的内容和意义 1 3 1 课题的内容 本文将蚁群优化算法应用于连续变量的加工路径流量规划优化设计问题。 首先用闭环排队网络对柔性制造系统进行建模，提取模型变量；然后用网格法 将变量离散化，达到能使用蚁群优化算法来进行求解的目的：设计出蚁群优化 算法求解的具体步骤，最后用一具体的算例来进行验证。 1 3 2 课题的意义 工件加工路径流量的优化分配问题是在进行制造系统的规划设计或生产 组织时经常遇到的问题，其求解结果将直接影响到生产设备的工作负荷，进而 影响到系统资源资源配置的合理性及系统的生产率等指标。在进行制造系统的 规划设计时，加工路径优化配置问题是必须要解决的基本问题。此时，如果加 工路径流量分配不合理，不仅会导致制造系统不良的运行性能，而且还会导致 较差的经济性能，造成极大的资源浪费。因此，对柔性制造系统工件的各加工 路径流量进行合理的分配，找出使系统运行效率较好的分配方案，是在运行柔 性制造系统前必须要解决的问题，具有重要的工程意义。 1 4 论文的组织结构 本论文的内容可以简述如下： 第一章为绪论：首先介绍了柔性制造系统的一般定义、组成、特点及工作 原理，并指出柔性制造系统是顺应社会发展的一种重要的现代化制造形式。继 而指出柔性制造系统资源优化配置的内容、重要性及现阶段国内外对此问题的 研究现状，最后提出了基于蚁群优化算法的柔性制造系统工件加工路径流量的 优化分配问题。 第二章为最优化问题的概述和解决方法：本章首先简要阐述了最优化问题 的理论及n p - - c o m p l e t e 问题的定义，说明了解决此类问题的困难。继而介绍 了解决柔性制造系统工件加工路径流量优化分配问题所常用的几种启发式搜 索算法如禁忌搜索算法和模拟退火算法优缺点。最后重点介绍了本文使用的蚁 群优化算法的生物学基础、基本原理及在旅行商问题上的成功应用，指出了蚁 群优化算法是一种新型的且具有较好发展前景的模拟进化算法。 第三章为柔性制造系统工件加工路径的优化配置问题：本章首先概述了柔 性制造系统的一般建模方法并经比较采用闭环排队网络的方法对柔性制造系 统进行建模：忽略系统的实际布置及一些不必要的细节，将系统简化为由若干 工位组成的排队模型，提取出系统变量。然后用网格法将变量离散化，使之能 适用于蚁群优化算法。继而给出基于蚁群优化算法的该问题的优化模型并用流 程图给出实现过程。最后用一具体的柔性制造系统实例来进行比较验证。 第四章为总结和展望：总结论文的总体工作指出其中的不足之处，提出该 领域未来可能研究的内容和方向。 1 5 本章小结 本章首先阐述了柔性制造系统的定义、组成结构，系统具备的潜在优势及 在生产实践中所面临的问题，由此引出在系统初期规划阶段对资源进行优化分 配以保证系统高效运行的重要性。然后，概述了柔性制造系统资源优化配置和 本文所要使用的蚁群优化算法的国内外研究现状。最后，介绍了本课题研究的 内容、意义及论文的组织结构。 第二章柔性制造系统流量分配优化方法 柔性制造系统工件加工路径流量优化分配问题从根本上说是一个求解最 优化的过程，并且是一个复杂的n p c o m p l e t e 问题。为此，要想较好的求解此 类问题，首先需要对最优化理论和n p 类问题有较为深入的认识。 2 1 最优化理论 最优化一般是指在某种状况下做出的决策或从几个候选者中选出最好的， 这种问题可以采用下面所叙述的数学模型“”： “在给定的约束条件( c o n s t r a i n t ) 下，找出一个决策变量( d e c i s i o nv a t i a b l e ) 的值，使得被称为目标函数( o b j e c t i r ef u n c t i o n ) 的表达愿望尺度的函 数达到最大值或最小值。” 一般来说决策变量有多个，因此用n 维向量x = ( 一z ，) 7 来表示，可以把 闯题写成下式： m i n f ( s )( 2 - 1 ) 其中：目标函数f ( x ) 是定义在包含s 的适当集合上的实值函数。可行域 s ( f e a s i b l er e g i o n ) 是该问题变量x 的可取值的集合。一般来说，可行域s 用于 变量x 相关的等式及不等式表示，则最优化问题也可以表示为； r a i nr ( x1 ( 2 2 a ) j j g ，口) 茎0 i = 1 ，( 2 2 b ) h ( x ) = o，= 1 m ( 2 - 2 c ) 其中：g ，( z ) ，h j ( j ) 为约束函数。 满足约束条件x s 的x 称为满足优化问题( 2 1 ) 的可行解( f e a s ib l es o l u t i o n ) 。满足： ，) f ( x l s ) ( 2 3 ) 的可行解x + s 称为问题( 2 1 ) 的最优解( o p t i m a ls o l u t i o n ) 。另外，在包含 可行解工+ s 的适当邻域u ( x + ) 罩，当 ，+ ) s ( x l s n u ( x ) ) ( 2 4 ) 成立时，称x + 为问题( 2 一1 ) 的局部最优解( 1 0 c a lo p t i m a lg o i u t i o n ) 。有些问 题的目标函数和约束条件非常复杂，要找出在整个可行域中使目标函数达到最 小的解非常难，这时面临的目标就成为求出局部最优解。为区别式( 2 3 ) 的最 优解与局部最优解，称式( 2 3 ) 的最优解为全局最优解( g o b a lo p t i m a s o l u t i o n ) ) “”，记为x 。这里所指的局部最优解是相对于全局最优解来说的， 因为在涉及问题中，我们只是在一个指定的局部区域内( 如u ( x + ) ) 寻找局部最 优解，而没有在整个可行解域( 如s ) 内寻找全局最优解，但同时在我们指定的 区域内还有很多予区域，例如u ( u cu ) ) ，每个子区域都有可能存在局部 0 最优解( 如”) ，在很多情况下，x 与z 不一致，此时我们称”为局部最小 陷阱。为了区别这些子区域上的局部最优解z ”，所以称在我们指定的区域内 得到的局部最优解x 为最优解。 根据变量的类型，最优化问题( 2 - i ) 可以划分为两类：一类是变量取连续 实数的连续最优化问题( c o n t i l l u o u $ o p t i m i z a t i o np r o b l e m ) ，另一类是变量 取整数或类似o 、1 的离散数的离散最优化问题( d i s c r e t eo p t i m i z a t i o n p r o b l e m ) 。而本文所要解决的是连续变量的最优化问题。 2 2p 类问题，n p 类问题和n p - g o m p l e t e 类问题 算法的时间和空间复杂性对计算机的求解能力有重大影响。算法对时间和 空间的需求称为算法的时间复杂性和空| 1 j _ j 复杂性。问题的时间复杂性是指求解 该问题的所有算法中时间复杂性最小的算法的时间复杂性，问题的空间复杂性 也有类似的定义。按照计算复杂性理论研究问题的难易程度，可把问题分为p 类、n p 类和n p c o m p l e t e 类 问题的复杂性一般表示为问题规模n ( 如t s p 问题中的城市数) 的函数，时间 复杂性记为t ( n ) ，空间复杂性记为s ( i 1 ) 。在算法分析和设计中，沿用实用性的 复杂性概念即把求解问题的关键操作，如加、减、乘、比较等运算指定为基本 操作，算法执行基本操作的次数则定义为算法的时间复杂性，算法执行期间占 用的存储单元则定义为算法的空间复杂性。在分析复杂性时，可以求出算法的 复杂性函数p ( n ) ，也可以用复杂性函数主要项的阶d ( p 缸) ) 来表示。若算法a 的 时间复杂性为l ( n ) = o ( d h ) ) ，且p ( n ) 为n 的多项式函数，则称算法a 为多项式算 法。时间复杂性不属于多项式时间算法统称为指数时间算法。 定义2 1 “”实例是问题的特殊表现，所谓的实例就是确定了描述问题特性 的所有参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实 例的输入长度。 定义2 2 “”给定一个实例，即确定这个实例的目标函数c ( s ，) 和可行解集q 的一组数据，并给定一个常数l ，是否存在一个可行解，使厂( ) ( e ? 判 定问题是用是或否来回答问题。 定义2 3 ”p 类问题指具有多项式时间求解算法的问题类。 定义2 4 “”若存在一个多项式函数g ( x ) 和一个验证算法h ，对一类判定问 题a 的任何一个“是”实例i 都存在一个字符串s 是i 的“是”回答，满足其输入 长度d ( s ) 不超过g ( d ( i ) ) ，其中d ( i ) 为i 的输入长度，且验证算法验证s 为i 的 “是”回答的计算时间不超过g ( d ( i ) ) ，则称判定问题a 为非多项式确定问题， 简称n p 。 由此可见，判定问题是否属于n p 问题的关键是对“是”的判定实例是否存 在满足上述条件的一个字符串和算法，其中字符串在此可理解为问题的个 解，而定义中没有强调字符串和算法是如何得到的。可见p 匕n p 。 定义2 5n 们如果4 和呜都是判定问题，吒和而是求解4 和4 的算法。如 果五是多项式算法，并且是多次以单位费用把如作为子程序的算法，称码在 多项式时间内归结为一2 ，称而为a 1 到a 2 的多项式时间归结( p o l y n o m i a l t i m e r e d u c t i o n s ) 已作a q o a ，。 定义2 6 “”如果n p 类中所有的问题都可以多项式归约到n p 类某个问题， 则称n 是n p - c o m p l e t e 问题。 定义2 7n ”如果某优化问题n 的判定问题是n p - c o m p l e t e 问题，则称问题 是n p - h a r d 问题。 定理2 1 “”如果问题ne n p ，那么存在一个多项式p 使得n 能用时间复杂 性为0 ( 2 一) 的确定性算法求解，其中：n 表示实例的输入长度。 定理2 1 说明了n p 类问题属于可计算问题。 定理2 2 “”如果吼是n p c o m p l e t e 问题，死 俨，且蜀可以多项式时间 归约到而，则f t ，是n p c o m p l e t e 问题。 由以上定理及定义可知，如果某n p c o m p l e t e l b 题有多项式时间算法，则 n p 类中所有的其他问题也有多项式时间算法，因此n p c o m p l e t e l b 题是n p 类中 最难的问题。另一方面，如果一个n p c o m p l e t e 问题没有多项式时间算法，则 所有的n p c o m p l e t e 问题也没有，因此所有n p - c o m l e t e 问题具有同等难度“”。 n p c o m p l e t e b 题具有重要的实际意义和工程背景，目前已有许多问题被 证明为n p c o m p l e t e l h 题，如背包问题( k n a p s a c kp r o b l e ) 、任务分配问题 ( a s s i g n m e n tp r o b l e m ) 、j o b s h o p f 题和f l o w s h o p 阅题、旅行商问题( t s p ) 和本文所要解决的柔性制造系统工件加工路径流量的分配问题。 n p c o m p l e r e 问题的精确解目前尚无有效算法来求得，一般总是设计一个 近似算法来求其近似解，也就是一个足够好但不一定是最好的答案，要求这种 近似算法在多项式时间内求得满意解。本文正是基于此使用蚁群优化算法这一 优化算法来求得柔性制造系统工件加工路径流量的近似最优解。 2 3 优化算法 计算机求解优化问题的主要手段就是对优化问题的可行解空间进行搜索。 而按照搜索策略的不同，我们可以将主要