Source-linked AI summary
Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit
Zhun Fan, Wenji Li, Xinye Cai, Hui Li, Caimin Wei, Qingfu Zhang, Kalyanmoy Deb, Erik D. Goodman
TL;DR
Constrained multi-objective optimization lacks benchmarks that flexibly represent different constraint difficulties and objective counts. This paper classifies constraint difficulty, develops a parameterized scalable construction toolkit, and evaluates the resulting benchmarks, finding algorithm preferences that depend on difficulty type while none solve all suggested problems efficiently.
Problem
Existing constrained multi-objective benchmarks provide limited coverage, with difficulty levels not adjustable and objective counts not scalable.
Method
The paper develops a toolkit using parameterized constraint functions for feasibility-hardness, convergence-hardness, and diversity-hardness, generating scalable CMOPs and CMaOPs.
Results
MOEA/D-CDP favored convergence-hard DAS-CMOPs, NSGA-II-CDP favored simultaneous difficulty, C-NSGA-III favored feasibility-hard CMaOPs, and C-MOEA/DD favored convergence-hard CMaOPs.
Takeaways & Limitations
The benchmarks expose difficulty-specific differences among CMOEAs and CMaOEAs, while none of the evaluated methods solve the suggested problems efficiently.
Takeaways & Limitations
The prior CTP and CF test suites do not provide adjustable difficulty levels for each difficulty type.
Abstract
from arXiv · showhide
Multi-objective evolutionary algorithms (MOEAs) have progressed significantly in recent decades, but most of them are designed to solve unconstrained multi-objective optimization problems. In fact, many real-world multi-objective problems contain a number of constraints. To promote research on constrained multi-objective optimization, we first propose a problem classification scheme with three primary types of difficulty, which reflect various types of challenges presented by real-world optimization problems, in order to characterize the constraint functions in constrained multi-objective optimization problems (CMOPs). These are feasibility-hardness, convergence-hardness and diversity-hardness. We then develop a general toolkit to construct difficulty-adjustable and scalable CMOPs (DAS-CMOPs, or DAS-CMaOPs when the number of objectives is greater than three) with three types of parameterized constraint functions developed to capture the three proposed types of difficulty. Based on this toolkit, we suggest nine difficulty-adjustable and scalable CMOPs and nine CMaOPs. The experimental results reveal that mechanisms in MOEA/D-CDP may be more effective in solving convergence-hard DAS-CMOPs, while mechanisms of NSGA-II-CDP may be more effective in solving DAS-CMOPs with simultaneous diversity-, feasibility- and convergence-hardness. Mechanisms in C-NSGA-III may be more effective in solving feasibility-hard CMaOPs, while mechanisms of C-MOEA/DD may be more effective in solving CMaOPs with convergence-hardness. In addition, none of them can solve these problems efficiently, which stimulates us to continue to develop new CMOEAs and CMaOEAs to solve the suggested DAS-CMOPs and DAS-CMaOPs.
1 Introduction
Constrained multi-objective problems are harder than unconstrained ones, yet existing benchmarks provide limited, non-adjustable coverage of constraint difficulty and objective scalability. The paper addresses these gaps with three difficulty types and a toolkit for constructing adjustable, scalable CMOPs and CMaOPs.
- Motivation: CMOPs optimize multiple conflicting objectives under constraints, requiring algorithms to balance feasibility search with convergence and diversity.Constraint-handling mechanisms address feasibility, while selection methods balance convergence against diversity.
- Limitations of Existing Benchmarks: Existing CMOP test suites are relatively few, and CTP and CF have limitations in adjustable difficulty, feasible-region coverage, and objective scalability.CTP and CF do not provide adjustable difficulty levels for each type, low feasible-region ratios across the search space, or scalable objective counts.
- Proposed Difficulty Classification: The toolkit classifies constraint difficulty as feasibility-hardness, convergence-hardness, or diversity-hardness.These correspond respectively to finding feasible solutions, approaching the Pareto front through infeasibility obstacles, and distributing solutions across the complete Pareto front.
- Constructed Benchmarks: The construction produces nine difficulty-adjustable and scalable CMOPs and nine corresponding CMaOPs.The toolkit is intended to overcome existing benchmark limitations in difficulty adjustment and objective scalability.
- Adjustability: Each difficulty type is parameterized, enabling users to adjust difficulty levels and combine them into varied constrained problems.A difficulty level is represented by a triplet whose parameters specify the levels of the three primary difficulty types.
2 Effects of Constraints on PFs
Constraints can reshape the Pareto front by making parts infeasible, blocking convergence, forcing optima onto boundaries, or reducing front dimensionality.
- Infeasible regions can make only part of the unconstrained Pareto front feasible, sometimes adding constrained optima on constraint boundaries.
- Infeasible regions may block the path toward the Pareto front while leaving the constrained front equal to the unconstrained front.
- When the entire original Pareto front is infeasible, every constrained Pareto-optimal point lies on a constraint boundary.
- Constraints can reduce a problem's Pareto-front dimensionality from M dimensions to K dimensions, where K < M.The illustrated case transforms a two-objective problem into a one-dimensional constrained front.
3 Difficulty Types and Levels of CMOPs
The paper distinguishes feasibility-, convergence-, and diversity-hardness according to how constraints challenge feasible-solution discovery, movement toward the front, and coverage of the front.
- Diversity-hard CMOPs have disconnected or unevenly difficult Pareto-front regions, making the complete front difficult for CMOEAs to achieve.
- Feasibility-hard CMOPs have very small feasible portions of the search space, often leaving initial populations mostly or entirely infeasible.
- Convergence-hard CMOPs use infeasible regions to hinder movement toward the Pareto front, making generational distance difficult to minimize.
- The three primary difficulty types can be combined into seven basic types and represented by a normalized parameter triplet (η, ζ, γ).The triplet specifies the levels of the three primary difficulties.
4 Construction Toolkit
The toolkit combines scalable objective functions with three parameterized constraint-function types, each targeting a distinct difficulty and supporting adjustable, multi-objective CMOP construction.
- Type-I constraints: Type-I constraints limit decision-variable boundaries, divide the Pareto front into disconnected segments, and control diversity-hardness with η.η ranges from 0 to 1, with η = 0 imposing no effect and η = 1 the maximum effect.
- Toolkit integration: The three constraint types correspond respectively to diversity-, feasibility-, and convergence-hardness, and their levels are jointly specified by (η, ζ, γ).The toolkit can be scaled to construct problems with more than three objectives.
- Type-I constraints: Increasing η decreases segment width and increases diversity difficulty, while the construction can scale beyond two objectives.Examples include η = 0.55, 0.75, and 1.0, as well as a three-objective case with η = 0.75.
- Type-II constraints: Type-II constraints limit reachable distance-function boundaries and control feasible-region proportions through ζ, generating feasibility-hardness.ζ ranges from 0 to 1; ζ = 0 gives the weakest constraints and ζ = 1.0 the strongest.
- Type-III constraints: Type-III constraints limit reachable objective boundaries so infeasible regions block population movement toward the Pareto front, generating convergence-hardness through γ.γ ranges from 0 to 1, with difficulty increasing as γ increases.
5 Scalability of the Number of Objectives
The toolkit scales CMOP objectives through a user-defined parameter and adjusts difficulty through a triplet controlling diversity-, feasibility-, and convergence-hardness.
- Constraint scalability: Type-III constraints create infeasible regions that block convergence toward the PF, with convergence-hardness increasing as γ increases.Figure 5 illustrates γ values of 0.1, 0.5, and 0.75; γ = 0 represents the weakest constraints and γ = 1 the strongest.
- Objective scalability: The number of objectives is controlled by the user-defined parameter m, allowing CMOPs to scale beyond two objectives.The objective construction is borrowed from the WFG toolkit and can be scaled to any number of objectives.
- Constraint scalability: Type-I, Type-II, and Type-III constraint functions respectively control diversity-hardness, feasibility-hardness, and convergence-hardness.These functions can be combined with scalable objective functions to construct DAS-CMOPs.
- Constraint scalability: The toolkit exposes K, P, and Q to control the numbers of the three constraint-function types, while n controls decision-variable dimension.The total number of constraint functions is K + P + Q, with n ≥ m.
- Difficulty adjustment: Difficulty is adjusted with the triplet (η, ζ, γ), whose three parameters range from 0 to 1.The parameters control the three primary constraint-difficulty types introduced by the toolkit.
6 A Set of Difficulty-adjustable and Scalable CMOPs
The proposed toolkit generates benchmark CMOPs and CMaOPs by combining scalable objective functions with difficulty-adjustable constraint functions, including WFG-based many-objective constructions.
- Benchmark construction: Nine difficulty-adjustable and scalable CMOPs and nine CMaOPs are suggested using the proposed toolkit.They are named DAS-CMOP1-9 and DAS-CMaOP1-9.
- CMOP construction: The CMOP set combines nine objective functions with difficulty-adjustable constraint functions to generate DAS-CMOP1-9.The objective functions include convex, concave, and discrete PF shapes.
- CMOP construction: DAS-CMOP1-3 and DAS-CMOP4-6 share constraint functions but differ in their distance functions.DAS-CMOP7-9 use three objectives, and DAS-CMOP8-9 share DAS-CMOP7’s constraint functions.
- CMaOP construction: CMaOPs use WFG-based objective functions that can scale to more than three objectives.The nine DAS-CMaOPs use the objective functions of WFG1-9, with 10 position-related and 20 distance-related decision parameters.
- CMaOP construction: The general CMaOP formulation combines scalable objective functions with sine, cosine, interval, and distance-based constraint forms.Its parameters include η, ζ, and γ, which adjust the corresponding constraint effects.
7 Experimental Study
Experiments across difficulty triplets show that algorithm suitability depends on constraint difficulty type, while increasing difficulty consistently makes the benchmark problems harder. MOEA/D-CDP favors convergence-hard DAS-CMOPs, NSGA-II-CDP favors simultaneous diversity-, feasibility- and convergence-hardness, C-NSGA-III favors feasibility-hard DAS-CMaOPs, and C-MOEA/DD favors convergence-hardness.
- DAS-CMOP comparisons: MOEA/D-CDP was significantly better on convergence-hard DAS-CMOP5 and DAS-CMOP6 in IGD values.For DAS-CMOP5, the convergence-hard triplets were (0.0, 0.0, 0.25), (0.0, 0.0, 0.5) and (0.0, 0.0, 0.75).
- DAS-CMOP comparisons: MOEA/D-CDP was more suitable for convergence-hard DAS-CMOPs, whereas NSGA-II-CDP was more suitable for simultaneous diversity-, feasibility- and convergence-hardness.This pattern is reported from median IGD values over 30 independent runs and detailed comparisons across DAS-CMOPs.
- DAS-CMaOP comparisons: C-NSGA-III was more suitable for feasibility-hard DAS-CMaOPs, while C-MOEA/DD was more suitable for convergence-hard DAS-CMaOPs according to HV.The conclusion is drawn from median HV values in 20 independent runs and the corresponding table comparisons.
- Difficulty effects: Increasing each value in a difficulty triplet made DAS-CMOPs and DAS-CMaOPs increasingly difficult for all four tested algorithms.The tested algorithms were MOEA/D-CDP, NSGA-II-CDP, C-MOEA/DD and C-NSGA-III.
- DAS-CMOP comparisons: NSGA-II-CDP was significantly better than MOEA/D-CDP on most DAS-CMOPs with simultaneous diversity-, feasibility- and convergence-hardness.The comparison is based primarily on IGD values across the tested difficulty triplets.
8 Conclusion
The paper presents a toolkit for generating difficulty-adjustable and objective-scalable constrained multi-objective benchmarks. It constructs nine DAS-CMOPs and nine DAS-CMaOPs, and experiments show that the intended difficulty types exist and produce different algorithm behaviors.
- Conclusion: The toolkit constructs difficulty-adjustable and scalable CMOPs and CMaOPs using three primary constraint functions corresponding to three difficulty types.The construction scales both the number of objectives and the number of constraints.
- Conclusion: Nine DAS-CMOPs and nine DAS-CMaOPs were generated using the proposed construction toolkit.The examples were used as test instances for comprehensive algorithm experiments.
- Conclusion: Experiments found that the three primary difficulty types existed in the corresponding test problems and that the tested algorithms behaved differently when approaching the PFs.The tested methods included MOEA/D-CDP, NSGA-II-CDP, C-MOEA/DD and C-NSGA-III.
- Conclusion: The construction method was found to be effective for generating the suggested CMOPs and CMaOPs.The conclusion follows from comprehensive experiments using varied difficulty triplets.