Full text
| |
| Author(s): |
Antonio Helson Mineiro Soares
Total Authors: 1
|
| 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: | 2014-06-27 |
| Examining board members: |
Alexandre Cláudio Botazzo Delbem;
António Gaspar Lopes da Cunha;
Frederico Gadelha Guimarães;
Cláudio Fabiano Motta Toledo;
Fernando José von Zuben
|
| Advisor: | Alexandre Cláudio Botazzo Delbem |
| Abstract | |
Evolutionary Algorithms that use the distribution of values of variables as probabilistic models (to direct the search process of problem solving) are called Estimation of Distribution Algorithms (EDAs). These algorithms have presented relevant performance in handling relatively complex problems. The performance of such algorithms depends directly on the quality of probabilistic models constructed that, in turn, depend on the methods of model building. The best models are often constructed by computationally complex methods, resulting in AEDs that require high running time although they are able to explore less points in the search space to find the solution of a problem. This work investigates probabilistic models obtained by algorithms of phylogeny reconstruction since some of them can produce models in an efficient way representing the main relationships among species (or among variables). This work proposes some strategies for better use of phylogeny-based models in the development of EDAs, such as the employment of a set of phylogenies instead of only one phylogeny as a model of correlation among variables, the synthesis of the most relevant information from a set of phylogenies into a structure of network and the identification groups of correlated variables from one or more networks by an algorithm of community detection. Using those advances for model construction, a new search technique, called Composed Exhaustive Search, was developed in order to find solutions for combinatorial optimization problems with different levels of difficulty. In addition, an extension of the new algorithm for multi-objective problems was proposed, which was able to determine the Pareto-optimal front of the combinatorial problems investigated. Finally, the developed EDA makes possible to obtain a trade-off in terms of number of evaluations and running time, finding results that are similar to the ones achieved by the best algorithms found for each one of these performance criteria in the problems tested. (AU) | |
| FAPESP's process: | 10/01705-0 - Estimation of Distribution Algorithms based on Phylogenetic Trees |
| Grantee: | Antonio Helson Mineiro Soares |
| Support Opportunities: | Scholarships in Brazil - Doctorate |