Multi-line distance minimization: a visualized many-objective test problem suite

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Brunel University
  • De Montfort University

Abstract

Studying the search behavior of evolutionary manyobjective optimization is an important, but challenging issue. Existing studies rely mainly on the use of performance indicators which, however, not only encounter increasing difficulties with the number of objectives, but also fail to provide the visual information of the evolutionary search. In this paper, we propose a class of scalable test problems, called multi-line distance minimization problem (ML-DMP), which are used to visually examine the behavior of many-objective search. Two key characteristics of the ML-DMP problem are: 1) its Pareto optimal solutions lie in a regular polygon in the two-dimensional decision space, and 2) these solutions are similar (in the sense of Euclidean geometry) to their images in the high-dimensional objective space. This allows a straightforward understanding of the distribution of the objective vector set (e.g., its uniformity and coverage over the Pareto front) via observing the solution set in the two-dimensional decision space. Fifteen well-established algorithms have been investigated on three types of 10 ML-DMP problem instances. Weakness has been revealed across classic multi-objective algorithms (such as Pareto-based, decompositionbased and indicator-based algorithms) and even state-of-the-art algorithms designed especially for many-objective optimization. This, together with some interesting observations from the experimental studies, suggests that the proposed ML-DMP may also be used as a benchmark function to challenge the search ability of optimization algorithms.

Details

Original languageEnglish
Pages (from-to)61-78
Number of pages18
JournalIEEE Transactions on Evolutionary Computation
Volume22
Issue number1
Early online date18 Jan 2017
Publication statusPublished - Feb 2018

Keywords

  • Algorithm design and analysis, Sociology, Pareto optimization, Search problems, Minimization, Visualization