Click acá para ir directamente al contenido

Enfoque bioinspirado para la optimización en ingeniería

Colonias de hormigas, la propagación de semillas, la formación de ríos, las migraciones y la improvisación jazzística son sistemas naturales que se utilizan actualmente como base para el diseño e implementación de modelos y software que resuelven problemas de optimización en ingeniería.

Martes 24 de enero de 2017

Enfoque bioinspirado para la optimización en ingeniería - Foto 1

La naturaleza enseña y sorprende con su capacidad de sobrevivencia en el medio. Sistemas organizados de recolección de alimentos, alineación en el traslado de las aves y el crecimiento de las bacterias son algunas de las experiencias que, a lo largo de la historia, la humanidad ha utilizado como ejemplos e inspiración para su desarrollo social y tecnológico. En esta lógica, un método de resolución de problemas derivado de la estructura y el comportamiento de un sistema natural se conoce como enfoque bioinspirado.  

El profesor de la Escuela de Ingeniería Informática de la Pontificia Universidad Católica de Valparaíso, Broderick Crawford, junto al grupo de investigación “Inteligencia Computacional”, trabaja en esta técnica con el objetivo de desarrollar y evaluar nuevos algoritmos para resolver problemas de ciencias básicas y dificultades de transferencia tecnológica.

Si bien la inspiración desde la biología ha acompañado desde sus inicios a la computación, el uso de algoritmos que imitan directamente el comportamiento de los organismos naturales es de desarrollo reciente.

Los primeros antecedentes de este método tuvieron lugar en la década del noventa, cuando Marco Dorigo, del Instituto de Investigación IRIDIA de la Universidad Libre de Bruselas, se inspiró en el comportamiento de las hormigas implementando algoritmos computacionales para resolver el Problema del Vendedor Viajero (TSP).

Éste tiene por objetivo encontrar el circuito óptimo para un viaje más corto que deberá seguir un vendedor para visitar una determinada cantidad de ciudades, donde cada una se visita exactamente una vez. “Es un tipo de problema de asignación que debe garantizar la exclusión de sub-tours en la solución óptima para obtener un ciclo Hamiltoniano (ciclo que pasa una y solo una vez por todos los nodos, vértices, de un gráfico) y que para valores grandes de ‘n’ resulta muy difícil de resolver”, explica Crawford.

Como éste, hoy muchos métodos bioinspirados han mostrado un desempeño igual o superior a las técnicas clásicas, resolviendo problemas de optimización en ingeniería. Y es más, también se han podido abordar problemas imposibles de resolver con otras técnicas. “Lo interesante es que no es solo un ejercicio académico, ya que en muchos casos los resultados obtenidos en este tipo de investigaciones científicas se han llevado a la práctica, concluyendo en la implementación de software utilizados en diferentes industrias”, comenta.

Inteligencia de Enjambre

Dentro de este tipo de enfoques se destaca la inteligencia de los enjambres y para comprenderlo, es necesario, en primer lugar, entender un enjambre como una población de elementos que interactúan entre ellos y con su medio ambiente, y que son capaces de optimizar un objetivo global a través de la colaboración siguiendo reglas simples. A estas comunidades las caracteriza su capacidad de auto organización, donde una gran cantidad de procesos simples pueden conducir a resultados complejos. Muchas veces, esta interacción se realiza indirectamente a través del entorno.

El alineamiento de las aves mientras vuelan, el comportamiento de los rebaños de animales durante el proceso de pastoreo y una colonia de hormigas son ejemplos claros de este tipo de conductas, siendo la última la más conocida. Al vivir en colonias, y gracias a la colaboración mutua, son capaces de mostrar comportamientos complejos en tareas que son difíciles de realizar individualmente por una hormiga.

Esta conducta emergente es capaz de resolver el problema, probablemente no de manera óptima, pero sí obteniendo soluciones suficientemente buenas, baratas y a tiempo. “Son muy útiles cuando existe un método que consume mucho tiempo o para obtener una solución inicial como entrada a otra técnica”, señala.

Los investigadores de la PUCV han aplicado la inteligencia de enjambres para resolver diferentes problemas, entre los que se destacan Software Project Scheduling Problem, Timetabling, Manufacturing Cell Design Problems, Open Pit Mining Problems, Social Golfer Problem, Sudoku puzzles, entre otros.

De esta forma queda demostrado que la práctica de hallar en el comportamiento de la fauna o de distintos sistemas biológicos la inspiración para crear algo totalmente nuevo o duplicar diseños naturales en productos y tecnologías para el desarrollo humano, se ha transformado en una pieza fundamental para resolver problemas desde la planificación automática, el reconocimiento de patrones y son parte de la rutina de investigación en campos como la economía, la medicina, la ingeniería e incluso en estrategias militares.

Optimización por Colonia de Hormigas

Se basa en la habilidad de las hormigas para encontrar los caminos más cortos entre el hormiguero y sus fuentes de alimento. Mientras se mueven entre su refugio y el lugar donde se encuentra su comida, las hormigas depositan una sustancia química denominada feromona que los otros miembros de la colonia pueden detectar.

En sus desplazamientos, si no encuentran ningún rastro, se mueven de manera aleatoria, y cuando ésta existe, tienen mayor tendencia a seguir el rastro. Las hormigas eligen el camino a seguir con una decisión probabilística sesgada por la cantidad de feromona: cuanto más fuerte es su rastro, mayor es la probabilidad de elegirlo. Así, su comportamiento lleva a un proceso de reforzamiento de dicha hormona en ciertos senderos, permitiendo a las hormigas encontrar los caminos más cortos.

Esta conducta emergente de toda la colonia, establece caminos óptimos y adaptativos entre el hormiguero y la comida, proporcionando muy buenas soluciones logísticas para alimentar a la colonia.

Una vez conocido el proceso natural, es posible llevar a cabo combinaciones de algoritmos similares en casos de problemáticas de diversas industrias, como por ejemplo:

  • La cadena de supermercados Migros en Suiza y la industria de pastas italiana Barilla utilizan la aplicación AntRoute para el enrutamiento de su flota de vehículos.
  • En Centro de Soft Computing de la Universidad Politécnica de Cataluña los ha aplicado para optimizar la línea de montaje de automóviles Nissan, donde se quería agrupar las tareas en el menor número posible de estaciones de trabajo de manera de satisfacer un tiempo de ciclo y obtener así la agrupación que minimizara este tiempo de ciclo.
  • La red de datos de Japón NNTnet utiliza AntNet, un algoritmo de hormigas adaptativo y distribuido para enrutamiento de paquetes en redes.

 

Proyecto FONDECYT 1140897 “An Autonomous Search System to Hybrid Constraint Solver Cooperation”.

Por Genny Viedma

Dirección General de Vinculación con el Medio