Optimización aleatoria

La optimización aleatoria (OA) es una familia de métodos de optimización numérica que no requieren el gradiente del problema de optimización y, por lo tanto, pueden utilizarse con funciones que no son continuas ni 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 ^{[ 1 ],} quien realizó una presentación temprana de la optimización aleatoria junto con un análisis matemático básico. La optimización aleatoria funciona moviéndose iterativamente a mejores posiciones en el espacio de búsqueda, las cuales se muestrean utilizando, por ejemplo, una distribución normal alrededor de la posición actual.

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

• Inicializa 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:
  • Muestre una nueva posición y sumando un vector aleatorio con distribución normal 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 mejor posición encontrada.

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

Matyas demostró que la forma básica del algoritmo RO converge al óptimo de una función unimodal simple mediante una prueba límite que muestra que la convergencia al óptimo es segura si se realiza un número potencialmente infinito de iteraciones. Sin embargo, esta prueba no es útil en la práctica, ya que solo se puede ejecutar un número finito de iteraciones. De hecho, dicha prueba límite teórica también demostrará que el muestreo puramente aleatorio del espacio de búsqueda inevitablemente producirá 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 bajo ciertas condiciones leves para las variantes de RO que utilizan otras distribuciones de probabilidad para el muestreo. Dorea ^{[ 4 ]} obtiene una estimación del número de iteraciones necesarias para aproximarse al óptimo. Estos análisis son criticados mediante experimentos empíricos por Sarma ^{[ 5 ]} , quien utilizó las variantes del optimizador de Baba y Dorea en dos problemas del mundo real, demostrando que el óptimo se alcanza muy lentamente y, además, que los métodos no pudieron encontrar una solución con la aptitud adecuada, a menos que el proceso se iniciara suficientemente cerca del óptimo.

• La búsqueda aleatoria es una familia de métodos de optimización estrechamente relacionados que toman muestras de una hiperesfera en lugar de una distribución normal.
• El método de 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 realiza pasos a lo largo de los ejes del espacio de búsqueda utilizando tamaños de paso que disminuyen exponencialmente.
• Optimización estocástica