MELO, Hygor Piaget Monteiro. Algoritmo genético para a solução do problema da maioria. 2011. 76 f. Dissertação (Mestrado em Física) - Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2011. / Submitted by francisco lima (admir@ufc.br) on 2014-03-18T13:18:48Z No. of bitstreams: 1 2011_dis_hpmmelo.pdf: 20960285 bytes, checksum: d491fad40b382e9aa0090b21e84cb0ac (MD5) / Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2014-03-18T22:06:36Z (GMT) No. of bitstreams: 1 2011_dis_hpmmelo.pdf: 20960285 bytes, checksum: d491fad40b382e9aa0090b21e84cb0ac (MD5) / Made available in DSpace on 2014-03-18T22:06:36Z (GMT). No. of bitstreams: 1 2011_dis_hpmmelo.pdf: 20960285 bytes, checksum: d491fad40b382e9aa0090b21e84cb0ac (MD5) Previous issue date: 2011 / Many natural and social systems exhibit globally organized behavior without the aid of a centralized control. Examples of such decentralized systems include conventions and norms, social learning in animals and humans, as well as fads, rumors and revolts. Examples are also abundant in biology: the evasive behavior of animals in large groups, such as fish and birds, show a great synchronicity even in the absence of an leader. In order to understand these decentralized systems, one must first understand strategies for global coordination that use only local information. This work explores the use of Genetic Algorithms in the creation of naturally efficient strategies in noisy environments. Genetic Algorithms are an important new tool in problem solving, and offer insight into how evolution may work. By using what is known about genetic algorithms, one can discover more about evolution and its mechanisms. The density classification task is used here to test strategy success, and revealed to be a good test for system-wide coordination and global information processing. Since it is very difficult to evolve highly fit rules when the number of neighbors $k$ is greater than 5, this suggests that evolution may build complex solutions based on solutions to simpler problems. Using this idea, we propose a method to promote rules increasing $k$. Based on the evolution of initial rules with few neighbors and using noise as evolutionary pressure, we were able to find efficient rules for a large number of neighbors, under the condition of a very high noise level. We find that the evolved rules are more robust to noisy environment than the majority rule. This increased efficiency at higher noise levels can be explained in terms of the larger weight given by these rules to the information of the evolving agent itself (not influenced by noise) than to the information obtained from its neighbors. As a consequence, the agents using these evolved rules tend to keep their own states, unless the great majority of their neighbors disagree with them, showing a persistence behavior that can be seen in social experiments. / Muitos sistemas naturais e sociais exibem comportamento globalmente organizado sem a presença de um controle central. Exemplos incluem convenções e normas, aprendizado social em animais e humanos, assim como modismos, boatos e revoltas. Exemplos em biologia também são abundantes: o comportamento evasivo de animais em grandes grupos, como peixes e pássaros, mostram uma grande sincronia mesmo na ausência de um líder. A fim de entender esses sistemas descentralizados, precisamos estudar primeiramente estratégias de coordenação global que utilizam apenas informações locais. Esse trabalho explora o uso do Algoritmo Genético na obtenção de estratégias naturalmente eficientes em ambientes ruidosos. O Algoritmo Genético é uma nova ferramenta importante na solução de problemas deste tipo, e oferece indícios de como a evolução deve atuar. Usando o que é conhecido sobre Algoritmos Genéticos, podemos descobrir mais sobre a evolução e seus mecanismos. A classificação por densidade é utilizada para testar o sucesso de estratégias, pois trata-se de um bom teste para coordenação global e processamento global de informações. Como é muito difícil evoluir regras com grande eficiência quando o número de vizinhos $k$ for maior que 5, isso sugere que a evolução deve construir soluções complexas baseadas em soluções de problemas simples. Usando essa ideia propomos um método de promover as regras aumentando o $k$. Com base na evolução inicial de regras com poucos vizinhos e usando o ruído como "pressão" evolutiva, nós fomos capazes de achar regras eficientes para um grande número de vizinhos, submetidas a condição de um alto nível de ruído. Achamos que as regras evoluídas são mais robustas a ambientes ruidosos do que a regra da maioria. A alta eficiência para grandes valores do ruído pode ser explicada em termos do maior peso dado por essas regras à informação da própria célula (não influenciada pelo ruído) do que a informação obtida através vizinhos. Como consequência, as células que empregam essas regras evoluídas tendem a manter seus próprios estados, até que uma grande maioria dos vizinhos discordem delas, mostrando um comportamento de persistência que pode ser encontrado em experimentos sociais.