A suposta ubiquidade de sistemas decomponíveis foi interpretada por Holland (1975) como o principal motivo para o desempenho dos algoritmos genéticos (Genetic Algorithms (GAs)). A hipótese de Building Blocks (BBs) sugere que algoritmos genéticos mais eficientes poderiam ser implementados, contudo, apenas anos depois essas ideias puderam ser avaliadas experimentalmente no contexto de algoritmos de estimação de distribuição (Estimation of Distribution Algorithms (EDAs)). EDAs utilizam modelos probabilísticos, estimados a partir da população, para inferir características do espaço de busca que poderiam ser utilizadas para implementar operadores de reprodução mais eficazes. Tanto em problemas mono- quanto multi-objetivo, EDAs emergiram sob a premissa de que a eficácia dos operadores de reprodução seria proporcional à representatividade dos modelos probabilísticos utilizados. No entanto, estudos recentes tem demonstrado que a dificuldade em se construir modelos confiáveis pode tornar essa premissa inviável. Ou seja, para certos problemas de otimização os modelos probabilísticos utilizados seriam, em geral, de baixa qualidade e, portanto, não produziriam operadores eficazes. Esta tese trata das limitações encontradas na construção de modelos probabilísticos (linkage learning) sob a perspectiva da multimodalidade dos problemas em questão. A análise teórica considerou problemas aditivamente separáveis, enquanto a generalização das conclusões foi investigada em instâncias do modelo NK-landscapes e do problema da mochila multidimensional (Multidimensional Knapsack Problem (MKP)). Os resultados indicaram que a acurácia dos modelos probabilísticos é se relaciona inversamente ao grau de multimodalidade da função objetivo e que, em casos de extrema multimodalidade a construção de modelos probabilísticos confiáveis pode ser tornar infactível. Este resultado poderia inviabilizar o uso de EDAs no contexto multiobjetivo, devido a intrínseca multimodalidade de tais problemas. No entanto, observou-se que apesar da ausência de estatísticas confiáveis sobre cada uma das funções objetivo, a correlação entre elas se torna estatisticamente observável e útil aos operadores de reprodução na manutenção da diversidade e controle convergência da população. / 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.

A suposta ubiquidade de sistemas decomponíveis foi interpretada por Holland (1975) como o principal motivo para o desempenho dos algoritmos genéticos (Genetic Algorithms (GAs)). A hipótese de Building Blocks (BBs) sugere que algoritmos genéticos mais eficientes poderiam ser implementados, contudo, apenas anos depois essas ideias puderam ser avaliadas experimentalmente no contexto de algoritmos de estimação de distribuição (Estimation of Distribution Algorithms (EDAs)). EDAs utilizam modelos probabilísticos, estimados a partir da população, para inferir características do espaço de busca que poderiam ser utilizadas para implementar operadores de reprodução mais eficazes. Tanto em problemas mono- quanto multi-objetivo, EDAs emergiram sob a premissa de que a eficácia dos operadores de reprodução seria proporcional à representatividade dos modelos probabilísticos utilizados. No entanto, estudos recentes tem demonstrado que a dificuldade em se construir modelos confiáveis pode tornar essa premissa inviável. Ou seja, para certos problemas de otimização os modelos probabilísticos utilizados seriam, em geral, de baixa qualidade e, portanto, não produziriam operadores eficazes. Esta tese trata das limitações encontradas na construção de modelos probabilísticos (linkage learning) sob a perspectiva da multimodalidade dos problemas em questão. A análise teórica considerou problemas aditivamente separáveis, enquanto a generalização das conclusões foi investigada em instâncias do modelo NK-landscapes e do problema da mochila multidimensional (Multidimensional Knapsack Problem (MKP)). Os resultados indicaram que a acurácia dos modelos probabilísticos é se relaciona inversamente ao grau de multimodalidade da função objetivo e que, em casos de extrema multimodalidade a construção de modelos probabilísticos confiáveis pode ser tornar infactível. Este resultado poderia inviabilizar o uso de EDAs no contexto multiobjetivo, devido a intrínseca multimodalidade de tais problemas. No entanto, observou-se que apesar da ausência de estatísticas confiáveis sobre cada uma das funções objetivo, a correlação entre elas se torna estatisticamente observável e útil aos operadores de reprodução na manutenção da diversidade e controle convergência da população. / 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.

Submitted by Maria Bernadete Dos Santos (mariabpds@id.uff.br) on 2017-09-27T17:53:27Z No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação Alexandre L. Torres.pdf: 2113771 bytes, checksum: e92b2eb0221ae3372965ba2accb94702 (MD5) Produto Final - Alexandre L. Torres.pdf: 357939 bytes, checksum: 0c6eccc1f4a85d82d3cd61292b293898 (MD5) / Approved for entry into archive by Biblioteca Central do Valonguinho Biblioteca Central do Valonguinho (bcv@ndc.uff.br) on 2017-10-03T17:14:22Z (GMT) No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação Alexandre L. Torres.pdf: 2113771 bytes, checksum: e92b2eb0221ae3372965ba2accb94702 (MD5) Produto Final - Alexandre L. Torres.pdf: 357939 bytes, checksum: 0c6eccc1f4a85d82d3cd61292b293898 (MD5) / Made available in DSpace on 2017-10-03T17:14:22Z (GMT). No. of bitstreams: 3 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação Alexandre L. Torres.pdf: 2113771 bytes, checksum: e92b2eb0221ae3372965ba2accb94702 (MD5) Produto Final - Alexandre L. Torres.pdf: 357939 bytes, checksum: 0c6eccc1f4a85d82d3cd61292b293898 (MD5) / Este trabalho relata uma metodologia ativa para o Ensino de Ligações Químicas: Composição de paródias musicais como uma proposta de potencializar a aprendizagem significativa. Trata-se de uma pesquisa de natureza qualitativa, do tipo pesquisa-ação, e utilizou, para o levantamento de dados e para a tomada de decisões no decorrer do processo de pesquisa, questionários, observações da atividade orientada, depoimento dos educandos durante e após a elaboração das paródias musicais, fotos, vídeos e análise das letras das paródias. A pesquisa foi realizada no Colégio Pedro II, Campus Niterói, Rio de Janeiro e aplicada no 1º. ano do Ensino Médio Regular do ano letivo de 2016. Os resultados obtidos indicam que a construção de paródias musicais favoreceu o processo de ensino-aprendizagem, sendo esse recurso didáticos visto pelos alunos como alternativa para facilitar a aprendizagem. Consideramos que este trabalho pode ser replicado, abrindo possibilidades de novas criações e pesquisas sobre o emprego de estratégias de metodologias ativas no ensino de Ciências da Natureza. Com o intuito de incentivar esta aplicação, elaboramos, como produto dessa dissertação, uma videoaula onde é mostrada a aplicação da metodologia e com orientações sobre a forma de utilização. / This paper reports an active methodology for the Teaching of Chemical Bonds: Composition of musical parodies as a proposal to potentiate meaningful learning. For this purpose we used a qualitative methodology and, for data collection and decision making during the research process, questionnaires, observations of the activity oriented, testimony of the students during and after the elaboration of the musical parodies, photos, videos and analysis of the letters of the parodies. The research was carried out at Pedro II School, Niterói, Campus, Rio de Janeiro and applied in the 1st. Year of Regular High School during the academic year of 2106. The results indicate that the construction of musical parodies favors facilitate the teaching-learning process. We consider that this work can be replicated and open possibilities of new creations and research on the use of active methodologies for teaching of Natural Sciences. In order to stimulate this application, we elaborate, as a product of this dissertation, a videoconference showing the application of the methodology and guidelines on how to use it.