An Instance Space Analysis of Constrained Multi-Objective Optimization Problems

Abstract

Multi-objective optimization problems with constraints (CMOPs) are generally considered more challenging than those without constraints. This in part can be attributed to the creation of infeasible regions generated by the constraint functions, and/or the interaction between constraints and objectives. In this paper, we explore the relationship between constrained multi-objective evolutionary algorithms (CMOEAs) performance and CMOP instances characteristics using Instance Space Analysis (ISA). To do this, we extend recent work focused on the use of Landscape Analysis features to characterise CMOP. Specifically, we scrutinise the multi-objective landscape and introduce new features to describe the multi-objective-violation landscape, formed by the interaction between constraint violation and multi-objective fitness. Detailed evaluation of problem-algorithm footprints spanning six CMOP benchmark suites and fifteen CMOEAs, illustrates that ISA can effectively capture the strength and weakness of the CMOEAs. We conclude that two key characteristics, the isolation of non-dominate set and the correlation between constraints and objectives evolvability, have the greatest impact on algorithm performance. However, the current benchmarks problems do not provide enough diversity to fully reveal the efficacy of CMOEAs evaluated.

References in corpus (5)

• Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem
• Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit
• Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning
• Characterization of Constrained Continuous Multiobjective Optimization Problems: A Feature Space Perspective
• Analyzing the Effect of Objective Correlation on the Efficient Set of MNK-Landscapes