Las hormigas
son insectos sociales que viven en colonias y que, debido a su colaboración
mutua, son capaces de mostrar comportamientos complejos y realizar tareas complejas
desde el punto de vista de una hormiga individual. Un aspecto llamativo del
comportamiento de muchas especies de hormigas es su habilidad para descubrir los caminos más cortos entre el
hormiguero y el alimento. Este hecho es especialmente llamativo si se valora
que muchas de las especies de hormigas son casi ciegas, lo cual dificulta el
uso de las habilidades visuales. Mientras se mueven entre el hormiguero y el
alimento, algunas especies de hormigas colocan una sustancia química denominada
feromona
(una sustancia que puede “olerse”). Si no se encuentra ningún rastro
de feromona, las hormigas se mueven de manera básicamente aleatoria, pero
cuando existe feromona depositada, tienen mayor tendencia a seguir el rastro.
De hecho, los experimentos realizados por biólogos han demostrado que las
hormigas prefieren de manera probabilística los caminos marcados con una concentración
superior de feromona. En la práctica, esta elección entre
distintos caminos toma cuerpo cuando varios caminos se cruzan. Entonces, las
hormigas eligen el camino a seguir con una decisión probabilística condicionada
por la cantidad de feromona: cuanto más fuerte es el rastro de feromona, mayor
es la probabilidad de elegirlo. Puesto que las hormigas depositan feromona
en el camino que siguen, este comportamiento lleva a un proceso de auto-refuerzo
que concluye con la formación de rastros señalados por una concentración de feromona
elevada. Este comportamiento permite además a las hormigas encontrar los caminos
más cortos entre su hormiguero y la fuente del alimento. Así, los
caminos menos prometedores pierden progresivamente feromona porque son
visitados cada vez por menos hormigas. Sin embargo, algunos estudios biológicos
han demostrado que los rastros de feromona son muy persistentes, la feromona
puede permanecer desde unas pocas horas hasta varios meses dependiendo de
varios aspectos distintos, como la especie de las hormigas, el tipo de suelo, etc.,
lo que provoca una menor influencia del efecto de la evaporación en el proceso
de búsqueda del camino más corto. Incluso se puede dar la paradoja que debido a
la gran persistencia de feromona, es difícil que las hormigas “olviden” un
camino que tiene un alto nivel de feromona aunque hayan encontrado un camino
aún más corto.
En la actualidad el management o gestión persigue de
forma exhaustiva la eficiencia con el fin de garantizar la supervivencia de las
compañías. Las variables de un proceso productivo se cuantifican en kpi´s
numéricos que indican la minimización de los costes y la maximización de su
utilidad. Para problemas pequeños se pueden utilizar herramientas como la programación
lineal (corresponde
a un algoritmo a través del cual se resuelven situaciones reales en las que se
pretende identificar y resolver dificultades para aumentar la productividad
respecto a los recursos principalmente los limitados y costosos, aumentando así
los beneficios), programación entera o mixta (son
aquellos donde la totalidad o un subconjunto de las variables de decisión toman
valores enteros), o programación dinámica (sirve para resolver
problemas combinando las soluciones de subproblemas), que permiten encontrar
rápidamente respuestas óptimas con un correcto desarrollo del modelo. Sin
embargo, cuando los problemas son más grandes y el número de variables y restricciones
aumenta, el conjunto de soluciones factibles crece hasta tal punto que no es
posible encontrar el óptimo en un intervalo razonable de tiempo. Por lo tanto,
un
modelo de solución efectivo debe estar basado tanto en la calidad de la
respuesta como en el tiempo de procesamiento que se requiere para alcanzarla.
Este último tipo de problemas son los que se conocen como del tipo NP-Hard, son
problemas que no
tienen algoritmos polinomiales por lo que un algoritmo que lo resuelva en forma
exacta puede tardar un tiempo prohibitivo. Así que la solución con algoritmos
polinomiales son soluciones aproximadas. Existen dos categorías de tales
algoritmos: algoritmos de aproximación o los algoritmos heurísticos.
Los métodos heurísticos también
pueden ser utilizados como parte de un proceso global de solución óptima, en
etapas iniciales o intermedias, para después buscar mejores soluciones con
otros métodos de optimización combinatoria. Sin embargo, las aproximaciones de
los métodos heurísticos son muchas veces estancamientos en óptimos locales y
sus resultados pueden estar demasiado lejos del óptimo global. El término “heurístico” proviene del griego heuriskein, que significa “descubrir”. Su definición es la
siguiente: un método heurístico es un procedimiento para resolver un problema de
optimización bien definido mediante una aproximación intuitiva, en la que la estructura
del problema se utiliza de forma inteligente para obtener una buena solución. Existen
también los problemas meta-heurísticos,
son aquellos que por soluciones heurísticas no se encuentran soluciones convincentes.
Las características tan importantes que
diferencian los heurísticos de los meta-heurísticos han incentivado en los
últimos años el desarrollo de nuevos modelos de este tipo y su aplicación para
resolver problemas complejos de operaciones dentro del mundo empresarial http://bit.ly/2cOG8MU
Entre las meta-heurísticas se encuentra
la Optimización basada en Colonias de Hormigas (ACO, del inglés, Ant Colony
Optimization) que fue presentada por Marco Dorigo en su tesis doctoral
en 1992. Los
algoritmos de OCH son esencialmente algoritmos constructivos: en cada iteración
del algoritmo, cada hormiga construye una solución al problema recorriendo un
grafo de construcción. Cada arista del grafo, que representa los posibles pasos
que la hormiga puede dar, tiene asociada dos tipos de información que guían el
movimiento de la hormiga:
•Información heurística, que mide la
preferencia heurística de moverse desde el nodo r hasta el nodo s, o
sea, de recorrer la arista ars. Se
nota por ηrs. Las hormigas no
modifican esta información durante la ejecución del algoritmo.
•Información de los rastros de feromona
artificiales, que mide la “deseabilidad aprendida” del movimiento de r a s. Imita a la feromona real que
depositan las hormigas naturales. Esta
información se modifica durante la ejecución del algoritmo dependiendo de las
soluciones encontradas por las hormigas. Se nota por τrs.
Para aplicar el algoritmo OCH es necesario establecer
una secuencia de pasos, los cuales se indican a continuación.
- Representar el problema mediante nodos.
- Definir el significado de los rastros de feromona de una manera adecuada.
- Poner pesos a la información heurística en cada nodo o arco.
- Desarrollar algoritmos que permitan realizar optimizaciones locales.
- Escoger un algoritmo OCH específico.
- Refinar los parámetros del algoritmo de OCH.
• Encuentra soluciones válidas con el menor costo.
• Tiene una memoria que almacena información de los caminos recorridos, la
cual puede ser utilizada para construir soluciones validas, evaluar la solución
generada y reconstruir el camino que ha seguido la hormiga.
• Posee un estado inicial, el cual corresponde a una secuencia unitaria y
una o más condiciones de paradas asociadas.
• Empieza con un estado inicial y
se mueve siguiendo estados validos construyendo así la solución de forma
incremental.
• El movimiento sobre un camino se
realiza aplicando una regla de transición, la cual es función de los rastros de
feromona disponibles de manera local, de los valores heurísticos almacenados en
la memoria de la hormiga y de las restricciones del problema a solucionar.
• En cualquier momento del desarrollo
del algoritmo se pueden actualizar los rastros de feromonas asociados a cada
camino.
• El proceso de realización del
algoritmo finaliza cuando se encuentra alguna condición de parada, lo cual
ocurre normalmente cuando se alcanzan los objetivos (Maniezzo, Gambardella y De
Luigi).
Aunque actualmente las técnicas del OCH están siendo utilizadas en
diferentes campos, aun es mucho el camino que falta por recorrer y son muchas
las aplicaciones que se pueden desarrollar aplicando esta meta-heurística. La aplicación
de algoritmos de colonia de hormigas a problemas de optimización combinatoria y
el desarrollo de nuevas y mejores variantes algorítmicas de las OCH son las tendencias
actuales en cuanto a investigación en esta área. También se está trabajando en
desarrollar aplicaciones basadas en problemas de optimización multi-objetivos y dinámicos. Este modelado matemático, la inteligencia
artificial, la computación paralela y otras técnicas de digitalización se
utilizan hoy en día en compañías multinacionales como por ejemplo ARCELOR MITTAL
para predecir demandas, comportamientos del mercado, programar secuencias de
fabricación, realizar compras o diseñar instalaciones. Por otro lado, en la actualidad se está llevando un trabajo arduo para
encontrar procedimientos que permitan mejorar la velocidad de los procesos y las
soluciones obtenidas por los algoritmos de OCH http://bit.ly/2mwxid4.
Para
terminar este post quiero decir que cuesta entender y comprender que problemas
tan complejos como los que se relatan en este post encuentren soluciones en
base al comportamiento de seres vivos tan diminutos como las hormigas. Sin
embargo problemas tan visibles como son la gestión de indicadores claves de una
compañía como; ingresos, clientes, deuda, etc., pasen tan desapercibidos por
aquellos directivos que los tienen que
gestionar y resolver. Será que las hormigas no nos han enseñado
todavía su secreto…
Ya lo dijo
Larry Bernstein; “No
automatices un flujo de trabajo indisciplinado. El ordenador no va a resolver
lo que los directivos del cliente no pueden”.
No hay comentarios:
Publicar un comentario