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.

Submitted by Marta Toyoda (1144061@mackenzie.br) on 2018-09-03T21:53:40Z No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2018-09-19T18:29:59Z (GMT) No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-09-19T18:29:59Z (GMT). No. of bitstreams: 2 THIAGO DE MATTOS.pdf: 12639390 bytes, checksum: 3bda0715285cb44c6daf5752a11a5355 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Boolean networks consist of nodes that represent binary variables, which are computed as a function of the values represented by their adjacent nodes. This local processing entails global behaviors, such as the convergence to _xed points, a behavior found in the context of the density classi_cation problem, where the aim is the network's convergence to a fixed point of the prevailing node value in the initial global configuration of the network; in other words, a global decision is targeted, but according to a constrained, non-global action. In this work, we rely on evolutionary searches in order to _nd rules and network topologies with good performance in the task. All nodes' neighborhoods are assumed to be de_ned by non-regular and bidirectional links, and the Boolean function of the network initialized by the local majority rule. Firstly, is carried out a search in the space of network topologies, guided by the ω metric, related to the "small-worldness" of the networks, and then, in the space of Boolean functions, but constraining the network topologies to the best family identified in the previous experiment.. / Redes Booleanas são compostas por nós que representam variáveis binárias computadas em função dos valores representados por nós adjacentes. Esta computação local leva a comportamentos globais, como a convergência para um estado fixo da rede. Tal comportamento é utilizado na tarefa de classificação de densidade, onde procura-se a convergência dos valores de todos os nós para um ponto fixo que reflete o estado predominante presente na configuração inicial da rede, ou seja, um objetivo global restrito a ações de caráter local. Neste trabalho são efetuadas buscas evolutivas de modo a encontrar regras e topologias de redes Booleanas com boa performance na classificação de densidade. Consideram-se exclusivamente vizinhanças irregulares e bidirecionais para todos os nós, representando inicialmente a função Booleana da rede através da regra da maioria da vizinhança. Primeiramente, efetuam-se buscas evolutivas por topologias de redes guiadas pela métrica ω, esta referente à classificação de redes de mundo pequeno, e em seguida, efetuam-se buscas evolutivas no espaço de possíveis funções Booleanas utilizando as topologias de redes encontradas anteriormente.

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

No estudo de sistemas complexos interessa capturar a evolução do seu comportamento emergente segundo um conjunto de regras cujas soluções descrevem o seu estado ao longo do tempo. Uma classe particular de modelos matemáticos e computacionais que permite realizar essa investigação são os autômatos celulares. O comportamento global deles é definido apenas por regras locais, o que os tornam um modelo exemplar para estudos de sistemas complexos. Estamos interessados em um tipo especial de autômato celular: os classificadores de densidade unidimensionais. Este tipo de autômato celular está relacionado com o problema da maioria que consiste em fazer convergir uma cadeia de símbolos aleatoriamente distribuídos em um reticulado, para uma cadeia homogênea com um único símbolo final (consenso global), aquele de maioria inicial. Este consenso deve ser obtido exclusivamente a partir de interações locais entre os sítios sem a instância de um controle central. Nesta pesquisa, realizamos alguns experimentos para caracterizar um autômato celular classificador de quatro estados proposto em Gács, Kurdyumov e Levin (1978). Embora seja um classificador imperfeito, este autômato celular é significativamente tolerante a falhas quando o submetemos a níveis de ruídos não nulos. Os resultados corroboram com outros estudos que investigam a robustez deste tipo de autômato celular e lançam luz sobre o entendimento da origem da coordenação global de sistemas que exibem as características aqui descritas / In the study of complex systems we are interested in capturing their evolution of its emergent behavior under a set of rules whose solutions describe the state of the system over time. A particular class of mathematical and computational model to perform this kind of research is the cellular automaton (CA). Its global behavior is defined by local rules, which makes it an exemplary model to study complex systems. Here, we are interested in a particular type of CA: one-dimensional CA that classifies densities. This kind of CA is related to the problem of the majority task that consists of converging an array of symbols, initially randomly distributed, to a single symbol, the more frequent one in the initial configuration of the array (global consensus). This consensus must be obtained solely out of local interactions, without the instance of a central control. In this research, we conducted some experiments to characterize a four-state CA classifier proposed in Gács, Kurdyumov e Levin (1978). While it is an imperfect classifier, this CA is significantly fault tolerant when submitted to the levels of non-zero noise. Our results corroborate other studies that had investigated the robustness of this type of CA, and shed light on the understanding of the origin of global coordinated systems that exhibit the characteristics described here

Made available in DSpace on 2016-03-15T19:37:38Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1720671 bytes, checksum: aa67cff2cc9f7abe5fb3b48bead6b38d (MD5) Previous issue date: 2011-08-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos (AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:37:41Z (GMT). No. of bitstreams: 1 Mateus Interciso.pdf: 1732926 bytes, checksum: f29787f421b0b5f1d6dedd2c1eb4e0fc (MD5) Previous issue date: 2011-09-23 / Fundo Mackenzie de Pesquisa / The search for cellular automata (CAs) rules capable of executing a determined task can be impossible to be achieve manually, given the huge size of the search space usually involved. A method for being able to find rules capable of executing the task at hand has been the usage of genetic algorithms (GAs) to evolve an initially random population, until the desired objective; each individual of those GAs are usually represented by a candidate transition rule. In problems formulated for the resolution by a binary cellular automaton, a recently used modification on the representation of the individuals was the usage of templates with the presence of an extra symbol, capable of representing every other valid symbol. Such schema of ternary representation is used on the present work, aiming for it s net effect on the search process on the GAs. This study is made for two classical tasks of binary unidimensional cellular automata, the density classification task and the parity problem, both traditional in the context of using GAs for searching transition rules with high performance. By comparing the results of the original GAs and their versions implemented with the ternary representation, it s shown that the ternary representation is able to improve the quality of the results. Particularly, it is analized the condition in which the usage of the ternary representation presents to be more effective, as well as some effects of the actual implementation. Possible future works are presented at the end. / A busca por regras de autômatos celulares que efetuem corretamente uma determinada tarefa pode ser impossível de ser efetuada manualmente, dado o enorme tamanho dos espaços de busca usualmente envolvidos. Uma forma para conseguir encontrar boas regras para a execução do problema em questão tem sido a utilização de algoritmos genéticos(AGs) para evoluir uma população inicialmente aleatória, até o objetivo desejado; nesses AGs cada indivíduo é normalmente representado como uma regra de transição candidata. Em problemas formulados para resolução por um autômato celular binário, uma alteração recentemente estudada na literatura para a representação dos indivíduos foi a utilização de templates (moldes) com a presença de um símbolo extra, capaz de representar os demais símbolos. Tal esquema de representação ternária é utilizada no presente trabalho, visando avaliar seu efeito no processo de busca realizado por AGs. O estudo é feito para duas tarefas clássicas de autômatos celulares unidimensionais binários, a tarefa de classificação da densidade e o problema da paridade, ambas tradicionais no contexto da utilização de AGs para encontrar regras de transição com alta performance. Ao comparar os resultados de AGs originais encontrados na literatura com suas versões implementadas com representação ternária, mostra-se que a representação ternária é capaz de melhorar a qualidade dos resultados. Em particular, analisam-se condições em que o uso da representação ternária se mostra mais efetivo, bem como apontam-se efeitos de alguns aspectos de implementação. Possíveis trabalhos futuros pertinentes ao estudo são discutidos ao final.

Made available in DSpace on 2016-03-15T19:38:09Z (GMT). No. of bitstreams: 1 Fernando Faria.pdf: 516281 bytes, checksum: fc784946b9c2438b3c18c34593a182cb (MD5) Previous issue date: 2008-03-11 / Wolfram Research, Inc. / Cellular automata are discrete dynamical systems composed of simple, locally connected structures (the cells), general in terms of their computational power, and that display complex patterns of behaviour. The purpose of this work was to expand previous studies by Zanon (2006), on non-uniform, one-dimensional cellular automata with nonlocal neighbourhood, in order to verify the existence of rules of these kinds of automata to solve the density classification task, that is, the determination of the predominant bit in a binary string. Our concern here was to look for solutions of the problem mainly by evolutionary computation means, to solve it in a non-trivial fashion, i.e., without including in the solution the majority rule over the entire lattice, and, at the same time, with the target of inferring common features for the solutions that would be found. The results achieved led to an expansion in the quantity of perfect solutions available in the literature, but it became clear that all of them have at least one of the rules involved able to account for the entire lattice at once, an evidence that solutions without rules with global action may not exist. Furthermore, the following observations have been made for the type of automata we considered: even distinct automata may have the same temporal evolution; a certain degree of flexibility is allowed in the total balancing of the rules present in a solution of the density classification task; and, in principle, no common patterns seem to exist between solutions for lattices with 3 and 5 cells, thereby suggesting the impossibility of constructing a solution to the problem from another of a smaller lattice. / Autômatos celulares são sistemas dinâmicos discretos, formados por estruturas simples (as células) conectadas localmente entre si, gerais em termos de seu poder computacional, e que apresentam padrões de comportamento bastante complexos. O intuito deste trabalho foi expandir estudos anteriores de Zanon (2006), sobre autômatos celulares unidimensionais não-uniformes, com vizinhança não-local, visando verificar a existência de autômatos desse tipo na resolução da tarefa da classificação de densidade, isto é, a determinação do bit predominante em uma cadeia binária. Interessou-nos aqui descobrir soluções do problema principalmente por meio de buscas evolutivas, resolvê-lo de forma não trivial, isto é, sem a necessidade da regra da maioria sobre todo o reticulado, e objetivando inferir características necessárias para as soluções que viessem a resolver o problema. Os resultados obtidos levaram a uma expansão da quantidade de soluções perfeitas reportadas na literatura, mas observou-se que todas elas contém pelo menos uma das regras envolvidas tomando todo o reticulado como base de ação, uma evidência da impossibilidade de existir soluções sem regras individuais de ação global. Adicionalmente, as seguintes constatações foram feitas para os autômatos celulares do tipo considerado: mesmo autômatos distintos entre si podem ter a mesma evolução temporal; uma flexibilização do balanceamento total das regras na solução do problema da classificação de densidade é conseguida; e, em princípio, não há padrões nas soluções perfeitas para reticulados de 3 e 5 células, sugerindo a impossibilidade de se construir uma solução a partir de outra de menor tamanho de reticulado.