导　　师： 杨平

学科专业： 080202

授予学位： 硕士

作　　者： ;

机构地区： 江苏大学

摘　　要： 机构运动链同构识别问题在机构创新设计、智能CAD系统中有着广泛的应用价值,但却又是困扰人类已久的难题,该问题已经被证明是NP难问题,至今没有最有效的解决方案,因此寻找更好的同构识别方法,成为国内外学者研究的热点。 本文所论述的方法,将机构运动链中的构件用节点代表,运动副用边代表,这样就可以将运动链唯一地转化为机构拓扑图,根据图论原理,拓扑图和它的邻接矩阵是一一对应的,这样一个运动链就可以由一个邻接矩阵唯一表示。在图论中,如果两个拓扑图同构,则它们对应的邻接矩阵可以相互转换,即一个矩阵经过诺干次同时交换相同的行和列以后,可以转换为另一个矩阵。因此,如果两个运动链同构,与它们对应的邻接矩阵就能相互转换,否则不能相互转化;图论知识已经证明它们互为充分必要条件,因此,如果两个图的邻接矩阵可以相互转换,则两图同构。本文根据这一原理,构造目标函数,判定运动链同构。 本文所构造目标函数的解空间庞大,而且随着运动链的构件数量的增多,解空间规模成级数增长,因此如何迅速地找到最优解成了解决问题的关键所在。本文采用混合人工免疫算法来优化寻找最优解过程。 人工免疫算法是近年来备受关注的智能优化算法,已被成功的应用在很多领域中,本文分析人工免疫算法流程,指出克隆免疫算法直接应用于同构识别问题的不足,并且改进了算法,取得很好的效果。 本文构造了人工免疫-模拟退火混合算法、免疫-遗传-模拟退火混合算法两种混合优化算法。在人工免疫-模拟退火混合算法中,根据人工免疫算法和模拟退火算法各自的特点和优势,对两算法进行了不同的分工,其中全局搜索采用克隆免疫算法,局部搜索采用模拟退火算法,充分结合两种算法的优点,使全局搜索和局部搜索高效结合,加快收敛速度。而后,本文在理论上分析了遗传算法和人工免疫算法结合的可行性、互补性和优越性,并提出遗传算子的优点可以充分克服人工免疫算法的不足的论断,在免疫-遗传-模拟退火混合算法中,用遗传算子作为一种辅助手段,增加了全局搜索的个体多样性,大大减少了陷入局部最优的可能性,从而加快了全局收敛速度。 本文分别用10杆运动链、12杆运动链、14杆运动链三组机构对上述三种算法的同构识别性能进行仿真测试,每一组测试分别独立计算1000次,统计最大循环次数、平均循环次数、最大计算时间、平均计算时间。统计的仿真结果表明,免疫-遗传-模拟退火混合算法的性能最优,计算时间最短,循环次数最少,单纯的人工免疫算法性能指标最差。本文就这一结果,做了理论分析,给出了一般性论证。 本文对混合人工免疫算法在机构运动链同构识别上的应用做出了理论分析、验证和评价,为机构运动链同构识别提供了新的手段,且所述混合人工免疫算法可直接应用于智能CAD系统。 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.

关 键 词： 机构运动链 同构识别 邻接矩阵 优化 人工免疫算法 遗传算法 模拟退火算法

分 类 号： [TH112]

领　　域： [机械工程]