基于遗传算法的机构运动链同构识别

提出了一种基于遗传算法的机构运动链同构识别方法。研究了遗传算法求解同构识别问题的模型,包括适合度函数,有序编码,有序交叉算子。进行了实例研究及计算机仿真,显示该方法是成功的。     

多自由度AT行星齿轮机构结构综合和同构判别

由于4～5自由度的AT行星齿轮机构方案数量规模过于庞大，造成优选时间过长。为了能胜任大规模AT结构方案的综合，提出基于字符串编码的构件综合和同构判别方法。根据行星齿轮机构各构件的类型特征定义构件的字符，再将AT结构转化为字符串；通过分析行星排字符串中制动构件和互连构件的特征，并利用组合原理设计合理的字符串综合算法，分别实现了对行星齿轮机构和AT结构的同构判别。在对AT结构进行综合的过程中，分别剔除不满足构件约束条件的行星齿轮机构字符串和AT结构字符串。通过5个算例验证了该方法的正确性和高效性。     

机构运动链邻接矩阵的素数表示与同构判别

提出用素数标识机构运动链中的构件,根据运动链的邻接关系建立一个用素数表示的基本邻接矩阵.利用该基本邻接矩阵及反映次级邻接关系的素数乘积生成同构判别矩阵,给出利用判别矩阵的行列式和线性方程组的解矢量判别机构的同构或异构的方法.进一步根据解矢量元素分类情况用新的素数对判别矩阵进行动态修改,最后可以得到元素各不相同的解矢量,机构运动链拓扑图的全部节点的相对位置由该解矢量唯一定位,从而找到两个同构机构的构件标号映射关系,给出两个机构运动链同构的充分必要条件.判别方法创新之处在于利用素数动态赋予相应的构件,以虚拟破坏图结构的对称性并虚拟改变图节点的局部邻接、次级邻接关系,而图的实际结构并不改变.该方法也适用于一般无向图的同构判别.判别实例表明该方法非常有效,计算时间复杂度为多项式且可建立同构的标号映射关系,具有很高的可靠性,并且容易实现自动判别.     

基于POX交叉的遗传算法求解Job-Shop调度问题

通过改进传统的遗传算法求解Job—Shop调度问题。为基于工序的编码提出了一种新的POX交叉算子，并与其他交叉算子进行了比较以显示其高效性。为了保留父代的优良特征和减少遗传算子的破坏性，设计了一种子代交替模式的交叉方式。将提出的改进遗传算法应用于muth and thompson‘s基准问题的实验运行，显示该算法的有效性。     

运动链同构判别的最少步数序列法研究

提出用素数刻画机构构件间的运动副,并得到运动链的素数权值矩阵。在此基础上用改进的Floyd算法得到任意两个顶点间走最少步数的最小权值连乘积矩阵,并按一定规则排序。由此映射关系反映了唯一的机构运动链的相互关系,给出两个机构运动链同构的充分必要条件,建立了运动链同构判别的新方法。该方法也适用于一般的无向图的同构判别。最后通过判别实例表明该方法准确、简单且易于在计算机实现,同构判别的解决为机构综合与分析奠定了基础。     

基于混合遗传算法的柔性制造系统优化设计

针对基于闭排队网络模型的柔性制造系统优化设计问题，提出了一种混合遗传算法，利用该模型中生产量函数和成本函数的单调性，设计了最大产量－成本梯度算子，来引导新一代种群从不可行域进入可行域，既实现了利用遗传算法求解柔性制造系统约束优化问题，又增强了遗传算法的局部搜索能力。由于该算法利用渐近边界分析思想和编码技术减少了计算量，从而使混合遗传算法既保持了遗传算法的全局寻优特点，又提高了运行效率。算例证明，该算法的求解质量优于目前该领域常用的隐枚举算法。     

含复合铰机构运动链的拓扑图表示与同构判别

提出一种适用于含任意复合铰个数的机构运动链拓扑图表示新方法,该方法在对含复合铰运动链转化为拓扑图时,在拓扑图顶点上标以顶点号和顶点对应的构件运动副数,与复合铰相连接的所有构件被看作是相互邻接的构件,该拓扑图完整表示了含复合铰机构运动链的信息,且不增加拓扑图顶点数规模。在拓扑图表示基础上,将邻接矩阵动态修改法应用到含复合铰运动链的同构判别,判别实例表明邻接矩阵动态修改法能有效对含复合铰机构运动链进行同构判别。     

机器人运动链拓扑胚图的特征字符串描述

在机构基于胚图的综合方法中,判别拓扑胚图的同构关系是一个难题。提出特征字符串的概念,用于描述含较多基本连杆的拓扑胚图。基于运动链拓扑胚图支链上不含二度点的特性,制定相关规则,用特征字符串准确描述代表基本连杆的顶点的相对位置,引出拓扑胚图。制定判别同构拓扑胚图的相关准则,论证了拓扑胚图同构的条件。举实例对同一特征字符串和不同特征字符串描述的拓扑胚图进行了同构判断。通过与邻接矩阵方法比较,证明特征字符串法简单、有效。     

混合离散变量优化设计的复合遗传算法

目前，对混合离散变量的遗传算法研究较少，而且现有算法对设计变量的处理不能很好地满足工程设计要求。为此，提出了一种面向设计、制造的设计变量工程化处理方法，能合理地处理优化设计中混合离散变量的取值问题。引入了混沌移民算子对基本遗传算法进行了改进，并开发了混合离散变量优化的复合遗传算法程序LSGA。工程设计实例表明，该算法对优化设计问题的特性无特殊要求，具有较好的普适性，而且程序运行可靠，全局收敛能力强。     

平面多杆机构杆组自动生成方法

阿苏尔杆组理论指出,通过对不同运动链选取不同的机架和原动件,能够得到各种可能的阿苏尔杆组与机构构型。基于这一理论提出一种阿苏尔杆组的自动生成方法。针对杆组的结构特点,提出简单易行的杆组同构判别方法,该判别方法也适用于平面多杆机构运动链的同构判别。联合应用运动链的邻接矩阵与关联矩阵,使得自动生成算法与计算机编程相结合,实现了平面多杆机构杆组的自动生成。该自动生成机构杆组的方法理论简单,编程可操作性强,能够实现多杆运动链在构成机构时杆组的准确快速的拆分。该方法将杆组的拆分过程与由杆组搭接形成机构的过程相联系,对拆分得到的所有杆组与机构构型进行同构判别,得到了六杆以内的13种杆组,以及由八杆运动链构成的153种机构。     

A mixed isomorphism approach for kinematic structure enumeration graphs based on intelligent design and manufacturing

When using graph theory for kinematic structure enumeration, the isomorphism identification of graphs is an important and complicated problem. The problem is known to be an NP-complete problem. This paper presents a mixed algorithm based on a mapping property, a genetic algorithm, and a simulated annealing algorithm for the isomorphism identification problem. A validity encoding scheme was developed by considering the mapping relationship between two graphs, and some reset measures for the crossover and mutation operators were developed based on the characteristics in which the encoding cell could not be reiterated. A simulated annealing algorithm was introduced into the mixed algorithm to prevent premature convergence in resolution, and some other measures were developed for improving the efficiency, based on the parameter selection. An example shows that the mixed algorithm is a valid algorithm for the isomorphism identification of kinematic structure graphs in mechanism design. It will be a reliable isomorphism identification algorithm for intelligent computer-aided design (CAD) and manufacturing (CAM).     

Hierarchical clustering approach for determination of isomorphism among planar kinematic chains and their derived mechanisms

The problem of isomorphism among kinematic chains and their derived mechanism has been a hot area of research from last several years. The researchers so far have proposed many methods which are mainly based on characteristic polynomial and some code based methods to test the isomorphism among kinematic chains. In this present communication a hierarchical clustering based computerized method is proposed for the above said problem and it is tested for planar kinematic chains upto twelve links without any counter examples. In this method a hierarchical clustering algorithm is also developed for the identification of distinct mechanism derived from kinematic chains. In this method kinematic chains are represented in the form of weighted squared shortest path distance matrix and this matrix is further transformed in the form of tree or dendrogram with the help of hierarchical clustering algorithm. This algorithm directly gives the number of distinct mechanism derived from a given kinematic chain. The cophenetic correlation coefficient of dendrogram is used as an index for isomorphism identification among kinematic chains. The proposed method is efficient and accurate and only one matrix for a given kinematic chain is developed for the determination of distinct mechanisms. This method is successfully examined for one degree of freedom, 6, 8, 10, 12 links planar kinematic chains, 9 links two degree of freedom and 10 links three degree of freedom planar kinematic chains. The computer algorithm for the proposed method has been proposed which can easily be converted into a computer program. These results are useful for designers to detect isomorphism in mechanisms derived from kinematic chains and duplication among kinematic chains.     

运动链拓扑胚图的同构判断

平面并联机构基于胚图的综合方法中,拓扑胚图的同构判断是关键的环节。针对不含二元杆的运动链拓扑胚图,解决它们之间的同构判断问题。运动链的拓扑胚图与拓扑图相比有着独特的个性,由于在支链上没有二元点,所以图的顶点之间的关系主要是顶点之间的相对位置。根据拓扑胚图的特性,从关于图的邻接矩阵的经典理论出发,建立图的任意顶点之间的路径数矩阵,将路径数矩阵的元素按照一定规则排列成路径数组。论证了拓扑胚图同构的条件。在度序列和一阶路径数组相等的前提下,利用二阶路径数组来判断拓扑胚图是否同构。举实例说明判断过程及具体应用。拓扑胚图同构判断问题的解决不仅为基于胚图的型综合奠定了基础,而且对于某些运动链拓扑图的同构判断也具有普遍意义。     

利用邻接矩阵的幂序列进行运动链和机构的同构判定

从同构的图论意义出发,提出了一个新的运动链结构不变量,进而提出了利用邻接矩阵的幂序列进行运动链同构判定的方法。它与现有的其他方法相比,具有直观、简便和显明图论依据的特点,且该方法不仅可以实现运动链的同构判定,而且可以成功地判定一般图的同构。在此基础上,本文最后给出了从同一运动链中识别出不同机构的两个方法。     

平面运动链同构识别方法的研究

同构识别在机构类型综合中占有重要位置。本文在对含高副平面运动链分析的基础上，提出了含高副平面运动链支路码的概念，并提出了一种用计算机对含高副和不含高副的平面运动链均适用的同构识别方法。该方法不受运动链杆数和自由度数的限制，且速度快、计算量少。经大量实例计算，该方法行之有效     

Synthesis of a complete set of contracted graphs for planar non-fractionated simple-jointed kinematic chains with all possible DOFs

The contracted graph shows the primary topological structure of kinematic chains and is the foundation for constructing kinematic structures of mechanisms. In this paper, a fully-automatic method is proposed to synthesize a complete set of contracted graphs for planar non-fractionated simple-jointed kinematic chains with all possible degrees of freedom. First, based on the 4-parameter index and link assortment array, the relationships of link assortment arrays and non-fractionated contracted graphs for different types of kinematic chains are revealed. Then, the general steps to generate the adjacency matrices of contracted graphs from the synthesis equation set are given. Efficient methods to detect fractionated structures and isomorphism are also addressed. Finally, a human-machine interactive synthesis program is developed, and the complete list of both contracted graphs and valid contracted graphs for planar non-fractionated simple-jointed kinematic chains with up to 19 links and all possible degrees of freedom is presented for the first time.     

基于转化邻接矩阵的含复铰运动链描述与同构识别

针对机构分析与综合中复合铰链难以处理和含复铰运动链同构识别困难的问题,分析复合铰链的内部结构,提出引入Pin构件将复合铰链转化为多个并联单铰链的新方法,从而将含复铰运动链转化为只含单铰的简单运动链。定义运动链转换邻接矩阵,用于描述含复铰运动链,通过分析发现该矩阵的内涵性质丰富,方便运动链的分析。提出运用转换邻接矩阵的阶数、对角线元素矢量、矩阵特征值和特征矢量等参数识别判断含复铰运动链同构关系的方法,这些特征参数是含复铰运动链的不变量。实例证明,利用转化邻接矩阵可简单、方便、直观地描述含复铰运动链,其特征值和特征矢量用于识别含复铰运动链的同构关系,具有准确、高效和简便的特点。定义的转化邻接矩阵及其运用方法为复合铰链的处理以及含复铰运动链的识别提供了新的途径。     

平面运动链同构识别的距离和序列法

对平面机构运动链结构组成进行探讨后,研究了运动链中的结构不变量,并基于缩杆邻接矩阵提出了4个新的运动链结构恒量序列,这些恒量序列将杆的级别、运动副数目以及各杆的连接关系考虑在内。以此为基础,提出了对运动链进行同构识别的距离和序列法。该方法实质上是对运动链进行分类同构识别,因此具有操作简单、可靠性好、识别效率高等特点,已成功应用于12杆以下机构运动链型综合时的同构识别     

In quest of a reliable and efficient computational test for detection of isomorphism in kinematic chains

The test based on comparison of the characteristic coefficients of the adjancency matrices of the corresponding graphs for detection of isomorphism in kinematic chains has been shown to fail in the case of two pairs of ten-link, simple-jointed chains, one pair corresponding to single-freedom chains and the other pair corresponding to three-freedom chains. An assessment of the merits and demerits of available methods for detection of isomorphism in graphs and kinematic chains is presented, keeping in view the suitability of the methods for use in computerized structural synthesis of kinematic chains. A new test based on the characteristic coefficients of the “degree” matrix of the corresponding graph is proposed for detection of isomorphism in kinematic chains. The new test is found to be successful in the case of a number of examples of graphs where the test based on characteristic coefficients of adjancency matrix fails. It has also been found to be successful in distinguishing the structures of all known simple-jointed kinematic chains in the categories of (a) single-freedom chains with up to 10 links, (b) two-freedom chains with up to 9 links and (c) three-freedom chains with up to 10 links.