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.
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- C. Floudas and P. Pardalos. A Collection of Test Problems for Constrained Global Optimization Algorithms. Springer Verlag, 1987. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- D. M. Himmelblau. Applied Nonlinear Programming. McGraw-Hill, 1972.Google Scholar
- W. Hock and K. Schittkowski. Test Examples for Nonlinear Programming Codes. Springer Verlag, 1981. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- O. Kramer and H.-P. Schwefel. On three new approaches to handle constraints within evolution strategies. Natural Computing, 5(4):363--385, 2006. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 ScholarCross Ref
- Z. Michalewicz and M. Schoenauer. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 4(1):1--32, 1996. Google ScholarDigital Library
- 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 ScholarCross Ref
- T. P. Runarsson and X. Yao. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation, 4(3):274--283, 2000. Google ScholarDigital Library
- H.-P. Schwefel. Evolution and Optimum Seeking. Wiley, 1995.Google ScholarDigital Library
- T. Suttorp, N. Hansen, and C. Igel. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning, 75(2):167--197, 2009. Google ScholarDigital Library
- 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 ScholarCross Ref
- 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 Scholar
Index Terms
A (1+1)-CMA-ES for constrained optimisation
Recommendations
Active covariance matrix adaptation for the (1+1)-CMA-ES
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationWe propose a novel variant of the (1+1)-CMA-ES that updates the distribution of mutation vectors based on both successful and unsuccessful trial steps. The computational costs of the adaptation procedure are quadratic in the dimensionality of the ...
On the behaviour of the (1, λ)-es for a conically constrained problem
GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computationWe consider a conically constrained optimisation problem where the optimal solution lies at the apex of the cone and study the behaviour of a (1,λ)-ES that handles constraints by resampling infeasible candidate solutions. Expressions that describe the ...
Black-box optimization benchmarking of NEWUOA compared to BIPOP-CMA-ES: on the BBOB noiseless testbed
GECCO '10: Proceedings of the 12th annual conference companion on Genetic and evolutionary computationIn this paper, the performances of the NEW Unconstrained Optimization Algorithm (NEWUOA) on some noiseless functions are compared to those of the BI-POPulation Covariance Matrix Adaptation-Evolution Strategy (BIPOP-CMA-ES). The two algorithms were ...
Comments