Tecnica de optimizacion por el metodo de las colonias de hormigas

Reporte sobre contextualización e implementación computacional de un problema de optimización metaheurística

Presentado por:

                 Samuel Ernesto Ruiz Villa

                                                Docente:

                         Andres Felipe Ocampo Palacio

                                       Curso:

                                       Técnicas de optimización

Universidad de Antioquia

Facultad de Ingeniería

Medellin

2016

contextualización del problema

La optimización mediante colonia de hormigas (ACO) tiene su fuente de inspiración en el comportamiento de algunas colonias de hormigas reales. Desarrollada por Marco Dorigo y otros a inicios de los 90.

En nuestro mundo natural, las hormigas (inicialmente) vagan de manera aleatoria, al azar, y una vez encontrada comida regresan a su colonia dejando un rastro de feromonas. Si otras hormigas encuentran dicho rastro, es probable que estas no sigan caminando aleatoriamente, puede que estas sigan el rastro de feromonas, regresando y reforzándolo si estas encuentran comida finalmente.

Sin embargo, al paso del tiempo el rastro de feromonas comienza a evaporarse, reduciéndose así su fuerza de atracción. Cuanto más tiempo le tome a una hormiga viajar por el camino y regresar de vuelta otra vez, más tiempo tienen las feromonas para evaporarse. Un camino corto, en comparación, es marchado más frecuentemente, y por lo tanto la densidad de feromonas se hace más grande en caminos cortos que en los largos. La evaporación de feromonas también tiene la ventaja de evitar convergencias a óptimos locales. Si no hubiese evaporación en absoluto, los caminos elegidos por la primera hormiga tenderían a ser excesivamente atractivos para las siguientes hormigas. En este caso, el espacio de búsqueda de soluciones sería limitado.

Por tanto, cuando una hormiga encuentra un buen camino entre la colonia y la fuente de comida, hay más posibilidades de que otras hormigas sigan este camino y con una retroalimentación positiva se conduce finalmente a todas las hormigas a un solo camino. La idea del algoritmo colonia de hormigas es imitar este comportamiento con "hormigas simulada" caminando a través de un grafo que representa el problema en cuestión.

[pic 1]

Figura 1. Evolución de trayectorias con el paso de hormigas

Planteamiento matemático:

Basado en la explicación anterior, se definen los siguientes parámetros:

Visibilidad (n(e)): Es un parámetro que describe la viabilidad de un tramo. Su magnitud es inversa a la longitud o costo del tramo.

[pic 2]

Cantidad de feromona: Como se había dicho antes, las hormigas al pasar frecuentemente por un camino, iran aumentando la cantidad de feromonas dejadas en el como rastro, permitiendo a otras hormigas seguir este camino, haciendo que sus búsquedas no sean aleatorias, sino que vayan convergiendo. Es esta tal vez el parámetro que involucra la heurística en este modelo, pues a cada iteración, los caminos se van definiendo más, tendiendo al de mejor rendimiento y siendo este un algoritmo iterativo de aprendizaje autónomo.

La cantidad de feromona se denota con el símbolo  (tao).
En cada iteración, el  actual se denota  y se define como:[pic 3][pic 4][pic 5]

[pic 6]

Donde:

  es el factor de evaporación de la feromona, ósea su nivel de desaparición[pic 7]

 es el aumento de la feronoma entre iteraciones, que es igual a el parámetro de aprendizaje sobre el costo del camino[pic 8]

[pic 9]

[pic 10]

[pic 11]

[pic 12]

La probabilidad de que una hormiga tome un tramo xy es:

[pic 13]

Formulación matemática:

Sea la red de posibles rutas

[pic 14]

Figura 2. Diagrama de rutas y valores de costo

Convenciones:

• Los caminos azules son los posibles tramos o trayectos que conforman una ruta o camino de Inicio a Final.

• Los círculos morados son los nodos entre tramos.

• Los números rojos son los costos asociados a cada trayecto

• Cada hormiga recorrerá alguna ruta tal que conecte el nodo 1 y 4

Desarrollo de ejemplo, calculo y toma de datos

Como se aprecia en la iteración inicial, se enlistan todos los caminos que pueden usar las hormigas con sus respectivos parámetros.

...