Efficient large scale global optimization through clustering-based population methods

• Published in: Computers & operations research 2021-03, Vol.127, p.105165, Article 105165
• Main Authors: Schoen, Fabio, Tigli, Luca
• Format: Article
• Language: English
• Subjects: Algorithms; Clustering; Clustering methods; Differential evolution; Evolutionary computation; Global optimization; Local optimization; Memetic algorithms; Multi-level single-linkage; Operations research; Optimization; Random projections
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2020.105165

•A population-based memetic algorithm as a generator of candidate points for starting local searches.•A criterion, based on the Multi-Level Single-Linkage clustering method, to decide whether to start or not a local search from a candidate point.•A dimensionality reduction tool, based on random projections, which is employed in the decision on whether to start a local search.•An implementation of a clustering criterion based on a sample, whose cardinality grows less than linearly, made of the current population members, past discovered local optima and the point from which those optima were found. Back in the 80’s clustering methods were considered state of the art for non-structured box constrained global optimization (GO). Their disappearance is mainly due to their increasing difficulties in solving even moderately sized GO problems, yet the basic idea was indeed a brilliant one. More recently population methods and Differential Evolution (DE) in particular has gained much attention in the GO heuristic world due to their easy implementation and good exploration capabilities. In order to improve the exploitation capability of DE, some memetic variants have been proposed with success. In this paper we revisit clustering methods and apply them both to standard low dimensional problems and to large scale ones; in particular we propose a novel approach to apply a clustering-type decision on when to start a local search to variants of memetic DE. The resulting algorithm, C-MDE (Clustering Memetic DE) outperforms the best-known methods both in quality of the returned solution and in the number of calls to the expensive local optimization phase, even in large dimension. For large dimensional problems, random projections are used in order to be able to decide on starting a local search on a limited number of features. The resulting GO method is a revisit of clustering techniques in which all of the defects which made those methods no more feasible are eliminated: in particular, the method is used within an adaptive population method and it efficiently runs also in large dimension. Thus we think the proposed approach will find a place in the top-performing modern GO algorithms.