Cómo el comportamiento de las hormigas puede ayudar a resolver problemas de logística

Desde hace algún tiempo, el hombre se inspira en la Naturaleza para desarrollar nuevas tecnologías y resolver problemas cotidianos. Un ejemplo de amplio conocimiento fue la invención de los aviones inspirados en la aerodinámica de las aves: todavía en la década de 1890, Otto Lilienthal estudió cómo una máquina más pesada que el aire, en este caso un planeador, podía obtener sustentación en un vuelo. A principios del siglo XX, los hermanos Wright y Santos Dumont mejoraron el desarrollo de este tipo de máquinas, al incorporar un mayor control sobre su conducción, lo que permitió múltiples maniobras. [1]

Pasemos ahora a ejemplos más insólitos: ¿sabías que el proceso de condensación de las gotitas de agua sobre el caparazón del escarabajo de Namibia inspiró un prototipo para ayudar a recolectar y abastecer de agua a las regiones áridas del planeta? ¿Alguna vez te has parado a pensar cómo las técnicas de camuflaje de animales como los moluscos marinos y los camaleones podrían ayudar en la fabricación de uniformes para las fuerzas armadas? Finalmente, el estudio de las propiedades autolimpiantes de las alas de la mariposa de seda azul podría servir para la fabricación de pinturas con las mismas características, facilitando la eliminación de la suciedad. Porque estos ejemplos dados ya están en estudio y/o ya han permitido la creación de nuevos productos disponibles en el mercado. [dos]

Pero, ¿cómo podría ayudar el comportamiento de los animales en la solución de problemas en el área de la logística? Pues bien, el crecimiento exponencial del número de soluciones viables en algunos problemas logísticos puede dificultar su resolución cuando se utiliza un método de optimización. Como ejemplo clásico, podemos citar el problema del viajante de comercio (o TSP – Travelling Salesman Problem), que tiene como objetivo visitar, al mínimo costo (tiempo o distancia recorrida), un conjunto de clientes, saliendo y regresando al mismo punto. [3]

Figuras 1: Afiche creado por P&G en 1962 para dar a conocer un concurso que premiaría a quien determinara la mejor ruta turística por 33 ciudades norteamericanas. [4]

Tenga en cuenta que los problemas de enrutamiento de vehículos, que se basan en el TSP, son problemas de nivel operativo, es decir, deben ser resueltos de forma rutinaria por la empresa y, por lo tanto, no son compatibles con un tiempo de resolución alto. [5] La solución para conciliar el tiempo con la frecuencia necesaria de resolución del problema es el uso de métodos heurísticos, algoritmos que permiten reducir el tiempo medio de búsqueda de solución al problema, permitiendo llegar a buenas soluciones, pero sin la garantía de su optimalidad. [6]

¡Y es en este punto que la Naturaleza puede servir de inspiración para la construcción de algoritmos inteligentes!

Las hormigas son un tipo de insecto que libera feromonas a lo largo del camino que recorren. Mira el siguiente video, en el que se destaca el rastro de feromonas que dejan unas hormigas argentinas que, digamos, van en busca de alimento. Tenga en cuenta que este rastro que conduce a una "buena recompensa" (en este caso, digamos un puñado de azúcar) tiende a intensificarse con el tiempo y atrae a más y más hormigas. Sin embargo, hay algunos que aún continúan caminando por caminos aleatorios.

¿Qué pasaría si este comportamiento se incorporara a la construcción de una heurística para buscar buenas soluciones al problema del viajante de comercio? Hagamos un puente simplificado entre el comportamiento de las hormigas y los principios del algoritmo. Para más detalles recomendamos estudiar el material disponible en la referencia [8].

1. Inicialmente, liberamos a las hormigas en un ambiente abierto para que pudieran comenzar a buscar su comida; en lenguaje computacional, en pocas palabras, le pedimos al algoritmo que comience a buscar soluciones viables al problema propuesto, siguiendo una función probabilística para decidir qué aristas se incorporarán en su camino. Esta función probabilística puede tener en cuenta, por ejemplo, la calidad de cada borde (relacionado con el tiempo o la distancia para recorrerlo) y el nivel de feromona depositada en cada uno de ellos.
2. Imaginemos, ahora, que se liberará una nueva oleada de hormigas en este mismo entorno. Ahora, estas nuevas hormigas podrán orientarse por el rastro de feromonas que dejó la oleada anterior. En lenguaje computacional, la próxima búsqueda de soluciones tendrá en cuenta el nuevo contenido de feromonas depositado en cada borde, es decir, cuantas más hormigas hayan elegido el mismo borde en la primera búsqueda, mayores serán las posibilidades de que este borde sea elegido por estas. hormigas nuevas.
3. Sin embargo, imagine que hay un camino más interesante, que conduciría a una mayor porción de comida, que ninguna de las hormigas de la primera ola pudo capturar inicialmente. Como el rastro de feromonas dejado, a pesar de atraer nuevas hormigas, no las obliga a seguirlo, puede haber hormigas de la nueva ola que sigan un nuevo camino (quizás más atractivo) y empiecen a depositar más feromonas en los bordes que lo componen. Computacionalmente, la importancia de la función de probabilidad es que se pueden generar nuevas soluciones aleatorias, que preferencialmente, pero no necesariamente, siguen los rastros con mayor contenido de feromonas y resultan mejores que las obtenidas previamente. Así, la heurística permite que la búsqueda no se “pegue” a una buena solución localmente, con la búsqueda de nuevas soluciones que, globalmente, puedan resultar más interesantes.

Los conocimientos que la naturaleza puede ofrecer a la logística no se detienen ahí. ¿Has oído hablar de los algoritmos genéticos? Un tema muy interesante para ser abordado en el futuro aquí en el blog.

Fontes:

[1] https://super.abril.com.br/tecnologia/quem-afinal-inventou-o-aviao/
[2] https://super.abril.com.br/ciencia/o-manual-incrivel-de-inspiracao-na-natureza/
[3] Ballou, Cadena de suministro de recursos humanos/Gestión logística empresarial – p. 197 – 5. ed. – Bookman, 2007.
[4] http://www.math.uwaterloo.ca/tsp/gallery/igraphics/car54.html
[5] Ballou, Cadena de suministro de recursos humanos/Gestión logística empresarial – p. 53 – 5. ed. – Bookman, 2007.
[6] Ballou, Cadena de suministro de recursos humanos/Gestión logística empresarial – p. 448 – 5. ed. – Bookman, 2007.
[7] https://www.youtube.com/watch?v=tAe3PQdSqzg
[8] http://www.dca.fee.unicamp.br/~lboccato/topico_4.1_IA013_colonia_formigas.pdf