• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.76.2020.tde-25082021-082338
Document
Author
Full name
Larissa Fernandes de Aquino
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2020
Supervisor
Committee
Fontanari, Jose Fernando (President)
Aguiar, Marcus Aloizio Martinez de
Martinez, Alexandre Souto
Title in Portuguese
Algoritmos bio e socio-inspirados na busca pelos máximos globais de relevos adaptativos
Keywords in Portuguese
Algoritmos de busca estocásticos
Algoritmos evolucionários
Aprendizado por imitação
Modelo NK
Problemas de otimização
Abstract in Portuguese
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.
Title in English
Bio and socio-inspired algorithms in the search for the global maxima of adaptive landscapes
Keywords in English
Evolutionary algorithms
Imitative learning
NK model
Optimization problems
Stochastic search algorithms
Abstract in English
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.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2021-08-31
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2021. All rights reserved.