Optimización aleatoria - Random optimization
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, se puede usar RO 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 derivadas o de caja negra.
El nombre de optimización aleatoria se atribuye a Matyas, quien realizó 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 usando, por ejemplo, una distribución normal que rodea la posición actual.
Algoritmo
Sea f : ℝ n → ℝ la función de adecuación o costo que debe minimizarse. Sea x ∈ ℝ n una posición o una solución candidata en el espacio de búsqueda. El algoritmo básico de RO se puede describir como:
- 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:
- Muestra una nueva posición y agregando un vector aleatorio distribuido normalmente a la posición actual x
- Si ( f ( y ) < f ( x )), 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 mostró que la forma básica de RO converge al óptimo de una función unimodal simple mediante el uso de una prueba de límite 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 solo se puede ejecutar un número finito de iteraciones. De hecho, tal prueba límite teórica también mostrará que un muestreo puramente aleatorio del espacio de búsqueda inevitablemente producirá una muestra arbitrariamente cercana al óptimo.
Baba, Solis y Wets 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 las 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. Estos análisis son criticados a través de experimentos empíricos por Sarma quien usó las variantes optimizadoras de Baba y Dorea en dos problemas del mundo real, mostrando que el óptimo debe ser abordado muy lentamente y además que los métodos fueron realmente incapaces de encontrar una solución de adecuación adecuada, a menos que el proceso se inició lo suficientemente cerca del óptimo para empezar.
Ver también
- La búsqueda aleatoria es una familia de métodos de optimización estrechamente relacionada que toma 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 que disminuyen exponencialmente.
- Optimización estocástica