Problema De La Mochila Usando Colonia De Hormigas.pdf

UNIVERSIDAD DE ANTIOQUIA ´ FACULTAD DE ELECTRONICA Y TELECOMUNICACIONES PROYECTO

PROBLEMA DE LA MOCHILA USANDO LA METAHEUR´ISTICA DE COLONIA DE HORMIGAS

KARINA AGUDELO VALENCIA BRAYAN MATOS ROMERO JHON ANDERSON LOPERA

JUAN FELIPE BOTERO

Semestre 2016-2

PROBLEMA DE LA MOCHILA USANDO LA METAHEUR´ISTICA DE COLONIA DE HORMIGAS Karina Agudelo Valencia Jhon Anderson Lopera Brayan Matos Romero 18 de noviembre de 2016

Resumen En el problema de la mochila se cuenta con un n´ umero N de objetos con diferentes tama˜ nos wj y beneficios pj ; los cuales van a ser empacados en una mochila que tiene una capacidad C, de forma que se maximice el beneficio total de almacenar los objetos. Para lograr resolver este problema se implementar´ a la metaheur´ıstica de la colonia de hormigas, una heur´ıstica y un m´etodo para obtener la soluci´ on optima del problema. Palabras clave: Metaheur´ıstica, hormigas, feromona, evaporaci´ on.

1.

2.

´ INTRODUCCION

OBJETIVOS

Analizar a fondo el comportamiento poblacional de la metaheur´ıstica de la colonia de hormigas y entender como se relaciona el rastro de feromona con la convergencia a soluciones optimas. Ademas, de comparar los resultados y el tiempo de procesamiento que requiere aplicar la metaheur´ıstica versus encontrar la soluci´on optima.

Los problemas de optimizaci´ on han sido ampliamente usados en muchos y diferentes ´ ambitos, desde solucionar problemas cotidianos, hasta realizar estrategias en grandes empresas, para resolver problemas de la mejor manera y en el menor tiempo posible.El m´etodo de optimizaci´ on por colonia de hormigas o ACO (por sus siglas en ingles) es un enfoque metaheur´ıstico propuesto para resolver problemas de optimizaci´ on combinatoria complicados. La fuente inspiradora de ACO es el rastro de feromonas y el comportamiento que siguen hormigas reales que utilizan este rastro como medio de comunicaci´ on. El ACO se basa en la comunicaci´on indirecta de agentes simples, llamados hormigas (artificiales), mediados por senderos (artificiales) de feromonas. Los senderos de feromonas sirven como una informaci´ on num´erica distribuida que las hormigas utilizan para construir soluciones probabilistas al problema que se est´ a resolviendo y las hormigas se adaptan durante la ejecuci´ on del algoritmo para reflejar su experiencia de b´ usqueda. Aqu´ı veremos la implementaci´ on del algoritmo ACO para dar una soluci´ on al problema de la mochila, de forma optima y con diferentes alternativas, tambi´en se analizar´ a los cambios en los resultados del algoritmo con diferentes instancias.

´ DEFINICION DEL PROBLEMA

3.

El problema de la mochila es un problema NPcompleto, que modela una situaci´on an´aloga a llenar una mochila que cierta capacidad, con todo o parte de un conjunto de objetos; cada objeto tiene asociado a ´el un peso (o un tama˜ no) y un beneficio. Los objetos colocados en la mochila deben maximizar el beneficio colectivo sin exceder la capacidad total de la mochila.

3.1.

MODELO ´ CION]

DE

OPTIMIZA-

N → N´ umero de objetos C → Capacidad de la mochila 1

pj → Beneficio asociado al objeto j ∈ [1. . . N ]

Cuando las hormigas se enfrentan a un obst´ aculo como el que se muestra en la figura (1), inicialmenwj → Tama˜ no del objeto j te no hay presencia de feromonas en ninguno de xj → Variable binaria que indica si el objeto j los dos caminos, por lo que existe una probabilidad ha sido elegido en el subconjunto o no. igual para cada hormiga de elegir la trayectoria izP quierda o derecha. Como el camino derecho es m´ as Maximizar: Z = j pj · xj corto que el izquierdo y requiere menos tiempo de viaje, mayor cantidad de hormigas transitaran de P Sujeto a: j wj · xj ≤ C ida y regreso por el camino de la derecha en un mismo lapso de tiempo; de esta manera las hormixj ∈ [0, 1]∀j ∈ N gas terminar´an dejando un nivel m´as alto de feroN, C, pj , wj ≥ 0 ∈ Z monas. Cuantas m´as hormigas tomen el camino de lado derecho, mayor es el rastro. Por lo tanto, hay surgimiento de un camino m´as corto. 4. METAHEUR´ISTICA CO- un La comunicaci´on de las hormigas a trav´es de camiLONIA DE HORMIGAS nos con feromonas les permite encontrar las rutas mas cortas entre su nido y las fuentes de alimentos. 4.1. Definici´ on Esta caracter´ıstica es ampliamente utilizada para la soluci´on de problemas de optimizaci´on que necesiLa teor´ıa de optimizaci´ on por colonia de hormitan mejorar sustancialmente los tiempos de c´ompugas o Ant Colony Optimization, fue introducida por to para la soluci´on de una aplicaci´on espec´ıfica. Marco Dorigo en los inicios de 1990, como herramienta para la soluci´ on de problemas de optimizaci´ on complejos, inspirado en el comportamiento 4.2. Algoritmo ACO real de las hormigas. Estos insectos, cuando est´an Son basados en una colonia de hormigas artificial, en busca de fuentes de abastecimiento para su coloque intenta construir posibles soluciones compunia, inician explorando el ´ area alrededor de su nido tacionales simples a diferentes problemas, para lo aleatoriamente; cuando encuentran una fuente de cual utiliza informaci´on heur´ıstica y rastros de fealimento, ´estas eval´ uan la calidad y cantidad de la romonas. El m´etodo de hormiga artificial tiene las comida y llevan una muestra de regreso a su nido. siguientes propiedades:[2] En todo ´este trayecto las hormigas, depositan feromonas sobre el camino transmitiendo informaci´on Encuentra soluciones v´alidas con el menor que sirven de gu´ıa, para que en el futuro las dem´as tiempo de procesamiento. encuentren los alimentos, la cantidad de feromonas Posee un estado inicial y una o m´as condiciones depositadas depender´ a de la calidad, cantidad del de paradas asociadas, y se mueve siguiendo los alimento y cantidad de hormigas que transitan por estados v´alidos construyendo as´ı la soluci´ on. dicho camino. Cuanto mayor sea la cantidad de feroEl movimiento sobre un camino se realiza aplimonas en un camino particular, mayor ser´a la procando una regla de transici´on, la cual es funbabilidad de que las hormigas seleccionen ese caci´on de los rastros de feromona disponibles de mino. Para una hormiga dada, el camino que elige manera local, de los valores almacenados en la es de acuerdo con la cantidad de feromona. [1] memoria de la hormiga y de las restricciones La mejor forma para abordar y comprender c´omo del problema a solucionar. las hormigas utilizan el camino con la mayor cantidad de feromonas (el camino m´ as corto) se muestra El proceso de realizaci´on del algoritmo finaliza en la figura (1): cuando se encuentra alguna condici´on de parada o iteraciones dadas, lo cual ocurre normalmente cuando se alcanza el objetivo.

4.3.

Pseudo-c´ odigo del algoritmo

En los algoritmos de hormigas, una colonia de hormigas artificiales est´a buscando una buena soluci´on al problema dado. Algunas variables utilizadas en la elaboraci´on del algoritmo fueron:

Figura 1: Comportamiento de las hormigas

C: Capacidad total de la mochila 2

Vc : Capacidad actual de la mochila

4.4.

N h: Numero de hormigas

Como ya se ha mencionado anteriormente dos par´ametros fundamentales en el ACO son la cantidad de feromona que se aplica en las soluciones y el atractivo que tiene un ¸camino.en particular. El movimiento de cada hormiga depende de la feromona τ como tambi´en del atractivo µj .

IT : Numero de iteraciones wj : Peso del ladrillo j pj: Beneficio del ladrillo j Pj : Probabilidad del ladrillo j Oj : Objeto que representa al ladrillo J

4.5.

Feromona y Atractivo

Elecci´ on de un Objeto

Para un mayor entendimiento del algoritmo impleLa soluci´on parcial para cada hormiga es un submentado ilustra un pseudo-c´ odigo con las acciones conjunto de los objetos que constituyen una soluprincipales de la metaheur´ıstica: ci´on completa al problema. Los par´ametros α y β, que se utilizan en la regla de probabilidad de Inicio transici´on Pj Mientras (aun haya iteraciones) haga: τjα µβj Para cada hormiga haga: Pj = P α β Mientras (haya espacio en la mochila) haga: j τj µj Para cada ladrillo haga: Indican la importancia del rastro de feromonas τj y Calcular la probabilidad del ladrillo j el atractivo µj durante las transiciones de un estado Terminar a otro. Elegir un ladrillo Oj con probabilidad Pj Aumentar la feromona de Oj Agregar Oj al una soluci´ on parcial S 4.6. Fase de Evaporaci´ on Actualizar la capacidad Vc = Vc − wj Con el fin de evitar una convergencia muy r´ apiEliminar Oj del conjunto de ladrillos da a una soluci´on localmente ´optima, se utiliza el Terminar mecanismo de evaporaci´on τ = ρτ , donde τ es un Recordar la soluci´ on S de cada hormiga n´ umero entre cero y uno. Con el tiempo, el rastro Terminar de feromonas se evapora, reduciendo as´ı su fuerza Recordar la Mejor soluci´ on de las hormigas atractiva. Usar un mecanismo de evaporaci´ on Actualizar la feromona de la mejor soluci´on. 4.7. Fase de Refuerzo Terminar Fin Los objetos que se incluyen en una soluci´on reciben una cantidad adicional de feromonas τ = γτ , en donde γ > 1 y pueden seleccionarse despu´es con una probabilidad mayor que otros objetos.[3] Cuando se ha encontrando una soluci´on factible, se aplica Empieza con un vector de soluci´ on S vac´ıo y va a ´esta un refuerzo en las feromonas de la hormiga on. a˜ nadiendo a ´este objetos seleccionados uno tras que encontr´o dicha soluci´on con la siguiente raz´ otro con una probabilidad Pj , desplaz´andose de 1 τj = τj + un estado a otro, sin superar la capacidad de Sbest +pj 1 + Sbest la mochila.

En general, se puede exponer el c´odigo en t´ermino de las acciones que sigue la colonia; de esta manera, para cada hormiga:

Construye una soluci´ on parcial S al problema Esto se hace despu´es de cada iteraci´on con el fin con un conjunto de ladrillos en cierto n´ umero de darle mas prioridad a las hormigas que generan de pasos. mejores soluciones. En cada paso toma en consideraci´on un conjunto de posibles ladrillos a su estado actual y se mueve a uno de estos con la probabilidad dada. Deposita feromona en todos los objetos incluidos en la mochila. La cantidad de feromonas depositadas depende de la calidad de esta soluci´ on. 3

5.

´ ANALISIS DE RESULTADOS Y CONCLUSIONES

A continuaci´ on se muestra la convergencia del algoritmo implementado para diferentes instancias:

Para 10 hormigas:

Figura 5: Resultado Obtenido para 10 hormigas en 70 iteraciones

Para 20 hormigas:

Figura 2: Resultado Obtenido para 10 hormigas en 20 iteraciones Figura 6: Resultado Obtenido para 20 hormigas en 20 iteraciones

Figura 3: Resultado Obtenido para 10 hormigas en 30 iteraciones Figura 7: Resultado Obtenido para 20 hormigas en 30 iteraciones

Figura 4: Resultado Obtenido para 10 hormigas en Figura 8: Resultado Obtenido para 10 hormigas en 50 iteraciones 50 iteraciones

4

Figura 9: Resultado Obtenido para 20 hormigas en Figura 13: Resultado Obtenido para 70 hormigas en 70 iteraciones 20 iteraciones Para 40 hormigas:

Figura 10: Resultado Obtenido para 40 hormigas en Figura 14: Resultado Obtenido para 70 hormigas en 20 iteraciones 30 iteraciones

Figura 11: Resultado Obtenido para 40 hormigas en 30 iteraciones Figura 15: Resultado Obtenido para 70 hormigas en 40 iteraciones

Figura 12: Resultado Obtenido para 40 hormigas en 70 iteraciones Figura 16: Resultado Obtenido para 70 hormigas en 50 iteraciones Para 70 hormigas: 5

entre estos. Otros par´ametros que interfieren directamente con el tiempo de ejecuci´on son: la probabilidad de acuerdo a la cual se elige el ladrillo que se ingresa en la mochila y el refuerzo de feromona para los ladrillos que se van escogiendo en cada etapa. De hecho se observo que usar un esquema de refuerzo agresivo, es decir aumentar demasiado la feromona, causa retraso en el tiempo de ejecuci´on. Es por esto que se defini´o un aumento del 20 % 5. Se realizo, ademas de la metaheur´ıstica y la soluci´on optima, una heur´ıstica con el fin de realizar comparaciones con los otros m´etodos. Se observ´o que la metaheur´ıstica con suficientes hormigas e iteraciones no solo genera mejores soluciones que la heur´ıstica, sino que es capaz tambi´en de llegar a la soluci´on optima. Figura 17: Comportamiento de las hormigas

6.

BIBLIOGRAF´IAS

1. Cuando las instancias se incrementan, sea el [1] Talbi Ghazali, Metahuristics from design to implementation, p´agina 240. n´ umero de hormigas, las iteraciones, o ambas, conservando la misma cantidad de ladrillos la soluci´ on arrojada por la metaheur´ıstica de la [2] Maniezzo, Gambardella y De Luigi, Ant Colony Optimization, 2004. colonia de hormigas es cercana al valor optimo del valor de la soluci´ on exacta, que se hallo [3] Krzysztof Schiff, Ant Colony Optimiusando la librer´ıa GLPK. zation For The 0-1 Knapsack Problem [Online], Disponible en: https: 2. Tanto aumentar el numero de hormigas y el //suw.biblos.pk.edu.pl/resources/i4/ numero de iteraciones incrementan el tiempo i5/i7/i3/i1/r45731/SchiffK_AntColony.pdf en ejecuci´ on del c´ odigo utilizado, sin embargo, genera mejores soluciones.. [4] Optimizaci´ on basada en Colonia de Hormigas [Online], Disponible en: 3. Los cambios que se realizaron en la ejecuci´on https://ccc.inaoep.mx/˜emorales/Cursos/ del algoritmo fue variando el n´ umero de hormiNvoAprend/hormigas.pdf gas e iteraciones, las instancias de capacidad y numero de ladrillos no se modificaron. Luego de [5] Juan Felipe Botero, Curso de T´ ecnicas de varias pruebas se observo que para 15 hormigas Optimizaci´ on [Online], Disponible en: https: y 38 iteraciones la soluci´ on de la metaheur´ıstica //sites.google.com/site/juanfebotero/ converge al optimo dado por GLPK. Aumentar teaching/tecnicas-de-optimizacion-2016-1 el numero de hormigas o el n´ umero de iteraciones muy por encima de estos valores es innecesario, solo se estar´ıa gastando tiempo de procesamiento ya que en la mayor´ıa de ocasiones se obtienen buenas soluciones sin la necesidad de usar demasiadas iteraciones u hormigas. 4. En el algoritmo existen par´ ametros que ayudan o perjudican en la convergencia a una buena soluci´ on. Por ejemplo, los par´ ametros α y β definen la intensificaci´ on y diversificaci´on de la metaheur´ıstica, respectivamente, sin embargo, se not´ o que aumentar α en mayor proporci´on que β causa un aumento en el tiempo de ejecuci´ on, por tanto se estableci´ o un compromiso 6