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.

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.