Hybrid EA-based Substructure Discovery Algorithm
Minqiang Li · Jisuanji fangzhen · 2008
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 to 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.