Bayesian optimization algorithm with community detection

Author(s)

Márcio Kassouf Crocomo

• Document type: Doctoral Thesis
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2012-10-02

Examining board members

Alexandre Cláudio Botazzo Delbem; António Gaspar Lopes da Cunha; Ricardo Hiroshi Caldeira Takahashi; Cláudio Fabiano Motta Toledo; Fernando José von Zuben

• Advisor: Alexandre Cláudio Botazzo Delbem

Abstract

ESTIMATION of Distribution Algorithms represent a research area which is showing promising results, especially in dealing with complex large scale problems. In this context, the Bayesian Optimization Algorithm (BOA) uses a multivariate model (represented by a Bayesian network) to find new solutions at each iteration. Based on BOA and in the study of community detection algorithms (to improve the constructed multivariate models), two new algorithms are proposed, named CD-BOA and StrOp. This paper indicates that both algorithms have significant advantages when compared to BOA. The CD-BOA is shown to be more flexible, being more robust when using different input parameters, what makes it easier to deal with a greater diversity of real-world problems. Unlike CD-BOA and BOA, StrOp shows that the detection of communities on a Bayesian network more adequately models decomposable problems, resulting in simpler subproblems that can be solved by a greedy search, resulting in a solution to the original problem which may be optimal in the case of perfectly decomposable problems, or a fair approximation if not. Another proposal is a new resampling technique for EDAs (called REDA). This technique results in multivariate models that are more representative, significantly improving the performance of CD-BOA and StrOp. In general, it is shown that, for the scenarios tested, CD-BOA and StrOp require lower running time than BOA. This indication is done experimentally and by the analysis of the computational complexity of the algorithms. The main features of these algorithms are evaluated for solving various problems, thus identifying their contributions to the field of Evolutionary Computation (AU)

• FAPESP's process: 10/01634-5 - BOCD - Bayesian Optimization with Community Detection: A New Estimation of Distribution Algorithm
• Grantee: Márcio Kassouf Crocomo
• Support Opportunities: Scholarships in Brazil - Doctorate