• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.76.2020.tde-25082021-082338
Documento
Autor
Nombre completo
Larissa Fernandes de Aquino
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2020
Director
Tribunal
Fontanari, Jose Fernando (Presidente)
Aguiar, Marcus Aloizio Martinez de
Martinez, Alexandre Souto
Título en portugués
Algoritmos bio e socio-inspirados na busca pelos máximos globais de relevos adaptativos
Palabras clave en portugués
Algoritmos de busca estocásticos
Algoritmos evolucionários
Aprendizado por imitação
Modelo NK
Problemas de otimização
Resumen en portugués
Algoritmos de otimização que imitam processos naturais, ditos algoritmos bio-inspirados, prometem encontrar soluções ótimas ou quase-ótimas de problemas de otimização sem utilizar praticamente nenhuma informação acerca desses problemas. Outros exemplos bem menos conhecidos de algoritmos de propósito geral são os algoritmos que imitam processos sociais ou culturais. Isso parece ser paradoxal, já que o modo como humanos solucionam problemas difíceis é exatamente através da colaboração em forças-tarefas e, portanto, algoritmos que imitam a forma como interagimos deveriam ser tão ou mais eficientes e populares quanto os algoritmos bio-inspirados. Nessa dissertação vamos estudar o desempenho de um algoritmo baseado na interação social, o aprendizado por imitação, e de dois tipos de algoritmos evolucionários, o algoritmo genético sexuado e o assexuado, na busca pelo máximo global de relevos de fitness ou relevos adaptativos gerados pelo modelo NK. A variação dos parâmetros N e K desse modelo permite a geração de relevos com diferentes dimensionalidades e rugosidades. A medida de desempenho dos algoritmos é proporcional ao número total de atualizações realizadas nos agentes até que o máximo global seja encontrado. A base de comparação é o desempenho da busca cega, onde os agentes são atualizados de modo completamente aleatório. Encontramos que mesmo para relevos sem máximos locais, os algoritmos evolucionários não têm um desempenho muito superior ao da busca cega devido, provavelmente, à estocasticidade do operador de seleção que nem sempre seleciona o agente de maior fitness. Como no aprendizado por imitação a escolha do agente de maior fitness, o agente modelo, é determinística o seu desempenho é muito superior ao dos algoritmos evolucionários nesse tipo de relevo. O preço a pagar é que o aprendizado por imitação é muito mais suscetível a ficar preso em máximos locais do que os outros algoritmos, gerando desempenhos catastróficos que lembram o fenômeno do pensamento de grupo da psicologia social. Entretanto, se os parâmetros do aprendizado por imitação forem ajustados de forma ótima, esse algoritmo é superior aos outros também na busca em relevos rugosos. Finalmente, para relevos muito rugosos, encontramos que a busca cega é superior aos algoritmos cooperativos considerados.
Título en inglés
Bio and socio-inspired algorithms in the search for the global maxima of adaptive landscapes
Palabras clave en inglés
Evolutionary algorithms
Imitative learning
NK model
Optimization problems
Stochastic search algorithms
Resumen en inglés
Optimization algorithms that mimic processes in nature, so-called bio-inspired algorithms, promise to deliver optimal or near-optimal solutions using hardly any information on the optimization problems they are set to tackle. Another much less known class of general- purpose search algorithms are the algorithms that mimic social or cultural processes. This seems paradoxical as the way humans tackle difficult problems is through the cooperative effort in task-forces and so algorithms inspired on the manner they interact should be more or at least as efficient and popular as the bio-inspired algorithms. In this dissertation, we study the performances of a social-inspired algorithm the imitative learning search as well as of asexual and sexual variants of evolutionary algorithms in finding the global maxima of fitness or adaptive landscapes generated by the NK model. The variation of the parameters N e K of that model allows the generation of landscapes of different dimensionalities and ruggedness. The performance measure is proportional to the total number of agent updates required by the algorithms to find the global maximum. The baseline performance is set by the blind search, where the agents are updated in a completely random manner. We find that even for landscapes that exhibit a single maximum, the evolutionary algorithms do not perform much better than the blind search due to the stochastic effects of the selection operator, that is not guaranteed to select the fittest agent. Since in the imitative learning the choice of the fittest agent in the population is deterministic, its performance is much superior to those of the other algorithms in this type of landscape. The tradeoff is that the imitative learning is more prone to be trapped in local maxima than the evolutionary algorithms, leading to catastrophic performances that are reminiscent of the groupthink phenomenon of social psychology. However, if the parameters of the imitative learning are finely tunned, it outperforms the other algorithms in the case of rugged landscapes as well. Finally, for too rugged landscapes, the blind search beats all the cooperative algorithms considered.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-08-31
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.