{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:53:21Z","timestamp":1773798801948,"version":"3.50.1"},"reference-count":39,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> This article investigates Gray Box Optimization for pseudo-Boolean optimization problems composed of M subfunctions, where each subfunction accepts at most k variables. We will refer to these as Mk Landscapes. In Gray Box Optimization, the optimizer is given access to the set of M subfunctions. We prove Gray Box Optimization can efficiently compute hyperplane averages to solve non-deceptive problems in [Formula: see text] time. Bounded separable problems are also solved in [Formula: see text] time. As a result, Gray Box Optimization is able to solve many commonly used problems from the evolutional computation literature in [Formula: see text] evaluations. We also introduce a more general class of Mk Landscapes that can be solved using dynamic programming and discuss properties of these functions. For certain type of problems Gray Box Optimization makes it possible to enumerate all local optima faster than brute force methods. We also provide evidence that randomly generated test problems are far less structured than those found in real-world problems. <\/jats:p>","DOI":"10.1162\/evco_a_00184","type":"journal-article","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T19:58:00Z","timestamp":1461787080000},"page":"491-519","source":"Crossref","is-referenced-by-count":54,"title":["Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT)"],"prefix":"10.1162","volume":"24","author":[{"given":"L. Darrell","family":"Whitley","sequence":"first","affiliation":[{"name":"Department of Computer Science, Colorado State University, USA"}]},{"given":"Francisco","family":"Chicano","sequence":"additional","affiliation":[{"name":"Department of Lenguajes y Ciencias de la Computaci\u00f3n, University of M\u00e1laga, Spain"}]},{"given":"Brian W.","family":"Goldman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Michigan State University, USA"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31612-8_31"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00341-9"},{"key":"B3","first-page":"331","volume-title":"International Joint Conference on Artificial Intelligence (IJCAI)","author":"Cheeseman P.","year":"1991"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598304"},{"key":"B5","volume-title":"Introduction to algorithms, 2nd edition","author":"Cormen T.","year":"1990"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(90)90142-Y"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-094832-4.50012-X"},{"key":"B9","first-page":"7:249","author":"Frank J.","year":"1997","journal-title":"Journal of Artificial Intelligence Research"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45105-6_106"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2002.1006234"},{"key":"B12","first-page":"3:129","author":"Goldberg D.","year":"1989","journal-title":"Complex Systems"},{"key":"B13","volume-title":"Genetic algorithms in search, optimization and machine learning","author":"Goldberg D","year":"1989"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-30698-8_11"},{"key":"B15","first-page":"14:359","author":"Hammer P. L.","year":"1963","journal-title":"Studii si cercetari matematice"},{"key":"B16","first-page":"437","volume-title":"Cliques, Coloring and Satisfiability. American Mathematical Society, 1996. Proceedings of the Second DIMACS Implementation Challenge","author":"Hampson S.","year":"1993"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258536"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1162\/106365602760972758"},{"key":"B19","volume-title":"Adaptation in natural and artificial systems","author":"Holland J","year":"1975"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1162\/106365600568220"},{"key":"B21","volume-title":"Stochastic local search: Foundations and applications","author":"Hoos H. H.","year":"2005"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17339-4"},{"key":"B23","first-page":"128:11","author":"Kauffman S.","year":"1987","journal-title":"Journal of Theoretical Biology"},{"key":"B24","first-page":"185","author":"Kautz H.","year":"2008","journal-title":"Handbook of satisfiability"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"B26","first-page":"459","volume-title":"Proceedings of the 10th National Conference on Artificial Intelligence","author":"Mitchell D.","year":"1992"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15844-5_11"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1145\/2739480.2754657"},{"key":"B29","first-page":"392","volume-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI\u201998)","author":"Rana S.","year":"1998"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056920"},{"key":"B31","first-page":"177","volume-title":"Institute for Mathematics and its Applications Workshop on Evolutionary Algorithms","author":"Rana S.","year":"1998"},{"key":"B32","first-page":"565","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)","author":"Schumacher C.","year":"2001"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03751-1_4"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1145\/2725494.2725497"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1145\/2739480.2754809"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330351"},{"key":"B38","first-page":"166","volume-title":"International Conference on Genetic Algorithms","author":"Whitley D.","year":"1991"},{"key":"B39","first-page":"940","volume-title":"Proceedings of AAAI-2013","author":"Whitley D.","year":"2013"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/4235.887236"},{"key":"B41","first-page":"34:871","author":"Young A.","year":"1984","journal-title":"Journal of Statistical Physics"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:58:49Z","timestamp":1615586329000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/24\/3\/491-519\/1027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1162\/EVCO_a_00184"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00184","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}