Evolutionary substructure discovery algorithm based on individuals with state backtracking
基于带状态回溯个体进化的子结构发现

In order to overcome the limit that the greedy search, which is often used by some prevalent graphical data mining systems, may often end up by providing sub-optimal solutions, an evolutionary algorithm was imported to perform data mining on databases represented as graphs. In order to handle the subgraph isomorphism problem, the concept of individuals with state backtracking was proposed, where the state information of some potential individuals produced during the evolution were preserved, which contributed to the design of genetic operators. A new diversity keeping scheme was also proposed to preserve the diversity both from the composition of population and the way of generation of individuals. In addition, removing the individuals not potential in current population reduced the search space greatly. Experimental results show that these measures enhance the searching capability of the algorithm and hence increase both the efficiency of the algorithm and the quality of solutions.