problema de la mochila

´ rez Auto
´ noma de Tabasco
Universidad Jua
Protocolo de Tesis

ESTUDIO COMPARATIVO DE TRES
IMPLEMENTACIONES DEL PROBLEMA DE LA
MOCHILA

Otoniel Hernandez Gomez1
Dr. Abdiel E. C´
aceres Gonz´
alez (Asesor)2
Universidad Ju´
arez Aut´
onoma de Tabasco, DACB
Carr. Cunduac´
an-Jalpa Km 1, Cunduac´
an Tabasco, M´exico
A.P. 24 C.P. 86690. Tel.(+52)914 336-0928
1
otoniel771hotmail.com
2
abdielc@acm.org

2

1. Introducci´
on

El problema [?] de la mochila es una abstraccion de muchas y diferentes situaciones, en las que se debe
tomar decisiones teniendo un objetivo que perseguir. El problema de la mochilase ha aplicado para
resolver problemas en la econom´ıa , transporte , producci´on, almacenamiento, log´ıstica.
El problema de mochila se ha estableci en lad´ecadas de 70’s, mediante una ilustracui´on en la que un
viajero cuenta con una mochila en la que puede guardar cierta cantidad de elementos, los cuales est´
an
disponibles en un repositorio. El excursionista debe decidir qu´e elementos deber´a llevar en su viaje, pues
en su mochila no cabe todos ellos de modo que en la decisi´on debe considerar llevar lo menos posible, lo
que sirva m´
as, y loque sea m´
as u
´til el problema del excursionista es una ilustraci´on de optimizaci´
on ,
que a la fecha ha sido resulto desde muchos enfoques: enfoques cl´asicos con programaci´on din´amica; el
enfoque evolutivo con algoritmos gen´eticos; el enfoque vasado en agentes con colonias de hormigas.
El problema de la mochila multidimensional Multidimensional Knapsack Problem (MKP) es unproblema de optimizacin multiobjetivo, el cual se compone de un nmero arbitrario de mochilas (objetivos) cada una con capacidad (restriccin) y un conjunto de elementos que tienen asociado un peso y un
beneficio.1
Este problema de optimizaci´
on a pesar de que ya est´a resulto mediante diferentes enfoques computacionales es de gran inter´es acad´emico por que las personas interesadas en ver laresoluci´on de este problema
ayudara en gran manera a sus estudios, proyectos y actividades.
Este problema es llenar la mochila de tal manera que se maximice el valor de los objetos transportados, respetando la limitaci´
on de la capacidad impuesta. T´ecnica de programaci´on din´amica, Se emplea
t´ıpicamente para resolver problemas de optimizaci´on y Permite resolver problemas mediante una secuencia dedecisiones.

2. Antecedentes

Cuando en un problema de optimizaci´
on se tienen varias funciones objetivo, la tarea de encontrar una
o m´
as soluciones ´ptimas se denominada optimizaci´on multiobjetivo o toma de decisiones multicriterio.
Bajo este enfoque la atencin no se puede centrar solo en uno de los objetivos dejando a un lado los
otros. Diferentes soluciones pueden producirsoluciones trade off (escenarios en conflicto) entre diferentes
objetivos. Una soluci´
on que es ´
optima con respecto a un objetivo puede no serlo para el resto, por lo
tanto ser´
a impropio escoger dicha soluci´on como ´optima del problema y se crea la necesidad de establecer
un compromiso entre los objetivos.
Los problemas con mltiples objetivos se encuentran presentes en la mayora de lasdisciplinas y su
soluci´
on siempre ha representado un reto para los investigadores. La principal motivaci´
n para el uso de
novedosos algoritmos, como los de la familia de los evolutivos, en la solucin de problemas de este tipo
radica en que al estar Basados en poblaci´on para realizar b´
usqueda de soluciones, ´estos pueden retornar
un conjunto de soluciones de buena calidad, hecho que es dealta importancia en este tipo de enfoques.

3. Justificaci´
on

Dentro de una gran variedad de problemas de planeaci´on de recursos, uno de los que han generado un
mayor n´
umero de estudios. Esto se debe principalmente a que: Es un problema de aplicac´on pr´actica y que
1 Zitzler, E., Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Ph.D. thesis, Swiss...