An efficient genetic algorithm for subgraph isomorphism
Jaeun Choi, Yourim Yoon, Byung-Ro Moon · 2012
In this paper we propose a multi-objective genetic algorithm for the subgraph isomorphism problem. Usually, the number of different edges between two graphs has been used as a fitness function. This approach has limitations in that it only considers directly-visible characteristics of current solutions, not considering the potential for being an optimal solution. We designed a fitness function in which solutions with higher potential can be rated high. This new fitness function has good properties such as transforming the solution space globally convex and improving the performance of local heuristics and genetic algorithms. Experimental results show that the suggested approach brings a considerable improvement in performance and efficiency.