基于树状图同构识别方法的机构运动链进化设计原型系统①

华尔天 李生辉 鹿 浩 何志国 沈永康

(*浙江工业大学先进制造研究所 杭州 310023) (**浙江水利水电学院先进水利装备浙江省工程研究中心 杭州 310018)

0 引 言

智能机械设计是当前学界与产业界的一个重要研究课题。作为智能机械设计的重要手段，进化设计更得到了学界与产业界的广泛关注。在产品造型设计领域，罗仕鉴等人[1]对产品仿生进化设计现状做了研究综述；苏建宁等人[2]基于整体流程，建立了多意象造型进化设计系统；张秦玮[3]提出了产品多意象造型进化设计的模型和基于NSGA-Ⅱ算法的进化设计技术。在个性化产品设计领域，包志炎等人[4]提出针对个性化定制产品的优势种群产生策略。赵婷婷等人[5]提出蔓延遗传算法，优化满足顾客需求的解的选择策略。在设计过程优化方面，Saldanha等人[6]以管壳式换热器设计为例，提出基于多目标的进化算法优化方法。刘策越[7]以机器人设计为例，提出开源式、模块化机器人设计进化形态。在交互式进化设计方面，华尔天等人[8]以汽车个性化定制为例，提出一种问答式智能交互演进设计方法。张静卓[9]以手表造型设计为例，提出一种交互式进化设计方法。在设计平台开发方面，文献[10-13]针对某一类机电产品，开发了主要用于产品改型的设计平台或原型系统。但对于某一个设计过程，如机构运动链、机械结构等的智能、进化设计研究尚未涉及。

机构运动链设计是机械设计的重要基础。设计人员在进行执行机构设计时，常因空间、位置、结构、受力等方面原因，需要在典型或原装备机构运动简图的基础上，设计出一种新的机构运动简图。类型综合法提供了一种机构运动链的创新设计思路，但因同构识别、计算量、有效性等问题，使得类型综合法在设计人员的实际使用中受到一定限制。聂松辉[14]和徐世福[15]从不同角度对类型综合法进行了改进，主要集中在简化过程、优化计算效率等方面，但在机构创新设计的计算复杂性、同构识别有效性及工具化等方面尚没有得到有效解决。本文基于树状图的同构识别[16-18]原理，提出了简化类型综合法[19，20]中机构运动链进化计算的方法，建立了结构化的机构运动链进化设计智能原型系统，并进行了实例验证，力图为机构运动链创新设计提供一种工具化手段，并为智能机械设计做出积极探索。

1 机构运动链进化设计

机构运动链进化设计是应用现代信息技术，通过计算机模拟生物进化过程，优化设计机构运动链的方法。机构运动链进化设计的基本思想为基于设计目标，以典型(或原装备)机构作为初始机构，运用进化算法、同构识别等规则，帮助设计人员创造出符合要求的新的机构运动简图。设计流程分为设计要求与约束分析、初始机构转化、类型综合及进化结果选择4个阶段。

设计要求与约束分析为设计人员凭借设计经验及设计理论分析结构与功能，制定筛选条件、适应度因子及进化参数等设计要素。初始机构转化是指初始机构经过一般化及编码操作转化为树状图编码结构的过程，文献[21]对一般化及具体化操作进行了深入研究。类型综合是进化设计的核心过程，通过不断的迭代进化、筛选，获得可行解集，针对机构运动链进化设计寻求开放解的非线性过程及无法预先给定问题解的结构形式等特点，选取遗传编程[22]作为手段，树状图编码结构可以灵活表示各类问题，便于携带语义信息、层次化描述问题。文献[23]阐述了应用遗传编程进行类型综合过程及筛选过程、建立约束模型及评价函数的方法。类型综合进化设计通过遗传编程能够获得满足基本拓扑特性要求的所有运动链，这使得进化计算后得到的运动链数量比较庞大。进化结果选择与转化是指在获得的树状图解集中选取优化解并转化为新的机构运动简图。

由于类型综合法自身缺陷，这些运动链中通常存在较多同构体，如果对进化计算得到的所有运动链逐一进行从树状图到机构运动简图的转化、比较、分析、择优等，将使机构运动链进化设计的后续过程变得极其困难。因此，需要对同构体进行识别、排除，减少机构运动链进化设计后续过程的难度和工作量，为更好地解决机构运动链进化计算中产生的同构体识别问题，提出基于树状图的机构运动链同构识别方法。应用树状图同构识别方法优化进化设计流程，并建立机构运动链进化设计人机混合智能原型系统，即转化、综合、筛选及同构识别由计算机完成，其余由人工完成，为机构运动链进化设计提供一种工具化手段。

2 基于树状图的同构识别方法

机构运动链同构识别属于P与NP问题，并兼具自身的拓扑结构特性，存在自环和重边现象，因此难免有失效的情况，是公认的国际机构学界的一个难点问题[24]。机构运动链进化设计过程中，类型综合结果中含大量同构体，将导致设计方案冗余，对设计方案的进化程度造成影响。至今，学者们提出了多种同构识别方法，如针对机构运动链自身识别，采用图论识别方法，通过杆件数、运动副数以及每一运动副所连杆件数等条件进行识别。由于图论方法需对运动链上每一运动副连接杆件数目进行统计，且含复合铰链的运动链连接关系更为复杂，目前，图论识别仅适合于简单运动链，尚无法对复杂运动链进行同构识别，限制了图论识别方法的使用。现阶段，较多识别方法将机构运动链转换为矩阵或其他结构进行识别。针对简单运动链场合，矩阵同构识别方法在邻接矩阵基础上，通过计算特征值[25]、特征向量[26]及特征多项式[27-28]等进行识别；针对复合铰链场合，矩阵同构识别方法需同时构建邻接矩阵及拓扑矩阵共同识别，刘江南和于德介[29]引入Pin构件，构造了转换邻接矩阵；张瑶等人[30]通过构造拓展邻接矩阵进行识别。矩阵同构识别依据为邻接矩阵及拓扑矩阵且不具唯一性，识别过程需建立机构运动链的邻接矩阵，机构运动链杆件数越多，矩阵的阶数越大；若含有复合铰链，需同时构造多个拓扑矩阵、邻接矩阵，易出现漏项，同时存在推理演算时间长或矩阵复杂无法构造等问题。随着计算机技术持续发展，将进化算法应用于同构识别，形成的新方法如编码法[31]、启发式方法[32]、人工神经网络(ANN)技术[33]同构识别等，操作复杂、运算量大、涉及算法复杂性高，不利于计算机实现。除上述方法，其他学科理论也应用于同构识别，如电路网络分析法、熵值法[18]，但其应用范围较小，不适于复杂运动链同构识别领域。

因此，为了更好地解决机构运动链进化设计中产生的同构体识别，以及传统同构识别的识别依据为邻接矩阵与拓扑矩阵且不具备唯一性等问题，本文提出树状图同构识别方法，依据同构识别原理，制定编码规则，生成唯一树状图编码结构，对树状图编码结构进行识别计算，判别树状图同构情况进而判别运动链的同构情况。

2.1 同构识别原理

机构运动链同构是指两运动链的杆件及运动副的连接关系一一对应[34]，即杆件数、运动副数相同，且杆件之间的连接关系相同。树状图同构识别将机构运动链编码为树状图编码结构，树枝为运动副，树叶为杆件，枝叶之间的连接关系表示运动副及杆件之间连接关系。编码后生成树状图编码结构，其树叶[22]信息表示杆件信息，树枝信息表示运动副信息，通过判别树状图编码结构的树状结构及树叶信息是否相同，进而判别运动链是否同构。为便于后续识别及转化过程，需制定编码规则，使运动链转化为唯一的树状图编码结构。

2.2 树状图编码

2.2.1 树状图编码规则

制定编码规则实现运动链与树状图编码结构一一对应。以根节点为起始点开始编码，每一独立环路对应一条树枝，确定终止点并终止编码。具体编码规则如下。

(1)根节点选择规则

根节点即树状图的起始杆件。除对称结构外，根节点的选取决定树状图的结构。选取规则为含运动副数最多的杆件或连接情况较为复杂的多副杆。

(2)复合铰链编码规则

复合铰链由2个以上杆件通过转动副连接构成，需同其下一级杆件整体考虑。为简化编码过程，将复合铰链作为整体、下级杆件以树枝分枝形式编码。

(3)多副杆件编码规则

多副杆指包含2个以上运动副数的杆件，需整体考虑。n副杆转化为n-1个2副杆简化编码。

(4)终止点选择规则

终止点为树状图的终止杆件。选取规则为根节点相连的多副杆或逆时针方向最近多副杆，按照先外环后内环的顺序进行选择。

2.2.2 树状图编码过程

第1步，对一般化运动链进行编号操作。根节点编号为1；以根节点为起点，顺时针编号，先外环后内环，直至所有杆件编号完毕。

第2步，一般化运动链编码过程。选取根节点开始编码；对每一独立环路编码；选取终止点结束编码。

第3步，获得树状图编码结构。

2.2.3 树状图编码结果

一般化运动链编码后生成如图1所示2种形式树状图，图1(a)体现树状图整体结构及树叶信息，确保识别过程的可靠性，图1(b)体现杆件间邻接关系，确保解码运动链的唯一性。

图1 树状图编码形式

2.2.4 编码唯一性

机构运动链转化为邻接矩阵，由于邻接矩阵仅表示杆件之间的邻接关系，无需对杆件进行编号操作，因此会生成多个相似矩阵，使得同构识别中邻接矩阵构建不具唯一性。针对识别依据唯一性，将机构运动链编码为树状图编码结构，并依据编码原理，验证机构运动链编码后生成唯一树状图。

机构运动链编码原理为：对机构运动链中杆件进行编号，依据编码规则选取根节点及终止点，简化多副杆及复合铰链编码运算，并依据环路法进行编码。环路法编码如下：以树叶表示杆件，树枝表示运动副，当两杆件之间有运动副直接连接时，与这两杆件相对应的两树叶之间用一条树枝连接；机构运动链的一条环路是一个杆件和运动副的交替序列，且满足起点与终点为不同杆件并且它包含的所有顶点杆件都不同。

依据编码规则及环路法编码后可生成2种唯一的树状图编码结构且每根枝条之间相互独立，编码序号形式树状图与杆件序号形式树状图的树状结构相同，树叶信息不同。编码序号形式树状图中树叶信息为杆件所含运动副数，杆件序号形式树状图中树叶信息为杆件编号，由于杆件编号已定，故机构运动链编码后生成唯一树状图。

2.3 树状图同构识别计算

识别计算为改进交叉计算，具体步骤如下。

第1步，随机选取个体作为父代。

第2步，复制并保留父代所有信息生成复制子代。

第3步，随机选取父代与复制子代的同级树枝节点作为交叉点交叉操作。

第4步，交叉操作后生成交叉子代并保留所有信息。

同级交叉示意图如图2所示。

图2 树状图改进交叉计算示意图

2.4 树状图同构识别流程

树状图识别流程如下。

第1步，分析树状图。树枝数或树叶数不同，则异构；否，则进行下一步。

第2步，对比最长树枝的树叶数。不同，则异构；否，则进行下一步。

第3步，进行改进交叉计算。比较树状图，若树状图所有编码信息完全相同，则两图同构；否，则异构。

2.5 树状图同构识别方法证明

依据机构运动链同构识别原理，若运动链同构，则杆件及运动副的连接关系一一对应。为验证树状图同构识别的有效性，则需证明：树状图编码结构可表示杆件及运动链之间的连接关系并便于识别。

机构运动链编码生成树状图编码结构过程中，按照编码规则选取根节点与终止点，简化多副杆及复合铰链，依据环路法生成每根枝条，生成2种编码形式树状图。2种编码形式中编码序号形式树状图中树叶所含信息为杆件所含运动副数，杆件序号形式树状图中树叶信息为杆件编号信息。根据环路法编码特性即树状图的每根枝条均为独立环路，即每根枝条之间为独立关系。依据上述理论基础，若一根枝条上树叶之间的连接关系及编码信息完全相同，则对应环路的连接关系及拓扑特性也完全相同；若树状图上所有枝条上树叶之间的连接关系及编码信息完全相同，树状图所示的机构运动链中杆件及运动副连接关系及拓扑特性也相同，则两运动链同构。

2.6 树状图同构识别方法比较

现以一组n杆m副运动链为例，杆件包含运动副数最多为p，比较矩阵同构识别及树状图同构识别，如表1所示。

矩阵同构识别方法需构造多个n×n阶矩阵且不具唯一性。树状图同构识别方法具有以下优势：机构运动链转化编码后生成2种唯一编码形式树状图，分别表明运动副信息及杆件之间的连接关系；若两编码结构树状图中编码信息完全相同，则两运动链同构；可以灵活解决含复合铰链的复杂运动链同构识别问题；树状图同构识别可以直接识别机构运动链进化计算中产生的同构体，无需进行转化操作。

表1 矩阵同构识别与树状图同构识别对比

2.7 树状图同构识别方法结论

通过制定编码规则使得机构运动链编码获得唯一树状图编码结构，对树状图进行同构识别，可通过降低计算量的方法提高识别效率，也可直接应用树状图同构识别对机构运动链进化设计中综合计算生成的树状图解集进行同构识别，进而减少后续进化结果选择与转化的工作量，提高进化效率。

3 基于树状图同构识别技术的机构运动链进化设计智能原型系统

运用树状图同构识别方法优化机构运动链进化设计流程，对综合解集进行识别，尽可能减少同构体对设计结果的影响。优化进化设计流程如下：设计人员分析初始机构的设计要求与设计约束，制定相关设计参数；对初始机构进行一般化转化及编码，生成树状图编码结构；对树状图编码结构进行遗传操作，实现类型综合过程，通过复制、交叉、变异生成大量树状图解集，通过适应度评价函数筛选，保留可行解集；对可行解集中树状图进行两两识别，保留异构可行解，直至所有树状图被标记已识别，异构可行解组成进化解集；对进化解集中结果进行选择及转化，生成进化机构运动简图，改进流程图如图3所示。

依据改进进化设计流程，建立基于树状图同构识别方法的机构运动链进化设计人机混合智能原型系统(见图4)，即转化、综合、筛选及识别由计算机完成，其余由人工完成，为机构运动链进化设计提供一种工具化手段。

图3 基于树状图同构识别方法的机构运动链进化设计流程图

3.1 系统需解决的问题及实现目标

机构运动链进化设计智能系统需解决的问题是输入初始机构，利用人工智能、计算机图形处理能力和模拟生物进化算法相结合，通过反复迭代、评估、筛选，获得符合设计要求的新的机构运动简图；实现目标是为设计人员提供一种工具化的机构运动链进化设计实用手段。

图4 机构运动简图进化设计智能原型系统

原型系统的总体思路是基于设计流程，将系统拆分为功能相对独立的模块，利用Matlab平台进行搭建连接，确定模块之间的逻辑关系，输入初始机构和必要参数，输出新的机构运动简图。

3.2 系统架构

设计人员根据相关设计知识分析设计要求与约束，依据必备构件、构件之间连接关系及设计要求设定适应度因子及筛选条件；通过人机交互界面输入初始机构、适应度因子及进化参数等；初始机构经转化模块、综合模块、筛选模块、识别模块获得进化解集，通过进化结果选择及辅助绘图模块完成机构运动简图进化设计，获得进化机构运动简图。除综合与筛选模块外，其余模块之间为递进关系。综合与筛选模块之间存在反馈关系，通过多次反馈流程不断进化种群，获得可行解集。

3.3 知识库

知识库是机构运动链进化设计的陈述性知识和过程性知识的集合。

(1)模型库

一般化杆件与编码结构及信息一一对应，杆件对应树叶，运动副以树枝形式与树叶相连；2副杆序号为I，编码信息为2，依次递推。其属性如表2所示。

表2 各杆件属性表

(2)规则库

规则库包括转化规则和编码规则。转化规则包括从初始机构运动简图转化为一般化运动链的规则，以及一般化运动链到机构运动简图的逆向过程的规则。编码规则为一般化运动链编码为树状图的规则。

1)转化规则

一般化规则为所有运动副均转化为一般化(转动)副；与N个构件相邻接的杆、滑块及滚子转化为具有N个一般化副的一般化杆；与N个构件相邻接的凸轮及齿轮转化为具有N+1个一般化副的一般化杆。

具体化规则为一般化规则的逆过程，依据一般化后杆件信息进行具体化。

2)编码规则

依据2.2节中的编码规则对根节点、终止点、多副杆及复合铰链进行编码。

(3)数据库

为了方便对设计数据进行管理，构建数据库存储输入设计数据及相关参数。利用Matlab对其中数据进行访问，实现快速存储、检索和编辑。

3.4 设计模块

设计模块为原型系统的关键功能模块，包括转化模块、综合模块、筛选模块及识别模块。

(1)转化模块

转化模块利用Matlab将机构运动简图转化为树状图，实现以下过程：①构件编号；②一般化转化；③判断杆件间是否存在交叉关系。若无，则进行编码；否，则修正；④选取根节点；⑤调用知识库规则编码；⑥获得树状图编码结构。

(2)综合模块

综合模块是进化设计的关键。传统类型综合以设计经验或邻接矩阵作为依据。本文以遗传编程作为技术手段实现树状图进化计算，更直观地解决复合铰链等的复杂操作。利用Matlab中GPlab工具包中现有模块并调用必要参数实现综合算法：①生成初始种群。初始种群由所需解决问题的各种可能初始个体组成。本系统中，初始机构的树状图编码结构即为初始个体。②选择。防止发生个体过早收敛等问题并结合机构运动链进化的特点，本系统选取锦标赛选择法作为选择策略。③复制。从种群中随机选择适应度值较大的个体作为亲代个体，保留该个体所有信息并完整地复制到子代群体中，具体步骤如下：第1步，根据选择概率在群体中随机选取个体Xi；第2步，复制Xi得到Xi’；第3步，将个体Xi作为子代个体并保留。④交叉。从种群中随机选择适应度值较大的2个个体作为亲代，父代个体不同部分重组生成新的子代；⑤变异。随机选择种群中的个体作为亲代，随机结点处变异形成新个体，并完整复制到下一代群体；⑥终止准则及相关参数。选取预设最大进化代数作为终止准则，设定的相关参数包括种群规模N，交叉率α，变异率β，进化代数n；⑦获得可行解集。

(3)筛选模块

筛选模块包括综合模块中以适应度值为依据的筛选过程及依据筛选条件选择综合可行解中符合设计目标的优化解。信息公理表明，在满足独立性公理的所有设计中，信息含量最少的设计便为最优设计。因此，在满足设计要求的前提下，尽量减少构件总数及运动副总数，使得机构的信息总量最小；同时，多副杆杆包含的信息量要多于2副杆，连接关系复杂则包含信息量更大。根据信息公理的要求，本文希望获得一种可行的解决方案，其构件总数少，多副杆数少，连接关系简单。通过上述分析，权衡每个评估指标以确定目标函数，如式(1)所示：

(1)

式中，x1表示杆件总数，x2表示多副杆数(包括3副杆、4副杆等)，x2+1是为了防止存在x2值为0的情况，即无多副杆数，w1和w2分别为x1和x2的权重，a为调节系数，为确保权重的平衡性，通过多组数据计算确定参数取值。

(4)识别模块

识别模块是进化设计的重要环节，可行解集在同构识别筛选后，可排除同构体的影响。树状图同构识别方法，更直观地解决进化计算生成综合解集中的同构问题。同构识别算法如下：①生成初始种群。筛选后可行解集作为初始种群；②选择。随机选取初始种群中的个体作为对比亲代，标记该个体已识别；③复制。随机选取种群中个体作为父代，进行复制获得复制子代，保留全部信息；④同级交叉。父代与复制子代同级节点同级交叉，获得交叉子代；⑤判别。对比亲代与交叉子代进行比较，若个体信息全部相同，则排除对比亲代；否，则保留；⑥终止法则。种群中所有个体均完成标记；⑦获得排除同构体后的进化解集。

3.5 进化结果选择及转化

设计模块设计后获得进化解集，选择优化解，通过辅助绘图模块转化为机构运动简图。

(1)进化结果选择

进化解集中解的数目存在以下几种情况，针对不同情况进行结果选择。

① 进化解集为唯一解，即有且仅有1个解满足筛选约束条件，直接输出并转化为机构运动简图。

② 进化解集中存在多个解时，选择信息含量最小、连接关系最简单的树状图作为优化解输出并转化。

③ 进化解集无解即符合筛选条件的解为初始机构树状图解，调整筛选条件，获得新的进化解集并选择转化。

(2)进化结果转化

进化结果转化为通过辅助绘图模块解码及具体化，获得新的机构运动简图。

4 实例验证

液压缓冲机构主要用于火车的进站定位停车装置、港口船舶的停靠岸装置及码头卸货船内载货列车的停止装置等，具体功能为运动中物体能够在短时间短距离内顺滑而缓慢的停止。其机构运动简图如图5所示。分析机构组成，包含机架(1)、连杆(3、4、5)、减震装置(2)及滑动装置(6)；分析功能特性，保留弹簧、气缸及活塞。设定筛选条件：构件数小于等于7即杆件数小于等于8；包含3个3副杆或1个4副杆2个3副杆；保留必备构件及约束关系。

图5 液压缓冲机构运动简图

4.1 原型系统设计结果

输入机构运动简图，为减少进化计算的运算量，给定进化参数如下：种群规模N=100，交叉率α=0.5，变异率β=0.3，进化代数n=30。评价函数根据式(1)，确定参数取值为：a=1.5，w1=8，w2=1。

结合信息公理选择优化解，经过辅助绘图模块转化，输出进化机构运动简图，如图6所示。

图6 进化机构运动简图

4.2 初始机构与进化机构比较

为实现构件信息含量最小及结构优化，对初始机构进行进化设计。初始机构与进化机构比较如表3所示。

表3 初始机构与进化机构比较

4.3 中间结果验证

为了进一步验证原型系统的稳定性，本文对中间结果也进行了验证。输入图5所示机构运动简图，经转化模块获得树状图，如图7所示。

图7 树状图编码结构

依据进化设计参数进行综合操作，获得约630个综合可行解集解，并对综合可行解集进行筛选。保留编码信息小于等于8的解；保留包含3个3副杆或1个4副杆2个3副杆的解；保留包含必备构件及相关约束的解；获得筛选后可行解集。

排除筛选后可行解中同构体，获得排除同构体(包括初始机构同构体)后的进化解集，其中包含2个7杆解及14个8杆解，如图8所示。

进化解集为多解情况，从图8中选取信息含量最小、连接关系最简单的解作为优化解，如图9所示。

通过辅助绘图模块输出新的机构运动简图。由于杆件序号树状图与运动链之间具有一一对应关系，具体化后生成唯一机构运动简图，该结果与原型系统设计结果相同。

图8 排除同构体后的进化解集

图9 杆件序号形式优化解树状图

5 结 论

本文制定编码规则，确保树状图编码结构的唯一性，并提出一种新的树状图同构识别方法，确定识别依据、识别计算及识别流程，并验证了识别方法的可行性；应用树状图同构识别方法优化机构运动链进化设计流程，排除机构运动链进化设计过程中同构体的影响。基于优化进化设计流程划分功能模块，分析模块之间的独立性与关联性，应用Matlab平台搭建连接各个模块，建立智能原型系统；运用进化设计智能原型系统优化设计液压缓冲机构，获得信息含量最小的优化解并转化为机构运动简图，并进行中间结果验证。本研究为机构运动进化设计提供了一种工具化实用手段，但仍存在一些问题有待研究，如实现设计要求与约束的智能分析，根据实际需求设定个性化适应度因子及评价函数等。