Memetic differential evolution methods for clustering problems

The Euclidean Minimum Sum-of-Squares Clustering ( MSSC ) is one of the most important models for the clustering problem. Due to its NP-hardness, the problem continues to receive much attention in the scientific literature and several heuristic procedures have been proposed. Recent research has been devoted to the improvement of the classical K-MEANS algorithm, either by suitably selecting its starting configuration or by using it as a local search method within a global optimization algorithm. This paper follows this last approach by proposing a new implementation of a Memetic Differential Evolution ( MDE ) algorithm specifically designed for the MSSC problem and based on the repeated execution of K-MEANS from selected configurations. In this paper we describe how to adapt MDE to the clustering problem and we show, through a vast set of numerical experiments, that the proposed method has very good quality, measured in terms of the minimization of the objective function, as well as a very good efficiency, measured in the number of calls to the local optimization routine, with respect to state of the art methods. (c) 2021 Elsevier Ltd. All rights reserved.

Automated summary

The Euclidean Minimum Sum-of-Squares Clustering (MSSC) is a key model for clustering and has attracted much attention due to its NP-hardness. Recent research has focused on improving the classical K-MEANS algorithm by selecting starting configurations or using it as a local search method in a global optimization algorithm. This paper proposes a new implementation of the Memetic Differential Evolution (MDE) algorithm specifically designed for the MSSC problem, showing good quality and efficiency in comparison to existing methods.