Differential Grouping with Spectral Clustering for Large Scale Global Optimization

Cooperative co-evolution (CC) is an effective strategy for large scale global optimization (LSGO) problems, which divides the problem into several smaller sub-problems based on the idea of divide-and-conquer. The grouping of decision variables has an important impact on the optimization results. Differential grouping (DG) and its improved versions detect the interaction relationship between variables according to the differential values, achieving competitive grouping results on the CEC'2010 benchmark functions which have uniform subcomponent sizes. However, these algorithms still have difficulty to obtain good decomposition for the more complex functions, especially for overlapping functions. Due to some degree of overlap between subcomponents, there will be no unique optimal decomposition of the decision variables. We draw lessons from the idea of clustering that objects in the same cluster are similar to each other and objects in different clusters are quite different. In this paper, we propose a differential grouping with spectral clustering (DGSC) algorithm. All the variables are treated as edge-connected points in space to construct an undirected weighted graph. The design structure matrix derived from the differential values is used as the similarity matrix of spectral clustering such that the weight of edges is expressed by the interaction relationship between these variables. This graph is divided into several subcomponents by clustering to decompose decision variables, making the degree of interaction between subcomponents as weak as possible and within the subcomponent as strong as possible. The experimental results show that DGSC has promising performance on the latest LSGO benchmark functions.