一种基于遗传算法思想实现的图匹配算法

摘要：针对计算机图数据处理难题中的图数据检索匹配问题。相比传统的基于统计分布、模式识别等理论，该文在研究了遗传算法的智能优化过程的基础上，对照图匹配过程中的对应信息元素的查找难题进行求解。将遗传算法的思想理论与图匹配方法相结合，利用智能优化算法对解决基于内容的图匹配问题探索提供新的解决方法，从智能优化的角度来考虑和快速解决图匹配过程中的结构对应检索难点。通过验证参数和对象得出图匹配问题新解。

关键词：图检索；图匹配；遗传算法；图数据

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）01-0088-04

1 概述

信息技术地不断发展出现了越来越多的以图作为逻辑表达的数据，例如城市规划中的建筑模型、化学分子结构式，生物网络，社会网络图中的实体关系和图像检索等等。从图数据中发现有用的知识已成为图数据查询领域一项重要的研究课题。图查询是其中最重要的一个研究分支，因为与图有关的绝大部分应用（例如：图查询、图分类、图聚类等）都需要利用图来管理、查询和分析图数据。

对于在大量累积的图数据（即图数据库）上进行查询处理的问题，已有的对图数据库查询处理的研究工作主要包括两大类：一类是在小尺寸图的大规模集合（简称为集合类图数据库）上处理查询，其中包括子图查询处理、超图查询处理和相关子图查询处理等；一类是在一个或为数不多的大尺寸图（简称为大图类图数据库）上处理查询，如子图匹配查询处理、可达查询和最短路径/距离查询等。然而，这些方法全部针对确定图数据，无法应用到不确定图数据的查询处理中。对不确定图数据库中多种查询类型（如子图匹配查询）的高效处理是一项具有挑战性的工作.因此对图数据的查询处理方法的研究具有现实意义和理论价值，有待探索.

虽然遗传算法是非常优秀的智能优化算法，但是目前大多数应用都可以归纳为解决路径问题，比如TSP问题，而将其与计算机数据的图数据匹配的研究还很少[6]。

本文针对不同的拓扑结构图，对两个图是否相似的过程采用遗传算法进行讨论，对于种群进化的过程思路进行拓展研究，在算法复杂度上对比现有的深度优先搜索、宽度优先搜索等算法得出遗传算法应用于图匹配问题的新解。

2 问题的定义

用图表示多边形，即用图的节点表示多边形的顶点，用图的边表示多边形的边，则多边形的匹配问题就可以用如与图的匹配来解决。

图匹配过程通常完成若干遍图查询的操作，图匹配问题要求判断两个图是否相同或相似，并对两图的相似程度进行度量，返回图之间的相似度值。一般说来，图匹配可以认为是基于模板的匹配，可定义如下：对于给定的图，从模式集中找出一个最为相似的图作为给定图的相似图。图匹配方法要求对于平移、旋转、比例改变等几何变换具有不变性；两图的相似程度应该是可度量且易于计算的，根据匹配算法得出的判断应与人的直觉相吻合。在本文中所涉及的图都是无向标号图。