Problema de la Mochila Binaria

En este problema se trata de elegir un grupo de objetos de entre un conjunto de $m$ con volúmenes $w_1,\dots,w_m$ y valores $p_1,\dots,p_m$ de manera tal que quepan en una mochila de capacidad $C$ maximizando el valor total de su contenido [#!Michalewicz92!#,#!Michalewicz96!#].

Este problema admite múltiples formulaciones según se dé uno u otro significado a las variables $w_i$ y $p_i$. Matemáticamente, se puede plantear como un problema de programación binaria así:

Encontrar para un vector de valores ${\bf p}:=(p_1,\dots,p_m)$ y otro de volúmenes ${\bf w}:= (w_1,\dots,w_m)$ un vector binario de selección ${\bf x}:=(x_1,\dots,x_m)$ con el que $x_j=1$ indica que se ha seleccionado el j-ésimo objeto, de modo que haga máximo el valor total $f({\bf x})={\bf p^\prime \cdot x}$ sujeto a la condición de capacidad limitada ${\bf w^\prime \cdot x} \leq C$, es decir:

$$\left\{ \begin{array}{rrcl} {\rm maximizar} & f({\bf x}) & =... ...\in & \{0,1\} \quad (\forall i = 1,\dots,m) \end{array}\right.$$

Se define por comodidad el vector de valores específicos $\mbox{\boldmath$\rho$} = (\rho_1,\dots,\rho_m)$ a través de $\rho_i := p_i/w_i\quad (\forall i=1,\dots,m)$.

La representación de este problema para resolverlo mediante un AG es elemental: los individuos ${\bf v}$ del espacio de búsqueda coinciden con los puntos ${\bf x}$ del dominio del problema. La j-ésima posición del genotipo señala la presencia o ausencia de j-ésimo objeto en la mochila. Esta representación es la más sencilla y también la más natural dado que los genes tienen un significado claro e inmediato. Además, si se ignora la restricción de capacidad (espacio de búsqueda irrestricto) existe una correspondencia biunívoca entre los individuos y los puntos del dominio, por lo que la representación es perfecta.

Para resolver este otro problema se ha modificado el programa desarrollado en la sección . Simplemente ha habido que cambiar la función de evaluación de forma que implemente la ecuación , como una clase descendiente de eoEvalFunc.

En las tablas y podemos ver los resultados obtenidos al resolver este problema utilizando las versiones secuencial y paralelas (con las diferentes estrategias de migración) del programa desarrollado.

Tabla: Resultados (media y desviación estándard) para el problema de la mochila utilizando la versión secuencial del programa desarrollado.

p=100 / g=100	Tiempo
544.9	0.33 $\pm$ 0.03
p=400 / g=100	Tiempo
568.2	1.06 $\pm$ 0.04
p=800 / g=100	Tiempo
580.3	2.30 $\pm$ 0.08
p=1600 / g=100	Tiempo
578.4	5.90 $\pm$ 0.05

Tabla: Resultados (media y desviación estándard) para el problema de la mochila utilizando la versión paralela (con diferentes estrategias de migración) del programa desarrollado.

Migración	4 proc.	Tiempo	8 proc.	Tiempo	16 proc.	Tiempo
Simple	566.1 $\pm$ 7.5	0.50 $\pm$ 0.03	565.1 $\pm$ 5.5	0.61 $\pm$ 0.04	565.4 $\pm$ 0.8	0.89 $\pm$ 0.08
Estrella	592.9 $\pm$ 2.3	0.88 $\pm$ 0.09	599.5 $\pm$ 2.1	0.98 $\pm$ 0.05	599.6 $\pm$ 3.6	1.49 $\pm$ 0.04
Broadcast	605.2 $\pm$ 0.6	0.90 $\pm$ 0.09	604.9 $\pm$ 5.5	1.02 $\pm$ 0.09	600.9 $\pm$ 6.2	1.7 $\pm$ 0.1
Anillo	581.5 $\pm$ 6.9	0.82 $\pm$ 0.02	590.4 $\pm$ 1.7	0.98 $\pm$ 0.05	589.6 $\pm$ 4.1	1.32 $\pm$ 0.06