• Author / Uploaded
• Alonso Tenorio

Citation preview

Problema de la mochila 0/1: Programaci´on Paralela Leticia Leonor Pinto Alva 3 de marzo de 2014 Resumen

El prop´ osito de este art´ıculo es resolver el problema de la mochila para objetos no divisibles usando programaci´ on din´ amica con un enfoque secuencial y paralelo. Si consideramos el caso en que teniendo un presupuesto fijo [1], debemos tomar una decisi´on frente a varias opciones, cada una con un costo y un valor, teniendo como objetivo seleccionar un subconjunto de estos a fin de maximizar el valor total. Este es en pocas palabras el problema de la mochila, que se presenta en diferentes situaciones como la contrataci´ on de trabajadores, la programaci´on de tareas y al hacer una oferta en subastas en b´ usqueda de patrocinados. Palabras Clave: Knapsack(Mochila), OPENMP, Threads(Hilos). La idea conceptual que se nos muestra es simple mas no su soluci´on, fue referenciado en 1897 en un art´ıculo de George Ballard Mathews[3]. Conectividad en Grafos y el problema de la mochila son problemas cl´asicos en los que se puede implementar mediante un ordenador ADN [7]. Estos problemas se pueden resolver por los ordenadores convencionales en tiempo polinomial(seudo-polin´omica para la mochila), pero s´olo en la medida en que son los suficientemente peque˜ nos en la memoria. Computadoras de tipo ADN utilizando programaci´on din´amica podr´ıan resolver problemas de dimensiones sustancialmente mayor debido a su gran capacidad de memoria en comparaci´on a ordenadores convencionales.

Figura 1: Knapsack Problem

La realizaci´on de este art´ıculo surgi´o por una idea simple que se presenta en nuestra casa, los programas de televisi´on, todo programa de televiEl problema de la mochila es uno de los 21 si´on antes de salir al aire necesita auspiciadores. problemas NP-completos de Richard Karp, esta- Para elegir a los auspiciadores se necesita de un blecidos por el inform´ atico te´ orico en un famoso estudio previo, es decir fijar un rango de preferenart´ıculo de 1972[2]. cias, adem´as de la ganancia posible obtenida con

1.

Introducci´ on

1

una cantidad de tiempo en que se presentar´a su publicidad. En base a eso se tomar´ a la decisi´on m´ as ´ optima y que genere asi el mayor beneficio posible tanto al programa como a la televisora.

enfoque de programaci´on lineal entera binaria,la cual tiene variables de decisi´on al conjunto soluci´on x1 , x2 , ..., xn donde xi ∈ Z y xi ∈ 0, 1 , con restricci´on del W(peso max).

En t´erminos generales, el problema de la mochila[10] aparece en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, tales como la b´ usqueda de la forma menos dorrochadora para cortar materia prima, concurso de asientos de inversiones y carteras, asientos en concurso de activos para activos de titulizaci´ on respaldados y la generaci´ on de claves para la Merkle-Hellman Knapsack cryptosystem. Por esto el estudio y desarrollo del problema de la mochila con el algoritmo de programaci´on din´ amica y aun mejor paralelizado resulta u ´til.

Problema de la Mochila Existen n elementos que poseen dos carater´ısticas: valor vi y peso wi , los cuales ser´an introducidos en un contenedor de tal manera que se maximice el valor acumulado (v1 , v2 , ..., vn ) de los objetos y no sobrepase la capacidad m´axima del contenedor W. Los objetos ser´an los xi que tendr´an un vi y un wi , estos xi pueden tomar el valor de 1 si se introduce o 0 si no se introduce en el contenedor. Matem´aticamente[9]:

Justificaci´ on Matem´ atica Se busca la funci´on objetivo: El problema de la mochila es un problema de optimizaci´ on matem´ atica[4] que trata de hallar una soluci´ on x∗ de un conjunto S que cumple las siguientes condiciones:

max

n X

x ∈ S = {x1 , x2 , ...., xn } , x0 = x∗

de tal manera que:

Si ∀x ∈ S, f (x0 ) ≥ f (x)

∀i = 1, 2, ...n, xi ∈ 0,1y

n X

wi xi ≤ W

i=1

Programaci´ on lineal

2.

Si un modelo de optimizaci´ on[11] usa programaci´ on lineal, entonces las funciones que lo componen(funci´ on objetivo y restricciones) son lineales.

2.1.

n X

Algoritmos Fuerza bruta

Se tiene el vector soluci´on (x1 , x2 , ..., xn ) donde xi ∈ 0, 1, luego se busca todas las combinaciones de este vector con el fin que satisfaga la funci´on objetivo y cumpla las restricciones.

Funci´ on objetivo: max

vi x i

i=i

ci xi

i=1

Si se considera a (x01 , x02 , ..., x0n ) la soluci´on del problema, entonces haberla encontrado tomar´ıa 2 x 2 x....x 2 x 2 as´ı sucesivamente n veces casos para hallarla.

donde, ci : coeficientes y xi : variable de decisi´on. Restricciones: n X

aij xi ≤ Rj Veamos un algoritmo:

i=1

donde, aij : coeficientes y Rj : restricciones. Para la definici´ on del problema se usar´a el 2

Inicio del programa: El algoritmo general de un algoritmo gen´etico es el siguiente:

mochila(w,v,W,n): w:vector de pesos v:vector de valores W:Peso total n:cantidad de items

1. Inicalizaci´on de la poblaci´on 2. Evaluaci´on de la poblaci´on 3. Mientras(no se llegue a la condici´on de fin)

i f ( n==0 o r W==0) // Caso b a s e en e l que no hay o b j e t o s / / ( n=0) o e l p e s o e s 0 return 0;

4. Selecci´on de padres:

i f (w [ n−1]>W) // S i wk > W // e n t o n c e s e l o b j e t o no s e e s c o g e r e t u r n m o c h i l a (W, w, v , n −1);

7. Evaluaci´on

5. Recombinaci´on 6. Mutaci´on

8. Selecci´on de supervivientes

// S i e l o b j e t o k e s e s c o g i d o e n t o n c e s // su p e s o e s r e s t a d o d e l t o t a l y // su v a l o r v [ k ] e s c o n s i d e r a d o // p a r t e de l a s o l u c . else : r e t u r n max( v [ n−1]+ m o c h i l a (W − w [ n −1] , w, v , n −1) , m o c h i l a (W, w, v , n − 1 ) ) ; Fin del programa Desarrollando el ´ arbol de recursi´ on se observa Figura 2: Combinaci´on y mutaci´on de cromosomas que la soluci´ on crece de manera exponencial, por En la figura 2 se muestra el proceso de combinalo tanto su complejidad ser´ıa: ci´on y mutaci´on, los dos primeros cromosomas se O(2n ) combinan, es decir comparten genes a sus descendientes, y forman los cromosomas (1,1,1,1,0,0,1) y (0,0,0,0,1,1,1). 2.2. Algoritmo Gen´ etico Luego existe una peque˜ na probabilidad que el cromosoma mute como se da en el caso del quinto cromosoma(1,0,0,1,0,1,1) que muta al cromosoma (1,1,0,1,0,0,1).

Generamos una poblaci´ on de individuos[6] cuyos cromosomas(conjunto de genes) simbolizan una soluci´ on del problema. La representaci´on del individuo es binaria de la forma(0,1,1,1,0,0,1) donde el n´ umero de bits en el cromosoma de cada individuo es el n´ umero de objetos disponible. En este caso existir´ an 7 objetos disponibles, donde si un gen toma el valor de 1 significa que ingres´o al contenedor y 0 si no lo hizo.

El algoritmo se ejecuta por generaciones hasta lograr obtener un individuo que cumpla con las caracter´ısticas ´optimas, luego este individuo ser´a la soluci´on para el problema.

3

Este m´etodo es r´ apido y no ocupa mucha memoria, por contra parte obtiene una soluci´on aproximada, en muchos casos es exacta, pero en otros casos podria no serlo generando un grado de incertidumbre que ser´ a adecuado dependendiendo de lo que busquemos.

2.3.

superpuestos y subestructura ´optima y por lo tanto es un buen candidato para la programaci´on din´amica. Algoritmo: Primero, ingresamos el n´ umero total de items, pesos, y valores de cada item. Luego ingresamos el m´aximo peso(maxWeight). Finalmente calculamos el m´aximo valor que puede ser obtenido usando la funcion Knapsack.

Programaci´ on din´ amica

B´ asicamente la eficiencia de este m´etodo es Funci´on Knapsack: resolver los subproblemas una sola vez, luego umero total de items, guardar cada soluci´ on en una tabla para su futuro Esta funci´on toma el n´ el peso de cada item(weight), el valor de cada uso[8]. item(value) y el peso m´aximo(maxWeight) como Aplicado a la resoluci´ on de problemas de op- argumentos. Que retornar´a el m´aximo valor que timizaci´ on se basa en el principio de optimalidad: pueda ser obtenido de estos items, considerando tambi´en el conjunto de items seleccionados. ”En una secuencia de decisi´ on ´ optima toda subsecuencia ha de ser tambi´en o ´ptima”

Declaramos vmax[items+1][maxWeight+1]. Donde vmax[i][w] representa el m´aximo valor que puede ser obtenido si el peso m´aximo resultara w y los items elegidos : 1,..,i. vmax[0][w] = 0 para todo w porque hasta el momento hemos elegido 0 items. vmax[i][0]=0 para todo w porque el m´aximo peso que podemos obtener es 0.

Dadas 2 tuplas: v1 , v2 , v3 , ..., vn y w1 , w2 , w3 , .., wn , y W>0. Queremos determinar un subconjunto T tal que: Maximice T, sujeto a T =0, supongamos que tomamos este item, entonces vmax[i][w] = rado en la soluci´ on o de (0) si no. max(vmax[i][w],vmax[i-1][w-weight[i]+ value[i]]). Sea A(i,j) quien representa el m´ aximo valor Donde, max es la funcion que retorna el m´aximo que puede ser obtenido si el peso m´ aximo es W de los 2 argumentos que toma. y los items son elegidos de 1,...,i. Optamos por la Luego para hallar el conjunto de elementos siguiente definici´ on recursiva: que toma recorremos la matriz que nos queda empezando de atr´as hacia adelante. Considerando que se evaluar´an solo si son mayores a cero y si vmax[iter][w] != vmax[iter-1][w] cubriendo el vector x que guardar´a las soluciones con 1 si es que no es el m´aximo y vamos restandole los pesos Este problema se presenta tanto en subproblemas guardados en el vector weight: 4

Siendo su complejidad O(n*W) donde n es el n´ umero de objetos y W el peso m´aximo.

i t e r=i t e m s ; w=maxWeight ; w h i l e ( i t e r >0 && w>0) { i f ( vmax [ i t e r ] [ w] ! = vmax [ i t e r − 1 ] [w ] ) { x [ i t e r ]=1; w=w−w e i g h t [ i t e r ] ; } i t e r −−; }

//Retorna el valor maximo int max(int a,int b) //Funcion knapsack //encargada de hallar valor max //y conjuntos de items int Knapsack(int items,int weight[], int value[],int maxWeight) { //Declaracion de las variables //Llenado de la fila 0 y columna 0 for(iter=1;iter0) { if(vmax[iter][w]!=vmax[iter-1][w]) { //Llena de 1s si esta dentro

Finalmente la impresi´ on de los item seleccionados se dar´ a imprimiendo las posiciones que hayan sido llenadas con 1s.

5

i/w 0 1 2 3

//del conj que nos da el valor max x[iter]=1; w=w-weight[iter]; } iter--; } printf("conj d items..");

0 0 0 0 0

1 0 2 2 2

2 0 2 4 4

3 0 2 6 8

vmax[iter][maxWeight]=8 = valor m´aximo.

//consideramos el conj d items //coincidiendo las posiciones //con los items for(iter=1;iter