Echegoyen Arruti, CarlosMendiburu, AlexanderSantana, RobertoLozano, José Antonio2025-01-172025-01-172013-09-13Echegoyen, 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_000951063-656010.1162/EVCO_a_00095https://academica-e.unavarra.es/handle/2454/52983Acceso 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.).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}^3application/pdfeng© 2012 by Massachusetts Institute of TechnologyEstimation of distribution algorithmsProbabilistic modelsFactorizationsRank-based selectionModel of infinite populationEquivalence classesTaxonomy of functionsNeighborhood systemDynamical systemsOn the taxonomy of optimization problems under estimation of distribution algorithmsinfo:eu-repo/semantics/article2025-01-17info:eu-repo/semantics/closedAccess