Algoritmos bio e socio-inspirados na busca pelos máximos globais de relevos adaptativos

• Ano de defesa: 2020
• Autor(a) principal: Aquino, Larissa Fernandes de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Algoritmos de busca estocásticos; Algoritmos evolucionários; Aprendizado por imitação; Evolutionary algorithms; Imitative learning; Modelo NK; NK model; Optimization problems; Problemas de otimização; Stochastic search algorithms
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/76/76131/tde-25082021-082338/

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.