Based On Hybrid Artificial Immune Optimization Algorithm For The Kinematic Chain Isomorphism Identification

The problem of mechanical chain isomorphism identification is very significant in creative design of mechanism,intelligent CAD systems and CIMS. But this problem had been proved to be a NP-hard problem for a long time. There is no popularly standard method to solve it.Many scholars have taken much efforts to search methods to figure it out but no method of them is wildly recognised by all researchers.In other words,this problem is still a hot spot in the mechanical science.In this paper,a good method is proposed wich is based on the graph theory.A mechanism graph consists of links and kinematic pairs.There are some vertices representing links and edges representing kinematic pairs.The topological graph composed by the vertices and the edges can uniquely represent a kinematic chain.According to the graph theory,a topological graph has an unique adjacency matrix.Thus a kinematic chain corresponds to a unique adjacency matrix.We know that if two topological graph are isomorphic,then an adjacency matrix of one of them can transform to the adjacency matrix of the other one through exchanging the rows and the columns which have the same lables.So if two kinematic chains are isomorphic,then the corresponding adjacency matrices of them can transform each other,else they not.Furthermore,a conclusion can be drawed that if two adjacency matrices can intert-ransform,then the corresponding chains are isomorphic,else not.This principle is the basic rule of this paper and the objective function is based on it.The solution space is vast and flexible.The scale of the solution space can expand exponentally with the increasement of the links.So getting a good method to search the optimum swiftly is very important and crucial.In this paper an artifical immune algorithm is introduced to optimize searching the optimum.The artificial immune algorithm has been as a hot research spot for some years. It can be applied to solve many tough problems in various fields such as computer security,industrial production,and so on.especially it can perform very good in pattern recognition.In this paper the follow of the artificial immune algorithm is demonstrated and some disadvantages of the simple application of aitificial immune algorithm in isomorphism identification are proved,and some improvements are proposed.There are two mixed algorithm in the paper.The first one combines the artificial immune algorithm with the simulated annealing algorithm.The other one combines the artificial immune algorithm with the genetic algorithm and the simulated annealing algorithm.In the first mixed algorithm,artificial immune algorithm is used to search globally and the simulated annealing algorithm performs the local search.This strategy is perfect to utilize the advantages of each algorithm and proved to speed the convergence.Then the theory of advantages of combination of the artifical immune algorithm and the genetic algorithm is presented.The advantages of genetic algorithm can offset the disadvantages of the artificial algorithm when mixing them.The genetic operators can improve the diversity of population and speed the convergence.It can make it possible to avoid the local optimum.There are three pairs of isomophic mechanical chains,separately 10-links, 12-links,and 14-links.The above three algorihms are applied respectively to test the isomophism of the three pairs.Each pair are tested 1000 times.Then the statistics show the maximum iteration,the average iteration,the maximum computation time and the average computation time.The simulation results show that the algorithm combined the altificial immune algorithm with the simulated annealing algorithm and the genetic algorithm is the best one,and the simple artificial immune algorithm perform worstly.The reason for this results are demonstrated theoretically in the paper.The hybrid artificial immune algorithms isomorphism identification are analysed,tested and estimated in this paper.And they are considered as a new method to solve the problem of kinematic chain isomorphism identification and can be applied directly in the intelligent CAD systems.