Búsqueda aleatoria y búsqueda en cuadrícula para optimización de funciones

La optimización de funciones requiere la selección de un algoritmo para muestrear eficientemente el espacio de búsqueda y localizar una buena o mejor solución.

Hay muchos algoritmos para elegir, aunque es importante establecer una línea de base sobre qué tipos de soluciones son factibles o posibles para un problema. Esto se puede lograr utilizando un algoritmo de optimización ingenuo, como una búsqueda aleatoria o una búsqueda en cuadrícula.

Los resultados logrados por un algoritmo de optimización ingenuo son computacionalmente eficientes para generar y proporcionan un punto de comparación para algoritmos de optimización más sofisticados. A veces, se descubre que los algoritmos ingenuos logran el mejor rendimiento, particularmente en aquellos problemas que son ruidosos o no fluidos y aquellos problemas en los que la experiencia en el dominio generalmente sesga la elección del algoritmo de optimización.

En este tutorial, descubrirá algoritmos ingenuos para la optimización de funciones.

Después de completar este tutorial, sabrá:

• El papel de los algoritmos ingenuos en proyectos de optimización de funciones.
• Cómo generar y evaluar una búsqueda aleatoria para optimización de funciones.
• Cómo generar y evaluar una grilla de búsqueda para optimización de funciones.

Pon en marcha tu proyecto con mi nuevo libro Optimización para el aprendizaje automático, que incluye tutoriales paso a paso y los archivos de código fuente de Python para todos. ejemplos.

Descripción general del tutorial

Este tutorial se divide en tres partes; ellos son:

1. Algoritmos ingenuos de optimización de funciones
2. Búsqueda aleatoria para optimización de funciones
3. Búsqueda de cuadrícula para optimización de funciones

Algoritmos ingenuos de optimización de funciones

Hay muchos algoritmos diferentes que puedes utilizar para la optimización, pero ¿cómo sabes si los resultados que obtienes son buenos?

Un enfoque para resolver este problema es establecer una línea de base en el rendimiento utilizando un algoritmo de optimización ingenuo.

Un algoritmo de optimización ingenuo es un algoritmo que no asume nada sobre la función objetivo que se está optimizando.

Se puede aplicar con muy poco esfuerzo y el mejor resultado logrado por el algoritmo se puede utilizar como punto de referencia para comparar algoritmos más sofisticados. Si un algoritmo más sofisticado no puede lograr un mejor resultado que un algoritmo ingenuo en promedio, entonces no tiene habilidad para resolver su problema y debe abandonarse.

Hay dos algoritmos ingenuos que se pueden utilizar para la optimización de funciones; ellos son:

• Búsqueda aleatoria
• Búsqueda de cuadrícula

Estos algoritmos se denominan algoritmos de “búsqueda” porque, en esencia, la optimización puede enmarcarse como un problema de búsqueda. P.ej. Encuentre las entradas que minimizan o maximizan la salida de la función objetivo.

Existe otro algoritmo que se puede utilizar llamado "búsqueda exhaustiva" que enumera todas las entradas posibles. Esto rara vez se utiliza en la práctica, ya que no es factible enumerar todas las entradas posibles, p. Requeriría demasiado tiempo para ejecutarse.

Sin embargo, si se encuentra trabajando en un problema de optimización para el cual todas las entradas pueden enumerarse y evaluarse en un tiempo razonable, esta debería ser la estrategia predeterminada que debería utilizar.

Echemos un vistazo más de cerca a cada uno de ellos.

Búsqueda aleatoria para optimización de funciones

La búsqueda aleatoria también se conoce como optimización aleatoria o muestreo aleatorio.

La búsqueda aleatoria implica generar y evaluar entradas aleatorias a la función objetivo. Es eficaz porque no supone nada sobre la estructura de la función objetivo. Esto puede resultar beneficioso para problemas en los que existe mucha experiencia en el dominio que puede influir o sesgar la estrategia de optimización, permitiendo descubrir soluciones no intuitivas.

…muestreo aleatorio, que simplemente extrae m muestras aleatorias sobre el espacio de diseño utilizando un generador de números pseudoaleatorios. Para generar una muestra aleatoria x, podemos muestrear cada variable independientemente de una distribución.

— Página 236, Algoritmos de optimización, 2019.

La búsqueda aleatoria también puede ser la mejor estrategia para problemas altamente complejos con áreas ruidosas o no suaves (discontinuas) del espacio de búsqueda que pueden causar algoritmos que dependen de gradientes confiables.

Podemos generar una muestra aleatoria de un dominio utilizando un generador de números pseudoaleatorios. Cada variable requiere un límite o rango bien definido y se puede muestrear un valor uniformemente aleatorio del rango y luego evaluarlo.

Generar muestras aleatorias es computacionalmente trivial y no ocupa mucha memoria; por lo tanto, puede ser eficiente generar una muestra grande de entradas y luego evaluarlas. Cada muestra es independiente, por lo que las muestras se pueden evaluar en paralelo si es necesario para acelerar el proceso.

El siguiente ejemplo proporciona un ejemplo de una función objetivo de minimización unidimensional simple y genera y luego evalúa una muestra aleatoria de 100 entradas. Luego se informa la entrada con el mejor rendimiento.

# example of random search for function optimization
from numpy.random import rand

# objective function
def objective(x):
	return x**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a random sample from the domain
sample = r_min + rand(100) * (r_max - r_min)
# evaluate the sample
sample_eval = objective(sample)
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f) = %.5f' % (sample[best_ix], sample_eval[best_ix]))

La ejecución del ejemplo genera una muestra aleatoria de valores de entrada, que luego se evalúan. Luego se identifica y reporta el punto con mejor desempeño.

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

En este caso, podemos ver que el resultado está muy cerca de la entrada óptima de 0,0.

Best: f(-0.01762) = 0.00031

Podemos actualizar el ejemplo para trazar la función objetivo y mostrar la muestra y el mejor resultado. El ejemplo completo se enumera a continuación.

# example of random search for function optimization with plot
from numpy import arange
from numpy.random import rand
from matplotlib import pyplot

# objective function
def objective(x):
	return x**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a random sample from the domain
sample = r_min + rand(100) * (r_max - r_min)
# evaluate the sample
sample_eval = objective(sample)
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f) = %.5f' % (sample[best_ix], sample_eval[best_ix]))
# sample input range uniformly at 0.1 increments
inputs = arange(r_min, r_max, 0.1)
# compute targets
results = objective(inputs)
# create a line plot of input vs result
pyplot.plot(inputs, results)
# plot the sample
pyplot.scatter(sample, sample_eval)
# draw a vertical line at the best input
pyplot.axvline(x=sample[best_ix], ls='--', color='red')
# show the plot
pyplot.show()

Al ejecutar el ejemplo nuevamente se genera la muestra aleatoria y se informa el mejor resultado.

Best: f(0.01934) = 0.00037

Luego se crea un gráfico de líneas que muestra la forma de la función objetivo, la muestra aleatoria y una línea roja para localizar el mejor resultado de la muestra.

Búsqueda de cuadrícula para optimización de funciones

La búsqueda de cuadrícula también se conoce como muestreo de cuadrícula o muestreo factorial completo.

La búsqueda de cuadrícula implica generar entradas de cuadrícula uniformes para una función objetivo. En una dimensión, serían entradas espaciadas uniformemente a lo largo de una línea. En dos dimensiones, esto sería una red de puntos espaciados uniformemente a lo largo de la superficie, y así sucesivamente para dimensiones superiores.

El plan de muestreo factorial completo coloca una cuadrícula de puntos espaciados uniformemente sobre el espacio de búsqueda. Este método es fácil de implementar, no depende de la aleatoriedad y cubre el espacio, pero utiliza una gran cantidad de puntos.

— Página 235, Algoritmos de optimización, 2019.

Al igual que la búsqueda aleatoria, una búsqueda en cuadrícula puede ser particularmente eficaz en problemas en los que normalmente se utiliza la experiencia en el dominio para influir en la selección de algoritmos de optimización específicos. La cuadrícula puede ayudar a identificar rápidamente áreas de un espacio de búsqueda que pueden merecer más atención.

La cuadrícula de muestras suele ser uniforme, aunque no tiene por qué ser así. Por ejemplo, se podría utilizar una escala log-10 con un espaciado uniforme, lo que permitiría realizar muestreos en distintos órdenes de magnitud.

La desventaja es que la tosquedad de la cuadrícula puede abarcar regiones enteras del espacio de búsqueda donde residen buenas soluciones, un problema que empeora a medida que aumenta el número de entradas (dimensiones del espacio de búsqueda) al problema.

Se puede generar una cuadrícula de muestras eligiendo la separación uniforme de puntos, luego enumerando cada variable por turno e incrementando cada variable según la separación elegida.

El siguiente ejemplo proporciona un ejemplo de una función objetivo de minimización bidimensional simple y luego genera y evalúa una muestra de cuadrícula con un espaciado de 0,1 para ambas variables de entrada. Luego se informa la entrada con el mejor rendimiento.

# example of grid search for function optimization
from numpy import arange
from numpy.random import rand

# objective function
def objective(x, y):
	return x**2.0 + y**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a grid sample from the domain
sample = list()
step = 0.1
for x in arange(r_min, r_max+step, step):
	for y in arange(r_min, r_max+step, step):
		sample.append([x,y])
# evaluate the sample
sample_eval = [objective(x,y) for x,y in sample]
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f,%.5f) = %.5f' % (sample[best_ix][0], sample[best_ix][1], sample_eval[best_ix]))

La ejecución del ejemplo genera una cuadrícula de valores de entrada, que luego se evalúan. Luego se identifica y reporta el punto con mejor desempeño.

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

En este caso, podemos ver que el resultado encuentra exactamente el óptimo.

Best: f(-0.00000,-0.00000) = 0.00000

Podemos actualizar el ejemplo para trazar la función objetivo y mostrar la muestra y el mejor resultado. El ejemplo completo se enumera a continuación.

# example of grid search for function optimization with plot
from numpy import arange
from numpy import meshgrid
from numpy.random import rand
from matplotlib import pyplot

# objective function
def objective(x, y):
	return x**2.0 + y**2.0

# define range for input
r_min, r_max = -5.0, 5.0
# generate a grid sample from the domain
sample = list()
step = 0.5
for x in arange(r_min, r_max+step, step):
	for y in arange(r_min, r_max+step, step):
		sample.append([x,y])
# evaluate the sample
sample_eval = [objective(x,y) for x,y in sample]
# locate the best solution
best_ix = 0
for i in range(len(sample)):
	if sample_eval[i] < sample_eval[best_ix]:
		best_ix = i
# summarize best solution
print('Best: f(%.5f,%.5f) = %.5f' % (sample[best_ix][0], sample[best_ix][1], sample_eval[best_ix]))
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a filled contour plot
pyplot.contourf(x, y, results, levels=50, cmap='jet')
# plot the sample as black circles
pyplot.plot([x for x,_ in sample], [y for _,y in sample], '.', color='black')
# draw the best result as a white star
pyplot.plot(sample[best_ix][0], sample[best_ix][1], '*', color='white')
# show the plot
pyplot.show()

Al ejecutar el ejemplo nuevamente se genera la muestra de cuadrícula y se informa el mejor resultado.

Best: f(0.00000,0.00000) = 0.00000

Luego se crea un gráfico de contorno que muestra la forma de la función objetivo, la muestra de la cuadrícula como puntos negros y una estrella blanca para obtener el mejor resultado ubicada en la muestra.

Tenga en cuenta que algunos de los puntos negros del borde del dominio parecen estar fuera de la trama; esto es solo un artefacto de la forma en que elegimos dibujar los puntos (por ejemplo, no centrados en la muestra).

Lectura adicional

Esta sección proporciona más recursos sobre el tema si desea profundizar más.

Libros

• Algoritmos de optimización, 2019.

Artículos

• Búsqueda aleatoria, Wikipedia.
• Optimización de hiperparámetros, Wikipedia.
• Búsqueda por fuerza bruta, Wikipedia.

Resumen

En este tutorial, descubrió algoritmos ingenuos para la optimización de funciones.

Específicamente, aprendiste:

• El papel de los algoritmos ingenuos en proyectos de optimización de funciones.
• Cómo generar y evaluar una búsqueda aleatoria para optimización de funciones.
• Cómo generar y evaluar una grilla de búsqueda para optimización de funciones.

¿Tiene alguna pregunta?
Haga sus preguntas en los comentarios a continuación y haré todo lo posible para responderlas.