Fenómeno de sincronización con autómatas celulares

En la naturaleza se dan lo que se conoce como fenómenos de sincronización, elementos que se sincronizan solos a partir de un pequeño intercambio de información local.

Si colocas varios metrónomos, cada uno marcando un tiempo, en una superficie que permita la transferencia de movimiento entre ellos acaban sincronizándose.

Las luciérnagas también sincronizan sus destellos hasta terminar destellando al unisono, este proceso tiene una complicación más ya que cada luciérnaga solo percibe a sus vecinas más cercanas por lo que el procesos de intercambio de información ocurre a escala local, pero acaba afectando de forma global.

Como vemos lo que tiene en común es el intercambio de información.

Vamos a simular esto mismo de una forma simple. Para ellos tendremos un autómata celular donde cada celda empieza en un estado de N posibles (4 en nuestro caso: rojo, azul, lima y amarillo) elegido al azar, cada uno de ellos con igual probabilidad. No cuesta mucho imaginar que en un autómata celular con C celdas habrá aproximadamente C/N celdas en cada estado distribuidas uniformemente.

En cada iteración cada celda mirará a sus 8 vecinos, elegirá uno al azar y copiará su estado.

El ejemplo está aquí y el código aquí.

El autómata durante su ejecución

En podríamos pensar que si dejamos funcionar este sistema durante mucho tiempo lo único que ocurrirá es que los individuos irán intercambiando sus estados en un confuso baile de colores. Sin embargo si se deja el tiempo suficiente los estados empiezan a agruparse y a crecer como si compitieran entre ellos hasta que uno a uno comienzan a desaparecer hasta que al final solo queda uno. Todas la celdas han sincronizado su color.

Resultado final con todas las celdas sincronizadas

Si el autómata es pequeño el resultado se alcanza antes, cuando es muy grande tarda mas tiempo en llegar a el, pero al final el resultado es el mismo todas se sincronizan (aunque el color final sea diferente cada vez)

¿Como es esto posible? En teoría no debería cambiar demasiado el estado global, cambiamos aleatoriamente el valor de cada celda copiando el de un vecino que a su vez es aleatorio. Fijaos que ni siquiera es un intercambio inteligente ni muy organizado. Lo que ocurre es que en el azar hay pequeñas desviaciones, pequeñas zonas locales donde un color se vuelve mayoritario esto es posible por el intercambio de información entre vecinos. Cuantos más individuos de ese color existan más probable es que ese estado sea copiado por otros. Cuando un individuo queda rodeado de vecinos en su mismo estado se ha creado un núcleo estable que será difícil de cambiar y que ira creciendo. Solo en la frontera de ese núcleo puede darse el cambio. Basta un pequeño desequilibrio para que el intercambio de información entre vecinos lo realimente y crezca. Al ser un proceso aleatorio hay vaivenes, un color que es mayoritario puede descender bruscamente y otro ocupa su lugar hasta llegado a un punto en que un color es tan mayoritario que acaba imponiéndose.

Debajo puede verse una gráfica con lo % de cada color en la ejecución del autómata.

La evolución en % de los cuatro colores hasta que uno se impone (el 2º)

Caminata aleatoria (random walk) en un autómata celular

Una caminata aleatoria, random walk en inglés, es un proceso aleatorio donde una partícula (aquí partícula es una forma elegante de decir «cosa») se mueve avanzando en direcciones aleatorias donde la elección en cada momento no está condicionada por ninguna elección anterior. Se suele ilustrar con el paseo realizado por un caminante borracho que elige aleatoriamente entre alguna de las posibles direcciones que tiene alrededor y da un paso en esa dirección. Tras ese paso repite el proceso. En nuestra simulación los pasos van a tener todos el mismo tamaño, una celda. Para evitar las diagonales (que seria avanzar 1,41 veces mas que por lo lados) se va a usar una vecindad de tipo von Neumann lo que deja solo cuatro vecinos por celda y solo cuatro direcciones en las que el caminante se puede mover (arriba, abajo, izquierda, derecha)

Los estados de las celdas son solo dos, si contiene al caminante o no. Para mejorar la visualización se suele definir un tercer estado que indica si la celda ha sido visitada alguna vez o no por el caminante. Este tercer estado es algo simplemente visual y no afecta en nada a los movimientos del caminante.

  • Negra, celda sin visitas
  • Blanca, celda visitada
  • Azul, indica la celda donde esta el caminante

Las reglas son muy simple, la celda donde este el caminante elige una de sus cuatro vecinas y se mueve ahí.

El simulador se puede ver aquí y el código aquí.

El autómata celular Ulam-Warburton

El autómata celular Ulam-Warburton (UWCA) genera un patrón fractal bidimensional usando autómatas celulares con vecindad de von Neumann con dos estados: encendido y apagado. Comienzan con una celda encendida(generalmente el central) y los demás apagadas. La regla que genera el autómata es muy sencilla, si tienes un único vecino encendido cambias tu estado a encendido. Cuando una celda se enciende ya no se apaga.
Por motivos de visualización se puede añadir un nuevo estado que sería «recién encendido» ese estado lo tienen las céldas que acaban de cambiar de estado y solo dura un ciclo antes de cambiar a encendido.

En el ejemplo cada estado viene indicado con un color:

  • negro: apagado
  • blanco: encendido
  • rojo: recién encendido

Se puede probar en este simulador https://cubiwan.github.io/cellularAutomataExamples/UlamWarburton.html y el código puede verse aquí.

Veamos algo de teoría, a partir del segundo ciclo el número de celdas nuevas en cada ciclo sigue esta formula:

Donde wt corresponde a :

¿Cómo calculamos el sumatorio hasta infinito? Vamos a hacerlo de una forma matemáticamente poco elegante y burda pero fácil de entender. Como 2^k crece muy rápido vamos a calcular el sumatorio solo de los primeros 30 valores (y con menos también serviría).

Debajo dejo el código JS para calcular el valor de wt y de u:

function sumWt(n, k){
    if(k == 0) {
        return 0;
    } else {
        return sumWt(n, k-1)+Math.floor(n/Math.pow(2,k))
    }
}

function wt(n){
    return n - sumWt(n, 30) //calcular hasta k = 30;
}

function u(n){
    return 4/3 * Math.pow(3, wt(n-1));
}

Vamos a calcular unos cuantos resultados para wt

0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6

Podemos intuir una especie de patrón, para verlo claro vamos a quitar las comas y cada vez que veamos un 1 empezaremos una nueva línea:

1
12  
1223  
12232334
1223233423343445
12232334233434452334344534454556

Vemos que el patrón es sencillo, tomamos todos los resultados donde el último 1 y los repetimos dos veces, al segundo grupo le sumamos uno.

1 => 1
1 (1+1) => 12
12 (1+1)(2+1) => 1223
1223 (1+1)(2+1)(2+1)(3+1) => 12232334

Si wt tiene ciclos significa que el número de celdas nuevas (u()) también lo tiene.da igual lo que haya crecido al estructura de celdas activas, habrá un punto en que solo haya 4 y siempre se repetirán los mismo números: 4,4,12,4,12,12,36,4,12,….

En la gráfica de número de celdas nuevas se puede ver esta repetición de subidas y caídas:

Este numero de repeticiones esta ligado con su estructura fractal.

El autómata celular Ulam-Warburton original usa la vecindad de von Neumann pero presenta un comportamiento similar usando la vecindad de Moore, si bien cambia el patrón:

Simular ideologías con autómatas celulares

Antes que nada y para evitar problemas aquí vamos tratar con dos ideologías ficticias y opuestas. Los profilobostios y los antifilobostios. Efectivamente no existe algo así como un filobostio es una palabra inventada. Así me evito problemas de gente que pone la ideología por delante del sentido común. Cualquier parecido con la realidad es pura coincidencia….o no.

Antes de continuar, todos los ejemplos vistos en este texto se pueden probar en esta demo en github, con el código fuente disponible.

Usaremos autómatas celulares bidimensionale para modelar la población. Cada celda será un individuo y su estado será la ideología que defiende. En cada iteración un individuo evalúa a sus vecinos y sus propia ideología y adapta su creencia. Vamos a tener en cuenta las siguientes normas:

  • Cada individuo solo tiene información de su entorno. No tiene un conocimiento extenso y completo. No por ello deja de posicionarse  dentro de la ideología y de defender su posición respecto a sus entorno.
  • Un individuo solo puede adoptar una ideología que esté en su entorno. Es decir, solo puede adoptar ideologías con las que tenga contacto y por lo tanto conozca.
  • Un individuo tiene preferencia por elegir la ideología mayoritaria en su entorno. Un individuo tiene más probabilidades de elegir la ideología de la que más información a favor posea.
  • El individuo tiene en cuenta su propia ideología

Con estas reglas se intenta simular el hecho de que un individuo generalmente no tiene información completa si no que su posición ideológica se conforma por su entorno que comprende tanto las personas con las que se relaciona como los medios con los que se informa. .

Ideología

Vamos a ver dos formas de representar la ideología.

Simple: hay dos posibles estados, rojo y azul, sin grados y sin termino medio. Define ideologías en la que estas en un bando o estas en el otro.

Extendida: la ideología cada individuo puede tener 17 estados de -8 a 8. Siendo cualquier valor mayor que 0 azul, profilobostios, cualquier valor menor de 0 rojo, antifilobostio, y si es exactamente 0 de color negro, neutro. El valor absoluto representa «lo extrema» que es la creencia de un individuo en esa ideología. Está representación permite que individuos con ideologías opuestas y cercanas al neutro sean más cercanos entre ellos que con los extremistas de su propia ideología. Un detalle importante es que los individuos neutros también influyen en los demás. En ese aspecto la neutralidad sería una posición ideológica activa y que actuaría como una tercera postura del individuo más que como una ausencia de ideología.

Mecanismos de decisión

Existen dos mecanismos de decisión.

Aleatoria: el individuo elige al azar una ideología entre sus vecinos y la suya propia. Este mecanismo respeta la idea de que es más probable que elijas la ideología que es mayoritaria en tu entorno. Solo que no siempre es así. Esta forma de elección permite simular la «el carisma». Una persona se deja convencer por aquella ideología que más le atrae sin ponderarla de forma meditada.

Media: el individuo analiza el valor de sus vecinos y el propio y elige la creencia más cercana a la media de todas las creencias. En el caso de la ideología simple, en lugar de calcular la media elige aquella ideología con más representantes.

Obstinados

Un elemento extra en estos modelos son individuos que no cambian de opinión, son defensores acérrimos de su ideología e ignora todo lo demás.

Ideología simple con selección aleatoria

Este es el caso más sencillo de entender. Representaría una población completamente polarizada y que se deja llevar por lo «atractivo» que sea el mensaje de una ideología. Cuando se ejecuta se puede observar que hay mucho movimiento, la gente cambia de ideología rápidamente y hay veces que alguna parece dominar de forma aplastante sobre otra para que luego todo cambie rápidamente. Un hecho importante es que tras un periodo de tiempo largo siempre hay una que se impone y la otra desaparece. En este caso ambas ideologías son «igual de atractivas» así que termina ganando una de las dos al azar. Lo que si que es cierto es que el proceso se refuerza, contra más extendida este una ideología más fácil es que crezca.

Puede parecer que esto es malo, pero realmente hay ideologías que son tan atractivas y útiles que es difícil que no se extiendan como por ejemplo «todos somos iguales», «robar está mal». Permite tener una base ideológica estable.

Una única ideología se impone

Ideología simple con selección aleatoria y obstinados

En el caso que estamos simulando conde ambas ideologías son igual de atractivas los obstinados impiden que la ninguna ideología se imponga actuando como fuente de nuevos partidarios de su ideología.

En esta situación el poder de los obstinados depende de lo atractiva que sea la ideología que defienden. Si defienden una ideología poco atractiva se quedan atrapados llegando a un caso similar al de «Ideología simple con selección media y obstinados» que veremos más adelante. Sin embargo si defienden una ideología muy atractiva esta puede llegar a extenderse y dominar.

Los obstinados impiden que una única ideología se imponga

Ideología simple con selección media

En este caso la población se divide en grupos que comparten ideología. En estos grupos un individuo se ve rodeado de un entorno estable que reafirma su ideología.

La población se divide en grupos ideológicos cerrados

Ideología simple con selección media y obstinados

Los obstinados no producen ningún efecto, al ser una decisión que tiene en cuenta a toda al vecindad su influencia es muy reducida y muchos de ellos acaban «atrapados» con vecindades que no comparten su ideología y a la que no tienen ninguna probabilidad de convencer.

La población se divide en grupos ideológicos cerrados con unos pocos obstinados aislados

Ideología extendida con selección aleatoria

El comportamiento aquí es muy parecido al de «Ideología simple con selección aleatoria» pero con múltiples ideologías. Lo curioso de esta situación es que cada «grado» en la ideología actúa como si fuera un bando contrario a todos los demás, se convierte en un todos contra todos de 17 bandos hasta que al final uno se impone a los demás.

Cada grado de creencia se comporta como un bando diferente, al final uno se impone

Ideología extendida con selección aleatoria y obstinados

Los obstinados impiden que la población colapse en un único valor manteniendo la competición entre ideologías. Al igual que en el caso con ideología simple el poder de los obstinados depende de lo «atractiva» que sea su ideología.

Los obstinados impiden que una única ideología se imponga

Ideología extendida con selección media

En este caso la ejecución rápidamente converge a una población donde se crean grupos ideológicos estables separados por una frontera de neutrales. Si nos fijamos en el color la mayoría de los individuos son cercanos a la neutralidad. La única excepción son pequeños que se crean dentro de los grupos más grandes cuyo color es más intenso.

La neutralidad y los grupos ideológicos muy cercanos a la misma predominan. Se pueden formar pequeños grupos más alejados de la neutralidad (arriba a la derecha el circulo rojo)

Ideología extendida con selección media y obstinados

Si al caso anterior añadimos unos pocos obstinados ocurre un cambio sorprendente. La población se radicaliza. Desaparecen los neutrales y los colores se vuelven más intenso.

Con un 10% de obstinados la neutralidad se reduce y la población de polariza
Con un 20% de obstinados la neutralidad casi desaparece y los individuos se alejan de ella

Conclusiones

Obstinación contra neutralidad

En el caso de las decisiones ponderadas con ideología extendida vemos que los obstinados actúan aumentando la polarización de la población. De hecho en el caso de la ideología simple donde la polarización es máxima los obstinados no tienen efecto. Promover la aparición de estimados puede servir ambas ideologías y así reducir «el peligro de los neutrales»

Para entender este peligro vamos a incluir un nuevo elemento, una especie de tendencia global en toda la población, está tendencia se puede deber a muchas causas: modas, noticias, decisiones políticas o errores.

Para simular esta tendencia basta con sumar o restar (según la tendencia beneficie a profilobostios o antifilobostios) a cada individuo. Tras está operación los ciudadanos neutros o cercanos a la neutralidad adoptan una posición ideológica.

Es decir en un mundo moderado un suceso externo puede fácilmente inclinar la balanza hacia uno de los lados.

Si fuéramos responsables de cualquiera de las dos ideologías nos interesaría eliminar este riesgo y la mejor forma para ambos bandos es promover la aparición de obstinados. Esto les protege de los neutrales y sus cambios de opinión, cuanto más cerca este un individuo de un extremo ideológico más difícil es que cambie de opinión. Como ambos bandos se benefician de este hecho su mejor movimiento es que ambos colaboren para lograr esta situación.

Selección arbitraria e ideología única

En los casos en que la ideología no se elige de forma ponderada si no de forma arbitraria una única ideología termina imponiéndose a las demás, el tiempo que esto tarde en ocurrir dependerá del tamaño de la población y de lo «persuasiva» (probabilidad de ser elegida) que sea cada ideología y del azar. Es importante saber que una ideología no tiene porque ser superior a otra, el simple azar la convierte en ganadora.

En este modelo cada pequeña diferencia ideológica se convierte en un bando aislado que lucha contra los demás hasta que se impone. No basta con que el tablero este azul o rojo, tiene que estar en un solo tono de este color.

Sin embargo es muy sensible a los obtusos que impiden que el sistema converja en una solo ideología manteniendo el enfrentamiento activo.

Cálculo de la frontera de Voronoi

Una vez que hemos calculado las particiones en el plano de Voronoi vamos a sacar las fronteras de las mismas. La frontera es el punto donde se pasa de un polígono a otro.

Partiendo del caso anterior calcular una frontera es simple, una frontera es aquel individuo que tiene algún vecino de un color/tipo diferente. Así de sencillo es calcular la fronteras en un autómata celular. Si alguno de los vecinos es distinto estoy en una frontera.

    this.isBorder = false;
    for(var i = 0; i < neighbors.length; ++i){
      if(neighbors[i].creature.point != this.point){
        this.isBorder = true;
    }

Cuando se ejecuta la demo se puede ver como las fronteras van creciendo extendiéndose hasta que chocan con otras fronteras y dejan de avanzar. El resultado final lo pongo en la imagen, en ella se pueden ver las fronteras de los polígonos en color negro.

Unos de los problemas que se pueden ver es que la frontera ocupa dos celdas de ancho. Esto se debe a que realmente la frontera es lo que pasa entre ambas celdas, pero lo que se está coloreando son las celdas que están en la frontera, es decir el vecino que esta a cada lado de la misma.

Diagrama de Voronoi con autómatas celulares

Vamos a usar autómatas celulares para calcular el diagrama de Voronoi de varios puntos. El diagrama de voronoi se calcula a partir de una serie de puntos P[i] en un espacio (en este caso un plano). A partir de cada uno de esos puntos P[i] crea uno polígono según la siguiente regla: un punto del plano pertenecerá a un polígono si no hay ningún otro punto P[i] más cercano. Las fronteras entre estos polígonos (Polígonos de Thiessen) son el diagrama de Voronoi.

<Voronoi diagram.png
De Gottie (fuente Wikipedia Image:Voronoi.png), Dominio público

En este las reglas del autómata son sencillas, si un vecino tiene una distancia menos que la propia, copia su color y su distancia + 1.

for(var i = 0; i < neighbors.length; ++i){
   if(neighbors[i].creature.distance < this.distance){
     this.distance = neighbors[i].creature.distance+1;
     this.point = neighbors[i].creature.point; 
} } 

Queda inicializar las celdas, para ello una celda puede ser dos tipos:

  • un punto a partir del cual calcular las fronteras o una celda normal, su distancia es 0 y se inicializan con un color de una lista.
  • una celda nomal, se inicializan sin pertenecer a ningún polígono, con color blanco y un valor de distancia muy grande (lo ideal seria infinito pero con que sea mayor que cualquier distancia entre dos puntos de la rejilla de celdas también sirve)
if(this.isPoint){
  this.distance = 0;
  this.point = initPointsNumber;
  initPointsNumber++;    
} else {
  this.point = -1;
  this.distance = 10000;
}

El funcionamiento del autómata es muy parecido al algoritmos de inundación las distancias menores se van propagando junto con el color hasta que encuentran un vecino cuya distancia es menor, en es punto es donde se encuentra el borde del polígono.

Tenéis el código aquí y un ejemplo aquí, el resultado es:

Si os fijáis bien parece que la imagen está cortada por los extremos, eso es porque en este caso no estamos calculando el diagrama de Voronoi en un plano si no en un toro (que es la forma geométrica del mundo de este autómata) por eso los polígonos cuando salen por un extremo continúan por el otro.

Autómatas Celulares

Para definir lo que es un autómata celular vamos a empezar por su versión más simple y vamos complicando el modelo. Empezamos por el más simple, un cuadrado que puede tener varios estados y cada estado está asociado a un color. El cambio de estados está regulado por un conjunto de reglas. Por lo que cada autómata queda definido por sus estados y las reglas que los cambian. A los autómatas de les conoce como celdas, individuos o células

Dos dimensiones

Siguiente nivel de dificultad los autómatas con vecinos a ambos lados. Son los autómatas unidimensionales. Se distribuyen en forma de línea. Cada autómata tiene dos vecinos que son otro autómata idéntico situado a la derecha e izquierda. Pero cómo sería muy aburrido tener muchos autómatas que cambien de estado sin interaccionar entre ellos ahora las reglas determinan el cambio según el estado propio y el de los dos vecinos.

El caso más estudiado de este tipo de autómatas celulares es el de celdas de dos estados: blanco y negro o 0 y 1 o muerto y vivo. Las reglas de cambio se expresan como tres celdas. La del centro representa el estado de la celda actual y la de la derecha e izquierda sus dos vecinos. El valor que tomara la celda central se representa debajo. Las reglas toman forma de figura del tetris. Por ejemplo dos formas de expresar la misma regla:

111110101100011010001000
0 1 0 1 1 0 1 0
regla90
Dos formas de expresar la misma regla

Esta regla es conocida como la regla 90. ¿De donde sale ese 90? . Muy sencillo, de la segunda fila de la tabla. En binario 01011010 = 90. Cada regla se denomina así, por el número decimal que se obtiene de poner en decimal los resultados de la regla de transformación. Como solo hay 8 posibles reglas (hay ocho posibles configuraciones de las tres celdas) solo hay 256 reglas.

Los autómatas unidimensionales se representa como una linea. Cada paso en su ejecución se representa como una linea nueva que se pone debajo de la anterior, formando un plano.

Regla 90 tras varios pasos

Tres dimensiones

Aumentamos una la dimensión vamos a los autómatas bidimensionales. En este caso hay 4 u 8 vecinos dependiendo que tipo de vecindad se ese, vecindad de Von Neumann solo tiene en cuenta los vecinos situados arriba, abajo, a la izquierda y a la derecha, mientras que la vecindad de Moore tiene en cuenta también los vecinos de las diagonales. En estos por lo general se tiene en cuenta el número de vecinos en un determinado estado para las reglas de cambio de estado. El ejemplo más famoso de este tipo es el juego de la vida que intenta emular una especie de ecosistema en un autómata muy simple cuyas reglas son:

  • Una célula rodeada de 3 o más vivas está viva al siguiente turno
  • Una célula rodeada de 2 células vivas no cambiara de estado
  • Una célula sin vecinas vivas estará muerta al siguiente turno

Fronteras

Uno de los problemas que tienes al diseñar un autómata es que haces con las celdas que están en los bordes (fronteras) del sistema. No tiene el mismo número de vecinos que las demás. Hay varias soluciones:

  • Valores fijos: se simula que más allá de las fronteras hay otras celdas con valores fijos
  • Mundo infinito: el autómata crece en cada iteración generándose nuevas celdas en los extremos. El problema de esto es que necesitas una cantidad enorme de memoria (idealmente infinita) para que funcione.
  • Mundo circular: se simula que los extremos están en contacto entre ellos, el superior con el inferior y el izquierdo con el derecho, por lo que no hay fronteras y el mundo es cerrado. Es la solución más habitual. Adoptando la forma de un cilindro en los autómatas unidimensionales y de un toro en los bidimensionales

Variaciones

Hemos explicado los ejemplos más sencillos vamos a ver algunas variaciones sobre estos ejemplos:

Más dimensiones. Si hay automatas de una y de dos dimensiones no cuesta mucho imaginar automatas de tres y es cierto que los hay y resultan utiles en cosas como la creacion de espacios en arquitectura, arte e ingenieria. ¿Y de más dimensiones? Alguno hay pero pierde una de las grandes vantajas de los automatas celulares, lo facil que es entender su evolución de forma visual.

Más estados. Es habitual los autómatas celulares con múltiples estados. Para no perder

Reglas estocásticas. Hasta ahora hemos visto reglas que calculan el estado que toma la celda de manera determinista, pero esto no tiene porque ser así, puede ser que la regla determine solo la probabilidad del cambio de estado.

Diferentes vecindarios. Ya hemos visto que hay dos vecindades tradicionales la Moore y la Von Neumann ¿Pero que pasa si queremos aumentar el número de vecinos o su complejidad?. Podríamos aumentar las dimensiones pero ya hemos visto que eso tiene un limite. La solución es ampliar l definición de «vecindad» en lugar de ser solo las celdas en contacto directo podemos usar como vecinos también las de las siguientes hileras. A esto se le denomina el radio de la vecindad.

RadioNº de vecinos
18
224
348
480

Numero de vecinos = ((2*radio+1)^2)-1;

Diferente geometría. Esta relacionado con el punto anterior. En lugar de usar cuadrados se pueden usar hexágonos, triángulos, combinaciones de diversas figuras. En el caso más extremo las relaciones de vecindad se puede representar como un grafo que conecte a los vecinos entre ellos siendo innecesario que tengan una representación geométrica.

Celdas con diferente reglas. Tampoco es necesario tener las mismas reglas para todos los individuos. Puede haber varios grupos de reglas que apliquen a distintos tipos de celdas o incluso que cada celda tenga sus propias reglas generadas como combinación de las suyas propias y de sus vecinos.

Simular con autómatas celulares la propagación de una enfermedad

Vamos a ver un ejemplo de uso de los autómatas celulares para que veamos lo fácil que es realizar algunas simulaciones simples con ellos. En este caso vamos a modelar la evolución de una enfermedad en una población. Hay modelos matemáticos muy elaborados sobre enfermedades y que desde luego son más realistas que el que vamos a construir (aunque realmente se puede elaborar tanto como quieras).  La ventaja de los autómatas celulares es que son mucho más visuales lo que permite entender el desarrollo del sistema de forma más intuitiva, además sus mecanismos son más fáciles de entender y modificar que un sistema de ecuaciones diferenciales.

Para modelar nuestro autómata celular vamos a usar terra.js

Cada celda va a simular ser un individuo diferente en contacto con otros individuos (sus celdas vecinas). Un individuo puede estar sano, infectado, recuperado o inmune. Cada estado se corresponde con:

  • Sano: el individuo no ha sido infectado, pero puede contagiarse si cualquiera de sus vecinos está enfermo
  • Enferma: el individuo esta enfermo, durante unos turnos seguirá en ese estado y será contagioso. Pasados esos turnos pasará a estar recuperado
  • Recuperado: tras recuperarse el individuo ni es contagioso ni puede volverse a contagiar
  • Inmune: el individuo es inmune a la infección, no puede estar enfermo (podemos considerarla como vacunada)

Cuando un individuo sano tiene como vecino a uno infectado tiene una probabilidad Pc de contagiarse. Esta probabilidad aumenta con el número de vecinos. La probabilidad de infectarse es 1-(1-Pc)^n siendo n el numero de vecinos infectados. ¿De donde sale esa formula?. Vamos despacito, si tenemos solo un vecino la probabilidad de infectarse es: Pc. Pero si tenemos dos vecinos la probabilidad de infectarse es: la probabilidad de infectarse del vecino A, la probabilidad de infectarse del vecino B y la posibilidad e infectarse de ambos. Resulta más sencillo calcular lo contrario,  la probabilidad de no-contagiarse de ninguno,  que para un vecino es Pnc = 1-Pc. La probabilidad de no infectarse de 2 vecinos es Pnc = (1-Pc)(1-Pc). De tres: Pnc = (1-Pc)(1-Pc)*(1-Pc). De n: Pnc = (1-Pc)^n. Como lo que queremos saber es la probabilidad de infectarse y lo que hemos calculado es la de no infectarse, la de infectarse debe de ser: 1- Pnc => 1-(1-Pc)^n 


var surrounding = neighbors.filter(function (cell) {

  return cell.creature.isIll;

}).length; 

if (Math.random() &lt; 1-Math.pow(1-pc, surrounding)){

  this.isIll = true;

  this.timesIll = illDuration;

}

Si un individuo ya esta enfermo le restamos tiempo de enfermedad cada turno hasta que llegue a 0 que es cuando deja de estar enfermo


this.timesIll--;

if(this.timesIll == 0){

  this.isIll = false;

  this.wasIll = true;

}

Al principio de la simulación los individuos se generan aleatoriamente según las probabilidades indicadas para cada tipo de celda:


var rnd = Math.random();

this.isIll = rnd &lt; startIll;

if(this.isIll){

  this.timesIll = illDuration;

} else {

  this.isInmune = rnd &lt; startIll+startInmune;

}

this.wasIll = false;

}

Ajustando los diversos parámetros se pueden ver distintos comportamientos del sistema.


var pc = 0.2; //probabilida de contagio

var startIll = 0.01; //prob. de estar enfermo al empezar

var startInmune = 0.2; //prob. de ser inmune al empezar

var illDuration = 5; //duración de la enfermedad

El código completo puede verse aquí y una demostración aquí

automata