A hybrid incremental genetic algorithm for subgraph isomorphism problem
Hyukgeun Choi, Jin-Hyun Kim, Byung-Ro Moon · 2014
Finding an isomorphic subgraph is a key problem in many real world applications modeled on graph. In this paper, we propose a new hybrid genetic algorithm(GA) for subgraph isomorphism problem which uses an incremental approach. We solve the problem with increasing the size of the subproblem step by step. The graph for which we search is gradually expanded from the empty structure to the entire one. We apply a hybrid GA to each subproblem, initialized with the evolved population of previous step. We present design issues for the incremental approach, and the effects of each design decision are analyzed by experiment. The proposed algorithm is tested on widely used dataset. With apposite vertex reordering along with moderate population diversity, incremental approach brought a significant performance improvement. Experimental results showed that our algorithm outperformed representative previous works.