On the taxonomy of optimization problems under estimation of distribution algorithms
| dc.contributor.author | Echegoyen Arruti, Carlos | |
| dc.contributor.author | Mendiburu, Alexander | |
| dc.contributor.author | Santana, Roberto | |
| dc.contributor.author | Lozano, José Antonio | |
| dc.contributor.department | Estadística, Informática y Matemáticas | es_ES |
| dc.contributor.department | Estatistika, Informatika eta Matematika | eu |
| dc.date.accessioned | 2025-01-17T10:56:38Z | |
| dc.date.available | 2025-01-17T10:56:38Z | |
| dc.date.issued | 2013-09-13 | |
| dc.date.updated | 2025-01-17T10:51:07Z | |
| dc.description | Acceso cerrado a este documento. No se encuentra disponible para la consulta pública. Depositado en Academica-e para cumplir con los requisitos de evaluación y acreditación académica del autor/a (sexenios, acreditaciones, etc.). | es_ES |
| dc.description.abstract | Understanding the relationship between a search algorithm and the space of problems is a fundamental issue in the optimization field. In this paper, we lay the foundations to elaborate taxonomies of problems under estimation of distribution algorithms (EDAs). By using an infinite population model and assuming that the selection operator is based on the rank of the solutions, we group optimization problems according to the behavior of the EDA. Throughout the definition of an equivalence relation between functions it is possible to partition the space of problems in equivalence classes in which the algorithm has the same behavior. We show that only the probabilistic model is able to generate different partitions of the set of possible problems and hence, it predetermines the number of different behaviors that the algorithm can exhibit. As a natural consequence of our definitions, all the objective functions are in the same equivalence class when the algorithm does not impose restrictions to the probabilistic model. The taxonomy of problems, which is also valid for finite populations, is studied in depth for a simple EDA that considers independence among the variables of the problem. We provide the sufficient and necessary condition to decide the equivalence between functions and then we develop the operators to describe and count the members of a class. In addition, we show the intrinsic relation between univariate EDAs and the neighborhood system induced by the Hamming distance by proving that all the functions in the same class have the same number of local optima and that they are in the same ranking positions. Finally, we carry out numerical simulations in order to analyze the different behaviors that the algorithm can exhibit for the functions defined over the search space {0,1}^3 | en |
| dc.description.sponsorship | This work has been partially supported by the Saiotek and Research Groups 2007-2012 (IT-242-07) programs (Basque Government), TIN2010-14931 (Spanish Ministry of Science and Innovation) and COMBIOMED network in computational biomedicine (Carlos III Health Institute). | |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Echegoyen, C., Mendiburu, A., Santana, R., Lozano, J. A. (2013) On the taxonomy of optimization problems under estimation of distribution algorithms. Evolutionary Computation, 21(3), 471-495. https://doi.org/10.1162/EVCO_a_00095 | |
| dc.identifier.doi | 10.1162/EVCO_a_00095 | |
| dc.identifier.issn | 1063-6560 | |
| dc.identifier.uri | https://academica-e.unavarra.es/handle/2454/52983 | |
| dc.language.iso | eng | |
| dc.publisher | MIT Press Journals | |
| dc.relation.ispartof | Evolutionary Computation, 21(3), 471-495 | |
| dc.relation.projectID | info:eu-repo/grantAgreement/MICINN//TIN2010-14931/ES/ | |
| dc.relation.publisherversion | https://doi.org/10.1162/EVCO_a_00095 | |
| dc.rights | © 2012 by Massachusetts Institute of Technology | |
| dc.rights.accessRights | info:eu-repo/semantics/closedAccess | |
| dc.subject | Estimation of distribution algorithms | en |
| dc.subject | Probabilistic models | en |
| dc.subject | Factorizations | en |
| dc.subject | Rank-based selection | en |
| dc.subject | Model of infinite population | en |
| dc.subject | Equivalence classes | en |
| dc.subject | Taxonomy of functions | en |
| dc.subject | Neighborhood system | en |
| dc.subject | Dynamical systems | en |
| dc.title | On the taxonomy of optimization problems under estimation of distribution algorithms | en |
| dc.type | info:eu-repo/semantics/article | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | cb45e960-5f19-491c-ba50-555e4ce5f169 | |
| relation.isAuthorOfPublication.latestForDiscovery | cb45e960-5f19-491c-ba50-555e4ce5f169 |