Búsqueda Local - dagoquevedo/parallelr GitHub Wiki

Introducción

La búsqueda local es un método de optimización heurística que retorna un óptimo local, el cual inicia desde una solución inicial , y durante cada iteración aplica una transformación a la solución concurrente generando un vecindario , el mejor elemento evaluado se denota como , si mejora a , entonces . El método se detiene cuando el número máximo de iteraciones es alcanzado. En esta práctica se implementarán métodos de optimización heurística sencilla para encontrar máximos locales de funciones, tomando los ejemplos propuestos por Womersley [1].

Objetivos

  1. Desarrollar una búsqueda local para maximizar una función bidimensional, e implementar una visualización de cómo procede la búsqueda en una gráfica de proyección plana [2]. La función a maximizar , donde y , es definida como:
  1. Implementar el algoritmo de búsqueda de recocido simulado [4] para maximizar la función y realizar un diseño experimental que examina los efectos en la calidad de la solución respecto al valor inicial de la temperatura y el valor de reducción de la temperatura . En este método estable que, si entonces la probabilidad de selección es , en caso contrario:

Implementación y diseño experimental

  1. La estructura del vecindario que se ha implementado para la búsqueda local de la maximización de , consiste en realizar dos movimientos aleatorios y cuyas combinaciones posibles generan cuatro movimientos para las coordenadas y .

  2. Para el diseño experimental del algoritmo de búsqueda de recocido simulado, se establece ejecutarlo con distintos valores para el máximo de iteraciones, es decir y con una discretización de . Establecemos que . Se realizan 50 replicas para cada combinación de los parámetros definidos. Tomando como referencia la solución que obtiene el máximo valor posible de la función esta dada por la solución , por lo que y la solución estimada por el método, se calcula la desviación relativa (gap %) de la manera siguiente:

Condiciones computacionales

Instancia SO Linux (Ubuntu 16.04) 64-bits, con procesador Intel (R) Core (TM) i7-5600U CPU @ 2.60 GHz y 12 GB de memoria RAM con 2 núcleos y 4 procesadores lógicos. El cluster hizo uso de 3 núcleos. La aplicación se ha codificado en R, haciendo uso del paquete doParallel [3] que incluye la función foreach.

Resultados

La figura 1 muestra la función en tres dimensiones. Se observa cómo los valores extremos de la función son los que logran los máximos valores de la superficie.

La figura 2 refleja una ejecución de la búsqueda local para maximizar la función y expresada de forma plana. Se observa cómo al incrementar , las soluciones obtenidas tienden a concentrarse en los puntos extremos (cercanos al óptimo global) y puntos centrales (óptimos locales), reduciendo el valor del gap.

La figura 3 refleja una ejecución del método de recocido simulado para maximizar la función , expresada de forma plana, igual que la búsqueda local se observa cómo al incrementar , las soluciones obtenidas tienden a concentrarse en los puntos extremos, reduciendo el valor de gap.

La figura 4 muestra el resultado del experimento de los efectos de la variación de los parámetros y sobre la calidad de la solución denotada por gap, la cual esta por el promedio entre replicas para cada combinación posible de parámetros y . Aquí, vemos como tiene un efecto positivo en la disminución del gap, por otro lado al decrementar el valor de , el enfriamiento de se realiza más agresivamente, por lo que a medida que avanzan las iteraciones, aceptar soluciones poco beneficiosas es menos probable, pero sigue existiendo una probabilidad positiva de aceptarlos.

Bibliografía

  1. R. Womersley. Local and Global Optimization: Formulation, Methods and Applications. School of Mathematics & Statistics, University of New South Wales, 2008, [url].
  2. S.E. Schaeffer. Práctica 7: Búsqueda local. R paralelo: simulación & análisis de datos, [url].
  3. R. Calaway, S. Weston, D. Tenenbaum. Foreach Parallel Adaptor for the 'parallel' Package. R Package, [url].
  4. S. Kirkpatrick C. D. Gelatt, M. P. Vecchi. Optimization by Simulated Annealing. Science , 220(4598):671-680, 1983, [doi].