Siguiente: Ejemplos de Aplicación Anterior: Beneficios en la Optimización Arriba: Beneficios en la Optimización

Análisis de Resultados

Los resultados se analizaron en términos de la media de los errores agrupados por tipo de instancias y en forma global, para cada valor utilizado de $maxK$ y $\mathcal{OS}$. El error se calcula como:

$$error = 100* \frac{ValRef - Valor \: Obtenido}{ValRef}$$ (4)

donde $ValRef$ es el óptimo de la instancia para los problemas de la mochila con múltiples restricciones ($MR$); y es la cota de Dantzig (mirar por ej. [24]) para la versión clásica ($ST$).

En la Tabla 1 se muestra la media del error para cada valor de $maxK$ y cada $\mathcal{OS}$, discriminado para las instancias $ST$ y $MR$.

Tabla 1: Medias del Error en función de $maxK$ y $\mathcal{OS}$ para instancias con una restricción ($ST$) y con múltiples restricciones ($MR$).

	Base	Decremento $maxK$			Incremento $maxK$
Instancia	1	2	3	4	2	3	4
MR	9.01	2.19	1.95	1.92	3.98	3.85	3.90
ST	6.86	4.58	3.87	3.58	4.73	4.28	4.11
Total	7.94	3.39	2.91	2.75	4.36	4.06	4.01

Se puede observar que tanto en forma global, como para cada tipo de instancia en particular, las versiones del algoritmo que usan $maxK > 1$ obtienen mejores resultados que los obtenidos con $maxK=1$. Esto ocurre para los dos esquemas de adaptación de $maxK$ propuestos. También se verifica que para ambos $\mathcal{OS}$'s, un incremento en el valor de $maxK$ permite reducir el error global (indicado en la columna $Total$). Para el caso de decremento, resulta beneficioso comenzar las mejoras con un operador que cambie 4 bits. Cuando con 4 ya no se obtengan mejoras, se reduce a 3, luego a 2 y finalmente se realiza un ``ajuste fino'' con $k=1$. La adaptación de $k$ en sentido contrario también resulta beneficiosa, aunque para las instancias $MR$ solo aparecen mejoras respecto a $k=1$ y no entre los valores obtenidos cuando se utiliza $maxK > 1$.

Es interesante analizar cuanto contribuye cada operador a la obtención del resultado final. En la Figura 4 se muestran la cantidad de transiciones a soluciones aceptables (en promedio) que permitió obtener cada operador para cada valor de $maxK$. Los valores obtenidos se escalaron en el rango $[1,100]$ para mejorar la interpretabilidad. Naturalmente cuando $maxK=1$, todas las mejoras se obtuvieron con $k=1$. Es a partir de $maxK=2$ donde el análisis se vuelve interesante.

En los resultados correspondientes al $\mathcal{OS}$ que decrementa $k$, se observa que cuando $maxK=2$, prácticamente un $95\%$ de la mejora se obtuvo con $2$-BitFlip y el restante porcentaje con $k=1$. Cuando $maxK=3$, el $80\%$ del progreso se debe al uso de $3$-BitFlip. Del restante $20\%$, casi toda la mejora se realiza con $2$-BitFlip. Finalmente cuando $maxK=4$, el operador $4$-BitFlip es el responsable del $70\%$ de los pasos de mejora. La utilización de $3$ y $2$-BitFlip completa prácticamente la optimización aunque aparecen aproximadamente un $5\%$ de mejoras correspondientes a $1$-BitFlip.

Para el caso de incrementos en $k$, se observa que para un valor de $maxK=2$, hasta un $20\%$ de mejora se puede conseguir con $2$-BitFlip una vez que la búsqueda se estancó con $1$-BitFlip. Para $maxK=3$ y $4$, los gráficos muestran que hasta un $75\%$ de la mejora corresponde a $1$-BitFlip, pero luego los operadores subsiguientes pueden mejorar los óptimos locales encontrados.

Figura 4: Contribución promedio de cada operador BitFlip para cada valor de $maxK$. En (a) resultados con administrador de operación decremento y en (b) con incremento.

(a)

(b)

También se analizó la media de la cantidad de evaluaciones realizadas para encontrar el mejor valor, discriminada en función de $maxK$ y por tipo de instancia (resultados no mostrados).

Cuando se utiliza un esquema de decremento, para las instancias con múltiples restricciones se observa una reducción de los valores a medida que aumenta $maxK$. Para las instancias del problema clásico, esta tendencia no se verifica. En este caso, el valor más alto de evaluaciones se alcanza con $maxK=2$. Luego aparecen los asociados a $maxK=\{1,4\}$ mientras que el menor valor corresponde a $maxK=3$.

Para el esquema de adaptación con incrementos de $k$, los resultados para $MR$ indican que un aumento de $maxK$ permite, no sólo obtener mejores resultados, sino también de forma más rápida. Para las instancias $ST$, el valor de $e2b$ (media de la cantidad de evaluaciones realizadas para obtener la mejor solución) para $maxK=1$ es el menor de todos, seguido por $maxK=3$ y $4$.

Naturalmente, esta medida del ``esfuerzo'' no se puede analizar en forma aislada sino teniendo en mente los resultados obtenidos en términos del error. Por lo tanto, creemos que las diferencias en la media del error pueden compensar un posible aumento en las evaluaciones necesarias.