PaperlayerView exact revision on arXiv

Source-linked AI summary

Push and Pull Search for Solving Constrained Multi-objective Optimization Problems

Zhun Fan, Wenji Li, Xinye Cai, Hui Li, Caimin Wei, Qingfu Zhang, Kalyanmoy Deb, Erik D. Goodman

arXiv:1709.05915v1cs.NEcs.AI

TL;DR

CMOP algorithms must balance conflicting objectives with constraint satisfaction, particularly when feasible regions are small or narrow. PPS separates unconstrained exploration from constraint-aware pulling, using the first stage to estimate constraint information for the second. Across benchmark problems, PPS achieves competitive or statistically better performance than five other CMOEAs on most instances.

  • Problem

    Constraint-handling methods must balance objectives and constraints, while small or narrow feasible regions make this balance difficult and can challenge diversity.

  • Method

    PPS uses a push stage that ignores constraints and estimates their landscape, followed by a pull stage using improved epsilon constraint-handling to reach feasible, non-dominated regions.

  • Results

    PPS achieves competitive or statistically significantly better results than five other CMOEAs on most benchmark problems.

  • Takeaways & Limitations

    PPS provides a viable framework for using constraint-landscape information to guide constraint-handling parameter settings.

Abstract

from arXiv · show

This paper proposes a push and pull search (PPS) framework for solving constrained multi-objective optimization problems (CMOPs). To be more specific, the proposed PPS divides the search process into two different stages, including the push and pull search stages. In the push stage, a multi-objective evolutionary algorithm (MOEA) is adopted to explore the search space without considering any constraints, which can help to get across infeasible regions very fast and approach the unconstrained Pareto front. Furthermore, the landscape of CMOPs with constraints can be probed and estimated in the push stage, which can be utilized to conduct the parameters setting for constraint-handling approaches applied in the pull stage. Then, a constrained multi-objective evolutionary algorithm (CMOEA) equipped with an improved epsilon constraint-handling is applied to pull the infeasible individuals achieved in the push stage to the feasible and non-dominated regions. Compared with other CMOEAs, the proposed PPS method can more efficiently get across infeasible regions and converge to the feasible and non-dominated regions by applying push and pull search strategies at different stages. To evaluate the performance regarding convergence and diversity, a set of benchmark CMOPs is used to test the proposed PPS and compare with other five CMOEAs, including MOEA/D-CDP, MOEA/D-SR, C-MOEA/D, MOEA/D-Epsilon and MOEA/D-IEpsilon. The comprehensive experimental results demonstrate that the proposed PPS achieves significantly better or competitive performance than the other five CMOEAs on most of the benchmark set.

I. INTRODUCTION

CMOP constraint handling must balance objective optimization against feasibility, especially when feasible regions are small or narrow. PPS addresses this by separating unconstrained exploration from constraint-aware recovery and using explored constraint information to guide later parameter settings.

  • CMOPs optimize multiple conflicting objectives subject to equality and/or inequality constraints.
  • Penalty methods balance objectives and constraints by adding constraint violation weighted by a penalty factor λ to each objective.λ = ∞ yields a death penalty; fixed and changing λ correspond to static and dynamic penalties.
  • CDP is parameter-free but can perform poorly when feasible regions are very small and narrow, where populations remain infeasible and diversity is difficult to maintain.
  • Epsilon constraint-handling relaxes feasibility using ε to preserve diversity when most solutions are infeasible, but selecting ε properly is non-trivial.When ε = 0, EC is equivalent to CDP.
  • PPS divides search into push and pull stages, first optimizing objectives without constraints and then using improved epsilon handling to move solutions toward the constrained Pareto front.The push stage also estimates the constraint landscape for parameter setting in the pull stage.
  • PPS is designed to cross large infeasible regions and use information gathered during unconstrained exploration to guide constraint-handling parameters.

II. THE GENERAL FRAMEWORK OF PUSH AND PULL SEARCH

PPS first approximates the unconstrained Pareto front while ignoring constraints, then switches to a pull search that moves infeasible solutions toward feasible, non-dominated regions. The switch is triggered when recent ideal- and nadir-point changes fall below a threshold.

  • PPS behavior depends on how infeasible regions affect the unconstrained Pareto front, including blocking, covering, or partially masking it.
  • When infeasible regions block the path but leave constrained and unconstrained fronts identical, push search can cross them without extra effort and approximate the true front before pull search.
  • When infeasibility covers the unconstrained front, push search approaches that front first, after which pull search moves the population toward the real constrained front.
  • The search switches from push to pull when the maximum recent rate of change between ideal and nadir points is less than or equal to the predefined threshold ε.The threshold is set to ε = 1e−3, and r_k is initialized to 1.0.
  • Overall, push search approximates the unconstrained front without constraints, while pull search considers constraints to reach feasible and non-dominated regions.

III. AN INSTANTIATION OF PPS IN MOEA/D

The paper instantiates PPS within MOEA/D by using an unconstrained decomposition-based search for the push stage. This implementation selects among subproblem solutions with a Tchebycheff decomposition approach.

  • A. The push search: The MOEA/D instantiation uses an unconstrained MOEA/D during push search to find non-dominated solutions without considering constraints.
  • A. The push search: MOEA/D decomposes the problem into single constrained optimization subproblems optimized simultaneously in a collaborative manner.Each subproblem is associated with a weight vector λ_i.
  • A. The push search: The implementation uses the Tchebycheff decomposition method among weighted sum, Tchebycheff, and boundary intersection alternatives.
  • A. The push search: A newly generated solution is retained for the next generation according to the g_te value specified in Algorithm 1.

B. The pull search

The pull search uses improved epsilon constraint-handling to move infeasible solutions toward feasible, non-dominated regions after the push stage. Its behavior depends on how constraints shape the constrained Pareto front.

  • Pull search: The pull stage applies a constraint-handling mechanism to pull infeasible solutions toward feasible and non-dominated regions.The proposed mechanism is an improved epsilon constraint-handling approach.
  • Pull search: When infeasible regions block the path but the constrained and unconstrained PFs coincide, the push stage can approximate the true PF without pull-stage changes.The pull search has no effect on the working population in this case.
  • Pull search: When the unconstrained PF is covered by infeasible regions, pull search gradually moves infeasible individuals toward feasible and non-dominated regions.The real PF lies on constraint boundaries in this situation.
  • Epsilon control: The epsilon level is initialized from the maximum overall constraint violation at the end of the push search.This initialization differs from earlier settings based on an individual in the initial population.
  • Pull search: During the pull stage, a newly generated solution is selected using the epsilon-related value gte and its overall constraint violation.The selection rule is specified in the pull-subproblem procedure.

C. PPS Embedded in MOEA/D

PPS is presented as a general framework and instantiated here within MOEA/D. The algorithm switches between push and pull strategies while updating subproblems and the feasible non-dominated solution set.

  • PPS Embedded in MOEA/D: PPS-MOEA/D decomposes a CMOP into N single-objective subproblems and initializes the search in the push stage.The algorithm also initializes the rate of change of ideal and nadir points.
  • PPS Embedded in MOEA/D: The algorithm sets epsilon and the search strategy according to the current generation and the corresponding epsilon-setting rules.These settings are updated during the repeated generational loop.
  • PPS Embedded in MOEA/D: PPS-MOEA/D uses push search while PushStage is true and pull search otherwise.Different search strategies are adopted when updating subproblems.
  • PPS Embedded in MOEA/D: The feasible and non-dominated solution set NS is updated using non-dominated ranking in NSGA-II.This update occurs after the generation count is advanced.
  • PPS Framework: PPS is a general framework that can be instantiated in different MOEAs, although this paper realizes PPS-MOEA/D.The framework uses information gathered during both stages to guide search.

IV. EXPERIMENTAL STUDY

The experimental study compares PPS-MOEA/D with five CMOEAs on LIR-CMOP1-14 under repeated, fixed-budget runs and specified evolutionary parameters.

  • Experimental Settings: PPS-MOEA/D is compared with MOEA/D-IEpsilon, MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP, and C-MOEA/D on LIR-CMOP1-14.The comparison uses five other constrained multi-objective evolutionary algorithms.
  • Algorithm Setup: The MOEA/D implementation decomposes a CMOP into N subproblems associated with weight vectors and constructs neighborhoods from the closest vectors.The initial population contains N solutions.
  • Algorithm Setup: The algorithm initializes PushStage = true and tracks ideal and nadir-point changes over previous generations.The generation counter is initialized at k = 1.
  • Variation Operators: New solutions are generated through differential evolution followed by polynomial mutation.The DE settings are CR = 1.0 and f = 0.5, with polynomial-mutation distribution index 20.
  • Experimental Settings: Each algorithm runs independently 30 times and stops after 300,000 function evaluations.The population size is N = 300 and the neighborhood size is T = 30.

B. Performance Metric

The study evaluates convergence and diversity using IGD and hypervolume. IGD is minimized, whereas larger HV indicates a non-dominated set closer to the true PF.

  • Performance Metrics: IGD and hypervolume are used to evaluate PPS-MOEA/D and the five comparison CMOEAs.Both metrics assess performance related to convergence and diversity.
  • IGD: IGD reflects convergence and diversity simultaneously by comparing an achieved approximate PF with representative points from the real PF.For two-objective LIR-CMOPs, 1000 true-PF points are sampled; for three objectives, 10000 are sampled.
  • IGD: A smaller IGD value indicates better performance regarding diversity and/or convergence.The interpretation is based on the representative-point comparison with the true PF.
  • Hypervolume: HV measures the closeness of the achieved non-dominated set to the real PF, with larger values indicating greater closeness.The reference point is placed at 1.2 times the distance to the true PF's nadir point.

1) A Comparison between PPS-MOEA/D and MOEA/D-IEpsilon:

Across LIR-CMOP1-14, PPS-MOEA/D generally outperforms or matches MOEA/D-IEpsilon on IGD and HV, with one difficult exception linked to incomplete push-stage convergence. Increasing the switching parameter improves PPS performance on that exception.

  • PPS-MOEA/D achieves significantly better IGD than MOEA/D-IEpsilon on LIR-CMOP1-2, LIR-CMOP5-8, LIR-CMOP11, and LIR-CMOP14.MOEA/D-IEpsilon is significantly better only on LIR-CMOP9; the remaining instances show no significant difference.
  • PPS-MOEA/D achieves significantly better HV on LIR-CMOP1-3, LIR-CMOP5-8, and LIR-CMOP14, while losing on LIR-CMOP9.The methods do not differ significantly on LIR-CMOP4 and LIR-CMOP10-13.
  • On LIR-CMOP9, PPS-MOEA/D is significantly worse on both IGD and HV despite the real PF lying on the unconstrained PF with disconnected parts.The authors suggest incomplete convergence to the whole unconstrained PF during the push stage as one possible reason.
  • With switching parameter l ≥70, PPS-MOEA/D becomes better than MOEA/D-IEpsilon on LIR-CMOP9.The comparison uses mean IGD and HV values under different l settings.
  • Overall, PPS-MOEA/D is superior on eight test problems, statistically indistinguishable on five, and inferior on one.The paper concludes that PPS enhances CMOEA performance in IGD and HV.

2) A Comparison of PPS-MOEA/D and the other four decomposition-based CMOEAs:

Against four other decomposition-based CMOEAs, PPS-MOEA/D performs significantly better across all tested LIR-CMOP instances on IGD and HV. Additional plots show more consistent convergence and recovery of disconnected Pareto-optimal solutions.

  • PPS-MOEA/D is significantly better than MOEA/D-Epsilon, MOEA/D-CDP, MOEA/D-SR, and C-MOEA/D on all fourteen problems in IGD.The comparison uses Wilcoxon tests over 30 independent runs.
  • PPS-MOEA/D is significantly better than the four alternatives on every test instance in HV.The paper reports better performance than all four decomposition-based CMOEAs across the full test set.
  • PPS-MOEA/D has the smallest mean IGD among six tested CMOEAs on LIR-CMOP6, LIR-CMOP7, and LIR-CMOP11.Box plots summarize the IGD values for these three problems across the tested algorithms.
  • On LIR-CMOP7, PPS-MOEA/D converges to the real PF at each running time, unlike the other five CMOEAs.Three large infeasible regions cover the unconstrained PF in this problem.
  • On LIR-CMOP11, PPS-MOEA/D finds all seven discrete Pareto-optimal solutions at each run, whereas other methods sometimes miss solutions.MOEA/D-IEpsilon fails to find all seven solutions in more than fifteen of 30 runs.

V. CONCLUSION

PPS divides CMOP search into push and pull stages, using constraint-free exploration before pulling infeasible solutions toward feasible, non-dominated regions. Experiments report competitive or significantly better performance than five CMOEAs on most benchmark problems, while identifying areas for further improvement.

  • Conclusion: PPS ignores constraints during the push stage, then uses improved epsilon constraint-handling to pull solutions toward feasible and non-dominated regions.The push stage also estimates constraint-landscape information for parameter setting in the pull stage.
  • Conclusion: For LIR-CMOP9, PPS-MOEA/D becomes better than MOEA/D-IEpsilon when the switching parameter satisfies l ≥70.The comparison uses mean IGD and HV values across different l settings.
  • Conclusion: The authors identify future improvements in pull-stage constraint handling, search-behavior switching, and integration of data mining or machine learning.They also propose testing PPS with non-dominated frameworks and on additional real-world constrained engineering problems.
Loading 1709.05915v1…