Siguiente: Análisis de Resultados Anterior: Beneficios en Escape de Arriba: Sobre el Uso de

Beneficios en la Optimización

En esta sección se describen los experimentos realizados para mostrar que un algoritmo que utiliza varios operadores en el proceso de búsqueda, permite obtener mejores resultados que otro que utiliza un único operador ⁴.

Para los experimentos se utilizó FANS como una búsqueda local simple con multi-arranque. Las pruebas se realizaron sobre 10 instancias del problema de la mochila: 5 instancias aleatorias de la versión con una única restricción (instancias $ST$) y 5 instancias de la versión con múltiples restricciones (instancias $MR$).

Se utilizó un administrador de vecindario $First$, el cual retorna la primera solución que mejore el costo de la actual, utilizando un máximo de intentos fijado en $maxTrials = n$, donde $n$ es el tamaño de la instancia. La solución inicial se genera aleatoriamente con un único valor en 1.

Como operador de modificación se utilizó el $k$-BitFlip, el cual complementa el valor de $k$ bits seleccionados al azar. Se implementaron dos administradores de operación $\mathcal{OS}$. El primero, denominado Decremento, hace $k_{t} = k_{t-1}-1$ cada vez que el Administrador de Vecindario no pueda obtener una solución mejor que la actual utilizando un operador que modificaba $k_{t-1}$ bits. Es decir, suponiendo $maxK=3$, entonces el algoritmo comienza a progresar con $3$-BitFlip. Cuando se estanca, sigue con $2$-BitFlip y luego con $1$-BitFlip. El segundo administrador, denominado Incremento, aumenta el valor de $k$: $k_{t} = k_{t-1}+1$. En este caso, siempre se comienza con $1$-BitFlip, se sigue con $2$-BitFlip y así hasta $maxK$-BitFlip. Cuando el administrador de vecindario no pueda obtener una solución mejor con $k=1$ o $k=maxK$, según se hagan decrementos o incrementos respectivamente, se ejecuta el procedimiento $Escape$, el cual genera una nueva solucion aleatoria. Posteriormente, el algoritmo se reinicia desde esta nueva solución.

El objetivo del experimento es mostrar que utilizar un valor de $maxK > 1$ resulta mejor que utilizar $maxK=1$. La base de comparación son los resultados obtenidos con $k=1$.

Por cada instancia, valor de $maxK=\{1,2,3,4\}$, y administrador de operación $\mathcal{OS}$ $= \{incremento, decremento\}$, se realizaron 30 ejecuciones del algoritmo, finalizando cada una cuando se agotaron las 15000 evaluaciones disponibles de la función de costo o se generaron 45000 soluciones. A continuación se presentan los resultados obtenidos.