{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T11:49:41Z","timestamp":1742644181703},"reference-count":31,"publisher":"MIT Press","issue":"4","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We propose a novel constraint-handling technique for the covariance matrix adaptation evolution strategy (CMA-ES). The proposed technique is aimed at solving explicitly constrained black-box continuous optimization problems, in which the explicit constraint is a constraint whereby the computational time for the constraint violation and its (numerical) gradient are negligible compared to that for the objective function. This method is designed to realize two invariance properties: invariance to the affine transformation of the search space, and invariance to the increasing transformation of the objective and constraint functions. The CMA-ES is designed to possess these properties for handling difficulties that appear in black-box optimization problems, such as non-separability, ill-conditioning, ruggedness, and the different orders of magnitude in the objective. The proposed constraint-handling technique (CHT), known as ARCH, modifies the underlying CMA-ES only in terms of the ranking of the candidate solutions. It employs a repair operator and an adaptive ranking aggregation strategy to compute the ranking. We developed test problems to evaluate the effects of the invariance properties, and performed experiments to empirically verify the invariance of the algorithm. We compared the proposed method with other CHTs on the CEC 2006 constrained optimization benchmark suite to demonstrate its efficacy. Empirical studies reveal that ARCH is able to exploit the explicitness of the constraint functions effectively, sometimes even more efficiently than an existing box-constraint handling technique on box-constrained problems, while exhibiting the invariance properties. Moreover, ARCH overwhelmingly outperforms CHTs by not exploiting the explicit constraints in terms of the number of objective function calls.<\/jats:p>","DOI":"10.1162\/evco_a_00310","type":"journal-article","created":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T17:42:40Z","timestamp":1649180560000},"page":"503-529","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":5,"title":["Adaptive Ranking-Based Constraint Handling for Explicitly Constrained Black-Box Optimization"],"prefix":"10.1162","volume":"30","author":[{"given":"Naoki","family":"Sakamoto","sequence":"first","affiliation":[{"name":"Graduate School of Systems and Information Engineering, University of Tsukuba and RIKEN Center for Advanced Intelligence Project naoki@bbo.cs.tsukuba.ac.jp"}]},{"given":"Youhei","family":"Akimoto","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Information and Systems, University of Tsukuba and RIKEN Center for Advanced Intelligence Project akimoto@cs.tsukuba.ac.jp"}]}],"member":"281","published-online":{"date-parts":[[2022,12,1]]},"reference":[{"key":"2022120106565969800_B1","doi-asserted-by":"crossref","unstructured":"Akimoto, Y., Auger, A., and Hansen, N. (2020). Quality gain analysis of the weighted recombination evolution strategy on general convex quadratic functions.Theoretical Computer Science, 832:42\u201367. Theory of Evolutionary Computation.","DOI":"10.1016\/j.tcs.2018.05.015"},{"key":"2022120106565969800_B2","doi-asserted-by":"crossref","unstructured":"Akimoto, Y., and Hansen, N. (2020). Diagonal acceleration for covariance matrix adaptation evolution strategies.Evolutionary Computation, 28(3):405\u2013435. PMID: 31120772.","DOI":"10.1162\/evco_a_00260"},{"key":"2022120106565969800_B3","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/978-3-319-45823-6_18","article-title":"An active-set evolution strategy for optimization with known constraints","volume-title":"International Conference on Parallel Problem Solving from Nature","author":"Arnold","year":"2016"},{"key":"2022120106565969800_B4","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/3071178.3071294","article-title":"Reconsidering constraint release for active-set evolution strategies","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Arnold","year":"2017"},{"key":"2022120106565969800_B5","first-page":"297","article-title":"A (1+1)-CMA-ES for constrained optimisation","volume-title":"Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference (GECCO)","author":"Arnold","year":"2012"},{"key":"2022120106565969800_B6","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1145\/2739480.2754813","article-title":"Towards an augmented Lagrangian constraint handling approach for the (1+1)-ES","volume-title":"Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO)","author":"Arnold","year":"2015"},{"key":"2022120106565969800_B7","first-page":"181","article-title":"Augmented Lagrangian constraint handling for CMA-ES\u2014Case of a single linear constraint","volume-title":"Proceedings of the 14th International Conference on Parallel Problem Solving from Nature","author":"Atamna","year":"2016"},{"key":"2022120106565969800_B8","doi-asserted-by":"crossref","unstructured":"Atamna, A., Auger, A., and Hansen, N. (2020). On invariance and linear convergence of evolution strategies with augmented Lagrangian constraint handling.Theoretical Computer Science, 832:68\u201397.","DOI":"10.1016\/j.tcs.2018.10.006"},{"key":"2022120106565969800_B9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04378-3","volume-title":"The theory of evolution strategies","author":"Beyer","year":"2001"},{"key":"2022120106565969800_B10","doi-asserted-by":"crossref","unstructured":"Chocat, R., Brevault, L., Balesdent, M., and Defoort, S. (2015). Modified covariance matrix adaptation\u2013evolution strategy algorithm for constrained optimization under uncertainty, application to rocket design.International Journal for Simulation and Multidisciplinary Design Optimization, 6:A1.26256634","DOI":"10.1051\/smdo\/2015001"},{"key":"2022120106565969800_B11","doi-asserted-by":"crossref","unstructured":"de Paula Garcia, R., de Lima, B. S. L. P., de Castro Lemonge, A. C., and Jacob, B. P. (2017). A rank-based constraint handling technique for engineering design optimization problems solved by genetic algorithms.Computers & Structures, 187:77\u201387.","DOI":"10.1016\/j.compstruc.2017.03.023"},{"key":"2022120106565969800_B12","unstructured":"Eaton, M.\n           (2007). Chapter 3: The normal distribution on a vector space, series. Lecture Notes\u2013Monograph Series. Institute of Mathematical Statistics, 53."},{"key":"2022120106565969800_B13","first-page":"2389","article-title":"Benchmarking a bi-population CMA-ES on the BBOB-2009 function testbed","volume-title":"Workshop Proceedings of the GECCO Genetic and Evolutionary Computation Conference","author":"Hansen","year":"2009"},{"key":"2022120106565969800_B14","unstructured":"Hansen, N.\n           (2016). The CMA evolution strategy: A tutorial. arXiv:1604.00772"},{"issue":"1","key":"2022120106565969800_B15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/106365603321828970","article-title":"Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)","volume":"11","author":"Hansen","year":"2003","journal-title":"Evolutionary Computation"},{"issue":"1","key":"2022120106565969800_B16","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1109\/TEVC.2008.924423","article-title":"A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion","volume":"13","author":"Hansen","year":"2009","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2022120106565969800_B17","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1162\/106365601750190398","article-title":"Completely derandomized self-adaptation in evolution strategies","volume":"9","author":"Hansen","year":"2001","journal-title":"Evolutionary Computation"},{"issue":"8","key":"2022120106565969800_B18","doi-asserted-by":"publisher","first-page":"5755","DOI":"10.1016\/j.asoc.2011.03.001","article-title":"Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems","volume":"11","author":"Hansen","year":"2011","journal-title":"Applied Soft Computing"},{"key":"2022120106565969800_B19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/CEC.2018.8477950","article-title":"A matrix adaptation evolution strategy for constrained real-parameter optimization","volume-title":"2018 IEEE Congress on Evolutionary Computation","author":"Hellwig","year":"2018"},{"issue":"2","key":"2022120106565969800_B20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1109\/TEVC.2014.2308294","article-title":"Parameter control in evolutionary algorithms: Trends and challenges","volume":"19","author":"Karafotias","year":"2015","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022120106565969800_B21","unstructured":"Kraft, D.\n           (1988). A software package for sequential quadratic programming. Technical Report DFVLR-FB 88-28, DLR German Aerospace Center---Institute for Flight Mechanics, Koln, Germany."},{"key":"2022120106565969800_B22","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/2739480.2754781","article-title":"A CMA-ES with multiplicative covariance matrix updates","volume-title":"Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO)","author":"Krause","year":"2015"},{"key":"2022120106565969800_B23","unstructured":"Le Digabel, S., and Wild, S. M. (2015). A taxonomy of constraints in simulation-based optimization. arXiv:1505.07881"},{"issue":"8","key":"2022120106565969800_B24","first-page":"8","article-title":"Problem definitions and evaluation criteria for the CEC 2006 special session on constrained real-parameter optimization","volume":"41","author":"Liang","year":"2006","journal-title":"Journal of Applied Mechanics"},{"issue":"1","key":"2022120106565969800_B25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco.1996.4.1.1","article-title":"Evolutionary algorithms for constrained parameter optimization problems","volume":"4","author":"Michalewicz","year":"1996","journal-title":"Evolutionary Computation"},{"key":"2022120106565969800_B26","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1109\/CEC.1999.781989","article-title":"An alternative constraint handling method for evolution strategies","volume":"1","author":"Oyman","year":"1999","journal-title":"Proceedings of the 1999 Congress on Evolutionary Computation"},{"issue":"3","key":"2022120106565969800_B27","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1109\/4235.873238","article-title":"Stochastic ranking for constrained evolutionary optimization","volume":"4","author":"Runarsson","year":"2000","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022120106565969800_B28","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1145\/3067695.3075986","article-title":"Modified box constraint handling for the covariance matrix adaptation evolution strategy","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Companion","author":"Sakamoto","year":"2017"},{"key":"2022120106565969800_B29","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1145\/3321707.3321717","article-title":"Adaptive ranking based constraint handling for explicitly constrained black-box optimization","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Sakamoto","year":"2019"},{"issue":"3","key":"2022120106565969800_B30","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1109\/TEVC.2018.2871944","article-title":"A covariance matrix self-adaptation evolution strategy for optimization under linear constraints","volume":"23","author":"Spettel","year":"2019","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"16","key":"2022120106565969800_B31","doi-asserted-by":"publisher","first-page":"6847","DOI":"10.1007\/s00500-018-03736-z","article-title":"A multi-recombinative active matrix adaptation evolution strategy for constrained optimization","volume":"23","author":"Spettel","year":"2019","journal-title":"Soft Computing"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/30\/4\/503\/2060164\/evco_a_00310.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/30\/4\/503\/2060164\/evco_a_00310.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T12:52:12Z","timestamp":1669899132000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/30\/4\/503\/110409\/Adaptive-Ranking-Based-Constraint-Handling-for"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":31,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,12,1]]},"published-print":{"date-parts":[[2022,12,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00310","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022]]},"published":{"date-parts":[[2022]]}}}