Algoritmo basado en la optimizacin mediante colonias de hormigas para la resolucin del problema del transporte de cargas desde varios orgenes a varios destinos.ACO = Ant Colony Optimization

Este es el problema que cualquier empresa de paquetera debe afrontar para el transporte entre delegaciones.

Se trata de elegir la alternativa de ruta de manera que el coste del sistema resulte ptimo en trminos econmicos.

La resolucin mediante programacin entera de este problema resulta inviable cuando seaplica a ejemplos de tamao real, por lo que se utilizan mtodos heursticos(basados en la experiencia y creatividad) para su resolucin.

Estudios realizados explican cmo animalescasi ciegos, como son las hormigas, son capaces de seguir la ruta ms corta en su camino de ida y vuelta entre la colonia y una fuente de abastecimiento.Esto es debido a que las hormigaspueden "transmitirse informacin" entre ellas gracias a que cada una de ellas, al desplazarse, va dejando un rastro de una sustancia llamada feromona a lo largo del camino seguido.As, mientras una hormiga aislada se mueve de forma esencialmente aleatoria, los "agentes" de una colonia de hormigas detectan el rastro de feromona dejado por otras hormigas y tienden aseguir dicho rastro.stas a su vez van dejando su propia feromona a lo largo del camino recorrido y por tanto lo hacen ms atractivo, puesto que se ha reforzado el rastro de feromona.

En el mundo natural, inicialmente las hormigas vagan aleatoriamente. Y si encuentran comida, vuelven a la colonia dejando el rastro de feromonas.Cuando las otras hormigas encuentran el rastro, ya no deben vagar aleatoriamente, sino que siguen el camino que dej la primera, y lo van reforzando con cada viaje.

La feromona en el camino menos recorrido, se va evaporando, haciendo que desaparezca ese rastro.

Qu nos dice eso?

Que el proceso se caracteriza por una retroalimentacin positiva, en la que la probabilidad con la que una hormiga escoge un camino aumenta con el nmero de hormigas que previamente hayan elegido el mismo camino.

Los algoritmos ACO son procesos iterativos. En cada iteracin se "lanza" una colonia de m hormigas y cada una de las hormigas de la colonia construye una solucin al problema.

Las hormigas construyen las soluciones de manera probabilstica, guindose por un rastro de feromona artificial y por una informacin calculada a priori de manera heurstica.

Los usos del algoritmo se utilizan para mquinas de aprendizaje y para problemas con una gran cantidad de datos. Se ha estudiado crear un modelo del mantenimiento de un cementerio donde las hormigas arraciman los cadveres de sus semejantes. ++=

AzcarMielCon algunos cambios del objetivo individual, reemplazndolo por varios objetivos, e involucrando diferentes conceptos como el econmico, o el medioambiental, se puede plantear el algoritmo hormiga para resolverlo.

Las hormigas prefieren la ms pequea gota de miel, antes que la ms abundante pero menos nutritiva azcar.Knapsack Problem(o problema de la mochila)Es un problema deoptimizacin combinatoria. Modela una situacin anloga al llenar unamochila, incapaz de soportar ms de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso yvalor especficos.

Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso mximo. Esto se ha adaptado a la tarea de supervisin de las mquinas deaprendizaje, encargadas de agrupar los grupos de objetos que son similares. De hecho se han demostrado que tales formas modificadas de algoritmos dan un funcionamiento y una exactitud mejores que los mtodos clsicos.

Este puede utilizarse para localizar ruta en sistemas GPS de manera sencilla sin tener que recalcular la ruta cuando no sea necesario.El algorimo se llama SoSACO, y est relacionado con la Teora de los Seis Grados de Separacinque afirma que una persona puede conectarse con cualquier otra del mundo a travs de sus conocidos en tan slo cinco pasos En Universidad Carlos III de Madrid, han creado un algoritmo que basndose en el comportamiento de las hormigas cuando buscan comida puede establecer relaciones contacto tras contacto en cuestin de milisegundos.De esta forma se puede conocer la afinidad entre usuarios Twitter o Facebook de manera casi inmediata. Adems el algoritmo tiene en cuenta las distintas relaciones y nueva informacin recibida lo que permite ponderar la bsquedaColonia de Hormigas, y las redes sociales

ENRUTAMIENTO DE PAQUETES EN REDES DE TELECOMUNICACIONES: ANTNETEl enrutamiento es la tarea consistente en determinar el camino que seguirn los paquetes en una red de telecomunicaciones cuando llegan a un nodo para alcanzar su nodo destino de la forma ms rpida posibleAntNet es un algoritmo de hormigas adaptativo y distribuido para enrutamiento de paquetes en redes.

El primer algoritmo basado en la optimizacin mediante colonias de hormigas fue aplicado alProblema del Viajante (Dorigo et al, 1996), obtenindose unos resultados bastante alentadores.

La solucin ms directa es la que aplica la fuerza bruta: evaluar todas las posibles combinaciones de recorridos y quedarse con aquella cuyo trazado utiliza la menor distancia.Sean N ciudades de un territorio. El objetivo es encontrar una ruta que, comenzando y terminando en una ciudad concreta, pase una sola vez por cada una de las ciudades y minimice la distancia recorrida por el viajante.El problema reside en el nmero de posibles combinaciones que viene dado por el factorial del nmero de ciudades (N!), y esto hace que la solucin por fuerza bruta sea impracticable para valores de N incluso moderados, con los medios computacionales actualmente a nuestro alcance.

Por ejemplo, si un ordenador fuese capaz de calcular la longitud de cada combinacin en un microsegundo, tardara algo ms 3 segundos en resolver el problema para 10 ciudades, algo ms de medio minuto en resolver el problema para 11 ciudades y 77.147 aos en resolver el problema para slo 20 ciudades.(TSP)El procedimiento que realizan las hormigas para la eleccin de la siguiente ciudad avisitar, pues se ofrece un balance entre la exploracin de nuevos caminos y laexplotacin del conocimiento acumulado acerca del problema;

PEROUn conjunto de agentes cooperativos intercambian informacin de manera indirecta, pero independientes unos de otros. En consecuencia, se vienen proponiendo varias estrategias de paralelizacin.

Paralela SincrnicaUn proceso inicial (master) levanta a un conjunto de procesos hijos, uno para cada hormiga. Despus de distribuir la informacin inicial acerca del problema, cada proceso inicia la construccin del camino y calcula la longitud del tour. Los resultados son enviados al master, quien se encarga de actualizar el nivel de feromonas y calcular el mejor tour encontrado hasta ese momento. Se inicia una nueva iteracin con el envo de la nueva matriz de feromonas.Parcialmente asincrnicaSe propone reducir la frecuencia de la comunicacin, para esto, cada hormiga realiza un cierto nmero de iteraciones del algoritmo secuencial, independientemente de las otras hormigas. Solo despus de estas iteraciones locales, se realiza una sincronizacin global entre las hormigas. Entonces, el master actualiza el nivel de feromonas y se inicia el proceso de nuevo.

- Secuenciacin de Tareas- Coloreo de Grafos- Enrutamiento de Vehculos- Ordenacin Secuencial- Pooling de vehculos- Lneas de produccin de coches- Problemas de Agrupamiento (Clustering)- Aprendizaje de Reglas Clsicas y Difusas- Bioinformtica: plegado de protenas 2D

El sistema de Hormigas Elitista se introdujo para solucionar el problema de la lentitud de convergencia del SH.La nica diferencia entre ambos es la regla de actualizacin que aplica un refuerzo adicional de los buenos arcos.

El sistema de Hormigas Max-Min (Max-Min Ant System, SHMM) es una nueva extensin del SH con una mayor explotacin de las mejores soluciones y un mecanismo adicional para evitar el estancamiento de la bsqueda.Mantiene la regla de transicin del SH, y cambia:* El mecanismo de actualizacin es ms agresivo al evaporar todos los rastros y aportar slo en los de la mejor solucin.* Define unos topes mnimo y mximo para los rastros de feromona.

Mantiene la regla de transicin del SH y cambia:El mecanismo de actualizacin es ms explotativo al evaporar todos los rastros, reforzar positivamente slo los de la mejor solucin global y negativamente los de la peor solucin actual.Aplica una mutacin de los rastros de feromona para diversificar.Reinicializa la bsqueda cuando se estanca.

Los sistemas de hormigas permiten disear algoritmos:Sencillos.Rpidos.Con buen rendimiento.Para problemas de optimizacin que se puedan representar en forma de grafo con pesos.