• Author / Uploaded
• Raul Benitez Martinez

Citation preview

Knapsack: Resolución y comparación mediante Algoritmos MOEA: SPEAII y Algoritmos MOACO: PACO Raúl Benítez, Victor Rumich, Carlos Aquino, Alberto Garcete Ingeniería Informática, Facultad Politécnica – Universidad Nacional de Asunción. San Lorenzo - Paraguay {raulkvd, varfer86, aquinoQCD29, albertogarcetepy}@gmail.com

Resumen. La resolución del problema de la mochila o Knapsack es realizada mediante dos tipos de algoritmos, uno de ellos es el SPEAII, variante del SPEA, que forma parte de los tipos de algoritmos evolutivos multiobjetivos o MOEAs; el otro es el P-ACO, uno de los algoritmos pertenecientes al grupo de metaheurística ACO u optimización por colonia de hormigas multiobjetivo MOACO. Por último, se presenta una comparación entre los resultados que arrojan los distintos algoritmos mediante métricas de rendimiento. Palabras Clave: Knapsack, MOEA, SPEAII, MOACO, P-ACO.

1

Introducción

Este documento muestra una comparación entre diversos algoritmos que utilizan la optimización multi-objetivo, uno de ellos con enfoque evolutivo y otro basado en el modelo del comportamiento de las colonias de hormigas reales, denominada metaheurística ACO (Ant Colony Optimization, u optimización basada en colonia de hormigas). El trabajo considera algoritmos propuestos como el SPEAII con respecto a la teoría de algoritmos evolutivos y/o genéticos, y algoritmos como el P-ACO con respecto a la teoría de la optimización basada en colonia de hormigas. Se realizaron pruebas con dos instancias del problema. Se utilizó un reconocido problema de prueba de optimización multi-objetivo, el Multiobjective 0/1 Knapsack Problem(o problema de la mochila). Este tipo de problema es considerado clásico en la literatura de optimización combinatoria y es del tipo NP-completo.

2

Formulación del problema

2.1 Multiobjective Knapsack 0/1 (Problema de la Mochila) El problema de la mochila (o Knapsack problem) es un problema de optimización combinatoria. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo. Dados un conjunto de m ítems y un conjunto de n mochilas, donde: •

pij representa el profit (valor) del ítem j en la mochila i,

•

wij representa el peso del ítem j en la mochila i, y

•

ci representa la capacidad de la mochila i,

la formulación matemática más común del problema es la del llamado problema de la mochila 0/1, que restringe el número de copias de cada ítem a cero o uno, y consiste en encontrar un vector: , tal que:

y

, con:

donde xj = 1 indica que se utiliza el ítem j.

3

Algoritmo MOEA

Los MOEAs se inician con un conjunto de individuos creados de forma aleatoria, los cuales constituyen la llamada población inicial. Cada individuo (cromosoma) en la población representa una solución al problema de optimización. En cada generación, los individuos son evaluados usando una función de adaptabilidad (fitness). Basados en este valor, algunos individuos, llamados padres, son seleccionados. La probabilidad de selección de un individuo está relacionada con su adaptabilidad, de forma a asignar mayor probabilidad de selección a los mejores individuos. Luego, un número de operadores genéticos son aplicados a los padres para producir nuevos individuos que formarán parte de la nueva población. El proceso continua intentando obtener soluciones cada vez mejores hasta que un criterio de parada sea satisfecho. Los algoritmos que se encuentran incluidos en el conjunto de MOEAs siguen básicamente los pasos descritos en el siguiente pseudo-código:

Algoritmo 1. Pseudo-código para cualquier algoritmo considerado MOEA.

procedure MOEA inicializar_parametros() generar_población_inicial()

while(!condicion_parada) evaluar_individuos() actualizar_conjunto_pareto() seleccionar_individuos() aplicar_operadores_geneticos()

3.1 SPEAII - Strength Pareto Evolutionary Algorithm II En el año 2001 Zitzler, Laumanns y Thiele hacen unas correcciones al algoritmo SPEA, al que llama SPEAII (Zitzler et al., 2001), y éste último se diferencia del primero por la asignación de la aptitud, la selección de los padres, el operador de truncamiento y en fijar el tamaño del archivo externo para todas sus generaciones.

Asignación de la Aptitud: Para la asignación de la aptitud, a diferencia del SPEA, se tiene en cuenta tanto los individuos dominados como los que dominan y la densidad de cada individuo. El valor de fuerza del individuo i , Si está dado por:

Donde j equivale al número de soluciones que i domina, Pt y P't son los individuos de la población y los individuos pertenecientes al archivo externo en la generación t respectivamente. Teniendo en cuenta esta nueva definición de valor de fuerza, se calcula el valor de una aptitud cruda (sin tener en cuenta la densidad) para cada individuo Ri el cual está dado por la siguiente ecuación:

Se debe tener en cuenta que en la medida que un individuo tenga un valor de aptitud pequeño será preferido a uno que tenga un valor más alto. Otro componente de la aptitud de cada individuo es la medida de densidad Di , la cual la proponen como una adaptación al método del vecino más cercano, así:

Donde es la distancia de i al k−ésimo elemento. Para hallar este valor se calcula la distancia de i a todos los individuos, tanto de la población como del archivo externo y luego se organiza estas distancias en una lista en orden ascendente, y se toma el valor del k−ésimo elemento comosiendo . Donde N es el tamaño de la población y N' es el tamaño del archivo externo. De esta forma el valor de aptitud para el individuo i esta dado por:

Individuos del archivo externo: Inicialmente se copia todos los individuos no dominados, tanto de la población como del archivo externo de la generación anterior, al archivo externo de la generación actual, una forma de identificarlos es seleccionando aquellos individuos que tenga valor de aptitud menor que uno. Para el SPEA II el tamaño del archivo externo siempre es constante en el tiempo, por tanto, en el caso en que estos individuos no sumen la cantidad dada por el usuario N' , se debe completar el archivo con los mejores individuos dominados, es decir, con los que tengan menor valor de aptitud.

Y si el número hallado de no dominados es mayor que N' entonces se debe remover los individuos necesarios hasta que el tamaño del archivo sea N' . La forma como se escoge el individuo a remover es hallando el que tenga la distancia mínima a otros individuos y este será eliminado, en el caso de que exista varios individuos con la misma distancia mínima, se escoge quien tenga la segunda menor distancia mínima. La selección de los padres: La selección se hace por torneo binario con remplazo participando solamente los individuos del archivo externo. Con las mejoras propuestas para este algoritmo, efectivamente logra valores mucho mejores que el SPEA, y aunque no haya tenido la misma popularidad que éste último, ha sido preferido junto con NSGA-II para la optimización de problemas reales.

Fig. 1. Una gráfica que muestra los pasos a seguir para implementar el “loop

principal” del algoritmo SPEAII.

4

Algoritmo MOACO

Los algoritmos basados en colonias de hormigas son sistemas multi-agentes, donde el comportamiento de cada hormiga en particular, denominada hormiga artificial, está inspirado en el comportamiento de las hormigas reales Este comportamiento se obtiene por medio de una sustancia química llamada feromona, que las hormigas depositan al caminar en busca de alguna fuente de comida, dejando de esta manera rastros de feromonas que las demás hormigas pueden oler. Las feromonas representan para las hormigas una forma de comunicación indirecta llamada “Stigmergy”. Se muestra el pseudo-código de un algoritmo ACO multi-objetivo genérico, denominado en adelante MOACO (MultiObjective Ant Colony Optimization). El PACO presentado a continuación, sigue éste pseudo-código:

Algoritmo 2. Pseudo-código de un algoritmo ACO multi-objetivo procedure MOACO inicializar_parametros() while not condicion_parada() generacion=generacion + 1 for ant=1 to m // m=cantidad de hormigas construir_solucion() evaluar_solucion() actualizar_feromonas() actualizar_conjunto_pareto() end for end while end procedure construir_solucion sol={Ø} while existen_estados_no_visitados() siguiente=seleccionar_siguiente_estado() sol=sol U {siguiente} marcar_como_visitado(siguiente) if(actualizacion_paso_a_paso) actualizar_feromonas_paso_a_paso() end while end

4.1 Pareto Ant Colony Optimization. Este algoritmo se propuso en [Doerner 2002], y se basa en la utilización de b tablas de feromonas (τb), una para cada objetivo. En cada iteración una hormiga computa una serie de pesos que fueron seleccionados uniformemente aleatorios, δ = ( δ1, δ2,…, δb), y los utiliza al calcular la regla de transición de estados. Estando en el estado i se selecciona el estado j según:

(4.1) Donde i es una variable aleatoria seleccionada según la distribución de probabilidades calculada con la ecuación:

(4.2) Las dos mejores hormigas de cada solución actualizan la tabla de feromonas correspondiente a dicho objetivo según la ecuación 4.3, realizando una actualización elitista.

(4.3) Cada vez que una hormiga avanza a otro estado, se realiza una actualización local paso a paso de las b tablas de feromonas según la ecuación 4.3, considerando un valor constante para ∆τ= τo, que representa el valor inicial para las feromonas, definido a priori.

5

Resultados Experimentales

5.1 Métricas de evaluación Ese utilizaron tres métricas para poder evaluar los resultados obtenidos, fueron la M1, M2 y M3 cada una de ellas se refieren respectivamente a la distancia existente a un frente Pareto óptimo, a la calidad de distribución de las soluciones sobre el frente Pareto y a la extensión sobre del frente Pareto. Para M1 se tiene la fórmula: M1 ' (Y ' )= 1/ |Y'| ∑ min { d(p, a} | a ∈ Y }

Calcula la diferencia entre un frente Pareto óptimo (Y) y un frente Pareto generado por la implementación (Y'). Para M2 la fórmula: M2 ' (Y ')= 1/(|Y'| - 1) ∑ ∣ {q∈Y ' ∣ d ( p , q)> σ } ∣ Calcula la adecuada distribución del Frente Pareto sumando la cantidad de puntos fuera del vecindario σ, en el frente Pareto. Para M3 la fórmula: M3 ' (Y ')= ( ∑ max {d ( pi , qi ) ∣ p , q∈Y ' } ) ^ (1/2) Calcula la extensión del frente Pareto, tomando la máxima distancia entre dos puntos, en cada función objetivo, realizando la suma y hallando la raíz cuadrada de la misma.

5.2 Resultados Los resultados obtenidos en base a pruebas hechas en el modelo del SPEA II arrojaron resultados próximos al frente Pareto óptimo, para la instancia correspondiente al de 100 items, con respecto a la instancia de 500 items en las métricas se observa una desviación considerable respecto al frente Pareto óptimo lo que hace sacar de conclusión que para instancias pequeñas (menores o iguales a 100) el SPEA II posee un buen rendimiento. La máquina donde se realizo las pruebas fue con las siguientes caracteristicas: memoria de 2 Gb y procesador de 2600 Mhz.

Tabla 1. Resultados obtenidos sobre Instancia 1 del Knapsack evaluado con SPEA II.

Instancia 1 (100 items)

M1

M2

M3

Frente Pareto óptimo

0

97,0

43,046

SPEA II

788,128

86,141

37,296

Tabla 2. Resultados obtenidos sobre Instancia 2 del Knapsack evaluado con SPEA II.

Instancia 2 (500 items)

M1

M2

M3

Frente Pareto óptimo

0

1122,906

92,136

SPEA II

5045,298

90,162

47,529

6

Conclusiones y trabajos futuros

Como grupo pudimos concluir que estos dos algoritmos, cuyo comportamiento imitan tanto lo que sucede a nivel genético, así como lo que sucede en el reino animal para el caso de la colonia de hormigas, resuelven verdaderamente serios problemas de optimización, dando un conjunto de posibles soluciones que son los mejores entre todas las posibilidades que existen. Aprender y entender como se lleva a cabo mediante una implementación real es un conocimiento que nos ayudó a sacarnos varias dudas acerca de lo que previamente teníamos en teoría.

7

Referencias

1. J. Paciello, H. Martínez, C. Lezcano and B. Barán. Algoritmos de Optimización multiobjetivos basados en colonias de hormigas. Proceedings of CLEI’2006. Latin-American Conference on Informatics (CLEI). Santiago. 2. Julio C. Ponce, Felipe Padilla, Alejandro Padilla y Miguel A. Meza. ACHPM: algoritmo de optimización con colonia de hormigas para el problema de la mochila 3. [Doerner2002] Doerner, K., Gutjahr, W., Hartl, R., Strauss, C., (2002), Pareto Ant Colony Optimization: A Metaheuristic Approach to Multiobjective Portfolio Selection, Proceedings of the 4th. Metaheuristics International Conference. Porto, 243-248. 4. Metodología para la optimización de múltiples objetivos basada en ag y uso de preferencias. http://www.bdigital.unal.edu.co/2237/

5.

Optimización multiobjetivo http://vimeo.com/40738998

con

algoritmos

evolutivos

-

Parte

01.

6. PISA - A Platform and Programming Language Independent Interface for Search Algorithms. http://www.tik.ee.ethz.ch/sop/pisa/