一种基于混杂EA的子结构发现算法

Hybrid EA-based Substructure Discovery Algorithm

将混杂进化算法引入图数据挖掘,定义了基于图的染色体表示与加边变异和减边变异算子。针对子图同构问题,采用了SUBDUE提出的带实例的子结构的概念并提出了个体的潜力和带历史的个体两个概念,前者用以衡量一个个体生成新子结构的能力,后者用来保存进化过程中有潜力的个体,从而使减边变异成为可能,在一定程度上克服了子图同构问题。实验结果表明,以上措施增强了算法的寻优能力,提高了算法的效率和解的质量。

A hybrid evolutionary algorithms based system was developed to perform substructure discovery on databases represented as graphs, among which new representation of chromosomes and new operators of adding-an-edge mutation and deleting-edges mutation on graphical databases were defined. In order to handle the subgraph isomorphism problem, the technique of substructure with its instances as a whole was adopted which had been proposed by a famous graphical data mining algorithm SUBDUE, and proposed two new concepts, one is the individuals＇ potential which measure individuals＇ capabilities io produce new individuals, the other is the concept of individuals with history in which some potential individuals produced during the evolution are preserved, which enables the deleting-edges mutation and overcomes the subgraph isomorphism problem in some extent. Experimental results show that these measures successfully improve the searching capability of the algorithm and hence increase both the efficiency of the algorithm and the qualities of solutions.