Autómatas celulares en evolución

Conecte los autómatas celulares con el algoritmo genético y vea qué sucede.

El artículo contiene GIF (tráfico) e imágenes contrastantes. Los epilépticos pueden tener una crisis epiléptica.

Reglas para autómatas celulares

El autómata celular más simple es un autómata celular unidimensional (también hay autómatas de dimensión cero; hablaremos de ellos a continuación). En un autómata celular unidimensional, tenemos una matriz unidimensional, cuyas celdas (celdas) pueden tomar uno de dos estados (1/0, verdadero / falso, blanco / negro, vivo / muerto). El siguiente estado de la celda en la matriz está determinado por el estado actual de la celda y el estado de dos celdas vecinas, de acuerdo con alguna regla.

El total existe $$$2 ^ 3 = 8$combinaciones de estados celulares y dos células vecinas:



A continuación, para cada una de las combinaciones, anotamos el estado de la celda para la próxima iteración (para el siguiente estado del autómata):



Tengo una regla para un autómata celular. Las reglas para autómatas celulares unidimensionales están codificadas con 8 bits ("código de tungsteno"). El total existe $$$2 ^ 8 = 256$autómatas celulares elementales:



Se pueden clasificar 256 máquinas manualmente. No nos detendremos en ellos. Calculamos el número de reglas existentes para autómatas celulares bidimensionales.

Un autómata celular bidimensional utiliza una matriz bidimensional. Cada celda tiene 8 vecinos en las cercanías de Moore (también hay un vecindario de von Neumann en el que no se tienen en cuenta las celdas diagonales. No lo consideraremos en el artículo):



Por conveniencia, escribimos las celdas en una línea (usaremos el orden seleccionado más adelante en el artículo):



Para un autómata celular bidimensional existe $$$2 ^ 9 = 512$combinaciones de estados celulares y 8 células vecinas:



La regla para un autómata celular bidimensional está codificada con 512 bits. El total existe $$$2 ^ {512}$autómatas celulares bidimensionales:



Numero:

$$

$$2 ^ {512} \ aprox1.340781 \ times10 ^ {154}$$

más átomos en el universo observable ( $$$10 ^ {80}$)
Manualmente, este número de máquinas no se puede resolver. Si miramos un autómata cada segundo, durante la existencia del Universo, habríamos logrado mirar todo $$$\ approx4.35 \ times10 ^ {17}$Máquinas automáticas.

La enumeración simple no funciona, pero con la ayuda de un algoritmo genético, podemos encontrar autómatas que mejor se ajusten a ciertos criterios predefinidos.

Lo programaremos en JavaScript. Todos los fragmentos de código están ocultos bajo spoilers para no confundir a los lectores que no están familiarizados con los lenguajes de programación.

Autómata celular bidimensional

Escribimos un autómata celular bidimensional con una regla aleatoria. Almacenaremos la regla en la matriz de reglas, cuya longitud de rulesize = 512:


A continuación, complete el estado inicial de la máquina con una casa aleatoria:


(aquí y más adelante en el artículo, como el ancho y la altura de la máquina, se toma un número aleatorio, no muy grande ni muy pequeño número impar 89)

La función que calcula el siguiente estado del autómata tiene el siguiente aspecto (para no ensuciarlo, eliminó la inicialización del lienzo):


Las variables xm y xp almacenan las coordenadas X del vecino a la izquierda y del vecino a la derecha (x menos yx más). Las variables ym e yp almacenan las coordenadas Y correspondientes.

Aquí:


definimos condiciones de contorno periódicas (el campo del autómata es la superficie del toro).

Siguiente:


en el orden anterior, escriba el contenido de las celdas en una cadena. Traducimos la cadena a un número decimal. Para esta combinación, encontramos en la matriz de reglas el estado que debe tomar la celda con las coordenadas x e y.


Después de todas las iteraciones, reemplace el estado anterior del autómata con uno nuevo:


Dibujamos un autómata usando la función setInterval:


Ejecutar en el navegador

Recomiendo iniciar la máquina con reglas aleatorias 10-20 veces antes de continuar leyendo el artículo.

Podemos ejecutar la máquina durante mucho tiempo con diferentes reglas aleatorias. La imagen que obtengamos no diferirá de la imagen en la pantalla del televisor en ausencia de una señal:



A continuación, pasemos a configurar nuestra "TV" utilizando el algoritmo genético.

Algoritmo genético

El tamaño de la población inicial es de 200 máquinas (individuos). Para las reglas, en lugar de una matriz unidimensional de regla, usaremos una matriz bidimensional de población. El primer índice (n) es el número del individuo en la población.


La matriz de estado físico contiene los coeficientes de estado físico de cada individuo. Este conjunto se completa en el proceso de selección. Después de la selección, comenzamos el proceso evolutivo.

Proceso evolutivo

De nuestra población tomamos la mitad de los individuos más adaptados (según el coeficiente de aptitud física). La mitad restante está destruida. Luego, tomamos dos individuos sobrevivientes y los cruzamos.



Para cruzar, seleccione una posición aleatoria en los genotipos de dos antepasados. Antes de esta posición, tomamos genes de un antepasado, después de esta posición, de otro. Ponemos los genes seleccionados en el genotipo a un descendiente. Los genes restantes son para otro. Colocamos dos antepasados ​​y dos descendientes en una nueva población. Al mismo tiempo, cada individuo participa en el cruce una vez.

Mutaciones Con una probabilidad del 5%, un gen seleccionado al azar muta (invierte) en cada individuo. Si aumenta la probabilidad de mutaciones, habrá mutantes más exitosos, pero al mismo tiempo, un mutante exitoso puede no tener tiempo para dejar descendencia exitosa antes de que mute nuevamente sin éxito. Volveremos a este tema más tarde.

Selección natural

Antes de comenzar el proceso evolutivo, se debe hacer una selección. La selección puede ser tanto natural como artificial. La selección artificial se realiza manualmente, un poco más tarde. Para la selección natural, estableceremos algunos criterios y seleccionaremos las máquinas que mejor coincidan con los criterios dados.

¿Qué criterios se pueden determinar de antemano? Toma la más fácil. Nuestra "TV" parpadea demasiado. Guardamos dos estados del autómata celular: 99 y 100 iteraciones. Cuente el número de celdas que no han cambiado. El número resultante se usará como coeficiente de aptitud. Obviamente, un criterio no es suficiente para nosotros. Es fácil seleccionar manualmente el autómata que mejor cumpla con el criterio dado: el autómata [0,0,0, ..., 0] y el autómata [1,1,1, ..., 1]. En la primera iteración, estos dos autómatas se rellenan con ceros o unos y dejan de cambiar su estado. Definimos el segundo criterio: la diferencia entre el número de 0 y 1 (celdas) en la máquina no excede de 100 (el número se toma "de la excavadora").

array1: estado del autómata en la 99ª iteración. array2 - en la iteración número 100:


Empezamos La solución óptima se encontró en el 421º ciclo de evolución. En el gráfico puedes ver el progreso:



El gráfico se escala a lo largo del eje Y. El punto más bajo es 0, el punto más alto es 7921. Es obvio que 7921 es la solución óptima (todas las celdas de la máquina 89x89 cumplen el criterio especificado). Después de 100 iteraciones, ninguna celda cambia su estado.

Los puntos azules en el gráfico son el mejor individuo de la población. Los rojos son los peores (solo se tienen en cuenta las personas que cumplen con el segundo criterio). Puntos negros: el coeficiente promedio de aptitud para toda la población (teniendo en cuenta las personas que no cumplen con el segundo criterio). El segundo criterio (el equilibrio entre blanco y negro) es muy difícil. Algunos autómatas no cumplen el segundo criterio incluso después de 421 ciclos de evolución. Por lo tanto, los puntos negros están debajo del rojo.

El conjunto de genes de la población (individuos a lo largo del eje Y, genes a lo largo del eje X):



Veamos qué canal capturó nuestra "TV":



La solución encontrada no es la única óptima. Si volvemos a ejecutar la evolución (con genotipos iniciales aleatorios), encontraremos otras soluciones óptimas. Uno de ellos:



Cambiar los criterios de selección.

Consideraremos el número de celdas para las que aparece un patrón en las proximidades de Moore de orden 2. Tomemos el patrón más simple:



Este criterio es interesante porque verificamos 25 celdas, mientras que el autómata calcula el estado de la celda en función de los estados de 9 celdas.

El criterio es muy estricto. Si tomamos un autómata aleatorio, después de 100 iteraciones se ve así:



Ni una sola celda en un autómata cumple con el criterio dado. Por lo tanto, suavizamos un poco el criterio:

1. Vamos a cometer un error en el patrón.
2. No buscaremos el patrón en la última iteración, sino en las últimas 50 iteraciones.

El segundo criterio (el equilibrio entre blanco y negro) se elimina.

Empezamos Tabla:



El eje y es arbitrario. (En la máquina anterior, la solución óptima es 7921. En esta máquina, alrededor de 30.)
Eje X - 3569 ciclos de evolución. Dos líneas verticales blancas marcan 500 y 1000 ciclos de evolución.
Puntos azules: el mejor individuo de la población, rojo: el peor, negro: la proporción promedio de toda la población.

La solución se encontró en los primeros 500 ciclos de evolución. Los próximos 500 ciclos, la solución mejora. Y luego el sistema prácticamente deja de evolucionar.

En las tres imágenes a continuación: 500 ciclos, 1000 ciclos y 3569 ciclos de evolución:



Fondo genético (3569):



En dinámica:



En la siguiente imagen, puede ver cómo se forma el oscilador (planeador) en esta máquina:



Podemos iniciar la máquina con el estado inicial en el que se llena una celda. Luego, arregle todas las combinaciones de celdas que se encuentran en las siguientes iteraciones del autómata. Una matriz de genes (genotipo de un autómata) es una matriz de todas las combinaciones posibles. Habiendo aislado solo las combinaciones que ocurren, podemos notar fácilmente todos los genes que están involucrados en la formación del oscilador. Las barras grises son genes que no participan en la formación del oscilador:



Las mutaciones en estos genes no se arraigan debido al hecho de que interrumpen la formación del patrón.

En nuestra máquina, un patrón (cuadrado) se forma solo alrededor de una celda negra. Intentemos iniciar el proceso evolutivo junto con el segundo criterio: la diferencia entre el número de células blancas y negras no excede de 400.

Comenzamos 3569 ciclos de evolución. Tabla:



Los puntos negros en el gráfico son el coeficiente de aptitud física promedio en una población. Puntos blancos: el coeficiente promedio de aptitud de la máquina anterior. Encontró una solución con un error en el patrón.

Fondo genético:



100 primeras iteraciones:



Última (100) iteración:



Un poco no el resultado que esperábamos. Hay cuadrados negros, blancos - no. Apriete el segundo criterio: la diferencia entre el número de celdas blancas y negras no excede de 100.

Comenzamos 14865 ciclos de evolución.
El gráfico compara los coeficientes de aptitud promedio de las poblaciones. Los puntos azules son nuestra ametralladora. El blanco y el negro son máquinas anteriores.



Un autómata evoluciona tan vigorosamente que puede parecer que no evoluciona en absoluto. El segundo gráfico se escala a lo largo del eje Y. Dos líneas blancas: 500 y 1000 ciclos.



En el mejor individuo, en promedio, 6 celdas corresponden a un criterio dado.

Veamos una máquina aleatoria de una población.
50 iteraciones:



Última (50) iteración:



No se encontraron resultados aceptables. El segundo criterio complica la búsqueda, por lo que lo rechazaremos (no lo usaremos más adelante en el artículo). Dejemos este patrón y busquemos algunos otros patrones.

Patrón:



Empezamos 3000 ciclos de evolución. Tabla:



Fondo genético:



En dinámica (100 iteraciones):



Última (100) iteración:



Patrón:



En máquinas anteriores, permitimos cometer un error en el patrón. Esta vez, busquemos el patrón exacto.

Comenzamos 4549 ciclos de evolución. Tabla:



Línea vertical blanca: 2500 ciclos de evolución. En este punto (un poco antes), la aptitud de la población comenzó a crecer rápidamente. Salvó a la población para buscar una solución provisional. La solución intermedia resultó ser mucho más interesante que la solución en el 4549º ciclo de evolución.

Solución encontrada en el ciclo 4549 de evolución:



Hay 100 iteraciones en Gif. Después de un cierto número de iteraciones (aproximadamente 500-2000), el estado del autómata se ordena casi por completo (la altura y el ancho del autómata se eligen especialmente por números impares para que el autómata no se pueda ordenar por completo):



Un autómata con tamaños pares de lados, después de un cierto número de iteraciones, toma un estado completamente ordenado. Automático 90x90, aproximadamente 1200 iteraciones:



Solución intermedia (encontrada en el ciclo 2500 de evolución):



Este autómata también puede procesar un cierto estado caótico inicial en un cierto estado ordenado finito (el estado ordenado final es el desplazamiento del patrón a lo largo del eje X hacia la izquierda + varias celdas osciladoras).

La máquina 16x16 se ha solucionado en aproximadamente 100 iteraciones:



32x32 - aproximadamente 1000 iteraciones:



64x64 - aproximadamente 6000 iteraciones:



90x90 - aproximadamente 370000 iteraciones:



11x11 (dimensiones impares del campo del autómata) - aproximadamente 178700 iteraciones:



El rifle de asalto 13x13 no se racionalizó en un período de tiempo aceptable.

En la imagen a continuación, la máquina en el campo 256x256 en la iteración número 100,000:



Recomiendo mirar este autómata en dinámica en un campo grande: es muy interesante observar el proceso de autoorganización del caos en este autómata: ejecutar en un navegador

Fondo genético de la población intermedia:



Reiniciar el proceso evolutivo le permite encontrar otras soluciones. Uno de ellos:





Otro patrón:



Al buscar un patrón, volvamos a cometer un error (sin errores, el sistema con el patrón seleccionado no evoluciona).

Empezamos 5788 ciclos de evolución. Tabla:



La escala es arbitraria.

Fondo genético:



En dinámica:



El estado ordenado del autómata (desplazamiento del patrón hacia arriba a lo largo del eje Y + varias celdas del oscilador):



Es mucho más interesante observar no la máquina en sí, sino los mutantes que aparecen en esta población:



En Gif, la máquina es 256x256. 200 iteraciones Las iteraciones restantes se pueden ver en el navegador .

Uno podría terminar con la selección natural y pasar a la artificial, pero quiero mostrar cuánto $$$2 ^ {512}$Un gran número. Entre este número de autómatas, podemos encontrar un autómata que dibuja cualquier patrón dado (con cierta precisión para patrones más complejos).

El siguiente patrón:



En experimentos anteriores, contamos la suma de celdas alrededor de las cuales se forma un patrón (si con un error, agregue 1 a la suma, si sin errores, agregue 2). La cantidad resultante se usó como un factor de aptitud para el algoritmo genético.

Para un patrón más complejo, este método no funciona. Un autómata en el que un número menor de celdas coincide más estrechamente con un criterio dado (el número de celdas que coinciden con el patrón en la vecindad de la celda) perderá cada vez más a un autómata en el que un mayor número de celdas coincide con menos precisión con un criterio dado. Como en el ejemplo con los cuadrados de arriba:



Para el patrón deseado, en la iteración número 100 de cada autómata en la población, rodeado por cada celda, consideraremos el número de celdas que coinciden con el patrón. Tomaremos solo el mejor resultado para cada máquina. El número de celdas que coincida con el patrón se utilizará como factor de aptitud. El patrón consta de 7x17 = 119 celdas. Este número se considerará la solución óptima. 6000 ciclos de evolución nos permitieron encontrar un autómata que dibuja un patrón con 5 errores (114 celdas coinciden con el patrón).

Gráfico en una escala arbitraria:



Un aumento en el porcentaje de mutaciones no perjudicó la aptitud de la población.

Hay muchos mutantes en el acervo genético de la población:



Un autómata aleatorio de una población en dinámica:



La mejor máquina en la iteración número 100:



Patrones buscados y encontrados:



Después de jugar con los criterios de selección, el tamaño del campo del autómata y el porcentaje de mutaciones, resultó mejorar la población y encontrar un autómata que solo comete 3 errores en el patrón.

Fondo genético:



Máquina en la iteración número 100:



Patrones buscados y encontrados:





En cuatro gráficos, puede ver cómo evoluciona el sistema con diferentes probabilidades de mutación (1 gen muta):



Los puntos rojos son el coeficiente de condición física promedio en una población. Los puntos negros son el coeficiente de aptitud de cada individuo. 3000 ciclos de evolución para cada sistema.

Grupos genéticos de poblaciones (en el mismo orden):









Autómatas en la iteración número 100:









Hagamos otro experimento. El patrón es el mismo. Los genotipos iniciales están llenos de genes aleatorios. La probabilidad de mutaciones es del 5%. De 1 a 8 genes mutan (se toma un número aleatorio de genes mutantes para cada individuo). 100 ciclos de evolución.



El gráfico es un mapa de calor. El tamaño en puntos en el gráfico es de 5 píxeles. El origen es la esquina superior izquierda.
En el eje Y (de 0 a 100) - ciclos de evolución. En el eje X (de 0 a 119), el número de celdas que coinciden con el patrón (para cada individuo de la población tomamos el mejor resultado). El brillo del punto es el número de individuos con el resultado especificado (coordenada X).

Ejecute el algoritmo genético 4 veces con los mismos parámetros (100 ciclos, 5% de mutaciones, hasta 8 genes mutan). En el gráfico, los 5 comienzan:



Los siguientes 5 comienzos: 25% de mutaciones, hasta 8 genes mutan:



La muestra es pequeña, pero podemos sacar conclusiones sobre la efectividad de aumentar el porcentaje de mutaciones.

A continuación, mostraré la ineficiencia del método de cruce utilizado en el artículo.

Método utilizado previamente:



En lugar de dividir el genotipo en dos partes, los descendientes heredarán genes ancestrales aleatorios:



5% de mutaciones:



25%:



A continuación usaremos este método de cruces.

Sobre esto con acabado de selección natural. Si alguien tiene ideas interesantes sobre los criterios para la selección natural, por favor dígalo en los comentarios.

Para la selección artificial usaremos autómatas celulares de segundo orden .

Autómata celular de segundo orden

Considere un autómata celular de dimensión cero de primer orden (todos los autómatas celulares que consideramos anteriormente son de primer orden). Un autómata celular de dimensión cero consiste en una célula. Una celda puede estar en uno de dos estados. El siguiente estado de la celda (t) está determinado por el estado actual de la celda (t-1). En total, hay 4 autómatas celulares de dimensión cero (entre ellos un oscilador):



En un autómata celular de segundo orden, el siguiente estado de la celda (t) está determinado por el estado actual (t-1) y el estado anterior de la celda (t-2). En total, hay 4 combinaciones de dos estados celulares. $$$2 ^ {4} = $ 1$- el número de autómatas celulares de dimensión cero del segundo orden:



Tales autómatas celulares exhiben osciladores más complejos.

$$$2 ^ {8} = 256$autómatas celulares de tercer orden:



$$$2 ^ {16} = 65536$los autómatas celulares de cuarto orden no se pueden mostrar en una imagen.

Búsqueda de autómata celular $$$n$-o orden con un período de oscilación igual a $$$n$- La tarea no es trivial y extremadamente interesante. Este tema merece un artículo separado.

En autómatas celulares unidimensionales de segunda dimensión, el siguiente estado de una celda está determinado por el estado actual de tres celdas y el estado anterior de una celda:



Hay $$$2 ^ {16} = 65536$autómatas celulares unidimensionales de segundo orden.

Código:



Los autómatas celulares de segundo orden dibujan patrones más complejos que los autómatas celulares de primer orden.

En las imágenes a continuación, varias máquinas aleatorias de segundo orden (en el lado izquierdo de la imagen, en el estado t-1, se llena una celda, a la derecha, para los estados aleatorios t-1 y t-2, el código binario es el contenido del conjunto de reglas):

0011111011001000:


0101101110011110:


0110000110010010:


0110011010010110:


1110011010010110:


0110111010000101:


1111101001110110:


1001010001100000:


La misma máquina



256x256 : 512x512 Aquí



se pueden ver otras máquinas:
Máquina celular unidimensional de segundo orden.
Autómata celular unidimensional de tercer orden.

Los autómatas celulares unidimensionales de segundo orden se pueden encontrar en el libro de Wolfram A New Kind of Science.

Selección artificial

Al igual que un autómata celular unidimensional del segundo orden, en un autómata celular bidimensional del segundo orden usaremos una celda adicional del estado anterior (t-2) del autómata.

Para mayor comodidad, colocamos esta celda al comienzo de la línea binaria: la



conveniencia radica en el hecho de que cuando la primera y la segunda mitad del genotipo coinciden, el autómata puede considerarse como un autómata de primer orden:



al agregar una celda, aumentamos el número de autómatas existentes en$$ veces.$2^{512}$
$$- el número de autómatas bidimensionales existentes de segundo orden. Para la selección natural, determinamos algunos criterios y comparamos los autómatas según este criterio. En el proceso de selección artificial, seleccionamos las máquinas manualmente, utilizando un principio poco claro: "esta máquina es interesante, pero eso no es muy". Este principio no le permite elegir la mejor máquina entre las máquinas aleatorias:hay varias formas de resolver este problema. Propongo considerar cuatro formas.$2^{512} \times 2^{512} = 2^{1024}$

1. En el estado inicial de la máquina, se llena una celda

Una forma es observar el desarrollo de un autómata celular, en el estado inicial del cual se llena una célula.

Llenamos la población inicial con máquinas aleatorias. Varias máquinas de la población inicial (30 iteraciones para cada una):





Un pequeño número de autómatas que exhiben un comportamiento menos caótico están presentes en la población. Los seleccionaremos para cruzar:





20 máquinas aleatorias de la población inicial (estado de las máquinas en la 30ª iteración):



Después de tres ciclos de evolución:



Después de ocho ciclos de evolución:



Ocho ciclos de evolución fueron suficientes para llenar a toda la población con una máquina con cierto rasgo (una máquina que dibuja triángulos) .

2. El genotipo está parcialmente lleno

Si se viola la proporción de unidades y ceros en el genotipo, se viola la proporción de unidades y ceros en el fenotipo.

En el genotipo (regla) del autómata, se registran las siguientes condiciones celulares para todas las combinaciones posibles de la célula y las células vecinas. Si hay más ceros (o unos) en el genotipo, entonces los ceros (o unos) se acumulan en los siguientes estados del autómata. Es interesante observar la correlación entre la razón de unos y ceros en el genotipo y la razón de unos y ceros en el fenotipo.

Construye un cuadro.

Crea una población de 200 máquinas. Rellenamos los genotipos con ceros (1024 genes en el genotipo de un autómata bidimensional de segundo orden). Siguiente$$ genes están llenos de unidades. Para la primera población$n$$$ , para la población 513$n=0$$$$n=512$ . A lo largo del eje $$es el número de población. A lo largo del eje$x$$$Marque y (con puntos blancos) la proporción de unos y ceros en el conjunto de genes de la población. Tenemos una hipérbola:para cada autómata (con un tamaño de campo de 89x89), consideramos 100 iteraciones. En la iteración número 100, contamos el número de unos y ceros en el estado (fenotipo) de cada autómata. Marcamos en el gráfico la razón de unidades y ceros (el número total de todas las unidades se divide por el número total de todos los ceros). Obtuvimos una curva: enlugar de la razón total de unos y ceros en todos los fenotipos, puede ver la razón de unos y ceros en cada fenotipo:en el lado izquierdo del gráfico hay puntos con la mayor desviación del valor promedio. Se puede suponer que estos son autómatas en cuyos genotipos el gen cero es igual a la unidad. Supuesto - verificado. Establecemos el gen cero siempre igual a cero. Dibujamos un nuevo cuadro:$y$















Compare con máquinas en las que el gen cero siempre es igual a uno:



en las máquinas de segundo orden, hay otro gen "cero": el 512. Veamos cómo este gen afecta el fenotipo.

Los genes 0 y 512 siempre son cero: el



gen 0 siempre es cero. El gen 512 siempre es igual a uno:



para no volver a burlarse de nuestros estimados epilépticos, los genes 0 y 512 se llenarán con ceros en la población inicial del algoritmo genético.

Veamos las máquinas de las que nos deshacemos al poner ceros en los genes 0 y 512.

Los primeros 8 estados de un autómata en el que solo se llena el gen 0 (el gen cero es uno, el resto son ceros): Un



autómata en el que solo



se llena el gen 512: Un autómata en el que solo se llenan los genes 0 y 512:



Señalemos un lugar en el gráfico donde la población comienza a dividirse en grupos:



en este lugar, los genotipos están llenos en un 25%.

Compara dos poblaciones.

Primera población 30 máquinas aleatorias en la iteración número 1000. Los genotipos están llenos al 50% (512 unidades y 512 ceros):



la segunda población. 30 máquinas aleatorias en la iteración número 1000. Los genotipos están llenos en un 25% (256 unidades y 768 ceros):



la segunda población es adecuada para la selección artificial. Podemos destacar fácilmente algunos de los signos en tales máquinas. Por ejemplo: "más oscuro", "menos caótico" (autómatas en los que se agrupan los glóbulos blancos), etc.

Seleccionamos "más oscuro". La probabilidad de mutaciones es del 10%, hasta 4 genes mutan. Después de la primera selección:



Después de la segunda selección:



Un autómata interesante apareció en la población.

256x256, estado de la máquina en la iteración número 1000: la



máquina llena gradualmente a la población.

Después de la octava selección:



apareció otra máquina interesante.

256x256, estado del autómata en la iteración número 1000:



Población después de trece selecciones:



Varios autómatas de esta población. 256x256, iteración número 1000 para todos. Debajo de la imagen hay un enlace, haciendo clic en el cual puede ver la máquina en la dinámica:


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.


Ver en dinámica.

3. Máquina automática Conway y similares.

El autómata celular bidimensional más famoso de primer orden es el autómata Conway Game "Life" .

Las reglas para el autómata Conway están escritas de la siguiente manera:
si hay 3 células vivas alrededor de una célula muerta, la célula cobra vida (de lo contrario, permanece muerta).
Si hay 2 o 3 células vivas alrededor de una célula viva, la célula permanece viva (de lo contrario, muere).
Una célula muerta es 0, una célula viva es 1.

Alrededor de una célula puede haber de 0 a 8 células vivas. Según 9 opciones en torno a los vivos y alrededor de la celda muerta. Escribimos todas las opciones en la matriz r:



La primera mitad de la matriz es para una célula muerta, la segunda para una célula viva.

Podemos describir la regla del autómata Conway para todas las combinaciones posibles (512) de una celda y 8 celdas vecinas:





Para un autómata de segundo orden, copie la segunda mitad de la matriz de reglas de la primera:



Iniciamos la máquina con la regla especificada. Vemos los planeadores y osciladores característicos. Varias iteraciones de este autómata: la



matriz r consta de 18 celdas. Hay$$ autómatas similares al autómata de Conway (que puede escribirse con las mismas reglas: el número de células vivas rodeadas por los muertos, en el que la célula cobra vida y el número de células vivas en el entorno en el que muere la célula).Puede verlosaquí(de manera predeterminada, se inicia el autómata Conway, el botón "Cambiar regla" llena la matriz r al azar).Múltiples máquinas aleatorias (código binario - matriz r):110010011001111111100001100110111110011111000100101110010000110000110010001111010011100111000111001000000110000101100010100001000001111101011111000001100110111111$2^{18}=262144$































Para un algoritmo genético, como genotipo, puede usar, como una matriz r ( $$combinaciones), y la matriz de reglas ($2^{18}$$$ combinaciones de primer orden para el autómata celular y$2^{512}$$$ - para un autómata celular de segundo orden).$2^{1024}$

$$es un número relativamente pequeño. Este número le permite seleccionar la regla para la máquina manualmente, sin usar un algoritmo genético (de hecho, lo que hizo Conway). Si llena la matriz de reglas con máquinas aleatorias de este tipo y utiliza esta matriz como un genotipo, entonces el experimento puede considerarse infructuoso, hasta cierto punto (lo suficiente como para no mostrar los resultados de este experimento en el artículo). En las reglas de autómatas celulares de este tipo, hay simetría. Por ejemplo, para las siguientes combinaciones de celdas:$2^{18}$






El estado de la celda en la siguiente iteración es el mismo. Después del primer cruce, se rompe la simetría en las reglas de los individuos descendientes. Los individuos ancestrales acumulan mutaciones que también destruyen la simetría. La violación de la simetría en el genotipo causa una violación de la simetría en el fenotipo.

Se puede ver la manifestación de esta simetría en el fenotipo si una célula se llena en el estado inicial del autómata.

Hagamos un experimento. Para mantener la simetría, utilizaremos la matriz r como genotipo. 5% de mutaciones, 1 gen muta. En el estado inicial, se llena una celda.

30 máquinas aleatorias de la población inicial. El estado de los autómatas en la trigésima iteración:



intentemos aislar los autómatas que se desarrollan (crecen) más lentamente a partir de una célula.







Después de la primera selección, se deshicieron de los autómatas que no se desarrollan:



en la nueva población hay varios autómatas (que no se desarrollan), estos son descendientes y mutantes sin éxito.

A continuación, seleccionaremos principalmente máquinas con un fondo blanco (celdas en las que la máquina no se ha desarrollado).


Población después de la segunda selección:



3 selecciones:



5 selecciones:



8 selecciones:



13 selecciones:



Las mismas máquinas en la 60ª iteración:



21 selecciones. El estado de los autómatas en la 30ª iteración: El



estado de los autómatas en la 60ª iteración:



34 selecciones. Estado de autómatas en la 30ª iteración:



Estado de autómatas en la 60ª iteración:



Además, el sistema no evoluciona. Tres autómatas de esta población (100 iteraciones

cada uno ): [1,0,1,1,1,0,0,1,0,0,1,1,0,1,0,1,1,1]


[1 , 0,1,1,1,0,0,1,0,0,0,0,0,0,0,0,0,1,1,1]


[1,0,0,1,1,0,0, 1,1,0,1,0,1,1,0,1,1,1]


En comparación, una máquina aleatoria:

[1,0,0,1,1,1,0,1,1,1,0, 0,1,1,0,0,0,1]

4. Autómata de Conway y similares (2)

En las máquinas con las reglas del tipo Conway, contamos el número de unidades de células en las cercanías de Moore. Este vecindario se puede dividir en 4 pares y contar el número de células vivas en estos pares: por lo



tanto, aumentamos el número de autómatas, pero mantenemos la simetría en el fenotipo.

Cada par puede tener de 0 a 2 células vivas. Par 4. Número de combinaciones$$$3^4=81$ .De acuerdo con la combinación 81 en torno a los vivos y alrededor de la célula muerta. El total existe$$ máquinas automáticas de este tipo. Numero:$2^{162}$

$$

$$2^{162}\approx5.846\times10^{48}$$

Es completamente astronómico y se ajustará a un algoritmo genético.

El tamaño del genotipo de cada individuo es de 162 genes:


A continuación, pintamos esta regla para todas las combinaciones posibles de una celda y ocho celdas vecinas:


Usaremos la matriz de reglas cuando calculemos el siguiente estado del autómata. Llamamos a la función fillrule () después de cargar la página y después de llamar a la función evolute ().

La población inicial parece caótica. 30 máquinas aleatorias, iteración número 1000:



este caos varía ligeramente en dinámica y las máquinas son bastante adecuadas para la selección, pero hagámoslo más fácil: elegiremos las "más oscuras".

Población después de cinco selecciones: a



continuación, puede buscar máquinas con los osciladores más complejos. Todo el proceso de diseño no tiene sentido. A continuación se presentan algunos de los autómatas más interesantes que se encuentran utilizando el algoritmo genético.

256x256, iteración 10000 para todos. Debajo de la imagen hay un enlace, haciendo clic en el cual puede ver la máquina en la dinámica:


Ver en dinámica.


.


.


.


.


.


.


.


.


.


.


.


.


.

?

Y puedes jugar por aquí:

autómatas celulares bidimensionales de segundo orden.

Interfaz:



el botón Inicio inicia las máquinas.
Stop - se detiene.
Uno es una iteración.
Borrar: detiene la máquina y llena el estado inicial de forma aleatoria.
Borrar (1 celda): detiene la máquina y llena una celda en el estado inicial.
Los botones restantes en esta línea cuentan el número especificado de iteraciones para cada autómata.
Renderizar un autómata en lienzo consume todo el rendimiento. Si necesita calcular rápidamente 200 iteraciones, haga clic en Count 200. No hacemos clic en el botón Count 5000, el navegador puede colgarlo.

Menos de 20 máquinas aleatorias (tamaño de la población - 200 máquinas). Debajo de las máquinas expendedoras casillas de verificación. Marcamos lo más interesante. Presione Seleccionar: el estado físico de la máquina aumentará en el número indicado a la derecha.
Mutaciones: la probabilidad de mutaciones.
Gens es el número de genes mutantes.

Iniciar evolución: lanza el mecanismo de cruces y mutaciones.

Rellenar genotipo: rellena el número especificado de genes en el genotipo de cada autómata.
Conway: llena la población con máquinas de tipo Konveevsky.

A continuación hay dos líneas: los
números de las máquinas que se muestran.
El contenido de la matriz fenotipo.

El acervo genético de la población es aún más bajo.

Todo el progreso se almacena en el almacenamiento local.

Puedes jugar con rifles de asalto tipo Konveevsky (con los que se consideraron últimos en el artículo) aquí:

4. Autómata de Conway y similares (2).