skip to main content
10.1145/2330163.2330207acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

A (1+1)-CMA-ES for constrained optimisation

Published:07 July 2012Publication History

ABSTRACT

This paper introduces a novel constraint handling approach for covariance matrix adaptation evolution strategies (CMA-ES). The key idea is to approximate the directions of the local normal vectors of the constraint boundaries by accumulating steps that violate the respective constraints, and to then reduce variances of the mutation distribution in those directions. The resulting strategy is able to approach the boundary of the feasible region without being impeded in its ability to search in directions tangential to the boundaries. The approach is implemented in the (1+1)-CMA-ES and evaluated numerically on several test problems. The results compare very favourably with data for other constraint handling approaches applied to unimodal test problems that can be found in the literature.

References

  1. D. V. Arnold and D. Brauer. On the behaviour of the (1+1)-ES for a simple constrained problem. In G. Rudolph et al., editors, Parallel Problem Solving from Nature -- PPSN X, pages 1--10. Springer Verlag, 2008.Google ScholarGoogle Scholar
  2. D. V. Arnold and N. Hansen. Active covariance matrix adaptation for the (1+1)-CMA-ES. In Genetic and Evolutionary Computation Conference -- GECCO 2010, pages 385--392. ACM Press, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. G. Collange, N. Delattre, N. Hansen, I. Quinquis, and M. Schoenauer. Multidisciplinary optimisation in the design of future space launchers. In P. Breitkopf and R. F. Coelho, editors, Multidisciplinary Design Optimization in Computational Mechanics, pages 487--496. Wiley, 2010.Google ScholarGoogle Scholar
  4. C. Floudas and P. Pardalos. A Collection of Test Problems for Constrained Global Optimization Algorithms. Springer Verlag, 1987. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. N. Hansen. Adaptive encoding: How to render search coordinate system invariant. In G. Rudolph et al., editors, Parallel Problem Solving from Nature -- PPSN X, pages 205--214. Springer Verlag, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. N. Hansen, A. Auger, R. Ros, S. Finck, and P. Posík. Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In Genetic and Evolutionary Computation Conference Companion -- GECCO 2010, pages 1689--1696. ACM Press, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. N. Hansen, R. Ros, N. Mauny, M. Schoenauer, and A. Auger. Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems. Applied Soft Computing, 11(8):5755--5769, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. D. M. Himmelblau. Applied Nonlinear Programming. McGraw-Hill, 1972.Google ScholarGoogle Scholar
  9. W. Hock and K. Schittkowski. Test Examples for Nonlinear Programming Codes. Springer Verlag, 1981. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. C. Igel, T. Suttorp, and N. Hansen. A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies. In Genetic and Evolutionary Computation Conference -- GECCO 2006, pages 453--460. ACM Press, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. G. A. Jastrebski and D. V. Arnold. Improving evolution strategies through active covariance matrix adaptation. In IEEE World Congress on Computational Intelligence -- WCCI 2006, pages 9719--9726. IEEE Press, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  12. O. Kramer, A. Barthelmes, and G. Rudolph. Surrogate constraint functions for CMA evolution strategies. In B. Mertsching et al., editors, KI 2009: Advances in Artificial Intelligence, pages 169--176. Springer Verlag, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. O. Kramer and H.-P. Schwefel. On three new approaches to handle constraints within evolution strategies. Natural Computing, 5(4):363--385, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. O. Kramer, C.-K. Ting, and H. Kleine Büning. A new mutation operator for evolution strategies for constrained problems. In IEEE Congress on Evolutionary Computation -- CEC 2005, pages 2600--2606. IEEE Press, 2005.Google ScholarGoogle ScholarCross RefCross Ref
  15. E. Mezura-Montes and C. A. Coello Coello. Constraint-handling in nature-inspired numerical optimization: Past, present, and future. Swarm and Evolutionary Computation, 1(4):173--194, 2011.Google ScholarGoogle ScholarCross RefCross Ref
  16. Z. Michalewicz and M. Schoenauer. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 4(1):1--32, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. A. I. Oyman, K. Deb, and H.-G. Beyer. An alternative constraint handling method for evolution strategies. In Proceedings of the 1999 IEEE Congress on Evolutionary Computation, pages 612--619. IEEE Press, 1999.Google ScholarGoogle ScholarCross RefCross Ref
  18. T. P. Runarsson and X. Yao. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation, 4(3):274--283, 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. H.-P. Schwefel. Evolution and Optimum Seeking. Wiley, 1995.Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. T. Suttorp, N. Hansen, and C. Igel. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning, 75(2):167--197, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. T. Takahama and S. Sakai. Constrained optimization by the ε constrained differential evolution with gradient-based mutation and feasible elites. In IEEE World Congress on Computational Intelligence -- WCCI 2006, pages 308--315. IEEE Press, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  22. T. Takahama and S. Sakai. Efficient constrained optimization by the ε constrained adaptive differential evolution. In IEEE World Congress on Computational Intelligence -- WCCI 2010, pages 2052--2059. IEEE Press, 2010.Google ScholarGoogle Scholar

Index Terms

  1. A (1+1)-CMA-ES for constrained optimisation

                  Recommendations

                  Comments

                  Login options

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

                  Sign in
                  • Published in

                    cover image ACM Conferences
                    GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation
                    July 2012
                    1396 pages
                    ISBN:9781450311779
                    DOI:10.1145/2330163

                    Copyright © 2012 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]

                    Publisher

                    Association for Computing Machinery

                    New York, NY, United States

                    Publication History

                    • Published: 7 July 2012

                    Permissions

                    Request permissions about this article.

                    Request Permissions

                    Check for updates

                    Qualifiers

                    • research-article

                    Acceptance Rates

                    Overall Acceptance Rate1,669of4,410submissions,38%

                    Upcoming Conference

                    GECCO '24
                    Genetic and Evolutionary Computation Conference
                    July 14 - 18, 2024
                    Melbourne , VIC , Australia

                  PDF Format

                  View or Download as a PDF file.

                  PDF

                  eReader

                  View online with eReader.

                  eReader