ads:
UNIVERSIDADE PRESBITERIANA MACKENZIE
PROGRAMA DE PÓS-GRADUAÇÃO
ENGENHARIA ELÉTRICA
Autômatos Celulares Não-Uniformes, com
Conexões Não-Locais, na Classificação de
Densidade
Fernando Faria
Texto de dissertação apresentado ao
Programa de Pós-Graduação em
Engenharia Elétrica como parte das
exigências do exame para obtenção
do título de Mestre em Engenharia
Elétrica.
Orientador: Prof. Dr. Pedro Paulo Balbi de Oliveira
São Paulo – SP
Janeiro/2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
2
Dedicatória
À minha
namorada
, amiga e
companheira Rachel
, pelo apoio,
compreensão e incentivo ao meu
aprimoramento profissional.
Aos meus
pais Joaquim e Benedita
,
pela minha formação moral e intelectual,
pelo amor e carinho recebidos durante toda
minha vida.
À
família Fumo
pelo apoio dado
neste trabalho.
Aos meus irmãos, meu
tio
Izaías
,
primos e amigos que sempre me apoiaram.
ads:
3
Agradecimentos
Aos familiares, amigos e todos aqueles que me acompanharam e ainda estão
comigo nesta jornada da vida.
Ao MackPesquisa, o Fundo Mackenzie de Pesquisa, pelo apoio financeiro que me
foi concedido, através de Reserva Técnica, que permitiu minha participação no evento
internacional NKS Summer School 2007, proporcionando maior conhecimento sobre
autômatos celulares, contribuindo de forma significativa ao trabalho.
Este trabalho contou com auxílios de pesquisa da FAPESP, através do Processo
2005/04696-3, e da Wolfram Research, através do Mathematica Academic Grant 1149,
concedidos a meu orientador.
Em especial ao professor Dr. Pedro Paulo, meu orientador, que conduziu a
orientação deste trabalho.
4
Sumário
LISTA DE FIGURAS..........................................................................................................6
LISTA DE TABELAS.........................................................................................................7
LISTA DE ABREVIAÇÕES ..............................................................................................9
RESUMO............................................................................................................................10
ABSTRACT .......................................................................................................................11
CAPÍTULO 1 - INTRODUÇÃO......................................................................................12
CAPÍTULO 2 – AUTÔMATOS CELULARES E ALGORITMOS GENÉTICOS....14
2.1 Algoritmos Genéticos (AGs)...................................................................................14
2.2 Autômatos Celulares (ACs) ....................................................................................16
2.3 Equivalência Dinâmica ...........................................................................................17
2.4 Tarefa de Classificação da Densidade ...................................................................21
2.5 ACs Não-Uniformes.................................................................................................23
2.6 ACs com Vizinhança Não-Local.............................................................................25
2.7 AC Não-Uniforme com Vizinhança Não-Local ....................................................26
2.8 Representação de Regras e Vizinhança de Raios Maiores Idênticas às de Raios
Menores..............................................................................................................................27
2.9 Grau de Balanceamento de uma Regra.................................................................30
2.10 Ordem Parcial das Regras Elementares em Relação à Regra 232......................31
2.11 Experimentos de Zanon (2006)...............................................................................32
2.11.1 ACs Não-Uniformes..........................................................................................33
2.11.2 ACs com Vizinhança Não-Local......................................................................34
2.11.3 ACs Não-Uniformes com Vizinhança Não-Local...........................................35
CAPÍTULO 3 – EXPERIMENTOS REALIZADOS E RESULTADOS OBTIDOS..37
3.1 Introdução................................................................................................................37
5
3.2 Experimentos para N=5..........................................................................................38
3.3 Experimentos para N=7, N=9 e N=11....................................................................42
3.3.1 Primeira Fase dos Experimentos.....................................................................42
3.3.2 Segunda Fase dos Experimentos .....................................................................44
3.4 Algoritmo de busca local.........................................................................................46
3.5 Experimentos pré-qualificação...............................................................................47
CAPÍTULO 4 - CONSIDERAÇÕES FINAIS ................................................................49
APÊNDICE A ....................................................................................................................51
APÊNDICE B –NKS SUMMER SCHOOL 2007.............................................................58
REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................59
6
Lista de Figuras
Figura 2.1: Processo de recombinação (crossover). 15
Figura 2.2: Exemplo de mutação. 15
Figura 2.3: Representação gráfica da regra de transição do AC elementar 150. 17
Figura 2.4: Evolução da regra 150 para uma condição inicial de 149 brancos e 1
preto,com 150 iterações. 17
Figura 2.5: Evolução temporal (por 100 passos) das regras dinamicamente
equivalentes à regra elementar 134, com reticulado de 149 células. 18
Figura 2.6: Representação binária da regra elementar 134. 19
Figura 2.7: Transformação complementar da regra 134 gerando a 158. 19
Figura 2.8: Transformação especular na regra 134 para gerar a 148. 20
Figura 2.9: Transformação complementar-especular na regra 134, gerando a regra
214. 20
Figura 2.10: Exemplos de soluções da DCT com maioria de 0s, figura à esquerda, e de
1s, figura à direita, na condição inicial do AC. 22
7
Lista de Tabelas
Tabela 2.1: Classes de regras equivalentes do espaço elementar. 21
Tabela 2.2: Representação da evolução de AC elementar não-uniforme. 23
Tabela 2.3: Dois melhores arranjos de regras de ACs não-uniformes encontrados em
[Sipper, 1996]. 25
Tabela 2.4: Evolução temporal de um AC não-uniforme e com vizinhança não-local.
27
Tabela 2.5: ACs não-uniformes e com vizinhanças não-locais equivalentes por
rotação. 27
Tabela 2.6: Transições de estados da regra elementar 168. 28
Tabela 2.7: Vizinhanças de raio 2. 28
Tabela 2.8: Vizinhanças de raio 2 com a configuração de posições dos bits relevantes
(2, 0, 1). 29
Tabela 2.9: Resultado da aplicação da regra elementar 168 na configuração de
posições de bits (2, 0, 1) gerando as transições de estados da regra idêntica de
raio de vizinhança 2. 29
Tabela 2.10: Evolução temporal do AC {{168, 2, 2}, {232, 2, 2}, {240, 1, 1}, {232, 1, 1},
{170, 2, 1}}. 30
Tabela 2.11: Evolução temporal do AC {{168, 2, 2}, {232, 2, 2}, {240, 1, 2}, {232, 1, 1},
{170, 2, 1}}. 30
Tabela 2.12: Grau de balanceamento das 64 regras compatíveis com a DCT. 31
Tabela 2.13: Ordem parcial das 64 regras elementares compatíveis com a DCT em
relação à regra da maioria 232. 32
Tabela 2.14: Os 14 arranjos ótimos de regras encontrados no reticulado de tamanho 5
por Zanon [2006]. 35
Tabela 3.1: Parâmetros utilizados nos experimentos para N=5. 38
Tabela 3.2: Conjunto de regras H3. 38
Tabela 3.3: Equivalências dinâmicas por transformação complementar entre as
regras do MR5. Para as regras não explicitadas, entenda-se que a regra obtida
pela transformação é idêntica à original. 39
8
Tabela 3.4: Algumas das soluções ótimas para N=5. 40
Tabela 3.5: Grau de balanceamento das regras dos MR5. 41
Tabela 3.7: Parâmetros utilizados nos experimentos para N=7, N=9 e N=11. 43
Tabela 3.8: Arranjos de regras com 480 acertos para N=9 na primeira fase. 44
Tabela 3.9: Arranjos de regras com 1869 acertos para N=11 na primeira fase. 44
Tabela 3.10: Arranjos de regras com 470 acertos para N=9 na segunda fase. 45
Tabela 3.11: Arranjos de regras com 1851 acertos para N=11 na segunda fase. 45
Tabela A.1: Arranjos ótimos de regras encontrados para N=3. 51
Tabela A.2: Arranjos ótimos de regras encontrados para N=5. 52
Tabela A.3: Arranjos de regras com 124 acertos encontrados para N=7. 56
9
Lista de Abreviações
AG Algorítmos Genéticos
AC Autômatos Celulares
c Configuração de vizinhança na Programação Celular
DCT Tarefa da Classificação da Densidade (do inglês, Density Classification
Task)
fi Função do desempenho da célula na Programação Celular
H3 Subconjunto das 64 regras compatíveis com a DCT cujas
representações binárias possuem distância de Hamming até 3 em
relação à regra 232
k Quantidade de estados do AC
MR5 Melhores regras para soluções encontradas em ACs de tamanho de
reticulado 5
N Tamanho de reticulado
nfi Função do desempenho dos vizinhos da célula na Programação Celular
r Raio de vizinhança
R Regra representante da classe de equivalência dinâmica
S Célula do Autômato Celular
10
Resumo
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.
Palavras-chave: Autômato celular, autômato celular não local, autômato celular não uniforme,
tarefa de classificação de densidade, algoritmo genético, computação evolutiva.
11
Abstract
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 non-
local 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.
Keywords: Cellular automaton, non-local cellular automaton, non-uniform cellular automaton,
density classification task, genetic algorithm, evolutionary computation.
12
Capítulo 1 - Introdução
Autômato celular (AC) é um sistema computacional totalmente discreto, com
transições de estado locais que, definido adequadamente, pode apresentar computabilidade
universal [Cook, 2004]. Apesar do seu processamento de informações ser feito localmente,
o AC pode apresentar comportamento complexo.
Um dos objetivos dos estudos de ACs é descobrir como usá-los para desempenhar
tarefas computacionais pré-definidas, como a tratada neste trabalho, o problema da
classificação de densidade (ou DCT, do inglês, density classification task), um problema
clássico para avaliar a capacidade dos ACs.
A partir da pesquisa desenvolvida por Zanon (2006), que utilizou ACs não-
uniformes com vizinhança não-local e mostrou, por exemplo, que há arranjos espaciais de
regras que solucionam a DCT para reticulados unidimensionais de 5 células, o presente
trabalho procurou expandir os experimentos de Zanon no sentido de:
• Procurar soluções adicionais para ACs com tamanho de reticulado 5,
• Verificar a existência de arranjos de regras para comprimentos maiores de
reticulados, e
• Analisar as soluções encontradas, buscando padrões que as correlacionassem.
Tais objetivos foram atingidos e, com respeito ao ultimo, foram descobertas as
seguintes características dos ACs não-uniformes com vizinhança não-local em relação às
soluções encontradas:
− As configurações de vizinhanças não-locais permitem uma pequena
flexibilidade em relação ao balanceamento total das regras.
− ACs não-uniformes com vizinhanças não-locais distintos podem ter a mesma
evolução temporal, sendo, portanto, efetivamente idênticos.
− Em princípio, não há casamento de padrões entre soluções encontradas para
tamanhos de reticulado 3 e 5, indicando que talvez não seja possível criar uma
solução em um tamanho de reticulado a partir de uma de tamanho menor.
13
Para tanto, foi utilizado um algoritmo evolutivo cuja eficácia já foi amplamente
validada na literatura em situações correlatas [Mitchell, 1998; Sipper, 1998], tendo sido
inclusive utilizada em [Zanon, 2006].
A seguir, o Capítulo 2 provê o material necessário de base para a dissertação.
Discutem-se alguns conceitos básicos de algoritmos genéticos e, em seguida, os conceitos
de autômatos celulares elementares, seus comportamentos dinâmicos, o problema da
classificação da densidade, os autômatos celulares não-uniformes, os com vizinhança não-
local e os experimentos de [Zanon, 2006]. O Capítulo 3 descreve os experimentos
realizados e o Capítulo 4 apresenta as conclusões obtidas e discutem-se trabalhos futuros.
14
Capítulo 2 – Autômatos Celulares e Algoritmos Genéticos
2.1 Algoritmos Genéticos (AGs)
O algoritmo genético (AG) foi inspirado nos conceitos de biologia evolutiva e visa
a busca de soluções para um problema computacional [Mitchell, 1998 e 1998b]. Packard
(1988) apresenta os primeiros resultados utilizando algoritmos genéticos (AGs) como meio
para encontrar regras de ACs que resolvessem um problema computacional.
No presente trabalho, o AG mostrou-se um algoritmo capaz de buscar boas
soluções (inclusive ótimas, em alguns casos) para a tarefa de classificação da densidade,
problema discutido com detalhes na Subseção 2.4. E também foi demonstrado que o AG
foi mais eficiente em relação a um algoritmo de busca local desenvolvido (conforme se
explica na Subseção 3.4).
Para tanto, busca-se aqui um arranjo de regras, cada um representado como um
indivíduo de uma população de soluções candidatas. Cada indivíduo é então submetido a
uma função de avaliação para verificar sua eficácia em relação ao problema.
Basicamente um AG segue os seguintes passos:
1. A geração da população inicial de indivíduos, feita geralmente de forma aleatória.
2. Os indivíduos são medidos pela função de avaliação e obtêm um índice de
desempenho.
3. Caso não haja uma resposta satisfatória, um processo de seleção gera um conjunto de
indivíduos para recombinação e mutação.
4. Na recombinação há a troca de parte de genes entre dois ou mais pais, formando novos
filhos. Tanto pai e filho são soluções candidatas do problema – no caso, arranjos
espaciais de regras – assim denominadas em analogia ao processo biológico, uma vez
que as soluções candidatas ‘filhos’ são obtidas a partir das soluções candidatas ‘pais’.
Por exemplo, pode ser sorteado um ponto de corte em cada um dos pais e, no filho
1
, os
genes do pai
1
são copiados até este ponto, e restante são os genes do pai
2
. No filho
2
, os
genes do pai
2
são copiados até o ponto de corte, e o restante são os genes do pai
1
. Este
processo é exibido na Figura 2.1.
15
5. Em seguida, cada um dos filhos passa pelo processo de mutação, em que cada um dos
genes deste filho tem uma probabilidade de ser alterado. Um exemplo de mutação pode
ser visto na Figura 2.2.
6. Essa nova população passa pelo processo de avaliação novamente e o processo interage
até que surja uma solução ótima ou se atinja uma condição de parada, que pode ser um
limite na quantidade de gerações, por exemplo.
Figura 2.1: Processo de recombinação (crossover).
Figura 2.2: Exemplo de mutação.
Os principais métodos de seleção são os seguintes:
− Aleatória: Todos os indivíduos têm a mesma probabilidade de serem escolhidos.
− Roleta: Cria-se uma roleta onde as casas são distribuídas para os indivíduos de
acordo com a aptidão de cada um, de forma que quanto maior é a aptidão maior é a
quantidade de casas e a probabilidade de ele ser sorteado. A aptidão (fitness) é o
índice de desempenho resultante da função de avaliação do problema.
16
− Torneio: Um grupo de indivíduos são selecionados aleatoriamente e entre eles é
escolhido um ´vencedor´, que fará parte da geração seguinte do algoritmo genético.
A escolha do vencedor pode ser determinística ou não determinística. No torneio
determinístico o vencedor é sempre o indivíduo com a maior aptidão; já no caso
não determinístico cada indivíduo tem probabilidade de ser escolhido,
proporcionalmente a seu valor de aptidão. A seleção dos indivíduos para o torneio
pode ser com ou sem repetição, dependendo se o individuo puder ser escolhido
para participar de mais de um torneio, ou não, respectivamente.
Pode-se ainda utilizar elitismo como parte do processo de seleção, que se refere à
preservação incondicional de uma parcela dos melhores indivíduos para a próxima geração
do AG, dando a capacidade de manter os ganhos obtidos durante a execução do AG.
2.2 Autômatos Celulares (ACs)
Autômato celular (AC) é sistema computacional de tempo e espaço discretos
composto por um reticulado n-dimensional de componentes iguais, chamadas de células,
com estados definidos e conectividade local.
Cada célula possui uma vizinhança e uma regra de transição. A vizinhança é um
conjunto de células, geralmente composto pela célula analisada e seus vizinhos. A regra de
transição é aplicada com base na vizinhança e produz o próximo estado da célula em
questão. Este processo é feito de forma sincronizada em todas as células do reticulado.
No presente trabalho são utilizados somente autômatos celulares unidimensionais e
com dois estados possíveis por célula (0 ou 1), ou seja, estados binários. A noção de AC
foi proposta inicialmente por John von Neumann na década de 1950 [von Neumann, 1966].
O AC elementar [Wolfram, 1984] é a mais simples configuração não trivial de
regras, em que cada célula do reticulado possui uma vizinhança local de três células,
incluindo a mesma e seus vizinhos imediatamente à esquerda e à direita, e dois estados, e é
aplicada uma única regra de transição em todo o reticulado.
O tamanho da vizinhança de uma célula é dado usualmente por 2r+1, onde r é
chamado de raio da vizinhança e a regra de transição do AC é o conjunto de combinações
de configurações de vizinhança, cada uma associada a seu bit de saída. [Wolfram, 1984]
17
definiu uma ordenação lexicográfica para representar as regras de um espaço em forma
decimal, que passou a ser bastante utilizada na literatura, sendo a adotada também aqui. A
Figura 1 mostra de forma gráfica a regra 150 que em binário é 10010110. A configuração
da regra lê-se do bit mais significativo para o menos significativo. No caso da Figura 2.3,
os bits 0 e 1 são mostrados pelas cores branca e preta, respectivamente.
Figura 2.3: Representação gráfica da regra de transição do AC elementar 150.
O espaço de regras de um AC é dado pela fórmula k
2r+1
, onde k é o número de
estado do AC. O AC elementar possui 2
2.2+1
= 2
8
= 256 regras elementares possíveis.
A evolução do comportamento de um AC a partir de uma configuração inicial do
reticulado pode ser ilustrada em função do tempo, conforme a Figura 2.4, que apresenta o
diagrama espaço-temporal do AC elementar 150.
Figura 2.4: Evolução da regra 150 para uma condição inicial de 149 brancos e 1 preto,com
150 iterações.
2.3 Equivalência Dinâmica
As regras dos ACs podem ser agrupadas em conjuntos considerados dinamicamente
equivalentes, isto é, possuem comportamentos temporais qualitativamente idênticos,
quando consideradas todas as condições iniciais possíveis. Elas poderão eventualmente
Tempo
0
150
18
apresentar comportamentos diferentes se analisadas sob uma condição inicial isolada.
Várias propriedades quantidades de regras equivalentes também se preservam na classe. A
figura a seguir ilustra o conceito, através da classe de equivalência dinâmica da regra
elementar 134.
Figura 2.5: Evolução temporal (por 100 passos) das regras dinamicamente equivalentes à
regra elementar 134, com reticulado de 149 células.
Pode-se descobrir as equivalentes dinâmicas de uma regra a partir de 3
transformações em sua representação binária. Para ilustrá-las, considere a representação
binária da regra 134, conforme mostra a Figura 2.6.
19
Figura 2.6: Representação binária da regra elementar 134.
A transformação complementar (ou conjugada) é a inversão de todos os bits de
entrada e de saída, com posterior reordenação dos bits de entrada. A Figura 2.7 ilustra o
processo, mostrando como a regra 134 dá origem à regra 158.
Figura 2.7: Transformação complementar da regra 134 gerando a 158.
A transformação especular inverte a ordem de cada um dos bits de entrada,
também com posterior reordenação dos bits de entrada. Assim, no caso das regras
elementares, os bits de entrada (vizinhanças) 110, 100, 011 e 001 se tornam,
respectivamente, 011, 001, 110 e 100, e as outras vizinhanças se mantêm, dado que suas
simetrias tornam as inversões invariantes. Nessa transformação os bits de saída ficam
inalterados. A Figura 2.8 ilustra o processo.
20
Figura 2.8: Transformação especular na regra 134 para gerar a 148.
A transformação complementar-especular (ou transformação especular-
complementar) é a junção das duas anteriores, aplicadas uma vez em seqüência,
independente da ordem. A Figura 2.9 mostra um exemplo.
Figura 2.9: Transformação complementar-especular na regra 134, gerando a regra 214.
A partir destas transformações obtiveram-se as regras 134, 158, 148 e 214, que
formam uma classe dinamicamente equivalente. No presente trabalho, em sintonia com
21
[Wolfram, 2002], a classe é identificada pela regra de menor numeração; no caso do
exemplo anterior, então, a regra representante da classe, denominado por R, é a 134.
Se agruparmos todas as regras do espaço elementar, chega-se a um total de 88
classes dinamicamente equivalentes, que são exibidas na Tabela 2.1.
Tabela 2.1: Classes de regras equivalentes do espaço elementar.
R
Equivalentes
R
Equivalentes
R
Equivalentes
R
Equivalentes
0 255 26
82, 167, 181 56
98, 185, 227 132
222
1 127 27
39, 53, 83 57
99 134
148, 158, 214
2 16, 191, 247 28
70, 157, 199 58
114, 163, 177
136
192, 238, 252
3 17, 63, 119 29
71 60
102, 153, 195
138
174, 208, 244
4 223 30
86, 135, 149 62
118, 131, 145
140
196, 206, 220
5 95 32
251 72
237 142
212
6 20, 159, 215 33
123 73
109 146
182
7 21, 31, 87 34
48, 187, 243 74
88, 173, 229 150
8 64, 239, 253 35
49, 59, 115 76
205 152
188, 194, 230
9 65, 111, 125 36
219 77
154
166, 180, 210
10
80, 175, 245 37
91 78
92, 141, 197 156
198
11
47, 81, 117 38
52, 155, 211 90
165 160
250
12
68, 207, 221 40
96, 235, 249 94
133 162
176, 186, 242
13
69, 79, 93 41
97, 107, 121 104
233 164
218
14
84, 143, 213 42
112, 171, 241
105
168
224, 234, 248
15
85 43
113 106
120, 169, 225
170
240
18
183 44
100, 203, 217
108
201 172
202, 216, 228
19
55 45
75, 89, 101 110
124, 137, 193
178
22
151 46
116, 139, 209
122
161 184
226
23
50
179 126
129 200
236
24
66, 189, 231 51
128
254 204
25
61, 67, 103
54
147
130
144, 190, 246
232
Note-se que cada regra elementar pode conter até outras 3 regras dinamicamente
equivalentes, havendo casos em que uma ou mais transformações geram a mesma regra,
como por exemplo a regra 178, para a qual todas as transformações geram a mesma regra.
2.4 Tarefa de Classificação da Densidade
A tarefa de classificação da densidade (do inglês, density classification task, DCT)
ou problema da maioria [Mitchell, 1998] visa avaliar o desempenho de ACs binários na
tarefa de determinar se há mais 0s ou 1s numa configuração binária inicial qualquer,
fazendo convergir todo o reticulado para 0 se existir mais 0s, ou para 1 se houver mais 1s.
22
Este problema foi originalmente introduzido por Gacs-Kurdyumov-Levin em 1978
[Mitchell, 1998]. Dois exemplos são mostrados na Figura 2.10.
Figura 2.10: Exemplos de soluções da DCT com maioria de 0s, figura à esquerda, e de 1s,
figura à direita, na condição inicial do AC.
[Land e Belew, 1995] provaram que não existe uma regra de transição única, de
qualquer raio de vizinhança, que resolva perfeitamente a DCT. Porém, flexibilizando esta
definição, [Fukś, 1997] mostrou que a DCT é solucionada utilizando uma composição
temporal de duas regras, neste caso, aplicando-se a regra 232 por um certo número de
passos após a regra 184.
Para cada tamanho de reticulado existe uma regra da maioria trivial, ou seja, uma
configuração de AC que resolve a DCT em somente um passo de tempo. Por exemplo,
para o AC de tamanho de reticulado 3 é a regra com raio de vizinhança um 232, para o
tamanho 5 é a regra com raio de vizinhança dois 4276676736, e assim por diante.
Por causa das características da DCT, é muitas vezes adequado considerar somente
o conjunto das regras ditas compatíveis com a DCT [Zanon, 2006], i.e., as que contêm as
transições de estado 000...0→0 e 111...1→1. No caso das regras elementares, existem 64
regras desse tipo, que são as que apresentam as transições de estado 000→0 e 111→1.
23
2.5 ACs Não-Uniformes
Como ACs uniformes não são capazes de resolver a DCT, [Sipper, 1996] fez
experimentos com ACs não-uniformes, nos quais cada célula S possui uma regra de
transição independente. Por exemplo, a Tabela 2.2 mostra a evolução de quatro passos
neste tipo de AC, onde na vizinhança da célula S
2
(S
1
, S
2
, S
3
) é aplicada a regra 50, para a
vizinhança da célula S
6
(S
5
, S
6
, S
7
) é aplicada a regra 65, e assim por diante.
Tabela 2.2: Representação da evolução de AC elementar não-uniforme.
130 50 80 150 136 65 242 186
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
t = 0 1 0 1 0 1 0 0 1
t = 1 0 1 0 0 0 0 1 1
t = 2 0 0 1 0 0 0 0 0
t = 3 0 1 0 1 0 1 0 0
t = 4 1 0 0 1 0 0 1 0
Em seu trabalho, Sipper (1996) utilizou o conceito de programação celular, uma
técnica evolutiva (assim como o algoritmo genético apresentado na Seção 2.1). Porém, este
modelo é caracterizado como coevolucionário porque a evolução do indivíduo depende
exclusivamente do desempenho de seus vizinhos dado pela função nf
i
(c), que determina
quantos vizinhos obtiveram melhor desempenho em relação à própria célula após a
avaliação de c configurações iniciais.
A população considerada foi o AC e os indivíduos as regras de transição de cada
célula. A cada indivíduo i são associadas duas funções: fi e nfi.
O funcionamento do algoritmo baseia-se nos seguintes passos:
1) Cada um dos indivíduos do AC é inicializado com uma regra de transição
aleatória e o seu f
i
= 0.
2) O AC é evoluído em M passos de tempo para c condições iniciais aleatórias
diferentes.
3) Em cada uma das c condições, se o estado final de cada indivíduo está correto
em relação ao problema, o seu f
i
é incrementado em 1, caso contrário, não é alterado.
4) Depois disso, calcula-se-a da função nf
i
para cada célula i. O valor de nfi
determina quantos vizinhos possuiu maior desempenho que i. A vizinhança é obtida pelo
24
raio utilizado nas regras. Baseado no valor de nfi os operadores genéticos são aplicados
assim:
• nfi = 0: nenhum vizinho possuiu desempenho melhor que indivíduo, então este
se mantém inalterado.
• nfi = 1: existe apenas um vizinho com desempenho melhor. Então o indivíduo
em questão é substituído por aquele vizinho, seguido de mutação.
• nfi = 2: existem dois vizinhos com desempenho melhor. A regra é substituída
pelo crossover entre estes dois vizinhos, seguido de mutação.
• nfi > 2: existem mais de dois vizinhos com melhor desempenho. A regra é
substituída pelo crossover de dois destes vizinhos escolhidos por sorteio,
seguido de mutação.
Inicialmente foram testadas as 256 regras dos ACs elementares em 1000
configurações iniciais, no tamanho de reticulado 149, e chegou-se à conclusão que a regra
232 conseguiu o melhor índice de desempenho igual a 0,83.
Num segundo momento, foi aplicada a programação celular para um AC não-
uniforme e o melhor resultado obtido foi de 0,93 e, conseqüentemente, mostrou que os
ACs não-uniformes podem ter desempenho melhor que os ACs uniformes.
As duas configurações de ACs não-uniformes que atingiram este resultado
continham as regras 224, 226 e 234, sendo que a 226 compôs a grande maioria do
reticulado, gerando um padrão predominante de uma regra nos ACs não-uniformes para a
solução da DCT. Também foi observada uma diferença de 1 bit (i.e., distância de
Hamming igual a 1) entre as representações binárias da regra 232 (11101000) – que tem o
melhor desempenho no AC uniforme – e as regras 224 (11100000), 226 (11100010) e 234
(11101010), que aparecem nos melhores ACs não-uniformes.
As duas configurações de regras dos melhores ACs não-uniformes são apresentadas
na Tabela 2.3.
25
Tabela 2.3: Dois melhores arranjos de regras de ACs não-uniformes encontrados em
[Sipper, 1996].
Arranjo de Regras 1 Arranjo de Regras 2
Regra Posição
Inicial
Posição
Final
Regra Posição
Inicial
Posição
Final
226 0 39 226 0 106
234 40 40 224 107 108
226 41 71 226 109 131
234 72 72 234 132 132
226 73 142 226 133 148
224 143 144
226 145 148
2.6 ACs com Vizinhança Não-Local
Os ACs com vizinhança não-local partem do princípio que as células não se
conectam estritamente a seus vizinhos imediatamente à esquerda e à direita e, portanto, em
geral sua configuração de vizinhança para uma célula S
i
é dada por (S
i-l
, S
i
, S
i+r
), onde l e r
indicam, respectivamente, as distâncias relativas dos vizinhos da esquerda e da direita. Este
tipo de AC permite que a informação existente em uma célula se espalhe mais rapidamente
pelo reticulado e a vizinhança, por sua vez, seja mais abrangente.
Um conceito utilizado neste trabalho é o de regras com ação global, onde pelo
menos um dos membros que compõem a vizinhança da célula tenha como raio de ação
todo o reticulado. Por exemplo, para o reticulado de tamanho 5, basta que a distância da
célula Si para um de seus vizinhos seja 2; para o tamanho 7, seja 3, e assim por diante.
Um dos primeiros trabalhos com este tipo de ACs foi apresentado em [Li 1992],
que estudou 4 tipos de vizinhança:
•
Conexões parcialmente locais: a vizinhança de cada célula S
i
, é formada por
(S
x
, S
i
, S
y
) onde as células S
x
e S
y
são escolhidas de forma aleatória.
•
Conexões parcialmente locais e distintas: é acrescentada à definição anterior a
restrição que, obrigatoriamente, S
x
≠
S
i
≠
S
y
.
•
Conexões não-locais: a vizinhança de cada célula S
i
é formada por (S
x
, S
w
, S
y
)
onde S
x
, S
w
e S
y
são escolhidas de forma aleatória, onde S
w
pode ser S
i
.
26
•
Conexões não-locais e distintas: é acrescentada ao conceito de conexões não-
locais que obrigatoriedade que S
x
≠
S
w
≠
S
y
, onde S
w
pode ser S
i
.
O trabalho de Li realizou um estudo da dinâmica dos ACs quando submetidos a
este tipo de AC e concluiu que os ACs não pesaram a uma diferença significativa em seu
comportamento dinâmico.
2.7 AC Não-Uniforme com Vizinhança Não-Local
O AC não-informe com vizinhança não-local consiste arranjos de regras em que
cada célula do reticulado possui uma regra de transição e configuração de vizinhança
independente, ou seja, ele unifica os conceitos de ACs não-uniformes e de ACs com
vizinhança não-local.
Os experimentos de Zanon (2006) demonstraram a existência de soluções ótimas
para a DCT utilizando ACs não-uniformes e com vizinhança para tamanho de reticulado 5,
ou seja, que obtiveram o acerto das 32 possibilidades. A partir disso, abriu-se a
possibilidade que houvesse soluções ótimas também para outros tamanhos de reticulados
usando este tipo de AC e este fato serviu de base para testes mais aprofundados neste
trabalho.
O AC não-uniforme e com vizinhança utilizada nesta dissertação é composto de
arranjos de regras, onde cada célula contém configuração de vizinhança com 3 células e
uma regra transição elementar (256 possibilidades).
A notação para cada célula do reticulado é escrita como
{regra, vizinho à esquerda, vizinho à direita},
de onde, por exemplo, {168, 2, 1} refere-se à regra 168, aplicada sobre a vizinhança
composta pela própria célula, pelo segundo vizinho à esquerda e pelo primeiro vizinho à
direita.
Conseqüentemente, a notação resultante para esse tipo de AC envolve o conjunto
de células; com isso, em um reticulado de tamanho de 5, tem-se, por exemplo, o arranjo de
regras {{168, 2, 1}, {232, 1, 1}, {250, 1, 2}, {162, 2, 1}, {170, 2, 2}}, cuja evolução
temporal é ilustrada na Tabela 2.4.
27
Tabela 2.4: Evolução temporal de um AC não-uniforme e com vizinhança não-local.
{168, 2, 1} {232, 1, 1} {250, 1, 2} {162, 2, 1} {170, 2, 2}
t = 0 1 0 1 0 1
t = 1 0 1 1 1 0
t = 2 1 1 1 0 1
t = 3 1 1 1 1 1
t = 4 1 1 1 1 1
A utilização de ACs com condição de contorno periódica (onde as extremidades são
interligadas), como é o caso neste trabalho, leva à existência de ACs não uniformes e com
vizinhanças não-locais equivalentes por rotação, ao considerarem-se o conjunto de todas as
condições iniciais possíveis.
Assim, para um AC não uniforme e com vizinhança não-local obtém-se seu
equivalente por rotação avançando em uma posição todas as células de todo o reticulado de
tamanho N, podendo gerar um total de N-1 ACs equivalentes. Na Tabela 2.5 mostra-se um
exemplo de ACs equivalentes por rotação.
Tabela 2.5: ACs não-uniformes e com vizinhanças não-locais equivalentes por rotação.
AC Original
{{168, 2, 1},{232, 1, 1},{250, 1, 2},{162, 2, 1},{170, 2, 2}}
ACs
equivalentes
por rotação
{{170, 2, 2},{168, 2, 1},{232, 1, 1},{250, 1, 2},{162, 2, 1}}
{{162, 2, 1},{170, 2, 2},{168, 2, 1},{232, 1, 1},{250, 1, 2}}
{{250, 1, 2},{162, 2, 1},{170, 2, 2},{168, 2, 1},{232, 1, 1}}
{{232, 1, 1},{250, 1, 2},{162, 2, 1},{170, 2, 2},{168, 2, 1}}
2.8 Representação de Regras e Vizinhança de Raios Maiores
Idênticas às de Raios Menores
Pode-se mostrar que toda regra existente em um determinado espaço de regras
também existe em qualquer outro que o contenha. Em outras palavras, qualquer regra com
vizinhança de raio r e k estados também pode ser representada como uma regra idêntica de
raio maior, onde a representação k-ária da regra de raio maior é obtida a partir da
representação da regra de raio menor, acrescida de algumas transições de estado que são
neutras em termos do comportamento temporal resultante.
Para demonstrar este conceito, seja a regra não-local {168, 2, 1}, cuja
correspondente idêntica de raio 2 é obtida, executando-se os seguintes passos:
28
1. Fazer a representação das transições da regra elementar 168, exibida na Tabela 2.6,
onde o primeiro bit de entrada é o vizinho da esquerda, o segundo é o bit central e o
terceiro é o vizinho da direita.
Tabela 2.6: Transições de estados da regra elementar 168.
Entrada
Saída
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
0
2. Gerar as vizinhanças de raio 2 que contém 5 bits de entradas sem os valores de saída,
observada na Tabela 2.7.
Tabela 2.7: Vizinhanças de raio 2.
Entrada Saída Entrada Saída Entrada Saída Entrada Saída
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
1
1
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
3. Determinar as posições dos bits de entrada relevantes de acordo com a configuração de
vizinhança da célula. Para facilitar o entendimento da configuração de posições dos
bits será usada a denominação:
(distância do bit do vizinho à esquerda, posição do bit central, distância do bit do vizinho à direita)
que neste caso é (2, 0, 1). O bit central da regra de raio 2 é o 3º bit, com isso, pode-se
determinar as posições do bit à esquerda e à direita, que são respectivamente o 1º bit
(bit na posição 3-2) e 4º bit (bit na posição 3+1). A demonstração disso é feita na
Tabela 2.8.
29
Tabela 2.8: Vizinhanças de raio 2 com a configuração de posições dos bits relevantes
(2, 0, 1).
Entrada Saída Entrada Saída Entrada Saída Entrada Saída
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
1
1
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
0
1
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
4. Aplicar a transição de estado da célula original nos bits relevantes na regra
correspondente de raio maior para obter os valores de saída. A Tabela 2.9 exibe (em
destaque) a aplicação das transições de estados da regra elementar 168, na
configuração de posições (2, 0, 1) das vizinhanças de raio 2, gerando as transições de
estado da regra de raio 2 correspondente à regra elementar 168.
Tabela 2.9: Resultado da aplicação da regra elementar 168 na configuração de posições de
bits (2, 0, 1) gerando as transições de estados da regra idêntica de raio de vizinhança
2.
Entrada Saída Entrada Saída Entrada Saída Entrada Saída
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
0
1
0
1
0
1
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
1
0
1
1
0
0
0
0
1
1
0
1
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
0
0
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
5. Ordenar as saídas de forma decrescente, de acordo com os bits de entrada das
transições de estados e transformá-los da representação binária para a decimal. No caso
exposto aqui, o valor de saída em binário é 11001100110011001100000011000000 que
em decimal resulta na regra idêntica (com r=2) 3435970752.
Este conceito é importante pois permite verificar se dois ACs não-uniformes e com
vizinhança não-local possuem o mesmo comportamento de evolução temporal. Um
exemplo disto são os ACs
{{168, 2, 2}, {232, 2, 2}, {240, 1, 1}, {232, 1, 1}, {170, 2, 1}} e
30
{{168, 2, 2}, {232, 2, 2}, {240, 1, 2}, {232, 1, 1}, {170, 2, 1}}
que são aparentemente distintos, mas, se transformados em arranjos de regras idênticas de
raio de vizinhança 2 resultam nos ACs
{2863308960, 4210729120, 4278255360, 4240506048, 3435973836} e
{2863308960, 4210729120, 4278255360, 4240506048, 3435973836},
que são os mesmos, possuindo, portanto, a mesma evolução temporal, como pode se
constatar nas Tabelas 2.10 e 2.11.
Tabela 2.10: Evolução temporal do AC
{{168, 2, 2}, {232, 2, 2}, {240, 1, 1}, {232, 1, 1}, {170, 2, 1}}.
{168, 2, 1} {232, 2, 2} {240, 1, 1} {232, 1, 1} {170, 2, 1}
t = 0 0 0 0 1 1
t = 1 0 1 0 1 0
t = 2 0 1 1 0 0
t = 3 0 0 1 0 0
t = 4 0 0 0 0 0
Tabela 2.11: Evolução temporal do AC
{{168, 2, 2}, {232, 2, 2}, {240, 1, 2}, {232, 1, 1}, {170, 2, 1}}.
{168, 2, 2} {232, 2, 2} {240, 1, 2} {232, 1, 1} {170, 2, 1}
t = 0 0 0 0 1 1
t = 1 0 1 0 1 0
t = 2 0 1 1 0 0
t = 3 0 0 1 0 0
t = 4 0 0 0 0 0
2.9 Grau de Balanceamento de uma Regra
Uma regra de k estados por célula é considerada balanceada se sua representação k-
ária possui a mesma quantidade de cada um dos k estados possíveis.
O balanceamento das regras de transição em ACs com estados binários diz respeito,
portanto, à proporção entre as quantidades de 0s e 1s na representação binária da regra, de
forma que a regra é dita balanceada se esta quantidade é a mesma para os dois estados.
Dada a noção de balanceamento de regras de ACs, pode-se definir ainda o grau de
balanceamento de uma regra, que neste trabalho baseia-se na quantidade de 1s presentes na
representação binária da regra, podendo variar, portanto, de 0 a 8. Neste caso, uma regra é
31
considerada balanceada se seu grau de balanceamento for 4. Por exemplo, como a
representação binária da regra 168 é 10101000, seu grau de balanceamento é aqui
considerado como igual a 3.
Este conceito é importante porque no caso da tarefa da classificação da densidade
verifica-se tanto do ponto de vista teórico [Sipper e Tomassini, 1999; Capcarrère e Sipper,
2001] quanto empiricamente [Wolz and de Oliveira, 2008] que boas regras são
balanceadas.
A Tabela 2.12 mostra o grau de balanceamento de todas as 64 regras elementares
compatíveis com a DCT.
Tabela 2.12: Grau de balanceamento das 64 regras compatíveis com a DCT.
Grau de
Balanceamento
Regras
1
128(10000000)
2
130 (10000010), 132 (10000100), 136 (10001000), 144 (10010000), 160 (10100000),
192 (11000000)
3
134 (10000110), 138 (10001010), 140 (10001100), 146 (10010010), 148 (10010100),
152 (10011000), 162 (10100010), 164 (10100100), 168 (10101000), 176 (10110000),
194 (11000010), 196 (11000100), 200 (11001000), 208 (11010000), 224 (11100000)
4
142 (10001110), 150 (10010110), 154 (10011010), 156 (10011100), 166 (10100110),
170 (10101010), 172 (10101100), 178 (10110010), 180 (10110100), 184 (10111000),
198 (11000110), 202 (11001010), 204 (11001100), 210 (11010010), 212 (11010100),
216 (11011000), 226 (11100010), 228 (11100100), 232 (11101000), 240 (11110000)
5
158 (10011110), 174 (10101110), 182 (10110110), 186 (10111010), 188 (10111100),
206 (11001110), 214 (11010110), 218 (11011010), 220 (11011100), 230 (11100110),
234 (11101010), 236 (11101100), 242 (11110010), 244 (11110100), 248 (11111000)
6
190 (10111110), 222 (11011110), 238 (11101110), 246 (11110110), 250 (11111010),
252 (11111100)
7
254 (11111110)
2.10 Ordem Parcial das Regras Elementares em Relação à Regra
232
A regra elementar 232 é conhecida como a regra da maioria, porque em sua
representação binária se houver mais bits 0 na vizinhança o bit de saída é 0, e se houver
mais bits 1, a saída é 1.
32
Podem-se classificar as regras elementares de acordo com a distância de Hamming
entre suas representações binárias e a regra 232, o que leva à construção de uma ordem
parcial das regras elementares com relação a 232.
Considerando somente o conjunto das 64 regras elementares compatíveis com a
DCT, a ordem parcial resultante é exibida na Tabela 2.13.
Os experimentos feitos neste trabalho mostraram que as regras elementares que
compõem as soluções da DCT têm no máximo distância de Hamming 4, indicando que
quanto menor a distância em relação à regra da maioria 232 maior a probabilidade de uma
regra compatível fazer parte de uma solução da DCT.
Tabela 2.13: Ordem parcial das 64 regras elementares compatíveis com a DCT em relação
à regra da maioria 232.
Regra da Maioria
232 (11101000)
Dist. De Hamming 1
168 (10101000), 200 (11001000), 224 (11100000), 234 (11101010), 236 (11101100),
248 (11111000)
Dist. De Hamming 2
136 (10001000), 160 (10100000), 170 (10101010), 172 (10101100), 184 (10111000),
192 (11000000), 202 (11001010), 204 (11001100), 216 (11011000), 226 (11100010),
228 (11100100), 238 (11101110), 240 (11110000), 250 (11111010), 252 (11111100)
Dist. De Hamming 3
128 (10000000), 138 (10001010), 140 (10001100), 152 (10011000), 162 (10100010),
164 (10100100), 174 (10101110), 176 (10110000), 186 (10111010), 188 (10111100),
194 (11000010), 196 (11000100), 206 (11001110), 208 (11010000), 218 (11011010),
220 (11011100), 230 (11100110), 242 (11110010), 244 (11110100), 254 (11111110)
Dist. De Hamming 4
130 (10000010), 132 (10000100), 142 (10001110), 144 (10010000), 154 (10011010),
156 (10011100), 166 (10100110), 178 (10110010), 180 (10110100), 190 (10111110),
198 (11000110), 210 (11010010), 212 (11010100), 222 (11011110), 246 (11110110)
Dist. De Hamming 5
134 (10000110), 146 (10010010), 148 (10010100), 158 (10011110), 182 (10110110),
214 (11010110)
Dist. De Hamming 6
150 (10010110)
2.11 Experimentos de Zanon (2006)
Nesta subseção são descritos os experimentos de Zanon [2006] com ACs não-
uniformes, ACs com vizinhança não-local, e com os dois tipos anteriores, na solução da
DCT, e os resultados obtidos. As conclusões obtidas em [Zanon, 2006] aparecem de forma
mais condensada em [Zanon e de Oliveira, 2008].
33
2.11.1 ACs Não-Uniformes
Utilizando um algoritmo genético, Zanon [2006] buscou ACs não-uniformes. Para
isso, utilizou dois conjuntos de teste, ambos relativos ao tamanho 35 de reticulado, i.e.,
com 35 células. O primeiro conjunto de teste era formado pelas 64 regras elementares
compatíveis que pudessem resolver a DCT e, o segundo, pelas regras 224, 226 e 234,
derivadas de [Sipper, 1996], aqui denominadas simplesmente como ´regras Sipper´.
A população de cada nova geração foi formada pelos melhores indivíduos e o
restante dos indivíduos foi selecionado para sofrer recombinação e mutação. A seleção foi
feita segundo 3 métodos:
• Toda a população pelo método da roleta.
• Somente a elite de forma aleatória.
• Somente a elite pelo método da roleta.
Para cada um dos conjuntos de testes foram realizadas 24 execuções, 8 para cada
método de seleção, totalizando 48 execuções no geral. Em cada uma delas, a população é
criada aleatoriamente com 100 indivíduos e evoluída por 50 gerações.
Para todas as execuções foram utilizados os seguintes parâmetros:
• Configurações iniciais: em número de 100, geradas de forma aleatória, com
densidade uniforme de 1s.
• Número de passos de tempo de execução de cada condição inicial: 120.
• Elite: 20 indivíduos.
• Probabilidade de mutação de cada gene: 2%.
Os ACs não-uniformes utilizando as regras Sipper obtiveram desempenho máximo
de 96% contra os 64% dos ACs não-uniformes compostos pelas 64 regras elementares
compatíveis; no entanto, estas últimas tinham uma tendência de crescimento, em sintonia
com os experimentos de [Sipper, 1996] e sugerindo que as regras Sipper sejam uma
evolução eficaz das 64 regras compatíveis.
34
2.11.2 ACs com Vizinhança Não-Local
Neste experimento, Zanon utilizou reticulado de tamanho 41, num total de 20
2
=
400 configurações de vizinhança não-locais, testadas na DCT por cada uma das 256 regras
elementares e cada um dos ACs foram evoluídos 151 passos.
O conceito de assimetria da vizinhança da célula S
i
é utilizado para a compreensão
dos resultados obtidos, sendo representado por A = |L – R|, onde A é o fator de assimetria,
L é a distância entre o vizinho à esquerda e S
i
, e R é a distância entre o vizinho à direita e a
célula S
i
. A vizinhança simétrica (A = 0) também compreende a vizinhança local ou
elementar (1, 1). Algumas conclusões são apresentadas a seguir:
• No geral, as vizinhanças simétricas estavam ou entre os melhores ou entre os piores
desempenhos.
• Das 256 regras, 7 delas (72, 104, 200, 232, 233, 236 e 237) apresentaram vizinhanças
não-locais com índices de desempenho melhores que com a vizinhança local, sendo
que a regra 232 atingiu 91% de desempenho e as outras 6 em torno de 50%.
• Considerando as outras 249 regras, nenhuma configuração de vizinhança não-local
conseguiu ganho de desempenho significativo em relação à sua vizinhança local.
Porém, o experimento não foi considerado representativo, pela quantidade
insignificante condições iniciais. Para obter resultados mais efetivos, realizou-se então um
experimento enumerativo no reticulado de tamanho 21 (que possui 2
21
= 2.097.152
condições iniciais distintas), e 100 configurações de vizinhança. No entanto, devido à
simetria de algumas vizinhanças, basta considerar somente 55 delas, porque o desempenho
da configuração (i, j) é igual ao da (j, i).
Para este experimento, bastava considerar um representante de cada uma das 88
classes dinamicamente equivalentes de regras pois, automaticamente, todas as regras
acabam sendo consideradas [Wolfram, 2002]. Algumas conclusões válidas foram as
seguintes:
• Das 88 classes, somente 24 delas apresentaram diferença entre a melhor e a pior
vizinhança acima de 10%, que é considerado significativo.
• A configuração de vizinhança (2, 8) da regra 232 apresentou o melhor desempenho. No
entanto, sua configuração local atingiu resultado muito ruim, de 2,33%.
35
• O fator de simetria A=3 mostrou tendência de estar entre as melhores configurações de
vizinhanças.
• Comprovando o experimento anterior, as vizinhanças simétricas continuavam, no
geral, se encontrando em um de dois grupos: ou o de melhor desempenho ou o de pior
[Zanon, 2006].
2.11.3 ACs Não-Uniformes com Vizinhança Não-Local
Em experimentos com ACs não-uniformes, no reticulado de tamanho 5, relatados
em [Kunyosi e Miki, 2004], soluções para a DCT não foram encontradas, sendo que as
melhores tiveram 30 acertos (de 32 possíveis, i.e., apresentaram desempenho de 93,75%), e
todas continham as regras 168, 184, 232 e 246.
Considerando os ACs não-uniformes com vizinhança não-local, inicialmente foram
realizados testes com as 4 variações de vizinhança da regra 232 no reticulado 5, onde cada
célula pode conter as regras {232,1,1}, {232,1,2}, {232,2,1} ou {232,2,2} num total de 4
5
= 1024 arranjos espaciais de regras. Os melhores resultados foram de 30 acertos dentre os
32 possíveis.
Tabela 2.14: Os 14 arranjos ótimos de regras encontrados no reticulado de tamanho 5 por
Zanon [2006].
Arranjos de regras com acerto total (32 possibilidades)
{248, 2, 2},{168, 1, 1},{184, 2, 1},{232, 2, 1},{232, 2, 2}
{248, 2, 2},{248, 1, 1},{168, 1, 1},{168, 2, 1},{232, 2, 2}
{248, 2, 2},{248, 1, 1},{184, 1, 1},{168, 1, 1},{168, 2, 2}
{248, 2, 2},{232, 1, 1},{168, 2, 2},{184, 2, 1},{184, 1, 2}
{248, 2, 2},{232, 1, 1},{184, 2, 2},{232, 1, 1},{168, 2, 2}
{248, 1, 2},{248, 1, 1},{168, 1, 1},{168, 2, 2},{232, 2, 2}
{248, 1, 2},{248, 1, 1},{168, 1, 1},{232, 2, 2},{232, 2, 2}
{248, 1, 2},{232, 1, 1},{168, 2, 1},{232, 2, 2},{232, 2, 2}
{248, 1, 1},{168, 2, 2},{232, 2, 2},{232, 1, 2},{184, 1, 2}
{248, 1, 1},{168, 1, 1},{168, 2, 1},{232, 2, 2},{232, 2, 2}
{248, 1, 1},{168, 1, 1},{232, 2, 2},{232, 2, 2},{232, 1, 2}
{248, 1, 1},{168, 1, 1},{232, 2, 1},{232, 2, 2},{232, 2, 2}
{248, 1, 1},{168, 1, 1},{232, 2, 1},{232, 2, 2},{232, 1, 2}
{248, 1, 1},{168, 1, 1},{168, 1, 1},{232, 2, 2},{232, 2, 2}
36
Cada uma das 4 regras possui 4 variações de vizinhança no reticulado de tamanho 5
(1,1), (1,2), (2,1) ou (2,2), resultando em 16
5
= 1.048.576 arranjos espaciais de regras
possíveis. Neste caso, foram encontrados 14 arranjos espaciais de regras ótimas que
resolvem a DCT, os quais são apresentados na Tabela 2.14.
37
Capítulo 3 – Experimentos Realizados e Resultados Obtidos
3.1 Introdução
Os experimentos aqui realizados são derivados de Zanon (2006), que utilizou ACs
não-uniformes com vizinhança não-local em testes enumerativos com 4 regras – 168, 184,
232 e 248 – e mostrou que há arranjos espaciais de regras que solucionam a DCT para
reticulados unidimensionais de 5 células. O presente trabalho buscou determinar se existem
respostas em outros tamanhos de reticulados com as 64 regras elementares compatíveis
com a DCT, e se há alguma lei de formação capaz de deduzir arranjos de regras para outros
tamanhos de reticulado.
Zanon (2006) utilizou um AG em seus experimentos e o mesmo foi aqui
aperfeiçoado para buscar soluções para a DCT utilizando arranjos não-uniformes de regras
com vizinhança não-elementar.
O trabalho foi implementado no software Mathematica, utilizando uma biblioteca
de autômatos celulares, que inclui um algoritmo genético para ACs [de Oliveira, 2007].
Na primeira fase dos experimentos com o AG, o objetivo foi determinar se havia
arranjos de regras que solucionassem a DCT nos reticulados unidimensionais de tamanho
(N) igual a 5, 7, 9 e 11; tais tamanhos de reticulado foram considerados por serem
pequenos o bastante para se avaliar soluções para a DCT sobre todas as condições iniciais
possíveis, e serviriam de ponto de partida para se tentar induzir soluções para tamanhos
maiores. Na segunda fase, foram feitos experimentos para N=9 e N=11, com restrição de
até o raio de vizinhança 3, com o intuito de se verificar a interferência da limitação de
vizinhança na qualidade dos resultados e, ao mesmo tempo, checar se bons arranjos de
regras necessitam de células com vizinhança de raio global.
O indivíduo considerado em todos os experimentos é formado por N tuplas, como
do conjunto exemplo {248, 1, 2}, onde 248 é o número da regra elementar, 1 representa a
posição do vizinho à esquerda da célula central, e 2 a posição de seu vizinho à direita.
38
3.2 Experimentos para N=5
Para a avaliação do tamanho de reticulado 5 foram considerados experimentos
compostos por 6 execuções, decorrente da combinação dos três métodos de seleção
descritos na Subseção 2.11.3, e de duas taxas de mutação (1% e 2%); em todos os casos
utilizou-se população de 100 indivíduos, evoluída por 100 gerações.
Os parâmetros utilizados são apresentados na Tabela 3.1.
Tabela 3.1: Parâmetros utilizados nos experimentos para N=5.
Parâmetros N=5
Configurações iniciais 32
Número de passos 10
Elite 20 indivíduos
População 100 indivíduos
Número de gerações 100
Utilizaram-se dois conjuntos de regras neste trabalho. O primeiro deles é
constituído pelas 64 regras elementares compatíveis com a DCT. O segundo é formado
pela regra da maioria 232 mais o subconjunto das regras compatíveis cujas representações
binárias possuem distância de Hamming até 3 em relação à regra 232; o conjunto
resultante, denominado H3, é exibido na Tabela 3.2.
Tabela 3.2: Conjunto de regras H3.
Regra da Maioria
232 (11101000)
Dist. de Hamming 1
168 (10101000), 200 (11001000), 224 (11100000), 234 (11101010), 236 (11101100),
248 (11111000)
Dist. de Hamming 2
136 (10001000), 160 (10100000), 170 (10101010), 172 (10101100), 184 (10111000),
192 (11000000), 202 (11001010), 204 (11001100), 216 (11011000), 226 (11100010),
228 (11100100), 238 (11101110), 240 (11110000), 250 (11111010), 252 (11111100)
Dist. de Hamming 3
128 (10000000), 138 (10001010), 140 (10001100), 152 (10011000), 162 (10100010),
174 (10101110), 176 (10110000), 180 (10110100), 186 (10111010), 188 (10111100),
194 (11000010), 196 (11000100), 206 (11001110), 208 (11010000), 218 (11011010),
220 (11011100), 230 (11100110), 242 (11110010), 244 (11110100), 254 (11111110)
Para cada um dos conjuntos executaram-se 10 experimentos (i.e., 2 conjuntos de
regras e 6 parametrizações distintas do AG), totalizando 120 execuções, os quais levaram a
272 soluções para a DCT.
39
Inicialmente observou-se que somente 15 regras apareciam nestas soluções: 160,
162, 168, 170, 176, 178, 224, 226, 232, 234, 240, 242, 244, 248 e 250.
A partir das soluções existentes foram feitos testes onde eram substituídas todas as
regras dos arranjos de regras com 32 acertos pelas suas equivalentes dinâmicas contidas
nas 64 regras compatíveis com DCT, e foi possível determinar que as regras 184, 186 e
208 fazem parte das regras que resolvem a DCT; com estas, mais as 15 mencionadas
anteriormente, chegou-se a um total de 18 regras. Observou-se também que todas essas
regras são equivalentes dinâmicas entre si por transformação complementar.
A Tabela 3.3 mostra a equivalência dinâmica entre as regras deste conjunto das
melhores regras para N=5, aqui denominado MR5.
Tabela 3.3: Equivalências dinâmicas por transformação complementar entre as regras do
MR5. Para as regras não explicitadas, entenda-se que a regra obtida pela transformação
é idêntica à original.
Regra Equivalente
Regra da Maioria
232 (11101000)
−
Dist. de Hamming 1
168 (10101000)
224 (11100000)
234 (11101010)
248 (11111000)
Dist. de Hamming 2
160 (10100000)
170 (10101010)
184 (10111000)
240 (11110000)
250 (11111010)
−
226 (11100010)
−
Dist. de Hamming 3
162 (10100010)
176 (10110000)
244 (11110100)
186 (10111010)
242 (11110100)
208 (11010000)
Dist. de Hamming 4
178 (10110010)
−
As conclusões obtidas até então permitiram concluir que, a partir de um arranjo de
regras qualquer para N=5, é possível criar outros, com o mesmo desempenho, através da
equivalência por rotação e pela substituição de todas as regras do arranjo por suas
equivalentes dinâmicas. Aplicando-se os dois mecanismos nas 272 soluções encontradas e,
eliminando-se as equivalentes por rotação ou por equivalência dinâmica, foram obtidas 199
soluções, as quais são apresentadas no Apêndice A.2; destas, algumas são mostradas na
Tabela 3.4.
40
Tabela 3.4: Algumas das soluções ótimas para N=5.
Arranjos de regras com acerto total (32 possibilidades)
{160, 1, 2}, {240, 1, 2}, {234, 1, 1}, {232, 2, 1}, {248, 2, 2}
{162, 2, 2}, {240, 1, 1}, {234, 2, 1}, {232, 2, 1}, {232, 2, 2}
{162, 2, 2}, {240, 1, 2}, {234, 2, 1}, {232, 2, 1}, {232, 2, 2}
{168, 1, 2}, {248, 1, 1}, {170, 2, 1}, {168, 2, 1}, {234, 2, 2}
{168, 2, 1}, {232, 2, 2}, {232, 2, 2}, {240, 1, 2}, {232, 1, 1}
{168, 2, 1}, {232, 2, 2}, {248, 2, 2}, {240, 1, 2}, {232, 1, 1}
{168, 2, 2}, {232, 2, 2}, {240, 1, 1}, {232, 1, 1}, {170, 2, 1}
{168, 2, 2}, {232, 2, 2}, {240, 1, 2}, {232, 1, 1}, {170, 2, 1}
{170, 1, 1}, {232, 2, 2}, {224, 2, 2}, {240, 1, 2}, {232, 1, 1}
{170, 1, 1}, {232, 2, 2}, {232, 2, 2}, {240, 1, 1}, {232, 1, 1}
Quando se analisaram os arranjos ótimos de regras pela perspectiva do grau de
balanceamento de suas regras percebeu-se que todas as soluções eram balanceadas ou
quase balanceadas se observadas como um conjunto. Para se entender esta observação,
considere-se, por exemplo, a solução {{168, 2, 1}, {232, 2, 2}, {248, 2, 2}, {240, 1, 2},
{232, 1, 1}}, cujas regras elementares envolvidas são 168, 232, 248, 240 e 232. Pois bem,
considerando-se agora o grau de balanceamento de cara regra individualmente, têm-se os
valores, respectivamente, 3, 4, 5, 4 e 4, que totalizam 20. Ora, este é exatamente o valor
total que se obteria se todas as regras individuais fossem balanceadas. Assim, tudo se passa
como se a solução em questão fosse balanceada em sua totalidade, ainda que suas regras
não o sejam individualmente. Essa propriedade é muito interessante pois pode ser
entendida como um certo relaxamento da condição de balanceamento que boas regras
individuais da DCT devem obedecer. Trata-se, portanto, de uma flexibilização ou ganho no
processo de resolução da DCT, decorrente da natureza não uniforme e não local da solução
sob análise.
Mais do que isso, observam-se no conjunto de soluções para N=5 apenas três graus
de balanceamento dos arranjos de regras
−
19, 20 e 21
−
todos em torno do valor 20 acima
discutido. Isso sugere, adicionalmente que esse tipo de AC compensa inclusive o não
balanceamento total das regras, caracterizando fortemente um segundo nível de
flexibilização no processo de solução da DCT, nos moldes da discussão acima. A Tabela
3.5 mostra o grau de balanceamento das regras MR5.
41
Tabela 3.5: Grau de balanceamento das regras dos MR5.
Grau de balanceamento Regras
2
160 (10100000)
3
162 (10100010), 168 (10101000), 176 (10110000),
208 (11010000), 224 (11100000)
4
170 (10101010), 178 (10110010), 184 (10111000),
226 (11100010), 232 (11101000), 240 (11110000)
5
186 (10111010), 234 (11101010), 242 (11110100),
244 (11110100), 248 (11111000)
6
250 (11111010)
Ainda relacionado a isto, as soluções foram divididas em grupos, segundo seus
graus de balanceamento de arranjos de regras (19, 20 ou 21). Além disso, foram
substituídas todas as regras e suas vizinhança de raio 1 em regras de raio 2 em cada arranjo
de regra. Observou-se então que em alguns arranjos de regras que possuíam a mesma
disposição das regras e algumas diferenças de vizinhanças possuíam as mesmas regras
correspondentes de raio 2, tendo,portanto, o mesmo comportamento temporal em todas as
condições iniciais possíveis. Portanto, foi possível concluir que existem arranjos de regras
que só diferem entre si por algumas de suas configurações de vizinhanças, mas
efetivamente possuem a mesma evolução temporal, possuindo, portanto, o mesmo
desempenho na DCT. Um exemplo são os conjuntos de ACs:
{{170, 1, 1}, {232, 2, 2}, {248, 2, 2}, {240, 1, 2}, {232, 1, 1}} e
{{170, 2, 1}, {232, 2, 2}, {248, 2, 2}, {240, 1, 1}, {232, 1, 1}},
ambos os quais possuem o mesmo arranjo correspondente de regras de 2, qual seja:
{3435973836, 4210729120, 4294942880, 4278255360, 4240506048}.
Como último experimento, foi compilado um conjunto de todas as soluções ótimas
para N=3 com as 18 regras do MR5, o que levou a 72 soluções perfeitas, já eliminadas
todas as soluções equivalentes por rotação e por equivalência dinâmica. Essas 72 soluções
formam o Apêndice A.1.
Inicialmente, verificou-se a possibilidade de um casamento de padrões de regras e
configuração de vizinhança das soluções de N=3 com as soluções de N=5, ou seja, se
existiam soluções de N=5 que continham a regra e configuração de vizinhança de todas as
42
células de uma das soluções de N=3, respeitando a ordem das células. Porém, nenhum
casamento de padrões foi encontrado.
Num segundo momento, testou-se o casamento de padrões somente das regras,
desprezando as suas respectivas configurações de vizinhanças. Neste caso houve alguns
casamentos, mas não foi possível inferir uma relação direta entre as soluções de N=3 e
N=5 que pudesse ser aplicada em outros tamanhos de reticulado.
3.3 Experimentos para N=7, N=9 e N=11
3.3.1 Primeira Fase dos Experimentos
O intuito da primeira fase dos experimentos era descobrir se existiam regras para
N=7, N=9 e N=11 e se os arranjos de regras poderiam ter regras com ação global.
Para a avaliação de N=7, N=9 e N=11 foram considerados experimentos compostos
por 9 execuções, decorrente da combinação dos três métodos de seleção descritos na
Subseção 2.11.3, e de três taxas de mutação (0,5%, 1% e 2%); em todos os casos utilizou-
se população de 100 indivíduos, evoluída por 200 gerações.
Devido ao fato que não foram obtidos arranjos de regras com índice máximo de
acertos na primeira execução do experimento em todos os tamanhos de reticulados,
acabou-se utilizando taxas de mutação menores (0,4%, 0,5% e 1%). A razão dessa
mudança era tentar obter modificações na configuração dos arranjos de regras de forma
mais localizada, o que poderia gerar arranjos de regras com maior desempenho.
A partir da segunda execução do experimento a população inicial do AG deixou de
ser aleatória e passou a conter a melhor geração da execução anterior, com o intuito de se
buscar maior desempenho; o processo evolutivo transcorria então até que se encontrasse
um arranjo ótimo de regras, ou até que não mais se pudesse melhorar o resultado anterior.
Os parâmetros utilizados são ilustrados na Tabela 3.7.
43
Tabela 3.7: Parâmetros utilizados nos experimentos para N=7, N=9 e N=11.
Parâmetros N=7 N=9 N=11
Configurações iniciais 128 512 2048
Número de passos 14 18 22
Elite 20 indivíduos
População 100 indivíduos
Número de gerações 200
Os conjuntos de regras utilizados nestes experimentos foram as 64 regras
elementares compatíveis com a DCT, as regras com distância de Hamming de até 3 bits
com relação à regra da maioria (H3), e o conjunto das regras elementares presentes nas
soluções para N=5 (MR5).
Na primeira fase dos experimentos, em que se buscava descobrir a existência de
arranjos de regras que solucionassem o problema sem a limitação de vizinhança,
chegaram-se aos seguintes resultados:
• Para N=7: 2 arranjos de regras com acerto máximo de 125 das 128 condições iniciais
possíveis: {{248, 2, 3}, {232, 1, 3}, {224, 3, 3}, {250, 1, 1}, {226, 2, 3}, {224, 2, 1},
{168, 3, 2}} e {{168, 3, 3}, {224, 2, 1}, {250, 2, 1}, {250, 2, 3}, {232, 2, 1}, {232, 3,
3}, {160, 2, 1}}. Adicionalmente a estes, existem mais 77 arranjos de regras com 124
acertos, que constam do Apêndice A.3.
• Para N=9: 14 arranjos de regras com acerto máximo de 480 das 512 condições iniciais
possíveis.
• Para N=11: 6 arranjos de regras com acerto máximo de 1869 das 512 condições iniciais
possíveis.
Os resultados para N=9 e N=11 são apresentados respectivamente nas Tabelas 3.8 e
3.9.
44
Tabela 3.8: Arranjos de regras com 480 acertos para N=9 na primeira fase.
Arranjos de regras com acerto parcial (480 das 512 possibilidades)
{162, 1, 4},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 2},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{184, 4, 4},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{176, 4, 4},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{250, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{186, 4, 4},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{240, 4, 4},{176, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{250, 4, 1},{176, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{218, 4, 4},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 4},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{224, 4, 2},{224, 2, 2},{170, 3, 4},{232, 1, 1},{186, 2, 3},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{232, 4, 4},{224, 2, 2},{170, 4, 4},{232, 1, 1},{186, 2, 3},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{240, 1, 2},{224, 2, 2},{170, 2, 4},{232, 1, 1},{186, 2, 3},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
{240, 1, 1},{224, 3, 2},{170, 4, 4},{232, 1, 1},{186, 2, 3},{242, 4, 3},{250, 1, 1},{234, 2, 1},{232, 2, 4}
Tabela 3.9: Arranjos de regras com 1869 acertos para N=11 na primeira fase.
Arranjos de regras com acerto parcial (1869 das 2048 possibilidades)
{234,4,2},{224,4,5},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{234,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
{234,4,2},{240,4,1},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{232,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
{234,4,2},{240,4,2},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{232,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
{234,4,2},{240,4,3},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{232,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
{234,4,2},{240,4,4},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{232,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
{234,4,2},{240,4,5},{160,4,3},{248,3,4},{248,1,3},{224,1,4},{232,5,2},{168,2,3},{234,5,5},{168,5,1},{250,4,2}
3.3.2 Segunda Fase dos Experimentos
Na segunda fase, procurou-se descobrir o efeito da limitação da vizinhança até o
raio 3 na qualidade dos resultados. Para tanto, os experimentos foram realizados para N=9
e N=11, que admitem raio máximo de vizinhança 4 e 5, respectivamente, impedindo,
portanto, a ocorrência de regras com ação global. O resultados obtidos nestes testes foram
os seguintes:
• Para N=9: 16 arranjos de regras com acerto máximo de 470 das 512 condições
iniciais possíveis.
• Para N=11: 19 arranjos de regras com acerto máximo de 1851 das 512 condições
iniciais possíveis.
45
Os resultados para N=9 e N=11 com limitação do raio de vizinhança são
apresentados nas Tabela 3.10 e Tabela 3.11, respectivamente.
Tabela 3.10: Arranjos de regras com 470 acertos para N=9 na segunda fase.
Arranjos de regras com acerto parcial (480 das 512 possibilidades)
{248,3,1},{232,3,1},{160,2,1},{170,1,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,1,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,2,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,2,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,2},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{160,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,1,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,1,1},{232,3,3},{232,3,3},{240,3,2},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,1,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,2,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,2,1},{232,3,3},{232,3,3},{240,3,2},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,2,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,1},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,2},{248,2,1},{232,2,1}
{248,3,1},{232,3,1},{168,2,1},{170,3,1},{232,3,3},{232,3,3},{240,3,3},{248,2,1},{232,2,1}
Tabela 3.11: Arranjos de regras com 1851 acertos para N=11 na segunda fase.
Arranjos de regras com acerto parcial (1869 das 2048 possibilidades)
{240,2,1},{232,1,3},{232,1,2},{240,3,1},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,1},{232,1,3},{232,1,2},{240,3,2},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,1},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,1,3}
{240,2,1},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,2,3}
{240,2,1},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,2},{232,1,3},{232,1,2},{240,3,1},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,2},{232,1,3},{232,1,2},{240,3,2},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,2},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,1,3}
{240,2,2},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,2,3}
{240,2,2},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,1},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,1,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,1},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,2,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,1},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,2},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,1,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,2},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,2,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,2},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,1,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,2,3}
{240,2,3},{232,1,3},{232,1,2},{240,3,3},{248,1,2},{232,2,3},{232,1,2},{232,1,1},{162,3,2},{232,2,1},{170,3,3}
Tais resultados evidenciam que a limitação de vizinhança reduz o valor máximo de
acertos para N=9 e N=11, sugerindo que arranjos de regras com ação global têm
desempenho um pouco melhor; dessa forma, sugerem ainda que, se existir alguma solução
46
para estes tamanhos de reticulados, ela possivelmente teria pelo menos uma regra de ação
global em sua composição.
Todos os melhores arranjos para N=7, N=9 e N=11 continham somente regras do
conjunto MR5, evidenciando a possibilidade de que se houver alguma solução para estes
tamanhos de reticulado possivelmente seria composto por regras deste conjunto.
3.4 Algoritmo de busca local
Como uma alternativa aos experimentos com AG, foi criado um algoritmo de busca
local onde o objetivo era tentar melhorar os resultados obtidos com o AG para N=7 que
levou a um total de 125 acertos em 128 possibilidades.
O algoritmo funcionava com os seguintes passos:
1) Escolhe-se um AC inicial aleatório, as regras e as configurações de vizinhança
a serem utilizadas no algoritmo.
2) Seleciona-se a primeira célula do AC.
3) Em seguida, gera-se uma combinação de ACs onde é trocado o valor desta
célula por cada valor da combinação entre as regras e as configurações de
vizinhança analisadas, mantendo-se o resto da estrutura do AC.
4) Executa-se a função de avaliação da DCT, verificando-se o resultado obtido
para todos os ACs gerados, e preservando-se os que têm melhor índice.
5) Seleciona-se então a próxima célula de cada um dos melhores ACs obtidos
anteriormente e executam-se os passos 3 e 4.
6) Terminando a célula do último melhor AC analisado, armazenam-se os
melhores ACs desta iteração. Havendo ACs que atingiram o índice da DCT
desejado ou não havendo melhora em termos de índice ou quantidade de
melhores ACs em relação à iteração anterior o algoritmo é finalizado; neste
ponto, mostra-se o resultado final. Caso contrário, seleciona-se novamente a
primeira célula destes melhores ACs e executam-se os passos 3 a 5 novamente.
47
Para testar a eficiência deste algoritmo, inicialmente testaram-se ACs com N=5 e o
algoritmo conseguiu obter arranjos de regras ótimos com o acerto de todas as 32
possibilidades existentes.
Porém, quando foram experimentados ACs com N=7, o algoritmo conseguiu obter
índice máximo de 124 acertos dos 128 possíveis, sendo inferior aos 125 obtidos pelo AG.
Mas, ressalte-se que apenas 2 soluções nesse patamar foram encontradas pelo AG (contra
77 soluções com acerto de 124), sugerindo novamente a efetividade do algoritmo. Num
segundo momento, os melhores ACs obtidos foram usados como ACs iniciais deste
algoritmo, mas não se conseguiu melhorar os índices do AG ou expandir a quantidade de
ACs com o mesmo índice de 125.
Estes experimentos foram desestimulados para N=9 e N=11 devido ao fato que, em
algumas das execuções feitas para N=7 atingiram 2 semanas de execução, e pelo fato de
que as combinações entre regras e configuração de vizinhança e o tempo de execução de
cada AC executado são muito maiores para N=9 e N=11 do que para N=7.
3.5 Experimentos pré-qualificação
Antes do exame de qualificação que precedeu este trabalho, foram feitos
experimentos análogos aos apresentados nas Subseções 3.2 e 3.3, mas esses resultados
foram invalidados devido a um parâmetro que foi utilizado inadequadamente na função de
avaliação dos arranjos de regras. Para entender o ocorrido, observe-se que uma condição
inicial pode ser considerada como pertencendo a um conjunto de outras equivalentes
obtidas por rotação dela, em condição de contorno periódica.
Assim, com o uso do referido parâmetro, o algoritmo verifica se uma condição
inicial a ser testada possui equivalentes por rotação, e se ela é a primeira representante
dessa classe de equivalência. Em caso afirmativo ela é avaliada e a avaliação obtida é
reproduzida para todos os outros membros de sua classe, eliminando a necessidade de
avaliar as condições iniciais equivalentes. O problema existente neste conceito é que cada
condição inicial deste grupo pode gerar respostas diferentes ao ser aplicada em um AC
não-uniforme e com vizinhança não-local, pelo fato de possuir células com regras e
configurações de vizinhanças independentes, o que não ocorre num AC convencional.
48
Assim, na primeira fase, os experimentos chegaram aos seguintes resultados:
• N=5: 257 arranjos ótimos de regras com de 32 acertos.
• N=7: 33 arranjos de regras com 128 acertos.
• N=9: 103 arranjos com desempenho máximo de 494 dos 512 acertos possíveis.
• N=11: 8 arranjos de regras com desempenho máximo de 1905, dos 2048 acertos
possíveis.
Na segunda fase, com limitação do raio de vizinhança a 3 para N=9 e N=11, os
experimentos resultaram em:
• N=9: 9 arranjos de regras com o desempenho máximo de 467 dos 512 acertos
possíveis.
• N=11: 27 arranjos de regras com o desempenho máximo de 1872, dos 2048
acertos possíveis.
Esse parâmetro mascarou os resultados obtidos, levando à conclusão incorreta de
que havia soluções para N=7, fato que não foi comprovado pelos experimentos relatados
nas Subseções 3.2 e 3.3; entretanto, em relação aos resultados para N=9 e N=11 foi
possível preservar a conclusão de que arranjos de regras com regras de ação global têm
desempenho melhor do que as de ação limitada.
49
Capítulo 4 - Considerações Finais
Os ACs não-uniformes com vizinhanças não-locais mostraram ser eficazes e de
rápida convergência para soluções da DCT, em sintonia com o fato de que expandir o raio
de vizinhança da células e cada uma conter regra independente aumenta a troca de
informação entre as células do AC.
Os resultados aqui obtidos expandiram as conclusões de Zanon (2006) e
determinaram que há arranjos ótimos que utilizam mais do que as 4 regras usadas no
experimento lá reportado.
Apesar de se ter encontrado soluções ótimas da DCT somente para N=5, foi
possível concluir sobre algumas características determinantes para se conseguir soluções
ótimas para outros tamanhos de reticulado:
1. A necessidade de existir pelo menos uma regra de ação global no arranjo de regras em
uma boa solução; isso se deve às observações que os melhores resultados aqui obtidos
possuem essa característica, e que todas as soluções para N=5 apresentam pelo menos
uma regra de ação global.
2. A partir de um ACs não-uniforme e com vizinhança não-local qualquer para N=5 se
obtêm arranjos de regras com o mesmo desempenho a partir da equivalência por
rotação ou pela substituição de todas as regras do arranjo por suas equivalentes
dinâmicas por transformação complementar.
3. Foi possível encontrar soluções para N=5 distintas no sentido de serem diferentes ACs
não uniformes, não locais, mas efetivamente idênticas, dado que possuem o mesmo
comportamento de evolução temporal. Tal constatação se verifica pois essas soluções
representam um mesmo AC não uniforme correspondentes no raio 2.
4. Os experimentos deste trabalho permitiram observar que todos os melhores arranjos de
regras para todos os tamanhos de reticulados analisados eram compostos por regras do
50
conjunto MR5, formado por 18 regras, o que evidencia que estas são boas regras a
comporem a formação dos ACs aqui estudados na DCT .
5. Nenhuma das soluções obtidas para N=3 serviu de modelo para gerar uma solução com
N=5, o que talvez indique que não seja possível inferir uma solução com N=7 a partir
de soluções com N=5.
Como próximos passos deste trabalho, caminhos possíveis seriam:
• Criar um melhor algoritmo de busca local que o aqui mencionado na Subseção 3.4, que
pudesse melhorar as soluções apresentadas aqui para N=7, N=9 e N=11, com vistas à
busca de soluções ótimas para esses tamanhos de reticulado.
• Fazer uma análise sobre a influência de cada uma das células com sua regra e
vizinhança no comportamento global do AC não-uniforme com vizinhança não-local
que permite a existência de soluções ótimas para N=5 e aplicá-la para N=7, N=9 e
N=11.
• Verificar se ACs não uniformes com vizinhanças não-locais seriam eficazes também
em outros problemas computacionais, como o da paridade, por exemplo, em que o
objetivo é determinar a paridade de uma cadeia binária [Wolz and de Oliveira, 2008].
• Fazer testes com arranjos de regras usando o conceito de regras de ação global e
vizinhanças com maior quantidade de vizinhos para N=7, N=9 e N=11, como por
exemplo, 5 células em vez das 3 células utilizadas neste trabalho. O intuito deste
experimento seria verificar se este tipo de AC poderia resolver o problema da DCT
para tamanhos de reticulados N=7, N=9 e N=11, pois neste trabalho não foi possível
encontrar soluções ótimas estes tamanhos de reticulados com ACs não-uniformes e
com vizinhança não-local de 3 células.
51
Apêndice A
A seguir, apresentam-se os arranjos de regras ótimos encontrados para N=3 e N=5,
e dos arranjos com 124 acertos para N=7, respectivamente nas Tabelas A.1, A.2 e A.3,
todos da primeira fase dos experimentos, isto é, sem limitação da configuração de
vizinhança.
Tabela A.1: Arranjos ótimos de regras encontrados para N=3.
Arranjos de regras com acerto total (8 possibilidades)
{160,1,1},{232,1,1},{232,1,1}
{160,1,1},{232,1,1},{234,1,1}
{160,1,1},{232,1,1},{248,1,1}
{160,1,1},{232,1,1},{250,1,1}
{160,1,1},{234,1,1},{232,1,1}
{160,1,1},{234,1,1},{234,1,1}
{160,1,1},{248,1,1},{232,1,1}
{160,1,1},{248,1,1},{248,1,1}
{162,1,1},{232,1,1},{232,1,1}
{162,1,1},{232,1,1},{234,1,1}
{162,1,1},{234,1,1},{232,1,1}
{168,1,1},{168,1,1},{232,1,1}
{168,1,1},{168,1,1},{234,1,1}
{168,1,1},{168,1,1},{248,1,1}
{168,1,1},{170,1,1},{232,1,1}
{168,1,1},{170,1,1},{234,1,1}
{168,1,1},{184,1,1},{232,1,1}
{168,1,1},{184,1,1},{248,1,1}
{168,1,1},{232,1,1},{170,1,1}
{168,1,1},{232,1,1},{184,1,1}
{168,1,1},{232,1,1},{232,1,1}
{168,1,1},{232,1,1},{234,1,1}
{168,1,1},{232,1,1},{248,1,1}
{168,1,1},{248,1,1},{168,1,1}
{168,1,1},{248,1,1},{184,1,1}
{168,1,1},{248,1,1},{232,1,1}
{168,1,1},{248,1,1},{248,1,1}
{170,1,1},{170,1,1},{232,1,1}
{170,1,1},{232,1,1},{232,1,1}
{176,1,1},{232,1,1},{232,1,1}
{176,1,1},{232,1,1},{248,1,1}
{176,1,1},{248,1,1},{232,1,1}
{178,1,1},{232,1,1},{232,1,1}
{184,1,1},{184,1,1},{232,1,1}
{184,1,1},{232,1,1},{168,1,1}
{184,1,1},{232,1,1},{232,1,1}
{184,1,1},{232,1,1},{248,1,1}
{184,1,1},{248,1,1},{232,1,1}
{224,1,1},{224,1,1},{232,1,1}
{224,1,1},{224,1,1},{248,1,1}
52
{224,1,1},{232,1,1},{232,1,1}
{224,1,1},{232,1,1},{240,1,1}
{224,1,1},{232,1,1},{248,1,1}
{224,1,1},{240,1,1},{232,1,1}
{224,1,1},{240,1,1},{248,1,1}
{232,1,1},{162,1,1},{232,1,1}
{232,1,1},{168,1,1},{168,1,1}
{232,1,1},{168,1,1},{170,1,1}
{232,1,1},{168,1,1},{232,1,1}
{232,1,1},{176,1,1},{232,1,1}
{232,1,1},{184,1,1},{168,1,1}
{232,1,1},{184,1,1},{232,1,1}
{232,1,1},{224,1,1},{224,1,1}
{232,1,1},{232,1,1},{224,1,1}
{232,1,1},{232,1,1},{232,1,1}
{232,1,1},{232,1,1},{240,1,1}
{232,1,1},{234,1,1},{160,1,1}
{232,1,1},{240,1,1},{240,1,1}
{232,1,1},{248,1,1},{168,1,1}
{234,1,1},{160,1,1},{234,1,1}
{234,1,1},{232,1,1},{160,1,1}
{234,1,1},{232,1,1},{162,1,1}
{240,1,1},{224,1,1},{232,1,1}
{240,1,1},{232,1,1},{224,1,1}
{248,1,1},{160,1,1},{232,1,1}
{248,1,1},{168,1,1},{184,1,1}
{248,1,1},{168,1,1},{248,1,1}
{248,1,1},{224,1,1},{240,1,1}
{248,1,1},{232,1,1},{168,1,1}
{248,1,1},{232,1,1},{176,1,1}
{248,1,1},{232,1,1},{184,1,1}
{248,1,1},{248,1,1},{160,1,1}
Tabela A.2: Arranjos ótimos de regras encontrados para N=5.
Arranjos de regras com acerto total (32 possibilidades)
{160,1,2},{240,1,2},{234,1,1},{232,2,1},{248,2,2}
{162,2,2},{240,1,1},{234,2,1},{232,2,1},{232,2,2}
{162,2,2},{240,1,2},{234,2,1},{232,2,1},{232,2,2}
{168,1,2},{248,1,1},{170,2,1},{168,2,1},{234,2,2}
{168,2,1},{232,2,2},{232,2,2},{240,1,2},{232,1,1}
{168,2,1},{232,2,2},{248,2,2},{240,1,2},{232,1,1}
{168,2,2},{232,2,2},{240,1,1},{232,1,1},{170,2,1}
{168,2,2},{232,2,2},{240,1,2},{232,1,1},{170,2,1}
{170,1,1},{232,2,2},{224,2,2},{240,1,2},{232,1,1}
{170,1,1},{232,2,2},{232,2,2},{240,1,1},{232,1,1}
{170,1,1},{232,2,2},{232,2,2},{240,1,2},{232,1,1}
{170,1,1},{232,2,2},{240,2,1},{240,1,2},{232,1,1}
{170,1,1},{232,2,2},{240,2,2},{240,1,1},{232,1,1}
{170,1,1},{232,2,2},{240,2,2},{240,1,2},{232,1,1}
{170,1,1},{232,2,2},{248,2,2},{240,1,1},{232,1,1}
{170,1,2},{224,2,1},{242,1,2},{232,1,2},{232,1,1}
{170,1,2},{224,2,1},{242,1,2},{232,2,2},{232,1,1}
{170,1,2},{232,1,2},{232,1,1},{170,1,1},{170,1,1}
{170,1,2},{232,1,2},{232,1,1},{170,1,1},{170,2,1}
53
{170,1,2},{232,1,2},{232,1,1},{170,2,1},{170,1,1}
{170,1,2},{232,1,2},{232,1,1},{170,2,1},{170,2,1}
{170,1,2},{232,2,2},{240,1,1},{232,1,1},{170,1,1}
{170,1,2},{232,2,2},{240,1,2},{232,1,1},{170,1,1}
{170,1,2},{232,2,2},{240,1,2},{232,1,1},{170,2,1}
{170,2,1},{232,2,2},{224,2,2},{240,1,2},{232,1,1}
{170,2,1},{232,2,2},{232,2,2},{240,1,1},{232,1,1}
{170,2,1},{232,2,2},{232,2,2},{240,1,2},{232,1,1}
{170,2,1},{232,2,2},{240,2,1},{240,1,1},{232,1,1}
{170,2,1},{232,2,2},{240,2,1},{240,1,2},{232,1,1}
{170,2,1},{232,2,2},{240,2,2},{240,1,1},{232,1,1}
{170,2,1},{232,2,2},{240,2,2},{240,1,2},{232,1,1}
{170,2,1},{232,2,2},{248,2,2},{224,1,2},{232,1,1}
{170,2,1},{232,2,2},{248,2,2},{240,1,1},{232,1,1}
{170,2,2},{224,2,1},{242,1,2},{232,1,2},{232,1,1}
{170,2,2},{224,2,1},{242,1,2},{232,2,2},{232,1,1}
{170,2,2},{232,1,2},{232,1,1},{170,1,1},{170,1,1}
{170,2,2},{232,1,2},{232,1,1},{170,1,1},{170,2,1}
{170,2,2},{232,1,2},{232,1,1},{170,2,1},{170,1,1}
{170,2,2},{232,1,2},{232,1,1},{170,2,1},{170,2,1}
{170,2,2},{232,2,2},{240,1,1},{232,1,1},{170,1,1}
{170,2,2},{232,2,2},{240,1,1},{232,1,1},{170,2,1}
{170,2,2},{232,2,2},{240,1,2},{232,1,1},{170,1,1}
{170,2,2},{232,2,2},{240,1,2},{232,1,1},{170,2,1}
{176,1,2},{232,1,1},{232,2,1},{232,2,2},{232,1,2}
{176,1,2},{240,1,2},{232,1,1},{232,2,1},{248,2,1}
{176,1,2},{248,1,1},{232,2,2},{232,2,2},{232,1,2}
{224,1,1},{234,1,1},{232,2,1},{248,2,2},{224,1,2}
{224,1,1},{234,1,1},{232,2,2},{232,2,2},{224,1,2}
{224,1,1},{234,1,1},{232,2,2},{248,2,1},{176,1,2}
{224,1,1},{234,1,1},{232,2,2},{248,2,2},{224,1,2}
{224,1,1},{234,2,2},{232,2,2},{232,1,2},{226,1,2}
{224,1,2},{240,1,1},{232,1,1},{232,2,1},{248,2,2}
{224,1,2},{240,1,1},{234,1,1},{232,2,1},{248,2,2}
{224,1,2},{240,1,2},{232,1,1},{232,2,1},{248,2,2}
{224,1,2},{240,1,2},{234,1,1},{232,2,1},{248,2,2}
{224,2,1},{232,2,2},{232,1,2},{240,1,1},{170,1,1}
{224,2,1},{232,2,2},{232,1,2},{240,1,2},{170,2,1}
{224,2,1},{248,2,1},{232,2,2},{232,2,1},{162,2,1}
{224,2,2},{232,1,1},{226,2,2},{232,1,1},{234,2,2}
{224,2,2},{248,1,2},{248,1,1},{170,1,1},{224,2,2}
{224,2,2},{248,1,2},{248,1,1},{170,2,1},{224,2,2}
{232,1,1},{170,1,1},{232,2,1},{232,2,2},{232,1,2}
{232,1,1},{170,1,1},{232,2,1},{232,2,2},{232,2,2}
{232,1,1},{170,1,1},{232,2,2},{232,2,2},{232,1,2}
{232,1,1},{170,1,1},{232,2,2},{232,2,2},{248,1,2}
{232,1,1},{170,1,2},{234,1,1},{162,1,2},{232,2,2}
{232,1,1},{170,2,1},{232,2,1},{232,2,2},{232,1,2}
{232,1,1},{170,2,1},{232,2,1},{232,2,2},{232,2,2}
{232,1,1},{170,2,1},{232,2,2},{232,2,2},{232,1,2}
{232,1,1},{170,2,1},{232,2,2},{232,2,2},{248,1,2}
{232,1,1},{170,2,2},{234,1,1},{162,1,2},{232,2,2}
{232,1,1},{170,2,2},{240,2,2},{232,1,1},{232,2,2}
{232,1,1},{224,2,2},{232,1,1},{234,2,2},{240,2,1}
54
{232,1,2},{224,1,1},{170,1,1},{234,2,1},{168,2,2}
{232,1,2},{224,1,1},{234,1,1},{234,2,1},{168,2,2}
{232,1,2},{232,1,1},{170,2,1},{168,2,1},{234,2,2}
{232,1,2},{248,1,1},{170,2,1},{168,2,1},{234,2,2}
{232,2,1},{170,1,1},{232,2,1},{232,2,1},{232,2,2}
{232,2,1},{170,1,1},{240,2,1},{232,2,1},{232,2,2}
{232,2,1},{170,1,1},{240,2,2},{232,2,1},{232,2,2}
{232,2,1},{170,1,1},{248,2,1},{234,2,1},{168,2,2}
{232,2,1},{170,2,1},{224,2,1},{232,2,1},{232,2,2}
{232,2,1},{170,2,1},{232,2,1},{232,2,1},{232,2,2}
{232,2,1},{170,2,1},{240,2,1},{232,2,1},{232,2,2}
{232,2,1},{170,2,1},{240,2,2},{232,2,1},{232,2,2}
{232,2,1},{170,2,1},{248,2,1},{234,2,1},{168,2,2}
{232,2,1},{232,2,1},{178,1,2},{240,1,1},{232,1,1}
{232,2,1},{232,2,1},{178,1,2},{240,1,2},{232,1,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,1},{170,1,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,1},{170,2,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,1},{232,1,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,2},{170,1,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,2},{170,2,1}
{232,2,1},{232,2,2},{232,1,2},{240,1,2},{232,1,1}
{232,2,1},{232,2,2},{232,2,2},{240,1,2},{232,1,1}
{232,2,1},{248,2,1},{232,2,2},{232,2,1},{162,2,1}
{232,2,2},{224,1,1},{234,1,1},{170,2,1},{168,2,2}
{232,2,2},{224,1,1},{234,1,1},{234,2,1},{168,2,2}
{232,2,2},{232,1,2},{168,1,2},{240,1,2},{232,1,2}
{232,2,2},{232,1,2},{178,1,2},{240,1,1},{232,2,2}
{232,2,2},{232,1,2},{232,1,2},{240,1,2},{232,1,2}
{232,2,2},{232,1,2},{234,1,2},{240,1,1},{232,1,2}
{232,2,2},{232,1,2},{240,1,2},{234,1,1},{224,2,2}
{232,2,2},{232,2,1},{178,1,2},{240,1,1},{232,1,1}
{232,2,2},{232,2,1},{178,1,2},{240,1,2},{232,1,1}
{232,2,2},{232,2,2},{224,1,1},{234,1,1},{168,2,1}
{232,2,2},{232,2,2},{224,1,1},{234,1,1},{170,1,1}
{232,2,2},{232,2,2},{224,1,1},{234,1,1},{170,2,1}
{232,2,2},{232,2,2},{224,1,2},{240,1,1},{232,1,1}
{232,2,2},{232,2,2},{224,1,2},{240,1,2},{232,1,1}
{232,2,2},{232,2,2},{232,1,2},{240,1,1},{232,1,1}
{232,2,2},{232,2,2},{232,1,2},{240,1,2},{232,1,1}
{232,2,2},{232,2,2},{240,1,2},{240,1,1},{232,1,1}
{232,2,2},{232,2,2},{240,1,2},{240,1,2},{232,1,1}
{232,2,2},{232,2,2},{248,1,1},{168,1,1},{232,2,1}
{232,2,2},{232,2,2},{248,1,1},{176,1,2},{232,1,1}
{232,2,2},{234,1,2},{240,1,1},{168,1,1},{232,2,1}
{232,2,2},{234,1,2},{240,1,2},{162,2,1},{232,2,1}
{232,2,2},{234,1,2},{240,1,2},{168,1,1},{232,2,1}
{232,2,2},{234,2,2},{240,1,1},{168,1,1},{232,2,1}
{232,2,2},{234,2,2},{240,1,2},{168,1,1},{232,2,1}
{232,2,2},{248,1,2},{232,1,1},{168,2,1},{232,2,2}
{232,2,2},{248,1,2},{240,1,1},{234,1,1},{224,2,2}
{232,2,2},{248,1,2},{240,1,2},{234,1,1},{224,2,2}
{234,1,2},{232,2,2},{240,1,1},{232,1,1},{162,2,1}
{234,1,2},{232,2,2},{240,1,2},{232,1,1},{162,2,1}
{234,2,1},{168,2,2},{232,2,2},{240,1,2},{232,1,1}
55
{234,2,1},{232,2,2},{224,2,2},{240,1,1},{232,1,1}
{234,2,1},{232,2,2},{232,2,2},{240,1,1},{232,1,1}
{234,2,2},{224,2,1},{250,1,1},{224,2,2},{168,2,1}
{234,2,2},{224,2,2},{240,1,1},{224,1,1},{234,1,1}
{234,2,2},{224,2,2},{240,1,1},{232,1,1},{170,1,1}
{234,2,2},{224,2,2},{240,1,1},{232,1,1},{170,2,1}
{234,2,2},{224,2,2},{240,1,2},{232,1,1},{170,1,1}
{234,2,2},{224,2,2},{240,1,2},{232,1,1},{170,2,1}
{234,2,2},{232,2,2},{224,1,2},{232,1,1},{170,2,1}
{234,2,2},{232,2,2},{240,1,1},{224,1,1},{234,1,1}
{234,2,2},{232,2,2},{240,1,1},{232,1,1},{168,2,1}
{234,2,2},{232,2,2},{240,1,1},{232,1,1},{170,1,1}
{234,2,2},{232,2,2},{240,1,2},{224,1,1},{234,1,1}
{234,2,2},{232,2,2},{240,1,2},{232,1,1},{170,1,1}
{234,2,2},{250,2,1},{160,1,2},{224,2,2},{232,1,1}
{240,1,1},{170,2,1},{224,2,1},{232,2,2},{232,1,2}
{240,1,1},{170,2,1},{240,2,1},{232,2,2},{232,1,2}
{240,1,2},{168,1,1},{248,2,1},{232,2,2},{232,1,2}
{240,1,2},{170,1,1},{248,2,1},{232,2,2},{232,1,2}
{240,1,2},{170,2,1},{240,2,1},{232,2,2},{232,1,2}
{240,1,2},{170,2,1},{248,2,1},{232,2,2},{168,1,2}
{240,1,2},{232,1,1},{168,2,1},{232,2,2},{244,2,1}
{240,1,2},{232,1,1},{232,2,1},{224,2,2},{244,1,1}
{240,2,1},{224,1,1},{232,2,2},{234,1,1},{170,1,2}
{240,2,1},{224,1,1},{232,2,2},{234,1,1},{170,2,2}
{240,2,1},{232,1,1},{232,2,2},{168,1,1},{170,2,2}
{240,2,1},{232,1,1},{232,2,2},{234,1,1},{170,1,2}
{240,2,1},{232,1,1},{240,2,1},{232,1,1},{232,2,2}
{240,2,1},{232,1,1},{240,2,2},{232,1,1},{232,2,2}
{240,2,1},{240,1,1},{232,2,2},{232,1,1},{170,2,2}
{240,2,1},{240,1,1},{240,1,2},{232,1,1},{232,2,1}
{240,2,1},{240,1,2},{232,2,2},{232,1,1},{170,1,2}
{240,2,1},{240,1,2},{232,2,2},{232,1,1},{170,2,2}
{240,2,1},{240,1,2},{240,1,1},{232,1,1},{232,2,1}
{240,2,1},{240,1,2},{240,1,2},{232,1,1},{232,2,1}
{240,2,2},{224,1,1},{232,2,2},{234,1,1},{170,1,2}
{240,2,2},{224,1,1},{232,2,2},{234,1,1},{170,2,2}
{240,2,2},{232,1,1},{232,2,2},{168,1,1},{170,2,2}
{240,2,2},{232,1,1},{232,2,2},{170,1,1},{170,2,2}
{240,2,2},{232,1,1},{232,2,2},{234,1,1},{170,1,2}
{240,2,2},{232,1,1},{240,2,1},{232,1,1},{232,2,2}
{240,2,2},{232,1,1},{240,2,2},{232,1,1},{232,2,2}
{240,2,2},{232,2,2},{232,1,2},{240,1,2},{170,2,1}
{240,2,2},{240,1,1},{232,2,2},{232,1,1},{170,1,2}
{240,2,2},{240,1,1},{232,2,2},{232,1,1},{170,2,2}
{240,2,2},{240,1,1},{240,1,1},{232,1,1},{232,2,1}
{240,2,2},{240,1,1},{240,1,2},{232,1,1},{232,2,1}
{240,2,2},{240,1,2},{232,2,2},{232,1,1},{170,1,2}
{240,2,2},{240,1,2},{232,2,2},{232,1,1},{170,2,2}
{240,2,2},{240,1,2},{240,1,1},{232,1,1},{232,2,1}
{240,2,2},{240,1,2},{240,1,2},{232,1,1},{232,2,1}
{242,1,2},{232,1,2},{240,1,1},{232,1,2},{224,2,1}
{242,1,2},{232,1,2},{240,1,2},{232,1,2},{224,2,1}
{248,1,1},{168,1,2},{224,2,2},{224,1,1},{250,1,2}
56
{248,1,1},{168,2,1},{224,2,2},{232,2,2},{248,1,2}
{248,1,1},{170,1,1},{160,2,2},{232,2,2},{248,1,2}
{248,1,1},{170,1,1},{224,2,2},{232,2,2},{248,1,2}
{248,1,1},{170,2,1},{160,2,2},{232,2,2},{248,1,2}
{248,1,1},{170,2,1},{224,2,1},{232,2,2},{232,1,2}
{248,1,1},{170,2,1},{224,2,2},{232,2,2},{232,1,2}
{248,1,1},{170,2,1},{224,2,2},{232,2,2},{248,1,2}
{248,2,1},{224,2,2},{232,2,1},{226,2,1},{232,2,1}
{248,2,1},{232,2,2},{168,1,2},{240,1,2},{170,2,1}
{248,2,1},{232,2,2},{232,1,2},{176,1,2},{170,2,1}
{248,2,1},{232,2,2},{232,1,2},{224,1,1},{170,1,1}
{248,2,1},{232,2,2},{232,1,2},{240,1,1},{168,1,1}
{248,2,2},{224,1,2},{168,1,2},{240,1,2},{232,1,2}
{248,2,2},{224,1,2},{232,1,2},{240,1,1},{232,1,2}
{248,2,2},{224,1,2},{232,1,2},{240,1,2},{232,1,2}
{248,2,2},{232,2,2},{232,1,2},{224,1,1},{170,1,1}
{248,2,2},{232,2,2},{232,1,2},{240,1,1},{168,1,1}
{250,2,1},{160,1,2},{224,2,2},{232,1,1},{234,2,2}
Tabela A.3: Arranjos de regras com 124 acertos encontrados para N=7.
Arranjos de regras com acerto parcial (124 das 128 possibilidades)
{168,3,3},{224,2,1},{250,2,1},{234,2,3},{232,2,1},{232,3,3},{160,2,1}
{168,3,3},{232,3,1},{240,3,1},{232,2,3},{248,1,3},{232,3,2},{232,2,1}
{168,3,3},{232,3,1},{240,3,2},{232,2,3},{248,1,3},{232,3,2},{232,2,1}
{168,3,3},{232,3,1},{240,3,3},{232,2,3},{248,1,3},{232,3,2},{232,2,1}
{170,1,1},{232,2,3},{168,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,1,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,1,3}
{170,1,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,2,3}
{170,1,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,2,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,1,3}
{170,2,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,2,3}
{170,2,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,3,1},{168,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,1,3}
{170,3,1},{168,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,3,1},{232,2,3},{168,2,3},{232,3,3},{232,1,2},{232,2,2},{170,2,3}
{170,3,1},{232,2,3},{168,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,3,1},{232,2,3},{234,2,3},{224,3,3},{232,1,2},{232,2,2},{170,2,3}
{170,3,1},{232,2,3},{234,2,3},{224,3,3},{232,1,2},{232,2,2},{170,3,3}
{170,3,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,1,3}
{170,3,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,2,3}
{170,3,1},{232,2,3},{234,2,3},{232,3,3},{232,1,2},{232,2,2},{170,3,3}
{232,1,2},{240,1,1},{170,1,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,1},{170,2,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,1},{170,3,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,2},{170,1,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,2},{170,2,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,2},{170,3,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,3},{170,1,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,3},{170,2,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,2},{240,1,3},{170,3,1},{232,2,1},{232,3,1},{232,3,3},{232,1,3}
{232,1,2},{240,1,3},{170,3,1},{232,2,1},{232,3,1},{232,3,3},{232,2,3}
{232,1,2},{240,1,3},{170,3,1},{232,3,1},{232,3,1},{232,3,3},{232,3,3}
{232,1,3},{232,1,2},{240,1,1},{170,3,1},{232,2,1},{232,3,1},{232,3,3}
57
{232,1,3},{232,1,2},{240,1,3},{170,1,1},{232,2,1},{232,3,2},{232,3,3}
{232,1,3},{232,1,2},{240,1,3},{170,2,1},{232,2,1},{232,3,1},{232,3,3}
{232,1,3},{232,1,2},{240,1,3},{170,3,1},{232,2,1},{232,3,1},{232,3,3}
{232,1,3},{232,1,2},{240,1,3},{170,3,1},{232,2,1},{232,3,2},{232,3,3}
{232,2,1},{168,3,2},{240,2,1},{232,3,3},{232,2,1},{248,2,3},{232,2,3}
{232,2,1},{168,3,2},{240,2,2},{232,3,3},{232,2,1},{248,2,3},{232,2,3}
{232,2,1},{168,3,2},{240,2,3},{232,3,3},{232,2,1},{248,2,3},{232,2,3}
{232,2,3},{232,1,2},{240,1,1},{170,1,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,1},{170,3,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,2},{170,1,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,2},{170,3,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,3},{170,1,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,3},{170,2,1},{232,2,1},{232,3,1},{232,3,3}
{232,2,3},{232,1,2},{240,1,3},{170,3,1},{232,2,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,1},{170,1,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,1},{170,2,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,1},{170,2,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,1},{170,3,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,1},{170,3,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,2},{170,1,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,2},{170,1,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,2},{170,2,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,2},{170,2,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,2},{170,3,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,2},{170,3,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,3},{170,1,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,3},{170,1,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,3},{170,2,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,3},{170,2,1},{232,3,2},{232,3,2},{232,1,3}
{232,3,3},{232,1,2},{240,1,3},{170,3,1},{232,3,1},{232,3,1},{232,3,3}
{232,3,3},{232,1,2},{240,1,3},{170,3,1},{232,3,2},{232,3,2},{232,1,3}
{240,3,1},{232,3,1},{232,2,3},{224,3,1},{232,3,2},{160,2,1},{248,3,2}
{240,3,1},{232,3,1},{232,2,3},{224,3,1},{248,3,2},{160,2,1},{248,3,2}
{240,3,2},{232,3,1},{232,2,3},{224,3,1},{232,3,2},{160,2,1},{248,3,2}
{240,3,2},{232,3,1},{232,2,3},{224,3,1},{248,3,2},{160,2,1},{248,3,2}
{240,3,3},{232,3,1},{232,2,3},{224,3,1},{232,3,2},{160,2,1},{248,3,2}
{240,3,3},{232,3,1},{232,2,3},{224,3,1},{248,3,2},{160,2,1},{248,3,2}
{248,2,3},{232,1,3},{224,3,3},{248,1,1},{226,2,3},{224,2,1},{168,3,2}
{248,2,3},{232,1,3},{224,3,3},{248,1,1},{226,2,3},{224,2,1},{170,1,2}
{248,2,3},{232,1,3},{224,3,3},{248,1,1},{226,2,3},{224,2,1},{170,2,2}
{248,2,3},{232,1,3},{224,3,3},{248,1,1},{226,2,3},{224,2,1},{170,3,2}
{248,2,3},{232,1,3},{224,3,3},{250,1,1},{226,2,3},{224,2,1},{168,2,2}
{248,2,3},{232,1,3},{224,3,3},{250,1,1},{226,2,3},{224,2,1},{170,1,2}
{248,2,3},{232,1,3},{224,3,3},{250,1,1},{226,2,3},{224,2,1},{170,2,2}
{248,2,3},{232,1,3},{224,3,3},{250,1,1},{226,2,3},{224,2,1},{170,3,2}
58
Apêndice B –NKS Summer School 2007
Durante este programa de mestrado, participei do NKS Summer School 2007, em
junho-julho de 2007, na cidade de Burlington, estado de Vermont, Estados Unidos, para o
qual fui aceito segundo esquema competitivo internacional.
O curso, patrocinado pela Wolfram Research, tinha como base o livro New Kind of
Science, de Stephen Wolfram, e tinha como objetivo o desenvolvimento de projetos
computacionais utilizando o software Mathematica (no caso, a versão mais recente, 6.0),
segundo a metodologia NKS. O projeto desenvolvido por mim foi descobrir regras
elementares que resolvessem a DCT em qualquer tamanho de reticulado, porém, a idéia era
inserir bits 0s ou 1s extras na condição inicial, de forma que se obtivesse o resultado final
desejado. Durante o curso foram apresentadas palestras sobre aplicações de autômatos
celulares em várias áreas como matemática, física e biologia, e foi uma oportunidade única
de conhecer personalidades da área cientifica relacionadas com autômatos celulares e
também para ter contato com outras pessoas que trabalham nesta área ou afins, em várias
partes do mundo.
Foram feitos testes com os ACs de tamanhos 5, 7, 9, 11 e 13, dado que são os
menores tamanhos de ACs para os quais não existem soluções triviais utilizando ACs
elementares. Os experimentos chegaram aos seguintes resultados:
• 19 regras para N=5: 7, 21, 23, 31, 33, 37, 41, 73, 87, 91, 97, 107, 109, 121,
123, 164, 218, 232.
• 8 regras para N=7: 7, 21, 23, 31, 37, 87, 91, 232.
• 6 regras para N=9, N=11 e N=13: 7, 21, 23, 31, 87, 232.
Com esses resultados, foi possível concluir que as 6 regras obtidas para N=9, N=11
e N=13 muito provavelmente resolvem também outros tamanhos de reticulados.
Esses resultados foram apresentados em uma palestra do NKS Summer School 2007
e foi exposto um pôster no NKS Conference 2007 [Faria, 2007].
59
Referências Bibliográficas
[Capcarrère e Sipper, 2001] M.S. Capcarrère e M. Sipper. “Necessary conditions for
density classification by cellular automata”. Physical Review E, 64(3):036113/1-
036113/4, 2001.
[Cook, 2004] M. Cook. “Universality in elementary cellular automata”. Complex Systems
15(1) 1-40, 2004.
[de Oliveira, 2007] P.P.B. de Oliveira. Cellular automata package for Mathematica,
Software de distribuição restrita, disponibilizada pelo autor, 2007.
[Fukś, 1997] H. Fukś. “Solution of density classification problem with two cellular
automata rules”. Physics Review E, 55:208IR-2084R, 1997.
[Faria e de Oliveira, 2007] F. Faria e P.P.B. de Oliveira. Autômatos celulares não-
uniformes, com vizinhança não-elementar, no problema da classificação de
densidade. Boletim Técnico de Pós-Graduação 089/2007, Universidade
Presbiteriana Mackenzie, São Paulo, SP, 11 páginas, 2007.
[Faria, 2007] F. Faria. Apresentação de palestra no NKS Summer School 2007 e pôster no
NKS Conference 2007. Disponível em:
http://www.wolframscience.com/summerschool/2007/participants/faria.html.
Visitado em: 01/12/2007, 2007.
[Kunyosi e Miki, 2004] M.K. Kunyosi e F.T. Miki. Solução do Problema de Classificação
de Densidade com Algoritmo Genético. Trabalho da disciplina de Inteligência Artificial,
Universidade Presbiteriana Mackenzie, Manuscrito não publicado, 2004.
[Land e Belew, 1995] M. Land e R. Belew. “No Perfect Two-State Cellular Automata for
Density Classification Exists”. Physical Review Letters, 74(25):5148, 1995.
[Li, 1992] W. Li. “Phenomenology of Nonlocal Cellular Automata”. Journal of Statistical
Physics, 68:829-882, 1992.
[Mitchell, Crutchfield and Das, 1996] M. Mitchell, J.P. Crutchfield and R. Das. “Evolving
cellular automata with genetic algorithms: A review of recent work”. In:
Proceedings of International Conference on Evolutionary Computation and Its
Applications. Moscow, 5, 1996.
60
[Mitchell, 1998] M. Mitchell. “Computation in cellular automata: A selected review”. In:
T. Gramβ, S. Bornholt, M. Groβ, M. Mitchell and T. Pellizzari. Non-Standard
Computation, Wiley-VCH: Weinheim, Germany, p. 95-140, 1998.
[Mitchell, 1998b] M. Mitchell. An Introduction to Genetic Algorithms. Bradford Book,
Reprint edition, 1998.
[Packard, 1998] N.H. Packard. “Adaptation towards the edge of the chaos”. In J.A.S.
Kelso, A.J. Mandell, M.F. Shlesinger, editors, Dynamic Patterns in Complex
Systems, pages 293-301, World Scientific, Singapore, 1998.
[Sipper, 1996] M. Sipper. “Co-evolving non-uniform cellular automata to perform
computations”. Physica D, 92:193-208, 1996.
[Sipper, 1998] M. Sipper. “A simple Cellular Automata that solves the density and
ordering problems”. International Journal of Modern Physics, 9(7), 1998.
[Sipper e Tomassini, 1999] M. Sipper e M. Tomassini. “Computation in artificially
evolved, non-uniform cellular automata”. Theoretical Computer Science, 217:81-
98, 1999.
[von Neumann, 1966] J. von Neumann. Theory of Self-Reproducing Automata. University
of Illinois Press, Illinois, 1966. Edited and completed by A.W. Burks.
[Wolfram, 1984] S. Wolfram. “Universality and complexity in cellular automata”. Physica
D, 10:1-35, 1984.
[Wolfram, 2002] S. Wolfram. A New Kind of Science. Champaign, IL: Wolfram Media,
2002.
[Wolz and de Oliveira, 2008] D. Wolz e P.P.B. de Oliveira. “Very effective evolutionary
techniques for searching cellular automata rule spaces”. Journal of Cellular
Automata, 2008. No prelo.
[Zanon, 2006] R.M. Zanon. Explorando Arranjos Espaciais e Conexões Não-Locais em
Autômatos Celulares Elementares. Dissertação de Mestrado em Engenharia
Elétrica, Faculdade de Computação e Informática, Universidade Presbiteriana
Mackenzie, São Paulo, 2006.
[Zanon e de Oliveira, 2008] R.M. Zanon e P.P.B. de Oliveira. Classificação de densidade
através de autômatos celulares com conexões não-locais, Manuscrito em processo
de submissão, 2008.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
