Skip to main content

MODELOS GRAFICOS PROBABILISTICOS EN APRENDIZAJE AUTOMATICO Y OPTIMIZACION: IMPLEMENTACIONES EFICIENTES Y APLICACIONES

TIN2010-14931

•
Funding agency name Ministerio de Ciencia e Innovación
Funding agency acronym MICINN
Program Programa Nacional de Proyectos de Investigación Fundamental
Subprogram Subprograma de Proyectos de Investigación Fundamental no Orientada
Call Proyectos I+D
Call year 2010
State Plan 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Management unit Subdirección General de Proyectos de Investigación
Beneficiary centre UNIVERSIDAD DEL PAIS VASCO EUSKAL HERRIKO UNIBERTSITATEA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

Academica-e. Repositorio Institucional de la Universidad Pública de Navarra
Publication Artículo científico (JournalArticle)

On the taxonomy of optimization problems under estimation of distribution algorithms

  • Echegoyen Arruti, Carlos
  • Mendiburu, Alexander
  • Santana, Roberto
  • Lozano, José Antonio
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.)., 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, 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).
Academica-e. Repositorio Institucional de la Universidad Pública de Navarra
Publication Artículo científico (JournalArticle)

Toward understanding EDAs based on bayesian networks through a quantitative analysis

  • Echegoyen Arruti, Carlos
  • Mendiburu, Alexander
  • Santana, Roberto
  • Lozano, José Antonio
The successful application of estimation of distribution algorithms (EDAs) to solve different kinds of problems has reinforced their candidature as promising black-box optimization tools. However, their internal behavior is still not completely understood and therefore it is necessary to work in this direction in order to advance their development. This paper presents a methodology of analysis which provides new information about the behavior of EDAs by quantitatively analyzing the probabilistic models learned during the search. We particularly focus on calculating the probabilities of the optimal solutions, the most probable solution given by the model and the best individual of the population at each step of the algorithm. We carry out the analysis by optimizing functions of different nature such as Trap5, two variants of Ising spin glass and Max-SAT. By using different structures in the probabilistic models, we also analyze the impact of the structural model accuracy in the quantitative behavior of EDAs. In addition, the objective function values of our analyzed key solutions are contrasted with their probability values in order to study the connection between function and probabilistic models. The results not only show information about the internal behavior of EDAs, but also about the quality of the optimization process and setup of the parameters, the relationship between the probabilistic model and the fitness function, and even about the problem itself. Furthermore, the results allow us to discover common patterns of behavior in EDAs and propose new ideas in the development of this type of algorithms., This work has been partially supported by the Saiotek and Research Groups 2007-2012 (IT-242-07) programs (Basque Government), TIN2008-06815-C02-01 and Consolider Ingenio 2010 - CSD2007-00018 projects (Spanish Ministry of Science and Innovation) and COMBIOMED network in computational biomedicine (Carlos III Health Institute). Carlos Echegoyen holds a grant from UPV-EHU. The work of Roberto Santana has been partially supported by the TIN2010-20900-C04-04 and Caja Blue Brain project (Spanish Ministry of Science and Innovation).