面向概念设计的拆卸规划及序列优化.doc

此文档收集于网络，如有侵权，请联系网站删除面向概念设计的拆卸规划及序列优化1.引言当今社会，面对日益严重的生态环境危机与资源危机，世界上大多数国家都意识到保护环境与节约资源的重要性，都相继制订了相关法律法规来保护生态环境并通过加强对废旧产品的回收再利用来节约资源。机械产品都是由各种材料的零部件组成，对其回收利用离不开拆卸。合理的回收废旧产品可以使大量的零部件及材料实现再循环利用，最大限度的减少资源浪费，提高资源利用率。合理的拆卸步骤不仅对提高废旧产品的拆卸效率有着至关重要的影响，也影响着产品维修效率的提高。面向概念设计的拆卸规划及序列优化就是研究如何为产品提供最优拆卸序列的这么一个课题。拆卸一般分为部分拆卸与完全拆卸，拆卸序列研究方法的一般过程为产品信息建模、序列规划及序列优化。产品信息建模即为产品建立数学模型，方便在序列规划阶段计算提取可行拆卸序列，序列优化即在一系列可行拆卸序列中寻求最优序列。本文主要归纳常用的产品信息建模方法及序列优化方法，并浅加比较，为拆卸序列规划方法研究给以参考。2.产品信息建模方法2.1 无向图一个无向图（Undirected Graph）是一个二元组G = ( V , E )，其中顶点V = (v1, v2, v3,vm )表示拆卸单元，如零件、组件等，m为拆卸单元个数；边E = （e1, e2, e3,en ）表示顶点之间的约束关系，n为约束边的条数。无向图所能表达的信息有限，即只能表达出拆卸单元之间的邻接关系。当一条边联接两个节点时，表示这两个拆卸单元之间在空间上存在有邻接关系。2.2 有向图有向图（Directed Graph）是一个二元组G = ( V , E )，其中顶点V = (v1, v2, v3,vm )表示拆卸单元，如零件、组件等，m为拆卸单元个数；边E = （e1, e2, e3,en ）表示顶点之间的约束关系，n为约束边的条数。有向图中的边是带有方向的边，其代表的含义是在拆卸过程中箭尾节点对箭头节点存在约束关系，即会阻碍箭头所指向节点的拆卸。有向图是在无向图基础上的拓展，可以表现出拆卸单元之间的拆卸约束和拆卸顺序关系。2.3 与或图2.3.1 集合与或图与或图（And/Or Graph）是一种超图。集合与或图的定义如下：定义1 设A 为一个非空有限集合, A 的幂集。如果集合,且, ,那么,定义V 为A 的一个顶点集合,元素v V 为A 的一个顶点。定义2 设V为A的一个顶点集合，V的元素个数为|V|。当| V | 2 时,任取V 中元素u , v1 , v2 , , vm(m 1) , 如果v1 , v2 , , vm 互不相交, 且,那么, 定义集合e = u , v1 , v2 , , vm 为A在V 中的一条边,顶点u 为该边的主顶点, v1 , v2 , vm 为从顶点, A 在V 中所有的边组成边集合E。当| V | = 1 或| V | = 2 时,定义A 在V 中的边集合为。定义3 设V 为A 的一个顶点集合, E 为A 在V 中的边集合,那么,定义偶对( V , E) 为A 关于V的集合与或图,记作。定义3 设V 为A 的一个顶点集合, E 为A 在V 中的边集合,那么,定义偶对( V , E) 为A 关于V的集合与或图,记作。定义4 设e = u , v1 , v2 , , vm 为集合与或图中的一条边, 定义有序对( u , v1 ) ,( u , v2) , , ( u , vm ) 之间的关系为顶点u 在边e 中的与关系。除了m 个有序对外,边e 中的顶点之间不存在其他的任何联系。定义5 在集合与或图中，以同一个顶点为主顶点的所有的边之间的关系，称为该顶点的主或关系；以同一个顶点为从顶点的所有的边之间的关系,称为该顶点的从或关系。例1 假设集合A = 1 ,2 ,3，则其幂集P ( A )= , 1 , 2 , 3 , 1 , 2 , 2 , 3 , 3 , 1 , 1 , 2 , 3 。取顶点集合v = 1 , 2 , 3 , 1 , 2 , 1 , 2 ,3 ,则根据V 确定边集合E = 1 , 2 , 3 , 1 , 2 , 3 , 1 ,2 ,3 , 1 , 2 , 3 , 1 ,2 , 1 , 2 。由此可得集合与或图，如图2-1a 所示。2.3.2 拆卸与或图对集合与或图进行进一步的规定，定义出拆卸与或图。规定1 定义1 中的集合A 代表丧失使用价值的产品,集合A 中的元素与产品中的零件一一对应,集合A 的元素个数| A | 等于产品的零件数量。文中所提到的产品零件不包括螺纹紧固件,如螺栓、螺钉等。规定2 定义1 中的集合。根据集合论，称为0元集,含有n个元素的集合,称为n 元集，则集合V 中| A | 元集元素称为产品顶点，代表丧失使用价值的产品，一元集元素称为零件顶点，代表构成产品的零件，其他元素称为部件顶点。规定3 定义2 中的m = 2 。定义6 符合上述三个规定的集合与或图，称为拆卸与或图。例2 假设集合A = 1 ,2 ,3 ,则其拆卸与或图如图2-1b 所示。图2-1 集合与或图和拆卸与或图2.3.3 与或图针对产品拆卸建模的缺陷在拆卸与或图中， n 元集部件顶点代表从产品的| A | 个零件中任取n 个零件所构成的集合。中所有的部件顶点为数学部件顶点，而其中代表产品真实部件的顶点，称为物理部件顶点。在使用拆卸与或图进行拆卸模型建模之前，必须从数学部件顶点中筛选出物理部件顶点，以保证设计结果的正确性。此外，根据拆卸模型的自身特点,部分物理部件顶点和零件顶点也要予以剔除。除剔除顶点外，代表拆卸工艺的边也存在筛选的问题。根据定义，拆卸与或图中顶点的个数为：边的数量为：单纯从公式上就可以看出，当产品包括20个以上零件时，其拆卸与或图中的顶点个数就将超过100万，而边的数量多达17亿以上。因此，利用拆卸与或图建模极易产生信息爆炸，影响其使用。如何正确有效地对数量极多的顶点和边进行筛选，就成为拆卸与或图使用中的瓶颈问题。目前，在使用拆卸与或图作为拆卸模型建模工具时，为避免信息爆炸，可以通过人工设定物理部件顶点来回避这一瓶颈，但这样的做法将会无法保证拆卸与或图中顶点和边的完备性，从而影响建模的准确性。2.4 Petri网2.4.1 Petri网基本概念Petri网是一种广泛应用于描述异步、并发现象的跨越多学科的图形化建模和分析工具。它既有严格的数学定义，又有直观的图形表示，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。因此，Petri网具有很好的模型描述特性，被广泛地应用于计算机科学技术和其它很多领域，如随机Petri网、着色Petri网、赋时Petri网、模糊Petri网等。近年来，由于Petri网的表达直观，易于理解，将其引入产品拆卸过程中，并结合零部件的回收效益及相应的拆卸成本，建立了拆卸Petri网。Petri 网是由库所（place）、变迁（transition）和带箭头的弧（arc）组成。库所描述系统的可能状态，如制造系统中机器的工作状态及被加工零件的状态等。变迁代表系统的可能的事件，如制造系统中的上下工件，开始结束加工等。通过建立局部状态与事件之间的联系。库所、变迁及弧构成了PN结构。系统的状态通过包含的托肯（tokens）数来描述，托肯用实心圆表示。定义1 PN的结构由4个元素描述：其中：(1)为库所的有限集合。n0；(2)为变迁的有限集合，n0;(3);(4)I:为输入函数，定义了从P到T的有向弧的权的集合；(5)O:为输出函数，定义了从T到P的有向弧的权的集合。在表示Petri网的有向图中，库所P用圆表示，变迁T用长方形或粗实线段表示；I为输入矩阵，定义了从库所到变迁的有向弧集合。若从库所p到变迁t的输入函数取值为非负整数，记为I(p，t)=；O为输出矩阵，定义了从变迁到库所的有向集合。若从变迁到库所的输出函数取值为非负整数，记为O(p，t)= 。特别的，=1，则不必标注；若=0，则不必画弧。I与O均表示为 nm 非负整数矩阵，O与I之差 C=OI 称为关联矩阵。在DES中某一事件必须在所有前提条件（状态）得以满足（实现）的情况下才可能发生。有时候要求某一前提条件必须满足多次。在 PN 中，我们以变迁t表示一事件，用变迁时能（Enabling）表示事件发生因前提条件得以满足而能够发生。定义2 一变迁在标识m下使能，当且仅当：。其中，表示t的所有输入库所的集合。定义3 在标识m下使能的变迁t的激发将产生新标识m：具体地：我们称标识m是（通过t激发）直接从m可达的。以机械手装配图为例，如图2-2，可拆卸性Petri网建模过程如下：步骤一： 创建拆卸结构特征单元及其对应关系。图中给出了以 16 种零件组成的机械手 cad 图模型，要得到它的拆卸关系图模型，要将组成其系统的零件进行拆卸件分类。按照算法流程图的说明，从零件 1 开始，对整个装配体零件进行遍历，得到三大类零件类列表如下：固定连结件件单元 PLU：8，11，12（13），（14、15）13 垫片是从属于 12号件螺钉的附件；而 14 与 15 号零件是配合使用的螺栓组合形式。限位结构件单元 LSU：（5、6），（9，10）这两组都是运动部件，从属于相邻的框架结构件。这里要指出零件组（5，6）寻找邻接矩阵可以初步确定分属于件 3 号或 7 号件；而零件组（9，10）虽也有两组零件相邻接 1 号和 16 号，但由于 16 号件的拆除不能导致零件组的拆除，因此零件组（9，10）只能作为零件1 的附加单元。其他结构件单元 OSU：1，2，3，4，7，16其中，基础件为 4 号零件；随着算法流程的进行，在给出了三大类拆卸特征单元的同时，它们之间的对应关系也相应确定。如表2-1所示：步骤二：确定拆卸层级关系。拆卸层级的确定要以连接件为线索，以框架结构件为对象进行从外而内的逐级剥离分析。首先，装配体中共确定了 4 组连接件单元，遍历各自的干涉矩阵，可以得到它们都是可以直接拆除的，但8号与11号零件虽可直接拆除，但并没有产生其它组件的直接拆卸，因此称只有连接件单元12（13）和14，15是级连接件单元；确定后，将它们全部拆除，分析对应的邻接矩阵，找到可以直接拆除的框架结构件 1,4，7 号零件，它们是级框架结构件。然后在按照这些框架结构件的邻接矩阵，找到对应的运动结构件单元，确定它们最终所属的框架结构件单元。即（5，6）属于 7 号件；图2-2 机械手装配图表2-1 零件的拆卸特性分类及对应关系LSU零件列表邻接PCU列表PCU层级LSU层级附加PCU列表邻接OAU列表附加OAU列表114,15I级I级14,1528II级II级838II级II级85,6412(13);14;15I级；I级I级712(13)I级I级12(13)5,65,61614;15;11I级II级119,109,10其中：PCU：代表定位连接件单元；LSU：代表县限位构单元； OAU：代表其他结构件单元；4号件为基础件更新相应的邻接矩阵信息和干涉矩阵信息。返回上面步骤，重新查找连接件列表，发现8;11号零件都可以带着相应邻接组件直接拆除，因此确定它们为级结构件单元，相应的级框架结构单元内包括零件2；3；16，这里要说明的是：8 号连接件与相配合的 2,3 号零件的拆卸顺序的平等的，因此也就产生了可选择性拆卸方向，这也是使本例产生多种拆卸路径的原因。16 号件还有一个运动结构件单元的附件（9，10）。至此所有除基础件外的框架结构件全部拆开，拆卸层级关系确定完毕。步骤三：给出拆卸 Petri 网图模型。明确了产品拆卸层级关系后，用拆卸 Petri网语言对拆卸模型描述后，得到拆卸关系图模型如下图2-3：图2-3 机械手框架结构拆卸Petri网图模型2.4.2 Petri网的优缺点Petri网内的元素灵活多变，这里的P、T、I、O只是Petri网中的基本元素，在元素中添加拆卸时间、拆卸费用等关于拆卸序列规划的元素之后，Petri网就可以用来描述拆卸模型的信息。2.5 拆卸约束图（拆卸混合图之一）（机电产品拆卸规划及拆卸设计方法研究胡迪）拆卸约束图（Disassembly Constraint Graph, DCG）是一种基于图论的产品拓扑结构模型，其表现形式是一个混合图，可以定义为一个三元组G = ( V, E, DE )。其中节点V=( v1, v2, v3,vn )表示拆卸单元，n表示装配体中拆卸单元的个数；无向边E = ( e1, e2,e3,em )表示两个拆卸单元之间存在的关系约束，m表示拆卸单元间联接关系的总个数；有向边DE = ( de1, de2, de3,dep )表示两个拆卸单元间存在空间干涉，箭尾拆卸单元在空间上阻挡了箭头所指的拆卸单元的拆卸，p表示拆卸单元在空间干涉的总个数。G可以分解为记录拆卸单元间的联接约束图（DCG图中无向边与节点组成的无向图）和空间干涉图（DCG途中有向边与节点组成的有向图）分别来表示。零件的拆卸就是在图中将其对应的节点及与其相关的边删除。如图2-4 a所示的装配体，其拆卸约束图如图2-4 b所示。图2-4 装配体及其拆卸约束图2.6 拆卸赋权混合图模型（拆卸混合图之二）（复杂产品可拆卸性分析与低碳结构进化设计技术研究）混合图是一种基于图论的产品拓扑结构模型，基本拆卸混合图模型可以定义为一个四元组，其中，顶点V = ( v1, v2, v3,vn )表示最小拆卸单元，如产品的零部件、子装配体等，n为最小拆卸单元个数;顶点v的邻域，在v的邻域里，比v拆卸优先级低的顶点构成其后继域，其余顶点集合为v的前趋域，且；约束关系定义为图的有向边或者无向边(v1,v2)，如果约束是通过紧固件或其他方法使得两个最小拆卸单元直接接触而产生，且存在强制的拆卸优先关系，则定义为强物理约束，记为，用带箭头的实线表示;如果最小拆卸单元间虽直接接触，但没有强约束关系，则定义为物理约束，记为表示为实线段;如果虽不直接接触但存在约束优先关系，则定义空间约束，记为，用虚箭头线表示。如下图所示的某产品部件，其中，A、B、C、D、E分别代表产品的最小拆卸单元，紧固件作为约束考虑，以减少产品的复杂度。顶点B的邻域、前趋域和后继域分别为，。，通过螺钉连接构成强物理约束关系，且A的拆卸顺序优先于C；为物理约束；而为空间约束，且虚线箭头表示A的拆卸优先于B。依次类推，得打该结构的拆卸混合图模型，如图2-5所示。 （a）部件结构图 （b）基本拆卸混合图图2-5 部件结构与基本拆卸混合图在基本的拆卸混合图的基础之上进行修改和补充得到拆卸赋权混合图，描述了产品零部件之间的约束关系，用五元组表示，其中，前四个元素的含义同2.6中的基本拆卸混合图模型相同，分别描述了最小拆卸单元、物理约束、强物理约束、空间约束，Wij为边的权重，根据接触类型、装配方法、拆卸工具类型、拆卸方向个数四类工程属性进行评分确定，具体代号和分值分配见下表。以字母代号的形式进行标注，权重分值为1100，权重W为四类工程属性对应分值之和。表2-2 权重代号与分值工程属性类型代号分值类型接触点接触P6线接触L12单面接触SF18多点接触MP24多面接触MF30放置P4装配方法插入I8旋入T12深结合D16不可拆卸装配ND20拆卸工具类型无工具H7普通工具SD14小型工具ST21特殊工具SPE28大工具LT35一个方向即可拆卸One3两个方向即可拆卸Two6拆卸方向个数三个方向即可拆卸Three9四个方向即可拆卸Four12五个方向即可拆卸Five15 图2-6表示了某个产品结构及其相应的拆卸赋权混合图模型。其中，节点A，B，C，D，E，F分别表示该产品的构成组件，紧固件作为约束考虑，以减少模型的复杂度。图中，通过螺钉连接构成强物理约束，而为空间约束，以此类推，最后该产品的这种拆卸约束关系就可以表示为下图所示的拆卸赋权混合图，其对应的权重见表2-3所示。图2-6 产品装配示意图及其拆卸赋权混合图模型表2-3 产品的权重边接触类型装配方法拆卸工具类型拆卸方向个数权重WMF(30)T(12)SD(14)Two(6)62MF(30)I(8)H(7)One(3)48MF(30)T(12)SD(14)One(3)59SF(18)T(12)SD(14)One(3)47SF(18)I(8)ST(21)One(3)50SF(18)I(8)ST(21)One(3)503 序列规划方法与优化拆卸序列规划方法是产品拆卸规划中的关键内容，主要的方法分为两类：一类是基于图搜索的拆卸序列生成方法，如部件紧固件法、与或图法、Petri网法、拆卸树法、割集法等。这类方法主要通过产品中零部件之间的几何拓扑信息来得到产品的拆卸序列，随着产品复杂程度的提高，容易产生组合信息爆炸而难以得到结果。另一类是人工智能搜索法，如遗传算法，蚁群算法、模拟退火算法、粒子群优化算法等。这类方法应用启发式规则迭代寻优，易于利用计算机求解，速度快。在基于图搜索的几何推理求解拆卸序列方面，Zhang和Kuo（Design for manufacture anddesign for X concepts, applications, and perspectives,A graph-based disassembly sequence planning for EOL product recycling,Disassembly sequence and cost analysis for electromechanical products）在部件紧固件图的基础上，采用割点法将产品分解为子装配体以完成拆卸序列的规划。潘晓勇（基于割集的拆卸序列生成方法）及郭伟祥（基于模块化思想的拆卸序列规划）和梁斌（装配规划中基于割集的装配顺序生成方法）均采用割集的方法生成产品的拆卸序列。Moore（Petri net approach to disassembly process planning for products with complex AND/OR precedence relationships）在与或图的基础上，将产品拆卸信息转化为Petri网，采用可达树获得方式对产品拆卸序列规划进行求解。Zeid（An Analogical Problem Solving Approach to Planning Disassembly）采用基于实例推理(Case-Based Reasonning, CBR)的方式对产品拆卸序列规划进行了研究。Johnson（Planning Product Disassembly for Material Recovery Opportunities）采用拆卸树的方式对产品拆卸序列规划进行了研究。Shana S. Smith（Rule-based recursive selective disassembly sequence planning for green design）采用基于规则推理的方法，对产品的选择性拆卸序列规划进行了研究。Carlos Andres（Disassembly sequence planning in a disassembly cell context）等提出了对有模块化结构的产品采用两阶段法进行拆卸顺序优化。第一阶段以拆卸费用最小为目标确定最大拆卸单元，目的是以相同的设备进行拆卸并提高设备的利用率，第二阶段是进行拆卸顺序规划。Christian Mascle（Algorithmic selection of a disassembly sequence of a component by a wave propagation method）在通过获取前一步拆卸状态数据的基础上，提出了基于递推的产品零部件拆卸算法。易建军（面向机械零件设计的可选择性拆卸策略研究）等在建立广义的机械零件 CAD模型的基础上，定义了装配体中的拆卸波是装配体中某些零件的一种拓扑关系，可反映零件之间的拆卸顺序。并在此基础上提出了一种基于拆卸波的零件可选择性拆卸规划算法。该算法的计算量小，容易用它来进行高效的搜索，获得最优的零件可选择性拆卸序列。此外，国内学者的研究方法还包括基于随机网络模型的拆卸计划（基于层次结构的拆卸序列生成研究）、基于广义轴理论的产品拆卸路径规划（基于广义轴理论的产品拆卸路径规划）、基于层次结构的拆卸序列生成（随机网络的产品拆机计划）等。在基于人工智能启发式算法求解拆卸序列方面，美国的 Chuck Zhang 等提出了一个基于模拟退火算法来优化产品的拆卸规划方案的算法（Optimum Disassembly Planning for Environmentally Conscious Manufacturing）。算法用装配联接图的方法对产品的装配关系建模，然后得到以拆卸方案。美国东北大学的Kongar和Gupta提出了一种使用遗传算法来求解拆卸序列规划问题的方法（Multi-Objective optimization in disassembly sequencing problems）。意大利的学者Failli F和Dini G等将蚁群优化方法应用于这一领域（Optimization of Disassembly Sequences for Recycling of End-of-Life Products by Using a Colony of Ant-like Agent）。南京航空航天大学的吴昊（基于改进遗传算法的产品拆卸序列规划基于改进遗传算法的选择性拆卸序列规划）对遗传算法进行了改进，提出了基于改进遗传算法的产品拆卸序列规划方法。陆中（面向维修性设计的民机产品拆卸序列规划方法）等提出了基于基因成对交叉与变异的遗传算法的完整拆卸序列优化方法。华中科技大学的章小红（基于蚁群算法的产品拆卸序列规划方法基于蚁群算法的单目标选择性拆卸序列规划研究）、清华大学的王辉（Assembly planning based on semantic modeling approach基于蚁群算法的产品拆卸序列规划研究）、哈尔滨工程大学的薛俊芳（基于蚁群优化算法的目标拆卸序列规划Selective optimized disassembly sequences based on ant colony optimization）采用蚁群算法对拆卸序列规划进行了相关研究，并论证了蚁群算法相对遗传算法求解拆卸序列的有效性和优越性。浙江大学的张秀芬（Product cooperative disassemblysequence planning based on branch-and-bound algorithmVirtual disassembly Simulation of varying target component for complex products基于粒子群算法的产品拆卸序列规划方法）采用粒子群算法对拆卸序列规划进行了研究,并通过实例比较了粒子群算法相对蚁群算法的优越性。3.1 粒子群优化算法(复杂产品可拆卸行分析与低碳结构进化设计技术研究)粒子群优化算法(Partical Swarm Optimization, PSO)是一种新型群集智能(Swarm Intelligence, SI)技术，采用群体进化和适应度函数评价优化结果，主要源于鸟集群飞行觅食行为的研究。将鸟群中的每只鸟看作搜索空间中的一个无体积的粒子，代表问题的一个可行解，具有位置和速度两个属性，以粒子位置坐标对应的适应度函数值确定粒子的“优劣”程度。每个粒子利用自身、自身的历史最优位置和整个粒子群的全局最优解提供的信息，在解空间内不断飞行，寻找满足条件的最优解。PSO通过群体中个体之间的协作和信息共享与竞争机制获得最优解，具有参数少易于调节、收敛速度快、鲁棒性好、效率高、编码简单和便于计算机实现等优点,目前已经广泛应用于函数优化!神经网络训练!模糊控制等多种优化问题。3.1.1 基于粒子群优化算法的序列规划流程该算法结合2.6中拆卸混合图模型，融合两方法的优点，实现复杂产品拆卸序规划的快速高效求解。利用粒子群优化算法进行产品拆卸序列规划的实质是将图搜索法和智能优化算法相结合的过程，主要包括三个步骤:建立拆卸信息图模型、粒子群预处理、粒子按进化规则飞行寻优。步骤一：建立图模型是求解成败的基础。为降低模型复杂度，借鉴组件一紧固件图的思想，将紧固件等联接件剔除掉，组件的拆卸实质是不断去除这些联接约束的过程，所以，将这些紧固件作为约束信息放入边中。另外，对于较复杂产品，可以将部件作为最小拆卸单元，然后逐层处理。预处理完成后，通过人机交互的方式从产品装配体中提取约束信息，生成拆卸混合图,并初始化约束矩阵和邻接矩阵。步骤二：初始化算法所需参数。通过粒子群的初始化生成系列可行拆卸序列作为粒子进化的基础，这样有助于减少粒子群进化的盲目性,并提高了拆卸序列的正确性。以拆卸信息图模型为基础，通过几何推理生成符合可拆卸条件的拆卸序列,作为初始粒子。步骤三：按照粒子位置和速度进化规则，初始粒子在全局和局部解域进行寻优，粒子适应度值用于评价粒子的优劣度，适应度值越小，说明该序列所用拆卸成本越少。用户可以预先给定一个阈值，或最大迭代次数作为算法的收敛条件。算法的具体流程如图3-1所示：3.1.2 粒子群优化算法与蚁群算法在拆卸序列规划中的比较在复杂产品可拆卸行分析与低碳结构进化设计技术研究一文中，作者利用虎钳作为拆卸实例进行分析，将粒子群优化算法与蚁群算法做了比较。两种算法的比较结果如表3-1所示：表3-1 运算结果比较表算法迭代次数工具变换次数方向改变次数运行时间(s)近似最优序列粒子群算法60560.5189975-8-9-3-10-2-6-1-4-7-12-11-0蚁群算法300461.4861358-5-9-7-2-3-10-12-4-6-11-1-0由上表可见，两种算法都可以求得近似最优解，且蚁群算法的优化结果优于粒子群算法，但粒子群算法的迭代次数较少，且计算时间少。这主要是由于蚁群算法缺乏全局搜索能力，为避免早熟，需要较多的迭代次数才能得到全局最优解，而粒子群算法机理简单，在初始解的基础上，能够综合利用各个粒子局部信息和种群的全局优化信息，并行地寻找最优解，因此可以在较少的迭代次数内求得最优解。3.2 蚁群算法（基于蚁群算法的拆卸序列规划方法研究）人工蚁群算法，简称蚁群算法（Ant Colony Algorithm），是一种新型的仿生算法。它是意大利学者M. Dorigo等人受自然界蚂蚁群集体行为特征的启发而最先提出来的，一些学者通过对蚁群系统模型的改造，提出几种不同形式的蚁群算法，并成功地应用于求解诸如 TSP 等组合优化问题。在应用中发现，蚁群算法具有以下优点：(1)对目标函数无特殊要求，适合于目标函数为高度非线性、非凸或离散型的最优模型；(2)算法具有较强的鲁棒性，对蚁群系统模型稍加修改，便可用来求解其它类型的规划或决策问题；(3)由于该算法是一种基于种群的进化算法，具有本质的并行性，所以易于实现分布式并行计算；(4)算法具有灵活性和开放性的特点，易于通过移植、杂交等方法同启发是算法或传统算法结合，以改善算法性能或形成新的算法。图3-1 最优拆卸序列求取流程3.2.1 蚁群算法流程基于蚁群算法完全拆卸序列规划方法的流程图如图3-2所示。其中，装配体的零件个数为N，连接矩阵为Ec，优先矩阵为Prec。蚁群算法的各个参数：为度因子，为期望启发因子，为全局信息挥发因子，为局部信息挥发因子，q为信息调整值，为初始信息，M为蚂蚁数量，T为循环次数，a为方向改变权值，b为工具改变权值。图3-2 蚁群算法系列优化算法流程图3.2.2 蚁群算法与遗传算法在拆卸序列规划中的比较在基于蚁群算法的产品拆卸序列规划方法研究一文中，作者以某型号小灵通为例，建立拆卸混合图，如图3-3所示，蚁群算法和遗传算法优化结果如表3-2所示。图3-3 小灵通零件图与拆卸混合图表3-2 蚁群算法和遗传算法优化结果比较算法蚁群算法遗传算法循环次数200200方向改变次数33工具改变次数684.86.0CPU运行时间7s80s由上表可以看出，两种算法在循环次数相同的情况下，蚁群算法的优化的综合代价之和比遗传算法的综合代价之和要稍微好一点。而且蚁群算法优化时CPU运行时间比遗传算法CPU运行时间也相对要小很多。这是因为，遗传算法在交叉或变异时，会产生很多无效的不可行的拆卸序列，这样就大大增加了搜索的空间。那么，蚁群算法是一步一步寻找信息素最大的路径，并且是在可拆卸零件空间里面搜索，每条路径都是可行的。而且蚁群算法是对拆卸混合图的动态更新，搜索空间随着混合图的更新也不断的缩小。3.3 遗传算法（基于遗