Búsqueda local iterada desde cero en Python

Búsqueda local iterada es un algoritmo de optimización global estocástico.

Implica la aplicación repetida de un algoritmo de búsqueda local a versiones modificadas de una buena solución encontrada anteriormente. De esta manera, es como una versión inteligente del algoritmo de escalada estocástica con reinicios aleatorios.

La intuición detrás del algoritmo es que los reinicios aleatorios pueden ayudar a localizar muchos óptimos locales en un problema y que los mejores óptimos locales suelen estar cerca de otros óptimos locales. Por lo tanto, las perturbaciones modestas de los óptimos locales existentes pueden encontrar mejores o incluso mejores soluciones para un problema de optimización.

En este tutorial, descubrirá cómo implementar el algoritmo de búsqueda local iterado desde cero.


Recomendado: ¿Qué es el Big data?.


Después de completar este tutorial, sabrá:

  • La búsqueda local iterada es un algoritmo de optimización de búsqueda global estocástica que es una versión más inteligente de la escalada estocástica con reinicios aleatorios.
  • Cómo implementar la escalada estocástica con reinicios aleatorios desde cero.
  • Cómo implementar y aplicar el algoritmo de búsqueda local iterado a una función objetivo no lineal.

Empecemos.

Búsqueda local iterada desde cero en Python

Búsqueda local iterada desde cero en Python
Foto de Susanne Nilsson, algunos derechos reservados.

Descripción general del tutorial

Este tutorial se divide en cinco partes; Ellos son:

  1. ¿Qué es la búsqueda local iterada?
  2. Función objetivo de Ackley
  3. Algoritmo de escalada estocástico
  4. Escalada estocástica con reinicios aleatorios
  5. Algoritmo de búsqueda local iterado

¿Qué es la búsqueda local iterada?

La búsqueda local iterada, o ILS para abreviar, es un algoritmo estocástico de optimización de búsqueda global.

Está relacionado o es una extensión de la escalada estocástica y la escalada estocástica con inicios aleatorios.

Es esencialmente una versión más inteligente de Hill-Climbing con reinicios aleatorios.

– Página 26, Fundamentos de metaheurística, 2011.

La escalada estocástica es un algoritmo de búsqueda local que implica realizar modificaciones aleatorias a una solución existente y aceptar la modificación solo si da mejores resultados que la solución de trabajo actual.

Los algoritmos de búsqueda local en general pueden atascarse en los óptimos locales. Un enfoque para abordar este problema es reiniciar la búsqueda desde un nuevo punto de partida seleccionado al azar. El procedimiento de reinicio se puede realizar muchas veces y se puede activar después de un número fijo de evaluaciones de funciones o si no se observan mejoras adicionales para un número determinado de iteraciones del algoritmo. Este algoritmo se llama escalada estocástica con reinicios aleatorios.

La posibilidad más simple de mejorar un costo encontrado por LocalSearch es repetir la búsqueda desde otro punto de partida.

– Página 132, Manual de metaheurística, 3a edición de 2019.

La búsqueda local iterada es similar a la escalada estocástica con reinicios aleatorios, excepto que en lugar de seleccionar un punto de inicio aleatorio para cada reinicio, se selecciona un punto en función de una versión modificada del mejor punto encontrado hasta ahora durante la búsqueda más amplia.

La perturbación de la mejor solución hasta ahora es como un gran salto en el espacio de búsqueda a una nueva región, mientras que las perturbaciones provocadas por el algoritmo estocástico de escalada de colinas son mucho más pequeñas, confinadas a una región específica del espacio de búsqueda.

La heurística aquí es que a menudo puede encontrar mejores óptimos locales cerca de donde se encuentra actualmente, y caminar de un óptimo local a otro óptimo local de esta manera a menudo supera al probar nuevas ubicaciones completamente al azar.

– Página 26, Fundamentos de metaheurística, 2011.

Esto permite que la búsqueda se realice en dos niveles. El algoritmo de escalada es la búsqueda local para aprovechar al máximo una solución candidata específica o región del espacio de búsqueda, y el enfoque de reinicio permite explorar diferentes regiones del espacio de búsqueda.

De esta forma, el algoritmo Iterated Local Search explora múltiples óptimos locales en el espacio de búsqueda, aumentando la probabilidad de localizar los óptimos globales.

La Búsqueda Local Iterada se propuso para problemas de optimización combinatoria, como el problema del viajante de comercio (TSP), aunque se puede aplicar a la optimización de funciones continuas utilizando diferentes tamaños de paso en el espacio de búsqueda: pasos más pequeños para la subida de colinas y pasos más grandes para el reinicio aleatorio.

Ahora que estamos familiarizados con el algoritmo de búsqueda local iterada, exploremos cómo implementar el algoritmo desde cero.

Función objetivo de Ackley

Primero, definamos un problema de optimización de canalización como base para implementar el algoritmo de búsqueda local iterada.

La función Ackley es un ejemplo de una función objetivo multimodal que tiene un único óptimo global y múltiples óptimos locales en los que una búsqueda local puede atascarse.

Como tal, se requiere una técnica de optimización global. Es una función objetivo bidimensional que tiene un óptimo global en [0,0], que se evalúa como 0.0.

El siguiente ejemplo implementa el Ackley y crea un gráfico de superficie tridimensional que muestra los óptimos globales y múltiples óptimos locales.

La ejecución del ejemplo crea el gráfico de superficie de la función Ackley que muestra la gran cantidad de óptimos locales.

Gráfico de superficie 3D de la función multimodal de Ackley

Gráfico de superficie 3D de la función multimodal de Ackley

Usaremos esto como base para implementar y comparar un algoritmo simple de escalada estocástica, escalada estocástica con reinicios aleatorios y, finalmente, búsqueda local iterada.

Es de esperar que un algoritmo estocástico de escalada de colinas se atasque fácilmente en los mínimos locales. Esperaríamos que la escalada estocástica con reinicios encontrara muchos mínimos locales, y esperaríamos que la búsqueda local iterada se desempeñara mejor que cualquier método en este problema si se configura adecuadamente.

Algoritmo de escalada estocástico

El núcleo del algoritmo de búsqueda local iterada es una búsqueda local y, en este tutorial, utilizaremos el algoritmo de escalada estocástica para este propósito.

El algoritmo Stochastic Hill Climbing implica generar primero un punto de partida aleatorio y una solución de trabajo actual, luego generar versiones perturbadas de la solución de trabajo actual y aceptarlas si son mejores que la solución de trabajo actual.

Dado que estamos trabajando en un problema de optimización continua, una solución es un vector de valores a evaluar por la función objetivo, en este caso, un punto en un espacio bidimensional acotado por -5 y 5.

Podemos generar un punto aleatorio muestreando el espacio de búsqueda con una distribución de probabilidad uniforme. Por ejemplo:

Podemos generar versiones perturbadas de una solución que funciona actualmente usando una distribución de probabilidad gaussiana con la media de los valores actuales en la solución y una desviación estándar controlada por un hiperparámetro que controla qué tan lejos se permite explorar la búsqueda desde la solución de trabajo actual.

Nos referiremos a este hiperparámetro como “Numero de pie“, por ejemplo:

Es importante destacar que debemos comprobar que las soluciones generadas se encuentran dentro del espacio de búsqueda.

Esto se puede lograr con una función personalizada llamada dentro_límites () que toma una solución candidata y los límites del espacio de búsqueda y devuelve Verdadero si el punto está en el espacio de búsqueda, Falso de lo contrario.

Esta función se puede llamar durante la subida de la colina para confirmar que hay nuevos puntos dentro de los límites del espacio de búsqueda y, de lo contrario, se pueden generar nuevos puntos.

Uniendo esto, la función Montañismo() a continuación implementa el algoritmo de búsqueda local estocástico de escalada de colinas. Toma el nombre de la función objetivo, los límites del problema, el número de iteraciones y el tamaño de los pasos como argumentos y devuelve la mejor solución y su evaluación.

Podemos probar este algoritmo en la función de Ackley.

Arreglaremos la semilla para el generador de números pseudoaleatorios para asegurarnos de obtener los mismos resultados cada vez que se ejecuta el código.

El algoritmo se ejecutará durante 1000 iteraciones y se utilizará un tamaño de paso de 0,05 unidades; Ambos hiperparámetros fueron elegidos después de un pequeño ensayo y error.

Al final de la ejecución, informaremos sobre la mejor solución encontrada.

Al unir esto, el ejemplo completo de la aplicación del algoritmo estocástico de escalada de colinas a la función objetivo de Ackley se enumera a continuación.

Al ejecutar el ejemplo, se realiza la búsqueda estocástica de escalada en la función objetivo. Cada mejora encontrada durante la búsqueda se informa y luego se informa la mejor solución al final de la búsqueda.

Nota: Sus resultados pueden variar dada la naturaleza estocástica del algoritmo o procedimiento de evaluación, o las diferencias en la precisión numérica. Considere ejecutar el ejemplo varias veces y compare el resultado promedio.

En este caso, podemos ver alrededor de 13 mejoras durante la búsqueda y una solución final de aproximadamente f (-0,981, 1,965), lo que da como resultado una evaluación de aproximadamente 5,381, que está lejos de f (0,0, 0,0) = 0.

A continuación, modificaremos el algoritmo para realizar reinicios aleatorios y veremos si podemos lograr mejores resultados.

Escalada estocástica con reinicios aleatorios

El algoritmo Stochastic Hill Climbing With Random Restarts implica la ejecución repetida del algoritmo Stochastic Hill Climbing y realizar un seguimiento de la mejor solución encontrada.

Primero, modifiquemos el Montañismo() función para tomar el punto de partida de la búsqueda en lugar de generarla aleatoriamente. Esto ayudará más adelante cuando implementemos el algoritmo de búsqueda local iterada más adelante.

A continuación, podemos implementar el algoritmo de reinicio aleatorio llamando repetidamente al Montañismo() funcionar un número fijo de veces.

En cada llamada, generaremos un nuevo punto de partida seleccionado al azar para la búsqueda de escalada.

We can then inspect the result and keep it if it is better than any result of the search we have seen so far.

Tying this together, the random_restarts() function implemented the stochastic hill climbing algorithm with random restarts.

We can then apply this algorithm to the Ackley objective function. In this case, we will limit the number of random restarts to 30, chosen arbitrarily.

The complete example is listed below.

Running the example will perform a stochastic hill climbing with random restarts search for the Ackley objective function. Each time an improved overall solution is discovered, it is reported and the final best solution found by the search is summarized.

Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see three improvements during the search and that the best solution found was approximately f(0.002, 0.002), which evaluated to about 0.009, which is much better than a single run of the hill climbing algorithm.

Next, let’s look at how we can implement the iterated local search algorithm.

Iterated Local Search Algorithm

The Iterated Local Search algorithm is a modified version of the stochastic hill climbing with random restarts algorithm.

The important difference is that the starting point for each application of the stochastic hill climbing algorithm is a perturbed version of the best point found so far.

We can implement this algorithm by using the random_restarts() function as a starting point. Each restart iteration, we can generate a modified version of the best solution found so far instead of a random starting point.

This can be achieved by using a step size hyperparameter, much like is used in the stochastic hill climber. In this case, a larger step size value will be used given the need for larger perturbations in the search space.

Tying this together, the iterated_local_search() function is defined below.

We can then apply the algorithm to the Ackley objective function. In this case, we will use a larger step size value of 1.0 for the random restarts, chosen after a little trial and error.

The complete example is listed below.

Running the example will perform an Iterated Local Search of the Ackley objective function.

Each time an improved overall solution is discovered, it is reported and the final best solution found by the search is summarized at the end of the run.

Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see four improvements during the search and that the best solution found was two very small inputs that are close to zero, which evaluated to about 0.0003, which is better than either a single run of the hill climber or the hill climber with restarts.

Further Reading

This section provides more resources on the topic if you are looking to go deeper.

Books

Articles

Resumen

In this tutorial, you discovered how to implement the iterated local search algorithm from scratch.

Specifically, you learned:

  • Iterated local search is a stochastic global search optimization algorithm that is a smarter version of stochastic hill climbing with random restarts.
  • How to implement stochastic hill climbing with random restarts from scratch.
  • How to implement and apply the iterated local search algorithm to a nonlinear objective function.

Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.