{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:58:11Z","timestamp":1783749491737,"version":"3.55.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Surrogate-assisted evolutionary algorithms have the potential to be of high value for real-world optimization problems when fitness evaluations are expensive, limiting the number of evaluations that can be performed. In this article, we consider the domain of pseudo-Boolean functions in a black-box setting. Moreover, instead of using a surrogate model as an approximation of a fitness function, we propose to precisely learn the coefficients of the Walsh decomposition of a fitness function and use the Walsh decomposition as a surrogate. If the coefficients are learned correctly, then the Walsh decomposition values perfectly match with the fitness function, and, thus, the optimal solution to the problem can be found by optimizing the surrogate without any additional evaluations of the original fitness function. It is known that the Walsh coefficients can be efficiently learned for pseudo-Boolean functions with\n            <jats:italic>k<\/jats:italic>\n            -bounded epistasis and known problem structure. We propose to learn dependencies between variables first and, therefore, substantially reduce the number of Walsh coefficients to be calculated. After the accurate Walsh decomposition is obtained, the surrogate model is optimized using GOMEA, which is considered to be a state-of-the-art binary optimization algorithm. We compare the proposed approach with standard GOMEA and two other Walsh decomposition-based algorithms. The benchmark functions in the experiments are well-known trap functions, NK-landscapes, MaxCut, and MAX3SAT problems. The experimental results demonstrate that the proposed approach is scalable at the supposed complexity of\n            <jats:italic>O<\/jats:italic>\n            (\u2113\n            <jats:italic>log<\/jats:italic>\n            \u2113) function evaluations when the number of subfunctions is\n            <jats:italic>O<\/jats:italic>\n            (\u2113) and all subfunctions are\n            <jats:italic>k<\/jats:italic>\n            -bounded, outperforming all considered algorithms.\n          <\/jats:p>","DOI":"10.1145\/3453141","type":"journal-article","created":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T14:57:04Z","timestamp":1627570624000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["A Novel Approach to Designing Surrogate-assisted Genetic Algorithms by Combining Efficient Learning of Walsh Coefficients and Dependencies"],"prefix":"10.1145","volume":"1","author":[{"given":"Arkadiy","family":"Dushatskiy","sequence":"first","affiliation":[{"name":"Centrum Wiskunde &amp; Informatica, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tanja","family":"Alderliesten","sequence":"additional","affiliation":[{"name":"Leiden University Medical Center, the Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter A. N.","family":"Bosman","sequence":"additional","affiliation":[{"name":"Centrum Wiskunde &amp; Informatica and TU Delft"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,7,29]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330247"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3071285"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.08.011"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2502606"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531277"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1155\/2016\/9420460"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321707.3321760"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1162\/106365602760972758"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1162\/1063656043138914"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1162\/10636560151075112"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321707.3321800"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2003.03.029"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2018.02.005"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1999.7.4.377"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2933923.2933973"},{"key":"e_1_2_2_17_1","volume-title":"Advances in Soft Computing, Rajkumar Roy, Takeshi Furuhashi, and Pravir K","author":"Pelikan Martin","unstructured":"Martin Pelikan and Heinz Muehlenbein . 1999. The bivariate marginal distribution algorithm . In Advances in Soft Computing, Rajkumar Roy, Takeshi Furuhashi, and Pravir K . Chawdhry (Eds.). Springer , London , 521\u2013535. Martin Pelikan and Heinz Muehlenbein. 1999. The bivariate marginal distribution algorithm. In Advances in Soft Computing, Rajkumar Roy, Takeshi Furuhashi, and Pravir K. Chawdhry (Eds.). Springer, London, 521\u2013535."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1570018"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the Annual Conference on Genetic and Evolutionary Computation (GECCO\u201904)","author":"Streeter Matthew J.","year":"2004","unstructured":"Matthew J. Streeter . 2004 . Upper bounds on the time and space complexity of optimizing additively separable functions . In Proceedings of the Annual Conference on Genetic and Evolutionary Computation (GECCO\u201904) , Kalyanmoy Deb (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 186\u2013197. Matthew J. Streeter. 2004. Upper bounds on the time and space complexity of optimizing additively separable functions. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation (GECCO\u201904), Kalyanmoy Deb (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 186\u2013197."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1885031.1885060"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001661"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330205"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/645513.657751"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908812.2908831"},{"key":"e_1_2_2_25_1","volume-title":"Parallel Problem Solving from Nature\u2014PPSN XV, Anne Auger, Carlos M","author":"Verel S\u00e9bastien","unstructured":"S\u00e9bastien Verel , Bilel Derbel , Arnaud Liefooghe , Hern\u00e1n Aguirre , and Kiyoshi Tanaka . 2018. A surrogate model based on Walsh decomposition for pseudo-Boolean functions . In Parallel Problem Solving from Nature\u2014PPSN XV, Anne Auger, Carlos M . Fonseca, Nuno Louren\u00e7o, Penousal Machado, Lu\u00eds Paquete, and Darrell Whitley (Eds.). Springer International Publishing , Cham , 181\u2013193. S\u00e9bastien Verel, Bilel Derbel, Arnaud Liefooghe, Hern\u00e1n Aguirre, and Kiyoshi Tanaka. 2018. A surrogate model based on Walsh decomposition for pseudo-Boolean functions. In Parallel Problem Solving from Nature\u2014PPSN XV, Anne Auger, Carlos M. Fonseca, Nuno Louren\u00e7o, Penousal Machado, Lu\u00eds Paquete, and Darrell Whitley (Eds.). Springer International Publishing, Cham, 181\u2013193."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598282"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453141","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:39Z","timestamp":1750195719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3453141"],"URL":"https:\/\/doi.org\/10.1145\/3453141","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}