Full text
| |
| Author(s): |
Jean Paulo Martins
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: | 2015-05-13 |
| Examining board members: |
Alexandre Cláudio Botazzo Delbem;
Carlos Manuel Mira da Fonseca;
Carlos Dias Maciel;
Maristela Oliveira dos Santos;
Elizabeth Fialho Wanner
|
| Advisor: | Alexandre Cláudio Botazzo Delbem |
| Abstract | |
The supposed ubiquity of nearly-decomposable systems was interpreted by Holland (1975) as the rationale for the performance of Genetic Algorithms (GAs), the Building Block (BB) hypothesis. His seminal studies suggest more efficient GAs as viable, but only later on his ideas have become practically tangible in the context of Estimation of Distribution Algorithms (EDAs). EDAs employ probabilistic modeling so as to infer properties of the search space (BBs) that could be useful for the effectiveness of reproduction operators. In both, single- and multi-objective contexts, EDAs have emerged on the assumption there is a correlation between how much information a model can conceive and how effective reproduction operators can be. However, more recent results suggest the difficulties in producing accurate linkage models can prevent such a relation to be true. In other words, for some optimization problems linkage learning might not be able to produce accurate linkage models, hence EDAs would not outperform GAs. This thesis addresses the limits of linkage learning in the context of single- and bi-objective problems, regarding the influence of multimodality on the accuracy of the linkage models and the efficiency of EDAs. A theoretical analysis was performed in terms of additively separable functions and general conclusions are assessed through experimentation with instances of the NK-model and the Multidimensional Knapsack Problem (MKP). The results indicated that the accuracy of the linkage models tends to decrease as a result of increasing multimodality, which weakens pairwise dependencies and might lead to pairwise independence in extreme cases. Since most EDAs rely on bivariate statistics to estimate multivariate distributions, their applicability is limited to optimization problems within a certain range of multimodality. In multi-objective problems, on the other hand, some EDAs have shown better performance than GAs, which seemed as a contradiction since multi-objective problems are inherently multimodal. Our results suggest that in such cases the correlation among the objective functions becomes statistically evident, as a consequence, linkage learning models such correlation instead of problems substructures, which is useful to obtain a better exploration of extreme regions of the objective space. (AU) | |
| FAPESP's process: | 11/07792-4 - Linkage-learning Analysis and Development of Model-based Multiobjective Genetic Algorithms |
| Grantee: | Jean Paulo Martins |
| Support Opportunities: | Scholarships in Brazil - Doctorate |