Siguiente: Mochila con Restricciones Múltiples Anterior: Implementación de FANS Arriba: Mochila Clásica

Experimentos y Resultados

La calidad de FANS se comparó de forma empírica frente a dos implementaciones de algoritmos genéticos (AG) y a una de recocido simulado (SA).

Los AG's diferían en el operador de cruce: para uno se utilizó cruce de un punto (GAop) y para el otro, cruce uniforme (GAux). Como operador de mutación se utilizó el operador de modificación de FANS, donde el valor del parámetro $k$ se elige aleatoriamente.

Los algoritmos se compararon sobre 45 problemas aleatorios, con $n=100$. Se consideraron tres tipos de correlación entre el peso y el beneficio de los items, dando lugar a tres grupos de instancias: no correlacionadas (NC), con correlación débil (DC), y con correlación fuerte (FC). Cada grupo contiene 15 instancias.

Todos los algoritmos utilizaban operadores simples y cantidad limitada e igual de ``recursos'' para todos los algoritmos. Por recursos deben entenderse evaluaciones de la función de costo y cantidad máxima de soluciones a generar.

Los resultados se midieron en términos del error respecto a la cota de Dantzig y se muestran en la Tabla 2. Cada valor representa la media y la varianza de los errores sobre las 30 ejecuciones realizadas por cada uno de los 15 problemas en cada clase.

Tabla 2: Media y varianza de los errores por tipo de instancia calculados sobre 30 ejecuciones por cada uno de los 15 problemas de prueba.

		NC			DC			FC
Algoritmo		Media	Var.		Media	Var.		Media	Var.
FANS		1.08	0.55		1.75	1.08		0.84	1.06
SA		1.61	3.17		1.80	1.37		1.32	1.25
GAop		2.06	0.80		2.74	1.18		1.32	1.26
GAux		1.32	0.77		2.63	1.25		1.37	1.25

Los resultados de la Tabla 2, junto a resultados de t-test, mostraron que los errores obtenidos por FANS fueron significativamente menores que los de ambos AG en los tres tipos de instancias. También fueron mejores que los de SA para las instancias NC y FC, y similares para las DC.

Ambos AG obtuvieron resultados similares sobre las instancias DC y FC, pero GAux fue mejor en el caso NC. Los errores obtenidos por SA resultaron menores que los de ambos AG's para las instancias NC y DC, aunque para las instancias FC, los tres algoritmos resultaron equivalentes.

El análisis de los resultados sobre el conjunto de 45 instancias de prueba, permitió verificar que FANS alcanzaba errores medios significativamente menores que SA, GAop y GAux. Los siguientes algoritmos en el ``ranking'' fueron SA, que superó a ambos AG, seguido por GAux que superó a GAop, principalmente por los resultados en las instancias NC.

Ademá, se pudo constatar que tanto FANS, SA y GAop, alcanzaron los errores medios más bajos en las instancias FC, contradiciendo la hipótesis que relaciona mayor correlación entre peso y beneficio, con mayor dificultad.