History

Reusable Local Search in Optsicom Framework

Se está considerando la creación de una librería para las búsquedas locales. No queda claro si será posible implementar tal librería de forma que sea realmente usable para la implementación de algoritmos. Para que la librería sea usable debe cumplir los siguientes requisitos:

Facilidad de Uso

Tiene que ser más sencilla de usar que la implementación ad hoc de la búsqueda tabú. O al menos, debe ser comparable en cuanto a dificultad. Parece una contradicción querer usar una librería que es tan compleja de usar como la propia implementación ad-hoc, pero esto tiene varias ventajas:
  • La librería podría ofrecerse en un modo “debug” que registrara aspectos importantes del tabú.
  • La librería podría ser altamente configurable sin cambiar el algoritmo que hace uso de ella.
  • La librería podría ser la base para la implementación de otros métodos de búsqueda local como VNS, SA, BI_LS, FI_LS

La implementación de la búsqueda tabú como una librería presenta un reto importante por los cambios estructurales que habría que realizar en el código comparado con una versión ad-hoc. El problema principal radica en la forma en la que se generan los movimientos. En una implementación ad-hoc, es habitual usar uno (o varios) bucles anidados para generar los movimientos. Dentro de cada uno de esos bucles se evalúa el incremento de la función objetivo de ese movimiento y dependiendo del algoritmo concreto se puede aplicar ese moviemiento de forma inmediata o bien evaluar todos los movimientos. Para una librería es complicado gestionar ese tipo de aspectos. Es decir, es complicado reiniciar el bucle general que hace llamadas a la librería. Existe otra aproximación que consiste en convertir el bucle de generación de moviemientos en una máquina de estados, pero eso se considera un problema en vez de una solución.

Para solucionar en parte estos problemas, se podrían usar corutinas (corutines). Las corutines permiten coordinar dos códigos con flujos de ejecución diferentes pero sin la sobrecarga de los Threads. coroutines, Hay un proyecto que lo resuelven de forma bastante elegante mediante instrumentación de código. Neal Gafter también ha hablado sobre este tema incluso proponiendo una solución basada en diferentes Threads que se ceden el control. Aquí hay un buen artículo que resume un poco todas las implementaciones existentes. Después de revisar un poco todas las alternativas, parece que usar la instrumentación de código es un solución viable para nosotros en este contexto. No obstante, quizás tenga la sobrecarga del boxing (más en la siguiente sección), pero al menos nos ofrecería un sistema para hacer experimentación muy completo y sobre todo sencillo de utilizar. Quizás incluso podríamos pensar en generación de código para la versión final del algoritmo :) Aunque si lo pensamos detenidamente, quizás no sea necesario usar corutinas.

Rendimiento

El rendimiento de la librería tiene que ser comparable con la implementación ad-hoc. Este aspecto puede ser complicado de llevar a cabo por dos cuestiones: el boxing y el mapping.
  • Boxing: Es habitual que varios aspectos de los problemas de optimización se pueda representar con valores de tipo entero. Este hace que la implementación ad-hoc sea muy eficiente. No obstante, una generalización debería llevarse a cabo con el uso de objetos. Por tanto, la conversión de enteros a objetos podría suponer una pérdida de rendimiento considerable. Existen técnicas para deducir esta sobrecarga, pero hay que medir cuidadosamente el impacto real de estas conversiones.
  • Mapping: En el desarrollo de métodos metaheurísticos es bastante habitual asociar información a elementos de la solución o de la instancia. Cuando estos elementos vienen representados por enteros, es muy práctico usar simplemente un array, de forma que el valor asociado al elemento se puede recuperar simplemente con un desplazamiento de memoria. La versión generalizada es utilizar una estructura de datos de tipo Map con la consiguiente pérdida de eficiencia.

Para evitar estos problemas, se pueden realizar varias implementaciones de la librería. Una de ellas genérica, basada en objetos y otras específicas basadas en enteros, booleanos, pares de enteros o similar. Una revisión de trabajos anteriores representativos en los que se haya usado tabú nos permitirá determinar los esquemas más utilizados. No obstante, siempre se puede comenzar con el esquema general y adaptar a esquemas específicos cuando sea necesario.

Partes de un método de búsqueda local

Los aspectos que definen un método de búsqueda son los siguientes:
  • Movimientos: Es esencial definir los movimientos que permiten guiar al método de búsqueda por el vecindario de una solución dada. Dependiendo de la estructura de la solución definida por el problema, estos movimientos pueden ser de diferentes tipos. Algunos de los más comunes son los siguientes:
    • Movimientos de intercambio: En problemas cuyas soluciones se puedan definir como elementos que pertenecen a un conjunto, los elementos se pueden intercambiar de grupo. También se pueden aplicar a problemas cuyas soluciones se representan como permutaciones.
    • Movimientos de mutación: Cuando la solución se puede representar como un array de booleanos, un movimiento puede ser cambiar uno de los elementos del array de 0 a 1.
    • Movimientos de inserción: En problemas cuyas soluciones se representan como permutaciones, un elemento puede "quitarse" de su posición e insertarse en cualquier otra.
  • Tipos de búsqueda local: Una vez definidos los movimientos es importante definir cuántos se evalúan antes de aplicar un movimiento a la solución y continuar con el siguiente movimiento.
    • Estrategia Best Improvement: Se evalúan todos los movimientos posibles para una determinada estructura de vecindad. Finalmente se aplica aquél que mejore en mayor medida el valor de la solución. El método finaliza cuando no se encuentra ningún movimiento que mejore la solución.
    • Estrategia First Improvement: Se evalúan los movimientos y se aplica el primero que se encuentre que mejore el valor de la solución. En este caso, es muy importante determinar el orden en el que se evalúan los movimientos. Algunas veces este orden es lexicográfico, pero no se recomienda porque centra el proceso de búsqueda en ciertas regiones del espacio de soluciones. Otras veces es simplemente aleatorio. En otras ocasiones, existe algún tipo de criterio (voráz o ligeramente aleatorizado) que guía la evaluación de movimientos. En estos últimos casos, la idea es explorar primero aquellas regiones en las que sea más probable encontrar soluciones mejores. El método finaliza cuando no se encuentra ningún movimiento que mejore la solución.
    • Estrategias híbridas First/Best: En algunos casos, se evalúan estrategias que combinan las dos anteriores. Por ejemplo, en problemas con soluciones representadas como permutaciones un movimiento puede ser el intercambio de un elemento por otro elemento. En las estrategias híbridas, se puede seleccionar un elemento (con criterio o aleatoriamente) e intentar intercambiar ese elemento por todos los demás. Si existe un intercambio que mejore, se aplica. Si no se encuentra, se selecciona otro elemento y se busca un intercambio que mejore. El método finaliza cuando no se encuentra ningún movimiento que mejore la solución.
    • Simulated Annealing: En este método, los movimientos se van evaluando en un determinado orden. Si el movimiento es de mejora, el movimiento se aplica. Si el movimiento no es de mejora, se aplica con una probabilidad que va decreciendo con el tiempo. El método finaliza cuando la probabilidad de aplicar un movimiento que no mejora es 0 y no se encuentra ningún movimiento de mejora.
    • VNS: Es una metaheurística que considera varios tipos de movimientos (o estructuras de vecindad). Con la primera estructura aplica una estrategia de búsqueda como las presentadas previamente. Cuando no se encuentra un procedimiento de mejora, en vez de finalizar la búsqueda local, se elige otra estructura de vecindad (otra forma de generar los movimientos) y se evalúan los movimientos de esa otra estructura. Así hasta que se han evaluado todas las estructuras de vecindad y en ninguna de ellas se encuentra un movimiento de mejora.
    • Búsqueda Tabú: Se aplica cualquiera de las estrategias "sencillas" vistas anteriormente. Cuando no se encuentra ningún movimiento de mejora, se aplica el movimiento que menos empeore la función objetivo y se comienza de nuevo. El procedimiento finaliza cuando no se consigue mejorar la solución durante un número determinado de iteraciones maxIter (aplicaciones de movimientos). Para evitar que la búsqueda vuelva a visitar una solución visitada previamente, los movimientos se marcan como estado "tabú" durante un número de iteraciones tanuTenure después de haberse aplicado. De esta forma, se evita que se vuelvan a aplicar y por tanto se vuelva al mismo punto del espacio de búsqueda. No obstante, la elección del valor de tabuTenure y maxIter es muy relevante para la efectividad de este método.

Cuestiones generales de la librería

Para hacer una librería de búsqueda tabú, se podría considerar el caso general de hacer una librería para cualquier tipo de búsqueda. No obstante, es muy complejo separar los elementos reutilizables de los elementos que no lo son. Evaluemos las partes de los algoritmos que son generales y cuales son específicas de los problemas:
  • Partes específicas del problema:
    • La definición de la estructura de vecindad (tipos de movimientos) es específica de los problemas. Se podría considerar que problemas que utilicen la misma estructura para representar la solución podrían compartir esa estructura de vecindad, pero de momento vamos a considerar que es totalmente específico del problema.
    • El orden en la que se evalúan los movimientos también es dependiente del problema. El orden lexicográfico o el orden aleatorio o el orden con algún tipo de criterio sólo se pueden llevar a cabo con información del propio problema. Cuando se usa una estrategia BestImprovement, el orden no es relevante, pero en las demás estrategias el orden es muy relevante.
    • La agrupación de movimientos es dependiente del problema. En esquemas híbridos best-first, sólo el problema es consciente de cuales son los límites razonables para aplicar una estrategia best o first.
  • Partes específicas del algoritmo:
    • Las demás :)

Detalles de implementación

Finalmente se ha implementado completamente una librería de búsquedas locales. Se ha intentado llevar a cabo de la forma más eficiente. Para ello se ha eliminado completamente el boxing y el mapping (para el caso de la búsqueda tabú) no se he implementado de forma genérica si no que se delega en un TabuAdapter implementado de forma específica para el problema o la estrategia elegida.

Después de la implementación se han realizado diversas pruebas de rendimiento y se ha llegado a una implementación genérica que consume cerca del 2% más que la versión ad-hoc. Es decir, es aproximadamente un 2% más lenta y también de forma aproximada es capaz de hacer un 2% de mejoras en un tiempo prefijado. Consideramos que esta merma del rendimiento es totalmente asumible y por tanto, la implementación de la librería de búsquedas locales ha sido un éxito.

A continuación se muestra una tabla comparativa con un tiempo límite de 2 segundos:

       Dev      #Best    Score    Time    #Const
LCW_Lib    0,30%    4    84    2,00    349,53
LCW_Adhoc  0,30%    4    82    2,00    356,53
TS3_Lib    0,03%    36    10    2,00    84,98
TS3_Adhoc  0,00%    43    3    2,00    87,24

En el caso del método tabú, se realizan un 2.7% menos de construcciones en la versión con la librería. En el caso del método mixto LCW, se realizan un 2% menos de construcciones con la librería. Como vemos, en número de mejores de TS3_Adhoc supera a TS3_Lib. Esto se debe a que se encuentran muchos mejores en las últimas construcciones. No obstante, este tipo de efecto "frontera" no aparece cuando el tiempo de ejecución es mayor y ya se ha llegado a la fase estable del algoritmo.

Llevando a cabo la implementación de la librería se ha obtenido un resultado curioso. La consulta del tiempo con System.currentTimeInMillis() es muy costosa. Tanto que si se evalúa el tiempo cada vez que se evalúa un movimiento en el problema del MDGP el tiempo de ejecución puede llegar a ser el doble. Sin duda un resultado a tener muy en cuenta en próximas implementaciones.