Isomorphism Identification of Kinematic Chains Using Novel Evolutionary Approaches

Abstract

This paper presents a new method to isomorphism identification based on two novel evolutionary approaches—ant algorithm (AA) and artificial immune system (AIS). Salient features of the two evolutionary approaches are their efficient, robust and general-purpose algorithms for isomorphism identification despite its nondeterministic polynomial (NP) hard nature. First, based on the rearrangement of the vertexes in kinematic chains, the isomorphism identification of kinematic chains is transformed into a degree-reducible traveling salesman problem (TSP), so that the dimension and complexity can be largely decreased. Then AA and AIS algorithms are adopted to solve the transformed TSP. At last, characteristics of the two evolutionary approaches are discussed based on case studies.