Optimización aleatoria

La optimización aleatoria (RO) es una familia de métodos de optimización numérica que no requieren que se optimice el gradiente del problema y, por lo tanto, la RO se puede utilizar en funciones que no son continuas o diferenciables . Estos métodos de optimización también se conocen como métodos de búsqueda directa, sin derivados o de caja negra.

El nombre de optimización aleatoria se atribuye a Matyas ^[1], quien hizo una presentación temprana de RO junto con un análisis matemático básico. RO funciona moviéndose iterativamente a mejores posiciones en el espacio de búsqueda que se muestrean utilizando, por ejemplo, una distribución normal que rodea la posición actual.

Algoritmo

Sea la función de aptitud o costo que debe minimizarse. Designemos una posición o solución candidata en el espacio de búsqueda. El algoritmo RO básico puede describirse entonces como: ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$ ${\displaystyle x\in \mathbb {R} ^{n}}$

• Inicialice x con una posición aleatoria en el espacio de búsqueda.
• Hasta que se cumpla un criterio de terminación (por ejemplo, número de iteraciones realizadas o aptitud adecuada alcanzada), repita lo siguiente:
  • Muestreo de una nueva posición y agregando un vector aleatorio distribuido normalmente a la posición actual x
  • Si ( f ( y ) <  f ( x )) entonces muévase a la nueva posición estableciendo x  =  y
• Ahora x ocupa la posición mejor encontrada.

Este algoritmo corresponde a una estrategia de evolución (1+1) con tamaño de paso constante.

Convergencia y variantes

Matyas demostró que la forma básica de RO converge al óptimo de una función unimodal simple mediante el uso de una prueba de límites que muestra que la convergencia al óptimo seguramente ocurrirá si se realiza un número potencialmente infinito de iteraciones. Sin embargo, esta prueba no es útil en la práctica porque sólo se puede ejecutar un número finito de iteraciones. De hecho, tal prueba teórica de límites también mostrará que el muestreo puramente aleatorio del espacio de búsqueda producirá inevitablemente una muestra arbitrariamente cercana al óptimo.

^{Baba [2]} y Solis y Wets ^[3] también realizan análisis matemáticos para establecer que la convergencia a una región que rodea al óptimo es inevitable en algunas condiciones suaves para variantes de RO que utilizan otras distribuciones de probabilidad para el muestreo. Dorea obtiene una estimación del número de iteraciones necesarias para acercarse al óptimo. ^[4] Estos análisis son criticados a través de experimentos empíricos de Sarma ^[5], quien utilizó las variantes optimizadoras de Baba y Dorea en dos problemas del mundo real, mostrando que el óptimo debe abordarse muy lentamente y, además, que los métodos en realidad no pudieron localizar un solución de aptitud adecuada, a menos que el proceso se haya iniciado lo suficientemente cerca del óptimo para empezar.

Ver también

• La búsqueda aleatoria es una familia estrechamente relacionada de métodos de optimización que toman muestras de una hiperesfera en lugar de una distribución normal.
• Luus-Jaakola es un método de optimización estrechamente relacionado que utiliza una distribución uniforme en su muestreo y una fórmula simple para disminuir exponencialmente el rango de muestreo.
• La búsqueda de patrones toma pasos a lo largo de los ejes del espacio de búsqueda utilizando tamaños de paso decrecientes exponencialmente.
• Optimización estocástica

Referencias

1. Matías, J. (1965). "Optimización aleatoria". Automatización y Control Remoto . 26 (2): 246–253.
2. Baba, N. (1981). "Convergencia de un método de optimización aleatoria para problemas de optimización restringida". Revista de teoría y aplicaciones de optimización . 33 (4): 451–461. doi :10.1007/bf00935752.
3. Solís, Francisco J.; Wets, Roger J.-B. (1981). "Minimización mediante técnicas de búsqueda aleatoria". Matemáticas de la Investigación de Operaciones . 6 (1): 19–30. doi :10.1287/moor.6.1.19.
4. Dorea, CCY (1983). "Número esperado de pasos de un método de optimización aleatorio". Revista de teoría y aplicaciones de optimización . 39 (3): 165-171. doi :10.1007/bf00934526.
5. Sarma, MS (1990). "Sobre la convergencia de los métodos de optimización aleatoria de Baba y Dorea". Revista de teoría y aplicaciones de optimización . 66 (2): 337–343. doi :10.1007/bf00939542.