An investigation of clustering strategies in many-objective optimization: the I-Multi algorithm as a case study

Abstract

A variety of general strategies have been applied to enhance the performance of multi-objective optimization algorithms for many-objective optimization problems (those with more than three objectives). One of these strategies is to split the solutions to cover different regions of the search space (clusters) and apply an optimizer to each region with the aim of producing more diverse solutions and achieving a better distributed approximation of the Pareto front. However, the effectiveness of clustering in this context depends on a number of issues, including the characteristics of the objective functions. In this paper we show how the choice of the clustering strategy can greatly influence the behavior of an optimizer. We investigate the relation between the characteristics of a multi-objective optimization problem and the efficiency of the use of a clustering combination (clustering space, metric) in the resolution of this problem. Using as a case study the Iterated Multi-swarm (I-Multi) algorithm, a recently introduced multi-objective particle swarm optimization algorithm, we scrutinize the impact that clustering in different spaces (of variables, objectives and a combination of both) can have on the approximations of the Pareto front. Furthermore, employing two difficult multi-objective benchmarks of problems with up to 20 objectives, we evaluate the effect of using different metrics for determining the similarity between the solutions during the clustering process. Our results confirm the important effect of the clustering strategy on the behavior of multi-objective optimizers. Moreover, we present evidence that some problem characteristics can be used to select the most effective clustering strategy, significantly improving the quality of the Pareto front approximations produced by I-Multi.