基于拆卸序列优化的零部件拆卸分析系统

王哲

（合肥工业大学机械与汽车工程学院，合肥230009）

0 引言

拆卸是采用一定的工具和手段，解除对零件造成约束的各种联接，将产品零部件逐个分离的过程。拆卸序列规划的定义为，在满足产品结构和装配关系等要求的前提下，生成零件拆卸序列的过程［1］。为了获得能够满足装配约束要求的拆卸序列，并对拆卸序列进行优化，提高拆卸效率及其使用价值，本文提出了基于拆卸混合图的拆卸序列优化模型［2］，并在获得满足要求的拆卸序列后使用遗传算法进行优化求解。为了方便装配件拆卸信息的管理及拆卸序列的优化，编写了拆卸分析系统，通过它可以计算得到近似最优序列。

1 拆卸序列模型

1.1 拆卸信息模型

本文考虑的产品拆卸信息模型主要包括三个部分：零件基本信息、拆卸过程信息及装配信息。零件基本信息主要包括该零件的名称、体积、重量等具体信息；拆卸过程信息即所使用的拆卸工具、拆卸时间等信息；而装配信息则主要是考虑零件拆卸过程中的约束关系。

根据以上拆卸信息模型采用混合图进行建模。拆卸混合图是一种常用的拆卸信息建模方法，如图1所示。混合图的顶点定义为产品的零件或部件，有向边或无向边分别表示了零部件之间的装配约束关系。

拆卸混合图可以用集合形式表示为

式中：G 为混合图集合；V=｛v1，v2，…，vn｝表示零部件集合；UE=｛ue1，ue2，…，uen｝是无向边集合，表示零件之间无接触约束关系；DE=｛de1，de2，…，den｝为有向边集合，表示零件之间存在拆卸优先关系，即有接触约束关系。

拆卸混合图可以很清楚地反映出零件直接的拆卸约束关系，但是计算机是无法直接识别这类图模型的，因此必须对其进行数字化处理。本文采用连接矩阵和优先矩阵来表达。

即可将混合图 G=｛V，UE，DE｝分解为 GC=｛V，UE｝和GP=｛V，DE｝。对于连接矩阵

其中，

特别规定当i=j时，cij=0。

对于连接矩阵

其中，

对于如图1所示拆卸混合图即可表示为：

1.2 拆卸序列生成

拆卸序列的生成基于定向搜索策略，即在优先关系矩阵的引导下，生成拆卸序列。具体流程如图2所示。

图2 拆卸序列生成图

验证表明随机选取零件作为拆卸的起始点比指定初始拆卸零件速度要快很多，其关键在于拆卸优先关系的合理定义和全面表述。根据此流程产生的拆卸序列作为初始序列能够满足拆卸的优先关系，因此初始序列是合理可行的。通过此方法能够快速地生成足量的初始拆卸序列。

1.3 拆卸序列的优化

影响拆卸效率的两个主要因素是拆卸方向的变更次数与拆卸工具的更换次数，因此拆卸序列的优化函数构建应主要考虑这两方面。对于所得拆卸序列s，构建的适应度计算公式如下：

其中：ωd和ωt分别代表拆卸方向和拆卸工具的权重，n为拆卸序列中所含零件总数，常数C为保证适应度随着时间增大而减小。对于 di，i+1和 ti，i+1，则有：

2 拆卸序列优化模型求解

拆卸序列规划实际上是一个NP组合优化的问题，传统的拆卸序列规划方法大多是基于图搜索的方法，但是图搜索算法存在其弊端，即随着被拆卸深度的增加，无法规避组合爆炸问题。

遗传算法无需遍历整个搜索空间就能够得到最优或是次最优解，就能够很好地解决组合爆炸问题。遗传算法是由美国Michigan大学的John Holland与其同事、学生们基于生物进化论中的自然选择和群体遗传学规律而提出的一种优化搜索算法［3］。基本思想是：把整个待拆卸体信息库空间映射成遗传空间，将具体零部件信息映射成遗传染色体，对其中的所有个体进行适应度大小的计算。之后对群体进行选择、交叉或变异等遗传操作，适应度小的个体自行淘汰，适应度大的个体保存下来。通过指定代数的反复操作或者达到适应度阈值后，求出最优个体。

具体算法流程图如图3所示。

2.1 染色体构造

在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称为编码。编码决定了交叉、变异等遗传运算方法，能够极大地影响算法的运行效率。

对于零部件的拆卸序列，直接采用零件序号进行实数编码明显更加方便与合理。实数编码省去了编码和解码的过程，更利于算法的实施。如染色体为“1，2，3，4，5”的一种拆卸序列为：1→4→2→3→5。

图3 遗传算法流程

2.2 交叉算子

交叉操作又称为基因重组，就是按给定的交叉概率Pc，从群体中随机选取2个父个体，互相替换2个父个体的其中一部分结构，之后进行重组形成新个体的操作。交叉操作是生成新个体的主要方式，能够提高算法的全局搜索能力。本模型采用的是部分映射交叉法，即在父个体中选择一个子序列并且在替换到另一个父个体时次序和位置尽可能不变。方式如下：

随机父个体 1：1→2→|3→4|→5。

随机父个体 2：1→4→|2→3|→5。

交换两父体字串：1→2→|2→3|→5；1→4→|3→4|→5。

映射关系为：2→3→4。

映射后的子代为：1→4→|2→3|→5；1→2→|3→4|→5。

2.3 变异操作

变异是以较小的概率对染色体串上的某些位值进行改变，从而形成新的个体的过程。变异操作决定了遗传算法的局部搜索能力，是产生新个体的辅助方法。

本模型采用的是置换变异方法，即随机选择2个基因，置换它们彼此在序列中的位置，并且要注意的是这种置换并不能改变零件之间的拆卸优先关系。举例如下：

父个体 1：1→2→3→4→5。

选择3、4进行置换后的序列为：1→2→4→3→5。

3 软件设计

3.1 软件设计思想

为了实现便捷地拆卸序列规划操作，基于拆卸序列优化开发了一个计算系统。系统主要设计思想是：令使用者在输入相对较少产品零件信息的基础上，通过该系统可以对产品进行拆卸分析，生成拆卸序列，并对产品的拆卸序列进行回收评估，之后运用遗传算法进行优化，得出最优或近似最优的拆卸序列。

3.2 参数选择

本文中采用基因组的编码方式表达装配体中零件的信息。一个基因组封装了零件拆卸中所有相关的信息，同时也是在数据库中储存的基本单元。基因组采用三位码编码，包括零件编号、拆卸工具、拆卸方向信息。表示如下：

其中：PID表示零件编号，由数据库自动生成；P_Tool表示拆卸工具编号，对应拆卸工具表中的工具；P_Direction表示拆卸方向，主要有｛+X，-X，+Y，-Y，+Z，-Z｝6个方向。

表1 Part数据库字段表

遗传算法中的参数选择主要有群体规模S，交叉概率PC，变异概率Pm，终止条件等。这些参数的选择对算法的运行性能影响较大，不恰当的选择会导致算法运行缓慢。

群体规模S表示群体中所含个体的数量，在本模型中即为零件个数，一般的取值范围是20～100；交叉概率PC，交叉操作是新序列生成的主要方式，所以交叉概率应取较大值，一般的取值范围是0.4～0.99；变异概率Pm，变异概率太小会是遗传算法趋近随机搜索，太大又会使产生新个体能力变差，一般取值范围是0.0001～0.1；终止条件主要是终止代数或适应度最小准则。终止代数指的是遗传算法运行到指定的进化代数G之后就停止运行，取出群体适应度最佳的个体作为所求问题的最优解输出；另一种终止条件是给定一个阈值C，当其连续L代的平均适应度差异小于该值时停止。

3.3 软件结构及系统流程

系统集成了多个模块的功能，其中产品模型信息管理、拆卸序列分析、拆卸序列优化等。系统具体工作流程如图4所示。

实现系统逻辑的伪代码表示如下∶

Initialize(s);//载入并初始化序列

Verify(x)

{验证序列x是否符合拆卸优先顺序}

Get_Fitness(x)

{按公式计算个体适应度值

returen Fs;}

Verify(Random(s));//随机打乱并验证序列s是否符合拆卸优先顺序

for(i=0;Fs＜=C||i＜=G;i++)//C代表给定的终止阈值,G代表给定的进化代数

{

While(Verify(s))

{Intersect(s);//交叉操作

图4 软件逻辑流程

Mutate(s);//变异操作

Get_Fitness(s);//计算个体适应度}

}

输出结果;

3.4 操作实例

图5为某装配体的装配体信息管理界面，该装配体由12个零件组成，界面支持装配体信息及零件信息的添加删除修改。

图6为拆卸序列规划界面，在参数设定框体中输入预先设定的遗传算法参数，这里取交叉概率PC=0.5，变异概率Pm=0.05，终止代数G=50，适应度阈值=180。生成初始序列为 8→9→2→10→3→4→11→1→12→7→5→6，之后点击计算即可在满足终止条件时生成最优或近似最优解，即 3→5→8→9→2→10→11→1→12→7→4→6。经验证，所得拆卸序列符合约束条件且为适应度最大解，证明软件从算法的执行上是可行的。

图6 拆卸序列规划界面

4 结语

本文提出了基于拆卸混合图的拆卸序列优化模型，并对序列优化的适应度进行了阐述。之后给出了使用遗传算法的拆卸序列模型求解办法。为方便装配件拆卸信息的管理及拆卸序列计算，编写了拆卸分析系统，计算了实例并获得了最优或近似最优拆卸序列，证明了软件的可用性。能够为装配件信息管理及拆卸序列的智能生成提供一定的支持。

［1］ 刘志峰，胡迪，高洋，等.基于贪婪算法的产品拆卸序列规划［J］.中国机械工程，2011（18）：2162-2166.

［2］ Zhang H C，Kuo T C.A Graph-Based Approach to Disassembly Model for End-of-Life Product Recycling［C］//IEEE/CPMT International Electronics Manufacturing Technology Symposium，1996：247-254.

［3］ 韩建升.基于遗传算法的拆卸序列规划研究［D］.武汉：华中科技大学，2007.

［4］ Silveira L R，Tanscheit R，Vellasco M.Quantum-Inspired Genetic Algorithms applied to Ordering ombinatorialptimization Problems［C］//WCCI2012IEEEWorld Congresson Computational Intelligence June，10-15，2012，Brisbane，Australia.

［5］ 张秀芬，张树有.基于粒子群算法的产品拆卸序列规划方法［J］.计算机集成制造系统，2009（3）：508-514.

［6］ 江吉彬，刘志峰，刘光复.基于工程语义信息的拆卸序列规划算法研究［J］.计算机集成制造系统，2006（4）∶625-629.

［7］ 赵树恩，李玉玲.模糊推理Petri网及其在产品拆卸序列决策中的应用［J］.控制与决策，2005（10）∶1181-1184，1188.

［8］ 章小红，李世其，王峻峰，等.基于蚁群算法的单目标选择性拆卸序列规划研究［J］.计算机集成制造系统，2007，13（6）∶1109-1114.

［9］ 谢歆，赵国华.Visual C++高级编程实例精解［M］.北京∶国防工业出版社，2001.