Dibujar con hormigas: imágenes de procedimiento utilizando algoritmos de optimización de colonias de hormigas

¿Por qué quería dibujar con hormigas?

Quería crear una obra de arte que explorara la complejidad del diseño de software. Cuando presento una gran base de código, pienso en su complejidad que surge independientemente y sus partes interconectadas y entrelazadas. Su forma general, por así decirlo, surge de las acciones de muchas personalidades individuales.

Estaba pensando en cómo presentar esto gráficamente, y una de las imágenes que encontró una respuesta en mí fue la imagen de una colonia de hormigas. Las hormigas son un gran ejemplo de la complejidad emergente (emergente). Ninguna hormiga es arquitecta, pero juntas construyen magníficas estructuras complejas.

Esquema de formicaria. Fuente: Wikimedia Commons .

Comencé buscando información sobre simulaciones de colonias de hormigas. Obviamente, existe literatura sobre esto, y es hermoso . Pero el truco fue que los hormigueros surgen en parte dependiendo de la física de la arena y la tierra en la que están construidos, porque su creación depende de cómo se ubicará la partícula cuando la hormiga la ponga. Quería crear algo en 2D, así que traté de ir directamente a la simulación sin escribir código de física de arena, es decir, tuve que abandonar la simulación física del hormiguero.

Debido a esto, comencé a buscar nuevamente, y me llevaron a una clase completamente diferente de simulaciones de hormigas:algoritmos de optimización de colonias de hormigas (algoritmos de colonias de hormigas) .

La optimización de colonias de hormigas es un algoritmo de agente utilizado para resolver el problema de encontrar la ruta más corta entre dos puntos de un gráfico. "Agente" significa que el algoritmo consiste en procedimientos separados (en este caso, "hormigas"), cuyo comportamiento emergente resuelve el problema.

Funciona de manera muy simple. Cada hormiga deja un rastro de "feromonas" en su camino. Las hormigas dejan un tipo de feromona después de abandonar el hormiguero y el otro cuando encuentran comida. Las hormigas que buscan comida buscan un rastro de una feromona "alimenticia", mientras que las que buscan hormiguero buscan un rastro de una feromona "casera".

Las hormigas que se encuentran en un camino más corto pueden hacer una ruta más rápida desde su casa hasta la comida y viceversa. Esto significa que crearán una capa más saturada de feromonas. Las hormigas que se mueven más tiempo preferirán una pista más rica y se moverán por un camino más corto. Cada hormiga individual funciona de acuerdo con reglas muy simples, pero con el tiempo las hormigas encuentran un camino más óptimo entre dos puntos.

Simulación

Escribí mi simulador de hormigas en Processing 3. Comencé mi propia implementación simulando el código de esta increíble publicación de Gregory Brown .

Después de que las hormigas comenzaron a moverse, comencé a expandir y modificar el código para que funcione mejor en cuadrículas de píxeles más grandes. Quería obtener simulaciones interesantes (no necesariamente efectivas ) y eso determinó mi trabajo en el código. Creé una visión muy rudimentaria para las hormigas para que cada hormiga pueda ver varios píxeles más adelante. Agregué la muerte y el renacimiento de las hormigas para que no se dispersen al azar por todo el espacio. Finalmente, hice que las hormigas fueran un poco más tontas: dejan la feromona constantemente, incluso si la búsqueda no tuvo éxito, lo que es similar al comportamiento real de las hormigas.

¡Aquí puede jugar el puerto de simulación en p5.js directamente en su navegador!

También puede echar un vistazo al código fuente portado en Github.

Sobre todo en la simulación, me fascinaron las bellas, extrañas y complejas formas creadas por las hormigas. No marchan en línea recta, sino que forman bucles, giros y ramas. Aún más interesante es que puedes controlar la apariencia de figuras creadas por hormigas cambiando varias variables de su mundo. Por ejemplo, puede cambiar la tasa de evaporación de feromonas y el rango de visión de las hormigas en píxeles.

Convertir hormigas en arte

Después de que la simulación comenzó a funcionar, el siguiente paso fue estudiar los datos que genera. Mi objetivo era crear algún tipo de imagen bidimensional, es decir, necesitaba capturar y dibujar las figuras creadas por las hormigas.

Al final, escribí diferentes tipos de salida: varios tipos de salida de trama y un vector. Para capturar la salida ráster, rastreé las celdas visitadas por las hormigas y la frecuencia de sus visitas. Después de jugar con los filtros de esta conclusión, puede obtener un rastro fantasmal de esos lugares donde visitaron las hormigas.

Un ejemplo de salida ráster. Los caminos son mucho más anchos a lo largo de las populares huellas de hormigas y donde las hormigas deambulaban al azar alrededor del hormiguero.

El resultado ráster fue interesante, pero quería ver las rutas individuales más claramente, así que exploré la posibilidad de exportar a svg. Para la salida vectorial, guardé el historial de cada hormiga, y cuando llegaron a la comida o al hormiguero, escribí esta historia en la lista. Para renderizar, probé cada ruta guardada y la rendericé como una serie de curvas.

Un ejemplo de salida vectorial. Aquí puedes ver los caminos individuales de las hormigas. Donde ha habido muchas hormigas, las líneas ligeramente superpuestas forman caminos más anchos.

Conecta los puntos

Sabía que quería dibujar hormigas viajando entre muchos puntos, por lo que el código para vincular varias simulaciones en una imagen fue uno de los primeros. Pero entonces, ¿qué debo dibujar?

Al principio decidí crear gráficos muy literales: comenzando con árboles binarios simples, luego pasando a visualizaciones más complejas. Esto parecía un paso natural, porque la optimización de la colonia de hormigas resuelve el problema de encontrar rutas en gráficos. También pensé que esta sería una forma interesante de visualizar la complejidad del código: ¿por qué no tomar un diagrama UML o un gráfico de dependencia y representarlos con hormigas?

Ya estaba familiarizado con Graphviz , así que decidí usar este kit de herramientas y el lenguaje de descripción de gráficos DOTpara especificar los nodos y bordes de mi simulación. Graphviz tiene un modo que genera un archivo DOT con anotaciones de coordenadas de píxeles. Escribí un analizador de archivos DOT muy feo y lo usé con un archivo DOT anotado para simular ubicaciones de hormiguero y comida.

Los experimentos con árboles binarios parecían prometedores y dieron un aspecto muy natural y orgánico.

Un simple árbol binario. Me dijeron que es como un angiograma.

Un árbol un poco más complejo, ya bastante profundo.

Luego comencé a construir más gráficos usando varias bases de código como entrada. Escribí algunos scripts simples de Python: uno convirtió el árbol git en un archivo DOT, el otro convirtió las dependencias de importación de C en un archivo DOT.

Gráfico de objetos en el árbol de objetos git dibujado por hormigas.

Dependencias entre archivos en el kernel de Linux. Los nodos y las aristas se crearon utilizando el estilo cuadrado de los gráficos Graphviz. De hecho, no es mucho más interesante que los gráficos aleatorios.

Aunque todos estos gráficos son interesantes y definitivamente complejos, me decepcionó que, de hecho, no dijeran nada sobre la forma general de las bases de código sobre las que se construyeron. Mientras más experimentaba con la visualización del código, más me daba cuenta de que construir un gráfico interesante a partir de una base de código en sí misma es una tarea separada y más difícil. Sin embargo, me gustó la complejidad de los gráficos muy grandes y luego volví a esto nuevamente.

Mi siguiente experimento fueron juegos con formas simples. Creé gráficos a partir de líneas, círculos, sinusoides y otras formas que son fáciles de describir con nodos y bordes.

Los puntos en el segmento, en el lado derecho del segmento, los puntos están más cerca uno del otro.

Diferentes frecuencias de onda sinusoidal. Supongo que las hormigas saldrán con un osciloscopio bastante bueno.

Los espacios triangulados más simples me parecieron los más interesantes. Generé muchos puntos distribuidos uniformemente, ya sea de forma aleatoria o dibujando formas, y luego usé la biblioteca de procesamiento para convertir estos puntos en una triangulación de Delaunay o un diagrama de Voronoi. Luego, las costillas resultantes se usaron para simular hormigas, donde cada costilla denotaba un "hormiguero" o "alimento".

Dibujado por hormigas diagrama de Voronoi.

Esto condujo a la aparición de un hermoso espacio lleno de complejas complejidades de hormigas, que describía la complejidad que me interesa mucho mejor.

Finalmente, abordé la tarea desde otro ángulo. Un amigo miró la simulación y preguntó qué pasaría cuando las hormigas chocan con la pared: ¿pueden evitar obstáculos simples? Mi código ya sabía cómo manejar paredes como casos límite, así que solo agregué paredes internas y luego pasé mucho tiempo tratando de enseñar a las hormigas a resolver laberintos.

Los caminos de las hormigas que intentan resolver un simple laberinto. Puedes ver la forma del laberinto al notar dónde no pueden ir las hormigas.

Tuve la idea de que si las hormigas pueden resolver laberintos simples, entonces puedes combinarlas para crear un trabajo más grande. Pasé mucho tiempo configurando las variables de simulación para que las hormigas pudieran resolverlas, pero aún así no pude hacer que resolvieran los laberintos de manera estable. Al final, todo esto se convirtió en rizos de caminos de hormigas, limitados por la forma del laberinto en sí.

Obra de arte terminada

En esta etapa, decidí dar un paso atrás y considerar el resultado de todos mis experimentos. Me di cuenta de que las imágenes más interesantes se obtuvieron de grandes campos de puntos y bordes semialeatorios, y decidí tomar esta decisión final configurando la simulación para dibujar líneas entre la triangulación de puntos aleatorios de Delaunay.

Ejecución de simulación completada. Contiene muchos caminos superpuestos a partir de los cuales se obtienen puntos difusos.

El último problema fue cómo convertir las curvas SVG en trabajos terminados. De los experimentos, supe que quería ordenar los caminos de alguna manera para resaltar los caminos con una forma hermosa. Pero la ejecución de la simulación terminada tomó una o dos horas, razón por la cual fue inconveniente cambiar las variables en cada ejecución del experimento.

Decidí escribir un segundo diagrama de Procesamiento que cargará la salida de simulación en SVG y luego aplicará los efectos visuales que necesito. Además, quería que el script de procesamiento posterior fuera interactivo para poder experimentar con diferentes pesos y colores de líneas, así como con umbrales de clasificación.

Intenté varias formas diferentes de evaluar las rutas que deberían estar en primer plano y en segundo plano. Se calcularon varios factores diferentes: el número de auto-intersecciones de la línea, el número de intersecciones por la línea de su línea de pendiente y la probabilidad de que la línea siga la pendiente predicha por los dos puntos anteriores.

Utilicé el script de procesamiento posterior para experimentos con diferentes pesos y valores de estas estimaciones, hasta que obtuve el aspecto que necesitaba.

Configuración de umbral para líneas frontales y de fondo.

En este punto, guardar la imagen al cambiar cada variable ayudó mucho. Cuando me acerqué a la imagen que necesitaba, fue mucho más fácil comparar una serie de variaciones menores que cambiar varios factores a la vez.

Después de una larga configuración y de hacer pequeños cambios, creé la siguiente imagen de mi simulación:

Acerqué el área que me pareció más interesante y la recorté para crear un buen equilibrio entre el espacio vacío y el espacio lleno.

El último paso fue la elección de cómo convertir esta imagen en un objeto físico. Solía ​​imprimirlos digitalmente como un póster de 40 × 50 cm e intenté (sin éxito) imprimir la pantalla en papel de color. Un póster impreso digitalmente se ve muy bien, pero en el futuro quiero copiar la imagen como parte de la imagen. Encuentro dibujos complejos meditativos y creo que puedo lograr efectos interesantes dibujándolos manualmente.

Se dedicó mucho más tiempo a este proyecto de lo que esperaba, y resultó ser más complicado de lo que parecía al principio. Pero esta es una excelente manera de experimentar con todo tipo de problemas de geometría computacional y algoritmos. Creo que es bastante irónico que escribí varios miles de líneas de código para trabajar en la complejidad, pero me complace que se vea bien y hable por sí mismo.

Source: https://habr.com/ru/post/undefined/