{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,24]],"date-time":"2024-05-24T07:48:36Z","timestamp":1716536916637},"reference-count":20,"publisher":"MIT Press - Journals","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p> In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure. <\/jats:p>","DOI":"10.1162\/1063656053583423","type":"journal-article","created":{"date-parts":[[2005,4,6]],"date-time":"2005-04-06T13:33:50Z","timestamp":1112794430000},"page":"125-143","source":"Crossref","is-referenced-by-count":28,"title":["Space Complexity of Estimation of Distribution Algorithms"],"prefix":"10.1162","volume":"13","author":[{"given":"Yong","family":"Gao","sequence":"first","affiliation":[{"name":"Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, T6G 2E8,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Culberson","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada, T6G 2E8,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"p_2","first-page":"19","author":"Bodlaender H. L.","year":"1997","journal-title":"Lectures Notes in Computer Science 1295, pages"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1998.6.2.109"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00059-4"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1080\/00018730110112519"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1081"},{"key":"p_12","first-page":"848","author":"Gao Y.","year":"2003","journal-title":"LNCS 2723, pages"},{"key":"p_14","first-page":"56","author":"Goldberg D.","year":"1993","journal-title":"Intern. Conf. on Genetic Algorithms, pages"},{"key":"p_16","first-page":"1003","author":"Heckendorn R.","year":"2003","journal-title":"LNCS 2723, pages"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04448-3_8"},{"key":"p_18","first-page":"527","author":"Kauffman S.","year":"1989","journal-title":"Stein, D. L., editor, Lectures in the Sciences of Complexity, Santa Fe Institute Studies in the Sciences of Complexity, pages"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1126\/science.264.5163.1297"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1109\/72.623217"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00149-9"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022221005097"},{"key":"p_28","first-page":"19","volume":"7","author":"M\u00fchlenbein H.","year":"1999","journal-title":"Journal of Computing and Information Technology"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009689913453"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585893"},{"key":"p_34","first-page":"367","author":"Yu T.","year":"2004","journal-title":"LNCS 3103, pages"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/1063656053583423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:30:58Z","timestamp":1615584658000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/13\/1\/125-143\/1197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1162\/1063656053583423"],"URL":"https:\/\/doi.org\/10.1162\/1063656053583423","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]}}}