机构同构图识别的映射-遗传复合算法研究

基于映射原理和遗传算法提出了一种判别图同构特征的复合算法，该算法通过研究两个图的映射关系并进行编码，结合遗传算法构建同构判别问题的模型。针对同构识别中码元不能重复的特征，提出了交叉算子和变异算子的重新设计对策；引入模拟退火算法确定了从当前解到新解转移的概率，从而避免陷入局部最优；基于数学实验提出了一些模型参数的选择原则以提高算法效率。算例表明，该复合算法可有效地应用于机构图的同构判别，为机构创新设计智能CAD研究提供了一种有效的同构识别方法。

Research on Mapping-Genetic Complex Algorithm for Isomorphism Identification of Mechanisms

A complex algorithm was presented by combination of the mapping property and the genetic algorithm for isomorphism identification of kinematic structures graphs of mechanisms. A validity encoding scheme was developed by considering the mapping relationship between two graphs, some reset measures for crossover and mutation operator were developed based on the characteristics which the encoding cell was not reiteration. In the meantime, the simulated annealing algorithm was introduced into the mixed algorithm to prevent premature convergence in resolution and some measures were developed for improving the efficiency based on parametrical selection. Example shows that the mixed algorithm is a validity algorithm for isomorphism identification of kinematic structural graphs of mechanisms. It will be a reliable isomorphism identification method for intelligent CAD.