Source-linked AI summary
MOEA/D with Angle-based Constrained Dominance Principle for Constrained Multi-objective Optimization Problems
Zhun Fan, Yi Fang, Wenji Li, Xinye Cai, Caimin Wei, Erik Goodman
TL;DR
The paper addresses constraint handling for constrained multi-objective optimization, where maintaining diversity during evolutionary search is difficult. It embeds the angle-based constrained dominance principle in MOEA/D and reports that MOEA/D-ACDP outperforms four other decomposition-based CMOEAs on benchmark instances and an engineering problem.
Problem
Constraint-handling mechanisms must solve CMOPs with large infeasible objective-space regions, while common CTP and CF benchmarks have large feasible regions that limit such evaluations.
Method
ACDP uses angle information between solutions to adjust dominance relations and maintain population diversity within MOEA/D.
Results
MOEA/D-ACDP outperforms four other CMOEAs on LIR-CMOP1-14 and significantly outperforms them on the I-beam engineering problem.
Takeaways & Limitations
MOEA/D-ACDP more effectively crosses large infeasible regions and explores feasible and infeasible regions while enhancing convergence to the Pareto front.
Takeaways & Limitations
Future work is needed to develop mechanisms that mine more useful information during evolution to further improve the proposed algorithm.
Abstract
from arXiv · showhide
This paper proposes a novel constraint-handling mechanism named angle-based constrained dominance principle (ACDP) embedded in a decomposition-based multi-objective evolutionary algorithm (MOEA/D) to solve constrained multi-objective optimization problems (CMOPs). To maintain the diversity of the working population, ACDP utilizes the information of the angle of solutions to adjust the dominance relation of solutions during the evolutionary process. This paper uses 14 benchmark instances to evaluate the performance of the MOEA/D with ACDP (MOEA/D-ACDP). Additionally, an engineering optimization problem (which is I-beam optimization problem) is optimized. The proposed MOEA/D-ACDP, and four other decomposition-based CMOEAs, including C-MOEA/D, MOEA/D-CDP, MOEA/D-Epsilon and MOEA/D-SR are tested by the above benchmarks and the engineering application. The experimental results manifest that MOEA/D-ACDP is significantly better than the other four CMOEAs on these test instances and the real-world case, which indicates that ACDP is more effective for solving CMOPs.
1. Introduction
Constrained multi-objective optimization requires constraint-handling mechanisms within multi-objective evolutionary algorithms. The introduction motivates improved testing and reviews major algorithmic approaches and limitations of common benchmarks.
- CMOPs combine multiple conflicting objectives with constraints, requiring constraint-handling techniques within multi-objective evolutionary algorithms.
- MOEAs are commonly classified as Pareto-domination-based, decomposition-based, or indicator-based, with MOEA/D representing the decomposition-based family.
- Constraint-handling approaches include penalty functions, specialized representations and operators, repair algorithms, separate objectives and constraints, and hybrid methods.
- CDP prioritizes constraints when comparing solutions, while stochastic ranking, ε-constrained methods, and non-greedy techniques provide alternative objective-constraint separation strategies.
- CTP and CF benchmarks have large feasible objective-space regions, limiting their suitability for evaluating constraint-handling mechanisms once populations become feasible.
2. Relative Work
MOEA/D decomposes a multi-objective problem into scalar subproblems using weight vectors, while decomposition-based CMOEAs combine this framework with different constraint-handling mechanisms.
- 2.1. MOEA/D: MOEA/D creates one scalar subproblem per uniformly distributed weight vector and associates each subproblem with one solution.
- 2.1. MOEA/D: This paper uses the Tchebycheff decomposition method within MOEA/D to define scalar optimization subproblems.
- 2.2. Decomposition-based CMOEAs: The compared decomposition-based CMOEAs are C-MOEA/D, MOEA/D-CDP, MOEA/D-Epsilon, and MOEA/D-SR, each pairing MOEA/D with a constraint-handling strategy.
- 2.2. Decomposition-based CMOEAs: C-MOEA/D uses an adaptive epsilon level based on constraint violation and the feasible-solution proportion when comparing aggregation values and violations.
- 2.2. Decomposition-based CMOEAs: MOEA/D-CDP ranks feasible solutions above infeasible ones and compares infeasible solutions by their constraint violations.
- 2.2. Decomposition-based CMOEAs: MOEA/D-Epsilon dynamically decreases its epsilon level as the generation counter increases, whereas MOEA/D-SR probabilistically balances aggregation values against constraints.
3. MOEA/D with Angle-based Constrained Dominance Principle
ACDP augments MOEA/D by using objective-space angles, constraint violation, decomposition values, and feasible-solution proportion to balance diversity and convergence. Its threshold increases during evolution, allowing early exploration and later convergence toward feasible regions.
- 3.1. Angle-based Constrained Dominance Principle: ACDP supplements constraint violation with objective-space angle and feasible-solution proportion when comparing solutions involving infeasibility.This addresses the tendency of CDP to ignore useful infeasible-region information when most solutions are infeasible.
- 3.1. Angle-based Constrained Dominance Principle: For similar solutions, ACDP selects the one with lower constraint violation; for dissimilar solutions, it probabilistically favors the lower decomposition value.The probability is the current proportion of feasible solutions, pf.
- 3.4. The Parameter Setting of Theta: With CDP, populations can become trapped near feasible regions, whereas ACDP maintains diversity, crosses infeasible regions, and converges more completely to the real Pareto front.These contrasting evolutionary processes are illustrated for MOEA/D with CDP and ACDP.
- 3.4. The Parameter Setting of Theta: The threshold θ(k) increases with generation, starting small to preserve diversity and becoming larger to emphasize convergence.When k reaches Tc, θ(k) equals π/2 and ACDP becomes CDP.
- 3. MOEA/D with Angle-based Constrained Dominance Principle: MOEA/D-ACDP integrates MOEA/D with the angle-based constrained dominance principle.The algorithm decomposes a CMOP into subproblems associated with weight vectors and applies ACDP during subproblem updates.
32 end
After generating and mutating offspring, MOEA/D-ACDP updates the ideal point and subproblems, then archives nondominated solutions.
- 32 end: MOEA/D-ACDP generates offspring with differential evolution crossover and polynomial mutation before updating the ideal point and subproblems.The subproblem updates use ACDP, and nondominated solutions update the external archive at each generation.
- 32 end: At each generation’s end, nondominated solutions are selected to update the external archive through nondominated sorting.
24 end
ACDP updates subproblems by combining aggregation values, constraint violations, objective-space angles, and the current feasible-solution proportion.
- 24 end: Feasible solutions are compared by aggregation value, while infeasible comparisons use angle-dependent constraint or aggregation rules.For larger angles, the lower aggregation value is selected with probability pf; otherwise the solutions are incomparable.
4. Experimental Study
MOEA/D-ACDP was evaluated on 14 LIR-CMOP benchmarks and the I-beam problem against four decomposition-based CMOEAs using IGD and HV. It significantly outperformed the alternatives on most LIR-CMOP cases and on the engineering problem.
- Experimental settings: The LIR-CMOPs were designed with large infeasible objective-space regions, whereas about half of sampled I-beam points were infeasible.The I-beam sampling estimated a feasible proportion of p = 0.5339.
- LIR-CMOP test instances: For LIR-CMOP3-14, MOEA/D-ACDP significantly outperformed all four compared algorithms in IGD, while on LIR-CMOP1-2 it outperformed three.The three alternatives were C-MOEA/D, MOEA/D-CDP, and MOEA/D-Epsilon.
- LIR-CMOP test instances: MOEA/D-ACDP significantly outperformed the compared algorithms in HV for LIR-CMOP2-14 and for LIR-CMOP1 against three alternatives.The HV results are reported in Table 2.
- LIR-CMOP test instances: On representative LIR-CMOP cases, MOEA/D-ACDP covered the real PF more completely and maintained better diversity than the other CMOEAs.The other algorithms were trapped in local optima on LIR-CMOP5, while MOEA/D-ACDP obtained most or all of the PF on several cases.
- LIR-CMOP test instances: MOEA/D-ACDP outperformed the other four decomposition-based CMOEAs on most of the 14 LIR-CMOP test instances.The comparison used IGD and HV over 30 independent runs.
- I-beam optimization problem: MOEA/D-ACDP significantly outperformed the other CMOEAs on the I-beam optimization problem according to HV.The I-beam problem minimizes cross-sectional area and static deflection under force P.
5. Conclusions
The paper concludes that MOEA/D-ACDP uses angle information to preserve population diversity and improve convergence on constrained multi-objective problems. Across LIR-CMOP benchmarks and an engineering problem, it outperforms four other CMOEAs, while future work targets further constraint-handling improvements.
- Conclusions: MOEA/D-ACDP outperforms four other CMOEAs on LIR-CMOP1-14 and the I-beam engineering problem.The tested alternatives are C-MOEA/D, MOEA/D-CDP, MOEA/D-Epsilon, and MOEA/D-SR.
- Conclusions: The proposed method is designed to cross large infeasible regions more effectively than general CMOEAs.
- Conclusions: ACDP uses solution angles to maintain population diversity during constrained multi-objective optimization.
- Conclusions: MOEA/D-ACDP explores feasible and infeasible regions simultaneously to improve convergence toward the Pareto front.This approach retains useful information from infeasible solutions rather than discarding it.
- Conclusions: Future work will develop new constraint-handling mechanisms and mine more evolutionary information to further improve performance.