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.

I. Introduction

In recent years, numerous large scale global optimization (LSGO) problems arise in the field of science or engineering, usually with thousands or even more decision variables [1], [2]. There are four main challenges for solving LSGO problems [3]. The first challenge is as the dimension of variables increases, the search space becomes much more complex and the number of local optimal solutions grows exponentially. The second challenge is that the properties of the search space may change along with the scale of decision variables increases. Thirdly, the evaluation of large scale problems is often costly. Another challenge is the interaction between variables contributes to the difficulty of large scale optimization. In order to overcome these challenges, a great deal of approaches for solving LSGO problems have arisen.