Introducción a la Sociomática El Estudio de los Sistemas Adaptables Complejos en el Entorno

Socioeconómico.

Dr. Gonzalo Castañeda

Capítulo 3: Autómatas Celulares

3.0.- Introducción• Los autómatas celulares (CA) son modelos computacionales

conformados por un gran número de componentes (o células), cada uno de los cuales se comunican con una fracción relativamente pequeña de los demás componentes.

• Creados por J. Von Neumann y S. Ulam en los 40’s y 50’s• Los CA se forman con una retícula en las que cada bloque o

celda es una célula, por lo general se trata de arreglos en 1-D o en 2-D.

• El estado de c/célula toma valores discretos que cambian a través del tiempo en función de su propio estado y el de los objetos (o células) ubicados en una cierta vecindad.

• Aunque las reglas de transición hayan sido impuestas de arriba-hacia-abajo, al aplicarse a todos los agentes se genera un proceso descentralizado (de abajo-hacia-arriba)

• El mundo artificial “crece” a partir de condiciones iniciales especificadas por el analista: configuración de la retícula, vecindades, estados iniciales, condiciones de frontera

3.1 topología de un CA• Con frontera: línea en 1-D, cuadrícula en 2-D• Sin frontera (periódicas): círculo en 1-D (se unen

extremos de la línea), torus en 2-D (se une el N al S y el E al O)

• En el caso con fronteras las vecindades limítrofes no son del mismo tamaño que las centrales

• Retícula en 2-D:

• Torus

Vecindades de un CA• Las vecindades de un CA se definen tomando como

centro cada una de las células de la retícula, y su tamaño depende del número de células incluidas en un determinado radio

• Cuando la “visión” de la célula se considera importante para delimitar el rango de interacción el radio de la vecindad es definido por el analista

• A) de Von Neumman B) de Moore

Reglas de transición• En la mayoría de los CA el conjunto de estados es binario

(blanco o negro, 1 ó 0, vivo o muerto, encendido o apagado)• En una vecindad Von Neumann existen 25 = 32 posibles

configuraciones• Como las reglas de transición se construyen con 32

argumentos y se asignan uno de los dos estado, existen 232 variedades de CA

• En una vecindad tipo Moore hay 29 = 512 configuraciones y 2 512 posibles CA

• En un CA de 1-D con 3 miembros, las configuraciones posibles son 23 y el número de reglas o CA son 28.

• El número de variantes de un CA crece exponencialmente con el número de estados (D) y con el tamaño de las vecindades (K) : DDK

3.2.-Autómatas celulares en 1-D

• Matemáticamente una regla de transición con una vecindad de radio 1 (K =3) se define:

• Una regla para este tipo de CA sería

)(),(),()1( 11 tDtDtDftD iiii

Di-1(t) Di(t) Di+1(t) Di(t+1)

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

• Representación gráfica de un CA en 1-D

• Representación Matemática

1)1( contrario lo de

i 0)(D si 0)1(

i 1)(D si 0)1(

i

ii

ii

tD

ttD

ttD

i

i

• Al graficar en renglones sucesivos los diferentes estados alcanzados por el CA de 1-D se visualiza su evolución a través del tiempo.

• Ejemplo cuando se inicializa con las dos células centrales activas

El triángulo de Sierpinski• Al aplicar la regla 90 a un CA de 1-D se logra

simular el triángulo de Sierpinski (topología es un círculo, célula encendida = color amarillo)

• La célula se apaga en t+1 para cualquier célula que está apagada o encendida en t cuando no existe alguna otra célula encendida en su vecindad (muerte por aislamiento)

• La célula también se apaga en t+1 para cualquier célula que está apagada o encendida en t cuando las otras dos células en su vecindad están encendidas (muerte por saturación).

• Cuando sólo una célula esta apagada o sólo una está encendida la célula central se enciende en t+1 o se deja encendida si ya lo estaba.

Simulación en NETLOGO: Model Library → Sample Models → Computer Science → Cellular Automata →

CA 1D Simple Examples → CA 1D Rule 90

3.3.- El Juego de la Vida• Creado en los 60’ por John Comway: analizar la

capacidad de auto-reproducción; entendida como la creación de programas (información a procesar) a partir de programas con estructuras de información –datos e instrucciones- similares

• (i) una célula viva muere cuando se encuentra aislada, es decir, cuando está rodeada por menos de dos vecinos;

• (ii) una célula viva muere cuando existe sobrepoblación, es decir, cuando tiene más de tres vecinos;

• (iii) una célula nace cuando está vacía (sin existencia) y tiene tres vecinos con vida;

• (iv) en todos los demás casos (exactamente dos vecinos) la célula no modifica su estado.

• Matemáticamente:• Aislamiento: • Stasis: • Reproducción:

• Sobrepoblación

• Objetos que se pueden crear son muy variados:• (i) estáticos (boat, block): • (ii) periódicos (blinker, toad): • (iii) móviles (Glider, Lightweight spaceship)

kii

t ,k

ik 0 1)(tD entonces 2)(D Si

kii

t ,k

iik (t)D 1)(tD entonces 2)(D Si

kii

t ,k

ik 1 1)(tD entonces 3)(D Si

kii

t ,k

ik 0 1)(tD entonces 3 )(D Si

Tumbler: ejemplo de objeto periódico

• La configuración inicial se auto-reproduce cada 12 periodos

• la celda (f4) se mantiene en negro por efecto de stasis,

• la celda (c3) pasa de negra a blanca por el efecto de la sobrepoblación;

• la celda (e2) pasa de negro a blanca por efecto del aislamiento;

• la celda (f1) se vuelve negra por efecto de la reproducción.

Simulación en NETLOGO: Model Library → Sample Models →

Computer Science → Cellular Automata → Life • Se siembran aleatoriamente 35% de células vivas (color rojo)• Por lo general cuando avanza la “vida” se llega a una situación

estacionaria• Pero esta puede crecer ininterrumpidamente (Gosper Glider

Gun)• Otras opciones disponibles en internet:• http://www.bitstorm.org/gameoflife/

* El juego de la vida y la computación universal

• Tiene la capacidad de realizar cualquier tipo de computación.

• Distintas configuraciones de un CA = códigos de instrucciones y datos de un programa.

• Regla de transición = sistema operativo que indica la forma de ejecutar el programa

• Distintos objetos o estructuras de información (i.e., glider, glider guns) se pueden asociar a operadores lógicos (and, or, not)

• Todas las combinaciones de operaciones lógicas se pueden construir en el juego de la vida.

3.4.- El Juego de las Mayorías• Se trata de un CA de 2-D en donde las opiniones de

un individuo se modifican en función del sentir mayoritario (presión social).

• Aplicaciones: formación de opiniones y actitudes, propagación de gustos, modas o normas sociales, intención de voto de los individuos.

• El estado suele ser binario ( cerveza o vino, Chelsea o Barcelona, güeras o trigueñas, pelo largo o corto)

kii

t ,k

ik 1 1)(tD entonces 4)(D Si

kii

t ,k

ik 0 1)(tD entonces 4)(D Si

En el caso contrario )()1( tDtD ii

En NetLogo : Model Library → Sample Models → Social

Science → Voting.* • El sembrado inicial es aleatorio (azul y verde), conforme avanza la corrida

se forman clusters en donde la opinión marginal adopta la posición mayoritaria (en la frontera se ubica el voto dividido)

• Otras reglas: (i) en caso de empate hay cambio de color, (ii) el voto de la célula central se le da al perdedor cuando hay una relación 5 a 3; (iii) agentes heterógenos con diferentes criterios para cambiar la decisión del voto

• ¿Es posible que las opiniones cambien de manera permanente?, ¿De qué depende el tamaño de los clusters?

• Cuando se toma un color aleatorio en caso de empate es posible generar una posición homogénea en todo el espacio (Gilbert y Troitzch).

• http://cress.soc.surrey.ac.uk/s4ss/code/NetLogo/majority.html

3.5.- Reglas probabilísticas• Sembrado inicial aleatorio pero el modelo es

considerado determinístico.• Modelo estocástico requiere de reglas

probabilísticas (se aplican en unos casos y en otros no) o introducir contingencias no previstas que afecten el entorno y las acciones

• Regla determinística:

• Regla estocástica: 0)1(D contrario caso elen

1 )1(D entonces 1 )(D Si

i

,ik ik

t

ttik

0)1(D contrario caso elen

1 )1(D entonces [0,1] aleatorio númeroy 1 )(D Si

i

,ik ik

t

ttik

CA estocástico en 1-DNETLOGO: Model Library → Sample Models → Computer Science → Cellular

Automata → CA Stochastic.* • Con reglas determinísticas el 100% ó 0% de las

veces se aplica “on” en las 8 configuraciones posibles

• Con reglas estocásticas se elige un porcentaje entre estos números (puede ser diferente para c/configuración)

• El indicador de entropía (probabilidad de que se repitan secuencias) (orden = 0, caos = 1 todas las secuencias tienen la misma probabilidad de aparecer)

• En la simulación se aprecia que el tipo de regla sí importa.

• Regla estocástica (default)

• Regla determinística (100% siempre ‘on’ en primera columna y 0% en segunda columna)

Modelo del chisme o rumorModel Library → Sample Models → Social

Sciences → Rumor Mill.* • Una vez que un individuo conoce un chisme (idea, innovación

actitud) lo divulga en su vecindad a través del contacto cotidiano

• La persona que conoce el chisme escoge un vecino al azar para pasárselo (el chisme nunca se olvida)

• En la pantalla el tono de color verde indica cuantas veces se ha oído el mismo chisme.

• ¿Por qué la transmisión se da en todas direcciones pero de manera irregular?

3.6 Vecindades extendidas• En ocasiones conviene representar a individuos con ‘visiones’

diferencidas• Comportamientos heterogéneos: (i) por actitudes (grado de

parroquianismo → connotación social); (ii) por disponibilidad de recursos (conseguir información distante→ costos de transacción)

• En los modelos de formación de opiniones el grado de influencia varía en función del distanciamiento (físico o social)

• Modelo de ‘impacto social’ de Latané (opresores y partidarios): (a) efecto de la reciprocidad; (b) ‘fuerza’ de la persuación

N

j kj

jko d

Si

1

2

2

Modelo de impacto socialCommunity Models (SITSIM)

http://ccl.northwestern.edu/netlogo/models/community/Sitsim • La opiniones iniciales se siembran aleatoriamente, el

observador define el ponderador que todos los agentes asignan a su propia opinión vis-a-vis el resto ( 0 = fuerza de los demás es muy reducida)

• El cambio de color ocurre cuando el indicador de influencia de los opositores es mayor al de los partidarios

• ¿Por qué la opinión minoritaria no desaparece? ¿por qué se forman islas? ¿ ¿qué sucede cuando se da mucho peso a la opinión propia?

3.7 Diseminación cultural• ¿La interacción social conduce a la

homogeneidad cultural?

• CA de Axelrod: estados descritos a través de vector multivariado y número finito de valores.

• No hay telepatía social, comunicación requiere similitud cultural (religión, lenguaje, ideología)

• A mayor similitud mayor interacción, a mayor interacción mayor similitud

• Célula A (2,7,4,4,0), célula B (3,7,5,4,1) 40% de similitud: variantes 7 y 4 en 2o y 4o lugar.

* El modelo de Axelrod• CA 10 x 10, vecindades Von Neumann• Vector culrural sembrado aleatoriamente con 5

elementos culturales y 10 variantes culturales• Regla de transición: (i) se activa al azar una célula y se

elige aleatoriamente a vecina• (ii) células interactúan con probabilidad definida a partir

del grado de similitud.• Interacción: cambia variante de elemento cultural

diferente en célula central• En vectores (2,7,4,4,0) y (3,7,5,4,1) cambia 2 por 3 si

primer elemento es elegido

* Patrón emergente• Coexisten convergencia cultural local y

polarización cultural global

• Cierto número de corridas con este escenario en los demás hay homogeneidad

• (a) inicial (b) 80, iteraciones

* Axelrod en Netlogo• Modelo de Diseminación cultural disponible

en “Community Models”

• Resultados: afinidad cultural es paulatina y regiones culturales en devenir histórico

• Secuencia de una corrida:

• Entre más variantes culturales mayor número de regiones culturales

• Entre más elementos culturales menor número de regiones culturales

• Intuición: existen mayores posibilidades de encontrar variantes afines

• ¿Qué pasa si cambia el tamaño del territorio?• (a) con 15 variantes (b) con 20 variantes

3.8.- Los autómatas celulares y el umbral del caos

• ¿Por qué en el juego de la vida se pueden crear objetos estáticos, periódicos y móviles?

• Langton estableció la conexión entre las transiciones de fase de la materia y la computación (capacidad de almacenar información y ejecutar instrucciones) → ‘umbral del caos’

• ¿Existe también un umbral del caos en la vida misma? Transición entre una sociedad industrial y una post-industrial → cambios tecnológicos, institucionales y culturales

• S, Wolfram: los autómatas celulares tienen una gran similitud con fenómenos físicos representados a través de sistemas de ecuaciones no lineales

Clases de Wolfram en los CA de 1-D• (i) Clase I :“punto de atracción”, células del autómata

terminan por alcanzar un arreglo homogéneo (todas vivas o muertas) en uno o dos periodos.

• (ii) Clase II: se converge a un escenario periódico o estado estacionario en el que los mismos patrones se repiten cada determinado ciclo.

• (iii) Clase III: situación caótica; a lo largo de la simulación se producen movimientos erráticos en los que no es posible identificar patrón alguno.

• (iv) Clase IV: entorno de gran complejidad; se combinan burbujas que se comportan cíclicamente y objetos que crecen y al combinarse entre si dan origen a nuevas estructuras en una dinámica muy creativa (juego de la vida)

Categorías de CA en 1-DNetLogo: Library → Sample Models → Computer Science → Cellular

Automata → CA 1D Elementary. • El programa ofrece la posibilidad de elegir el

porcentaje de células vivas y el número de regla de transición a aplicar

• A continuación se presenta el caso de una densidad de vivas del 10%

• Clase I: Homogéneo: después de una fase de transición eventualmente todos viven o mueren (regla 255)

• Clase II: Periódico: el patrón se repite periódicamente en el espacio o en el tiempo. (regla 59)

• Clase III: caótico: el patrón crece de manera anárquica con pequeñas islas de orden (regla 161)

• Clase IV: complejidad: comportamientos locales estables y objetos que se transforman (regla 73)

Categorías en un modelo de crecimiento con ecuaciones no-lineales

• El modelo (P(0) = 0, C = 5000:• (a) ‘Punto de atracción ( = 1) (b) ‘Atractor periódico’ ( = 2)

• (ib’) Ciclos irregulares ( = 2.5) (iv) ‘trayectoria caótica’ ( = 3)

)(P C )(P )(P ttt

Lambda de Langton• Wolfram detectó una categoría adicional a la establecida en sistemas

matemáticos no-lineales: (Clase IV)• Peró Langton planteó que esa categoría tiene características

especiales• La lambda () define la probabilidad de que cualquier célula de la

reticula está muerte en el periodo siguiente (0 → Clase I, 0.5 → Clase III); la Clase IV en una región intermedia.

• Matemáticamente

• en donde N = total de configuraciones de la regla de transición que conducen a un estado muerto.

• Analogías: (Sólidos → Transición de Fase → Líquidos)• (Clases I y II → Clase IV → Clase III); • (Orden → Complejidad → Caos);• (se detiene la operación del algoritmo → indecisión → no se detiene

la operación del algoritmo).

K

K

D

ND

* Crítica a Langton• Difícil capturar a través de un parámetro () un fenómeno multi-

dimensional• Si una regla (110) está en la región de complejidad ¿qué

sucede con las reglas vecinas?

• No hay coincidencia entre Wolfram y Langdon • 3 reglas vecinas caóticas, 5 restantes estacionarias “umbral

del caos”; en realidad existen diversos bordes o fronteras

• Para un CA con D = 2, k = 3 se tienen 32 reglas caóticas y 6 complejas para una de .44 y .46 en promedio, respectivamente → complejidad en el umbral del caos

• Inferencia de Langton tiene sentido en el agregado pero no en los casos individuales

• Cabe notar que para se dan cualquiera de los tres comportamientos (punto fijo, ciclos, caos) → no es posible identificar cambios en con transiciones

• Reglas complejas están al lado de comportamientos caóticos, pero no necesariamente en la frontera del caos existen comportamientos complejos

• “Umbral del caos”, aunque no validado científicamente es todavía útil como metáfora