Source-linked AI summary
An Improved Epsilon Constraint-handling Method in MOEA/D for CMOPs with Large Infeasible Regions
Zhun Fan, Wenji Li, Xinye Cai, Han Huang, Yi Fang, Yugen You, Jiajie Mo, Caimin Wei, Erik Goodman
TL;DR
CMOPs combine conflicting objectives with constraints, while common benchmarks do not effectively test constraint handling in problems with large infeasible regions. The paper proposes MOEA/D-IEpsilon, which dynamically adjusts ε using the population's feasible ratio, and reports better performance than four competing CMOEAs on LIR-CMOPs and a robot gripper problem.
Problem
Common CTP and CF test suites have relatively large feasible regions and therefore cannot effectively measure constraint-handling techniques for CMOPs with large infeasible regions.
Method
MOEA/D-IEpsilon embeds an improved ε-constraint-handling mechanism in MOEA/D and dynamically adjusts ε according to the population's feasible ratio.
Results
MOEA/D-IEpsilon was significantly better than MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP and C-MOEA/D on LIR-CMOP1-14 and also outperformed them on the robot gripper optimization problem.
Takeaways & Limitations
MOEA/D-IEpsilon is more suitable for solving CMOPs with large infeasible regions within the tested benchmark and robot gripper settings.
Takeaways & Limitations
The paper identifies further work in developing constraint-handling mechanisms for CMOPs with different types of difficulty.
Abstract
from arXiv · showhide
This paper proposes an improved epsilon constraint-handling mechanism, and combines it with a decomposition-based multi-objective evolutionary algorithm (MOEA/D) to solve constrained multi-objective optimization problems (CMOPs). The proposed constrained multi-objective evolutionary algorithm (CMOEA) is named MOEA/D-IEpsilon. It adjusts the epsilon level dynamically according to the ratio of feasible to total solutions (RFS) in the current population. In order to evaluate the performance of MOEA/D-IEpsilon, a new set of CMOPs with two and three objectives is designed, having large infeasible regions (relative to the feasible regions), and they are called LIR-CMOPs. Then the fourteen benchmarks, including LIR-CMOP1-14, are used to test MOEA/D-IEpsilon and four other decomposition-based CMOEAs, including MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP and C-MOEA/D. The experimental results indicate that MOEA/D-IEpsilon is significantly better than the other four CMOEAs on all of the test instances, which shows that MOEA/D-IEpsilon is more suitable for solving CMOPs with large infeasible regions. Furthermore, a real-world problem, namely the robot gripper optimization problem, is used to test the five CMOEAs. The experimental results demonstrate that MOEA/D-IEpsilon also outperforms the other four CMOEAs on this problem.
1 Introduction
CMOPs require simultaneous optimization of conflicting objectives under constraints, but common test suites inadequately stress constraint handling because their feasible regions are relatively large. The paper introduces LIR-CMOPs and MOEA/D-IEpsilon to address problems with large infeasible regions.
- 1 Introduction: CMOEAs seek representative Pareto-optimal solutions while balancing convergence and diversity under multiple constraints and conflicting objectives.Constraint handling and the multi-objective evolutionary algorithm are the two basic components of a CMOEA.
- 1 Introduction: CTP1-5 and CF1-10 have relatively large feasible regions, so CMOEAs can approximate their Pareto fronts without encountering infeasible obstacles.The passage concludes that these instances are poor tests of constraint-handling mechanisms.
- 1 Introduction: LIR-CMOP1-14 were designed with large infeasible regions and relatively small feasible regions that populations cannot easily discover.This characteristic creates challenges for existing CMOEAs and also occurs in the robot gripper optimization problem.
- 1 Introduction: MOEA/D-IEpsilon is an improved ε-constrained MOEA/D that dynamically uses the population's feasible ratio to balance exploration of feasible and infeasible regions.The proposed mechanism is intended to keep a good search balance compared with the original ε-constrained method.
- 1 Introduction: The paper evaluates MOEA/D-IEpsilon against four decomposition-based CMOEAs and tests the methods on LIR-CMOPs and a robot gripper optimization problem.The comparison includes MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP and C-MOEA/D.
2 Related work
Related work covers MOEA/D decomposition strategies and four decomposition-based constraint-handling methods. The paper identifies why their existing parameter or selection rules are poorly suited to crossing large infeasible regions, motivating an improved ε mechanism.
- 2.1 MOEA/D: MOEA/D decomposes a multi-objective problem into scalar subproblems defined by weight vectors and optimizes them simultaneously in a collaborative way.A set of uniformly spread weight vectors formulates the subproblems.
- 2.1 MOEA/D: Weighted-sum decomposition can find only part of a non-convex Pareto front, whereas Tchebycheff decomposition can approximate both concave and convex parts.The weighted-sum approach works well for minimizing problems with convex Pareto fronts.
- 2.1 MOEA/D: Boundary intersection evaluates convergence and diversity using distances d1 and d2, but its penalty factor θ must be set in advance.The method can solve multi-objective problems with any Pareto-front shape.
- 2.2 Decomposition-based CMOEAs: C-MOEA/D adaptively sets ε from CVmean and the feasible ratio, while MOEA/D-Epsilon changes ε dynamically with the generation counter.C-MOEA/D compares solutions using the adaptive threshold and aggregation value or constraint violation.
- 2.2 Decomposition-based CMOEAs: MOEA/D-CDP always favors feasible solutions, while MOEA/D-SR uses a static pf parameter to balance objective and constraint selection.When pf = 0, MOEA/D-SR is equivalent to MOEA/D-CDP.
- 2.2 Decomposition-based CMOEAs: The paper argues that the four existing methods inadequately support crossing large infeasible regions and therefore proposes an improved ε-constrained method embedded in MOEA/D.It states that ε may need to exceed the maximum current constraint violation, whereas the reviewed mechanisms restrict ε, decrease it, or use static selection parameters.
3 The Proposed method
The method improves epsilon constraint handling by dynamically adjusting relaxation according to the population’s feasible-solution ratio, then embeds it in MOEA/D. This balances exploration of feasible and infeasible regions while optimizing decomposed constrained subproblems.
- Epsilon level comparison: The epsilon constraint-handling approach controls constraint relaxation through an epsilon level ε.When ε = 0, epsilon comparison is equivalent to CDP; when ε = ∞, constraints are ignored.
- Original epsilon setting: The original epsilon-setting method decreases ε(k) until the control generation Tc, after which ε(k) = 0.Its initialization and decay depend on the initial population’s constraint violations, cp, Tc, population size, and maximum generation.
- Improved epsilon setting: The proposed method replaces monotonically decreasing epsilon levels with rules that can decrease, increase, or set ε(k) to zero.Rule2 uses (1 − τ)ε(k − 1), rule3 uses (1 + τ)φmax, and rule4 sets ε(k) = 0 when k ≥ Tc.
- Improved epsilon setting: The feasible-solution ratio rk selects whether ε reduction emphasizes feasible-region search or ε increase emphasizes infeasible-region exploration.If rk < α, rule2 is used; otherwise, rule3 is used before Tc, while α controls the balance between the two regions.
- Improved epsilon setting: The improved method can increase ε during evolution, which is intended to help solve CMOPs with large infeasible regions.Its three update rules respectively strengthen feasible-region search, infeasible-region exploration, and feasible-region selection pressure after Tc.
- Embedding in MOEA/D: MOEA/D-IEpsilon integrates the improved epsilon method into MOEA/D by decomposing a CMOP into collaboratively optimized constrained scalar subproblems.The implementation uses Tchebycheff decomposition, differential-evolution crossover, polynomial mutation, and epsilon-based subproblem updates.
4 Test instances
The LIR-CMOP suite contains two- and three-objective constrained problems designed with large infeasible regions and varied Pareto-front geometries and constraint placements. Its instances test convergence, constraint handling, and the difficulty of finding fronts on constraint boundaries.
- Suite design: LIR-CMOP1-14 are designed with large infeasible regions, while their objective functions combine shape and distance components.Shape functions include convex and concave forms; scaled distance functions in LIR-CMOP5-14 increase convergence difficulty.
- Two-objective instances: LIR-CMOP1-4 contain very small feasible regions and correspondingly large infeasible regions.Their feasible regions are illustrated in Fig. 1(a)-(d).
- Two-objective instances: LIR-CMOP5 and LIR-CMOP6 use convex and concave Pareto fronts matching their unconstrained counterparts.A MOEA without constraint handling can achieve these fronts.
- Two-objective instances: LIR-CMOP7-8 place unconstrained Pareto fronts in infeasible regions and locate their true fronts on constraint boundaries.Without constraint-handling methods, a MOEA cannot find the real Pareto fronts for these instances.
- Three-objective instances: LIR-CMOP13 and LIR-CMOP14 extend the suite to three objectives, with the former matching its unconstrained front and the latter lying on constraint boundaries.These instances are shown in Fig. 2(a)-(b).
5 Experimental study
The experiments compare five decomposition-based CMOEAs on LIR-CMOP1-14 using IGD and HV over repeated independent runs. MOEA/D-IEpsilon achieves the strongest reported performance across the benchmark suite, with better convergence and diversity on problems containing large infeasible regions.
- Experimental settings: Five CMOEAs are evaluated on LIR-CMOP1-14 using IGD and HV, with 30 independent runs and 300,000 function evaluations per run.The comparison includes MOEA/D-IEpsilon, MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP and C-MOEA/D.
- IGD results: On LIR-CMOP9, MOEA/D-IEpsilon obtains the whole real PF, whereas the other four CMOEAs achieve only part of it.This indicates better diversity for MOEA/D-IEpsilon on that instance.
- IGD results: On LIR-CMOP11, MOEA/D-IEpsilon achieves the whole PF, while the other four CMOEAs do not converge to the whole PF.The reported comparison identifies better convergence for MOEA/D-IEpsilon on LIR-CMOP11.
- HV results: MOEA/D-IEpsilon is significantly better than the other four CMOEAs in HV on all fourteen LIR-CMOP test instances.A larger HV value represents better performance regarding convergence and diversity.
- Overall analysis: Across LIR-CMOP1-14, MOEA/D-IEpsilon has better convergence and diversity, attributed to automatic adjustment of the epsilon level for large infeasible regions.The benchmark problems share multiple large infeasible regions.
6 Robot Gripper Optimization
The robot gripper problem has two conflicting objectives and eight constraints, and MOEA/D-IEpsilon is evaluated against four decomposition-based CMOEAs. The method achieves significantly better hypervolume performance and its optimized gripping forces agree with simulations within 0.1%.
- Problem definition: The problem uses two conflicting objectives and eight constraints to optimize the robot gripper mechanism.The objectives represent force transmission and gripper weight, with minimizing the second objective producing a lightweight design.
- Problem definition: The formulation minimizes the force-transmission objective f1(x) and the total-element objective f2(x) = a + b + c + e + l.The first objective concerns the ratio between actuating force and minimum gripping force; the second sums gripper elements.
- Problem definition: The gripper model uses seven decision variables with specified ranges, while two conditional rules determine the value of f.The variables are x = [a, b, c, e, l, f, δ]^T; Rule1 and Rule2 assign f under different geometric conditions.
- Experimental settings: MOEA/D-IEpsilon and four decomposition-based CMOEAs are tested with differential-evolution crossover until 600,000 function evaluations.The comparison includes MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP, and C-MOEA/D; hypervolume is used because the ideal Pareto front is unknown.
- Experimental results: MOEA/D-IEpsilon is significantly better than the other four CMOEAs on the robot gripper optimization problem in hypervolume.The comparison uses 30 independent runs, and the resulting nondominated solutions and hypervolume distributions are plotted.
- Experimental results: Theoretical and simulated minimum gripping forces differ by less than 0.1% across three representative gripper configurations.The simulations use ADAMS 2013 with a spring stiffness coefficient of 10^13 N/m, supporting the correctness of the optimized results.
7 Conclusion
MOEA/D-IEpsilon combines an improved epsilon constraint-handling method with MOEA/D and is reported as suitable for CMOPs with large infeasible regions. Experiments also report advantages over four decomposition-based CMOEAs, including on the robot gripper problem.
- MOEA/D-IEpsilon embeds an improved epsilon constraint-handling method within MOEA/D.
- The performance of MOEA/D-IEpsilon is not sensitive to the initial epsilon value.
- MOEA/D-IEpsilon explores feasible and infeasible regions simultaneously during evolution.
- Using the feasible ratio of the current population, MOEA/D-IEpsilon dynamically balances exploration between feasible and infeasible regions.
- MOEA/D-IEpsilon is reported as suitable for CMOPs with large infeasible regions and outperforms four other CMOEAs on the LIR-CMOP test suite and robot gripper optimization problem.The comparison includes MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP and C-MOEA/D.
8 Appendix
The appendix identifies LIR-CMOP1-14 as the paper’s test instances and includes a figure showing non-dominated solutions obtained by MOEA/D-IEpsilon.
- LIR-CMOP1-14 are listed as the appendix’s constrained multi-objective optimization test instances.
- Fig. 7 presents the non-dominated solutions achieved by MOEA/D-IEpsilon.
9 Compliance with Ethical Standards
The paper states that it contains no studies involving human participants or animals and reports no conflict of interest.
- The authors declare that they have no conflict of interest.
- The article contains no studies with human participants or animals performed by the authors.