A Coevolutionary Approach to Substructure Discovery Based on Individual Cooperation

A cooperative coevolutionary EA based algorithm is developed to discover potentially useful substructures from graphical databases. Unlike the usual coevolutionary algorithms which are based on the divide-and-conquer strategy with different populations representing different subtasks, the cooperation in our algorithm is at individual-level and implemented by a new genetic operator, the individual cooperation operator. The operator, during the searching process, enables different individuals to search the same substructure in a cooperative way and hence handles the problem of losing instances, which is very common and vital to the algorithm performance. In addition, an approximate graph matching algorithm is also proposed to make the operator more efficient. Experimental results show that the new operator successfully enhances the searching capability of the algorithm and improves the qualities of solutions.