More Web Proxy on the site http://driver.im/

research-article

Constraint handling within MOEA/D through an additional scalarizing function

Authors:

Saúl Zapotecas-Martínez,

Antonin PonsichAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 595 - 602

https://doi.org/10.1145/3377930.3390240

Published: 26 June 2020 Publication History

Abstract

The Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) has shown high-performance levels when solving complicated multi-objective optimization problems. However, its adaptation for dealing with constrained multi-objective optimization problems (cMOPs) keeps being under the scope of recent investigations. This paper introduces a novel selection mechanism inspired by the ε-constraint method, which builds a bi-objective problem considering the scalarizing function (used into the decomposition approach of MOEA/D) and the constraint violation degree as an objective function. During the selection step of MOEA/D, the scalarizing function is considered to choose the best solutions to the cMOP. Preliminary results obtained over a set of complicated test problems drawn from the CF test suite indicate that the proposed algorithm is highly competitive regarding state-of-the-art MOEAs adopted in our comparative study.

References

[1]

M. Asafuddoula, T. Ray, R. Sarker, and K. Alam. 2012. An adaptive constraint handling approach embedded MOEA/D. In Proceedings of the 2012 IEEE Congress on Evolutionary Computation ((CEC'2012)). IEEE, Brisbane (Australia), 1--8.

[2]

N. Beume and M. Emmerich B. Naujoks. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181, 3 (September 2007), 1653--1669.

[3]

V. J. Bowman. 1976. On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multiple-Criteria Objectives. In Multiple Criteria Decision Making, H. Thiriez and S. Zionts (Eds.). LNEMS, Vol. 130. Springer, Berlin, Heidelberg.

[4]

Carlos A. Coello Coello, David A. Van Veldhuizen, and Gary B. Lamont. 2002. Evolutionary Algorithms for Solving Multi-Objective Problems (2nd. ed.). Kluwer Academic Publishers, New York (USA).

[5]

Oliver Cuate, Lourdes Uribe, Adriana Lara, and Oliver Schütze. 2020. A benchmark for equality constrained multi-objective optimization. Swarm and Evolutionary Computation 52 (2020), 105130.

[6]

I. Das and J.E. Dennis. 1998. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journl on Optimization 8, 3 (March 1998), 631--657.

Digital Library

[7]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (August 2002), 182--197.

Digital Library

[8]

K. Deb, A. Pratap, and T. Meyarivan. 2001. Constrained test problems for multi-objective evolutionary optimization. In Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization (EMO'2001) (LNCS), Eckart Zitzler et al. (Ed.), Vol. 1993. Springer Berlin Heidelberg, Zurich (Switzerland), 284--298.

[9]

Z. Fan, Y. Fang, W. Li, X. Cai, C. Wei, and E. Goodman. 2019. MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems. Applied Soft Computing 74 (January 2019), 621--633.

[10]

Z. Fan, Y. Fang, W. Li, J. Lu, X. Cai, and C. Wei. 2017. A comparative study of constrained multi-objective evolutionary algorithms on constrained multi-objective optimization problems. In Proceedings of the 2017 IEEE Congress on Evolutionary Computation ((CEC'2017)). IEEE, San Sebastián (Spain), 209--216.

Digital Library

[11]

Z. Fan, W. Li, X. Cai, H. Huang, Y. Fang, Y. You, J. Mo, C. Wei, and E. D. Goodman. 2019. An Improved Epsilon Constraint-handling Method in MOEA/D for CMOPS with Large Infeasible Regions. Soft Computing 23, 23 (February 2019), 12491--12510.

[12]

Z. Fan, W. Li, X. Cai, H. Li, H. Huang, and Z. Cai. 2016. An improved epsilon constraint handling method embedded in MOEA/D for constrained multi-objective optimization problems. In Proceedings of 2016 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, Athens (Greece), 1--8.

[13]

Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, and E. Goodman. 2019. Push and pull search for solving constrained multi-objective optimization problems. Swarm and Evolutionary Computation 44 (February 2019), 665--679.

[14]

Hisao Ishibuchi, Takemi Fukase, Naoki Masuyama, and Yusuke Nojima. 2018. Dual-Grid Model of MOEA/D for Evolutionary Constrained Multiobjective Optimization. In Proceedings of the 2018 Genetic and Evolutionary Computation Conference ((GECCO'2018)). SIGEVO, Kyoto (Japan), 665--672.

Digital Library

[15]

Himanshu Jain and Kalyanmoy Deb. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-point Based Non-dominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach. IEEE Transactions on Evolutionary Computation 18, 4 (August 2014), 602--622.

[16]

Muhammad Asif Jan and Rashida Adeeb Khanumb. 2013. A study of two penaltyparameterless constraint handling techniques in the framework of MOEA/D. Applied Soft Computing 13, 1 (Jan. 2013), 128--148.

Digital Library

[17]

M. A. Jan and Qingfu Zhang. 2010. MOEA/D for constrained multiobjective optimization: Some preliminary experimental results. In 2010 UK Workshop on Computational Intelligence (UKCI). 1--6.

[18]

S. Kukkonen and J. Lampinen. 2005. GDE3: the third evolution step of generalized differential evolution. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation ((CEC'2005)). IEEE, Edinburgh (UK), 443--450.

[19]

Hui Li and Qingfu Zhang. 2009. Multiobjective Optimization Problems with Complicated Pareto Sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation 12, 2 (April 2009), 284--302.

[20]

H.L. Liu, F. Gu, and Q. Zhang. 2014. Decomposition of a multiobjective optimizationproblem into a number of simple multiobjective subproblems. IEEE Transactions on Evolutionary Computation 18, 3 (September 2014), 450--455.

[21]

C. Peng, H.L. Liu, and F. Gu. 2017. An evolutionary algorithm with directed weights for constrained multi-objective optimization. Applied Soft Computing 60 (November 2017), 613--622.

Digital Library

[22]

Wei Peng and Qingfu Zhang. 2008. A decomposition-based multi-objective Particle Swarm Optimization algorithm for continuous optimization problems. In GrC 2008. 534 --537.

[23]

M. Pescador-Rojas, R. Hernández Gómez, E. Montero, N. Rojas-Morales, M.C. Riff, and C.A. Coello Coello. 2017. An Overview of Weighted and Unconstrained Scalarizing Functions. In Proceedings of the 9th International Conference on Evolutionary Multi-Criterion Optimization (EMO'2017) (LNCS), Heike Trautmann et al. (Ed.), Vol. 10173. Springer International Publishing, Munster (Germany), 499--513. https://doi.org/

Digital Library

[24]

T. Ray, H.K. Singh, A. Isaacs, and W. Smith. 2009. Infeasibility Driven Evolutionary Algorithm for Constrained Optimization. Springer Berlin Heidelberg, Heidelberg (Berlin), 145--165.

[25]

Tetsuyuki Takahama, Setsuko Sakai, and Noriyuki Iwane. 2005. Constrained Optimization by the e-Constrained Hybrid Algorithm of Particle Swarm Optimization and Genetic Algorithm. In AI 2005: Advances in Artificial Intelligence, Shichao Zhang and Ray Jarvis (Eds.). LNCS, Vol. 3809. Springer Berlin Heidelberg, 389--400.

[26]

T. Takahama, S. Sakai, and N. Iwane. 2005. Constrained Optimization by the ε Constrained Hybrid Algorithm of Particle Swarm Optimization and Genetic Algorithm. In AI 2005: Advances in Artificial Intelligence (LNCS), Shichao Zhang and Ray Jarvis (Eds.), Vol. 3809. Springer Berlin Heidelberg, Berlin, Heidelberg, 389--400.

Digital Library

[27]

A.P. Wierzbicki. 1980. The use of reference objectives in multiobjective optimization. In Multiple Criteria Decision Making Theory and Application, G. Fandel and T. Gal (Eds.). LNE, Vol. 177. Springer.

[28]

Y. Yang, J. Liu, S. Tan, and H. Wang. 2019. A multi-objective differential evolutionary algorithm for constrained multi-objective optimization problems with low feasible ratio. Applied Soft Computing 80 (July 2019), 42--56.

Digital Library

[29]

X. Yu, X. Yu, Y. Lu, G.G. Yenc, and M. Cai. 2018. Differential evolution mutation operators for constrained multi-objective optimization. Applied Soft Computing 67 (June 2018), 452--466.

Digital Library

[30]

S. Zapotecas-Martínez and C. A. Coello Coello. 2013. MOEA/D assisted by RBF Networks for Expensive Multi-Objective Optimization Problems. In Proceedings of the 15th annual conference on Genetic and Evolutionary Computation (GECCO'2013). ACM Press, Amsterdam, The Neatherlands, 1405--1412.

[31]

S. Zapotecas-Martínez and Carlos A. Coello Coello. 2014. A Multi-objective Evolutionary Algorithm based on Decomposition for Constrained Multi-objective Optimization. In Proceedings of the 2014 IEEE Congress on Evolutionary Computation ((CEC'2014)). IEEE, Beijing (China), 1--8.

[32]

S. Zapotecas-Martínez and C. A. Coello Coello. 2011. A Multi-objective Particle Swarm Optimizer Based on Decomposition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation (GECCO'2011). ACM Press, Dublin, Ireland, 69--76.

[33]

Q. Zhang and H. Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (November 2007), 712--731.

Digital Library

[34]

Qingfu Zhang, Wudong Liu, and Hui Li. 2009. The Performance of a New Version of MOEA/D on CEC09 Unconstrained MOP Test Instances. In 2009 IEEE Congress on Evolutionary Computation (CEC'2009). IEEE Press, 203--208.

[35]

Q. Zhang, A. Zhou, S. Zhao, P.N. Suganthan, W. Liu, and S. Tiwari. 2008. Multiobjective optimization test instances for the CEC 2009 special session and competition. Technical Report CES-487. University of Essex and Nanyang Technological University, Colchester (UK).

Cited By

Panteleev APopova N(2024)Development and Application of a Multi-Objective Ant Colony Op-timization Method for Portfolio ProblemModelling and Data AnalysisМоделирование и анализ данных10.17759/mda.202414020514:2(80-97)Online publication date: 1-Jul-2024
https://doi.org/10.17759/mda.2024140205
Wang BQin YMeng XWang YLiu Z(2024)ATM-R: An Adaptive Tradeoff Model With Reference Points for Constrained Multiobjective Evolutionary OptimizationIEEE Transactions on Cybernetics10.1109/TCYB.2023.332994754:8(4475-4488)Online publication date: Aug-2024
https://doi.org/10.1109/TCYB.2023.3329947
Ming FGong WZhen HWang LGao L(2024)Constrained multi-objective optimization evolutionary algorithm for real-world continuous mechanical design problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108673135(108673)Online publication date: Sep-2024
https://doi.org/10.1016/j.engappai.2024.108673
Show More Cited By

Index Terms

Constraint handling within MOEA/D through an additional scalarizing function
1. Applied computing
  1. Operations research
    1. Decision analysis
      1. Multi-criterion optimization and decision-making
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
      2. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Simultaneous use of different scalarizing functions in MOEA/D
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

The use of Pareto dominance for fitness evaluation has been the mainstream in evolutionary multiobjective optimization for the last two decades. Recently, it has been pointed out in some studies that Pareto dominance-based algorithms do not always work ...
Analysis of inverted PBI and comparison with other scalarizing functions in decomposition based MOEAs

MOEA/D is one of the promising evolutionary approaches for solving multi and many-objective optimization problems. MOEA/D decomposes a multi-objective optimization problem into a number of single objective optimization problems. Each single objective ...
A Study on the Specification of a Scalarizing Function in MOEA/D for Many-Objective Knapsack Problems
LION 7: Revised Selected Papers of the 7th International Conference on Learning and Intelligent Optimization - Volume 7997

In recent studies on evolutionary multiobjective optimization, MOEA/D has been frequently used due to its simplicity, high computational efficiency, and high search ability. A multiobjective problem in MOEA/D is decomposed into a number of single-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
154
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Panteleev APopova N(2024)Development and Application of a Multi-Objective Ant Colony Op-timization Method for Portfolio ProblemModelling and Data AnalysisМоделирование и анализ данных10.17759/mda.202414020514:2(80-97)Online publication date: 1-Jul-2024
https://doi.org/10.17759/mda.2024140205
Wang BQin YMeng XWang YLiu Z(2024)ATM-R: An Adaptive Tradeoff Model With Reference Points for Constrained Multiobjective Evolutionary OptimizationIEEE Transactions on Cybernetics10.1109/TCYB.2023.332994754:8(4475-4488)Online publication date: Aug-2024
https://doi.org/10.1109/TCYB.2023.3329947
Ming FGong WZhen HWang LGao L(2024)Constrained multi-objective optimization evolutionary algorithm for real-world continuous mechanical design problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108673135(108673)Online publication date: Sep-2024
https://doi.org/10.1016/j.engappai.2024.108673
Aliniya ZKhasteh S(2024)Dynamic constrained multi-objective optimization based on adaptive combinatorial response mechanismApplied Soft Computing10.1016/j.asoc.2024.111398155(111398)Online publication date: Apr-2024
https://doi.org/10.1016/j.asoc.2024.111398
Yasuda YKumagai WTamura KYasuda K(2024)A Multi‐Objective Evolutionary Algorithm Based on Bilayered Decomposition for Constrained Multi‐Objective OptimizationIEEJ Transactions on Electrical and Electronic Engineering10.1002/tee.24200Online publication date: 6-Oct-2024
https://doi.org/10.1002/tee.24200
Liang JBan XYu KQu BQiao KYue CChen KTan K(2023)A Survey on Evolutionary Constrained Multiobjective OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.315553327:2(201-221)Online publication date: Apr-2023
https://doi.org/10.1109/TEVC.2022.3155533
Zeng YCheng YLiu J(2023)A coevolutionary algorithm assisted by two archives for constrained multi-objective optimization problemsSwarm and Evolutionary Computation10.1016/j.swevo.2023.10137282(101372)Online publication date: Oct-2023
https://doi.org/10.1016/j.swevo.2023.101372
Amarawardhana KEnshaei HJayasinghe S(2022)Review on constraint handling techniques for microgrid energy/power management systemsEnergy Systems10.1007/s12667-022-00549-wOnline publication date: 14-Dec-2022
https://doi.org/10.1007/s12667-022-00549-w
Rahimi IGandomi AChen FMezura-Montes E(2022)A Review on Constraint Handling Techniques for Population-based Algorithms: from single-objective to multi-objective optimizationArchives of Computational Methods in Engineering10.1007/s11831-022-09859-930:3(2181-2209)Online publication date: 9-Dec-2022
https://doi.org/10.1007/s11831-022-09859-9
de-la-Cruz-Martínez SMejía-de-Dios JMezura-Montes E(2022)Efficient Archiving Method for Handling Preferences in Constrained Multi-objective Evolutionary OptimizationHandbook on Decision Making10.1007/978-3-031-08246-7_5(93-119)Online publication date: 27-Sep-2022
https://doi.org/10.1007/978-3-031-08246-7_5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents