• 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
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.76.2020.tde-25082021-082338
Document
Auteur
Nom complet
Larissa Fernandes de Aquino
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2020
Directeur
Jury
Fontanari, Jose Fernando (Président)
Aguiar, Marcus Aloizio Martinez de
Martinez, Alexandre Souto
Titre en portugais
Algoritmos bio e socio-inspirados na busca pelos máximos globais de relevos adaptativos
Mots-clés en portugais
Algoritmos de busca estocásticos
Algoritmos evolucionários
Aprendizado por imitação
Modelo NK
Problemas de otimização
Resumé en portugais
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.
Titre en anglais
Bio and socio-inspired algorithms in the search for the global maxima of adaptive landscapes
Mots-clés en anglais
Evolutionary algorithms
Imitative learning
NK model
Optimization problems
Stochastic search algorithms
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-08-31
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.