Siguiente: Minimización de Funciones Anterior: Implementación de FANS Arriba: Mochila con Restricciones Múltiples

Experimentos y Resultados

En esta aplicación se compararon los siguientes 5 algoritmos: FANS con el administrador $R\vert S\vert T$ ($F_{rst}$); FANS con el administrador $First$ ($F_{ff}$); un AG con cruce uniforme (GAux); un AG con cruce de un punto (GAop); y una implementación de recocido simulado (SA).

Los algoritmos se compararon bajo la hipótesis de nulo o mínimo conocimiento del problema y cantidad limitada e igual de recursos para todos los métodos.

Los experimentos se realizaron sobre 9 instancias, disponibles en [3], identificadas como pb5, pb7, Weing1, Weing3, Weing7, Weish10, Weish14, Weish18, Weish27. El número de items varía entre 20 y 105 conteniendo entre 2 y 30 restricciones.

Para cada instancia se ejecutó 30 veces cada algoritmo. Cada ejecución finalizó cuando se agotaron las $maxEvals = 15000$ evaluaciones de la función de costo disponibles o cuando se generaron $maxEvals * 4$ soluciones. Este límite se estableció porque solamente se evaluaban las soluciones factibles.

Como en el caso anterior, los resultados se analizaron en términos del error respecto al óptimo en cada problema y en forma global sobre todo el conjunto.

La Tabla 3 (a) muestra la media del error sobre las 30 ejecuciones en cada problema. Los resultados indican que ambas versiones de FANS tuvieron errores menores que los demás algoritmos en todos los casos, salvo Weing3, Weing7 y Weish27. SA alcanzó el mejor valor en Weing7 y GAux en los dos restantes.

En la Tabla 3 (b), se indica para cada algoritmo (mediante una $x$) aquellos problemas que resolvió de forma óptima en alguna de las 30 ejecuciones. Se observa que $F_{rst}$, $F_{ff}$ y GAux obtuvieron el óptimo en 6 de 9 casos, mientras que GAop en 5 de 9 y SA solamente alcanzó el óptimo de un solo problema (este problema fue resuelto por todos los algoritmos).

Tabla 3: En (a), media de los errores obtenidos por cada algoritmo sobre cada problema (30 ejecuciones). En (b), una $x$ indica que el algoritmo de la columna obtuvo el óptimo del problema de la fila en algún intento.

	$F_{rst}$	$F_{ff}$	SA	GAop	GAux
pb5	1.04	0.92	6.52	3.37	3.07
pb7	0.94	1.19	4.13	3.83	4.23
weing1	0.20	0.19	8.07	0.92	1.37
weing3	1.54	1.32	22.04	1.85	0.91
weing7	0.50	0.51	0.48	1.13	0.93
weish10	0.27	0.14	1.22	1.34	1.18
weish14	0.85	0.78	1.93	1.85	0.91
weish18	0.73	0.71	1.39	0.95	0.89
weish27	3.02	2.89	2.85	3.21	1.18

	$F_{rst}$	$F_{ff}$	SA	GAop	GAux
pb5	x	x
pb7	x	x
weing1	x	x		x	x
weing3				x	x
weing7
weish10	x	x	x	x	x
weish14	x	x		x	x
weish18	x	x		x	x
weish27					x

(a)

(b)

El análisis de la media y la varianza de los errores sobre el conjunto de los problemas (resultados no mostrados), revelaron que globalmente ambas versiones de FANS alcanzaron los valores de error más bajos, seguidos por GAux. La media del error para GAux y GAop fue casi el doble que la obtenida por $F_{rst}$ y $F_{ff}$, mientras que los valores de SA fueron 5 veces mayores.

Para confirmar si existían diferencias significativas en las medias del error se realizaron los correspondientes tests, los cuales confirmaron que ambas versiones de FANS resultaron mejores que GAux, GAop y SA. Ambos AG superaron a SA, y no se detectó diferencia significativa entre ambos.