基于双链遗传算法的复杂特征识别方法研究  

On Recognition of Complicated Features Using Double-link Genetic Algorithm

作　　者：刘金山[1] 廖文和[1] 刘长毅[1] 郭宇[1] 

机构地区：[1]南京航空航天大学机电学院,南京210016

出　　处：《机械科学与技术》2008年第4期437-441,共5页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家863项目(2002AA411030)资助

摘　　要：子图匹配问题是典型的非多项式算法问题,但又是基于图的特征识别方法的基础,导致目前提出的基于图的特征识别方法很难实现交叉特征识别、包含凸边的特征识别等问题。针对特征识别的需求,提出了一种双链遗传算法。该算法采用双链结构描述特征识别问题的染色体,一条链描述面信息,另一条描述特征对于面的分割。同时根据双链的特点,定义了双链染色体的交叉、变异、选择、半表留复制等运算。实验证明双链遗传算法具有解决特征识别的可行性,且结果较其他特征识别方法识别特征范围更广和可以合并被分割的特征、识别包含凸边的特征等优点。Subgraph match is a classic NP hard problem and the basis for graph-based feature recognition. Therefore, it is difficult for graph-based feature recognition method to recognize the feature intersection and the features with convex edge. To solve this problem, a new genetic algorithm is presented that uses double links to represent the structure of feature chromosome. One link is used to describe the information of faces , and the other is used to describe the division of faces in features. The operation of crossover, mutation, selection and reserve copy is defined to fit the characteristic of double link genetic algorithm. The double-link genetic algorithm is applied to feature recognition and is proved to be feasible, and it can recognize more features than the classic feature recognition method and can combine the broken features.

关 键 词：遗传算法 特征识别 子图匹配 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]