La búsqueda aleatoria (RS) 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, RS 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 derivadas o de caja negra.
El nombre "búsqueda aleatoria" se atribuye a Rastrigin [1], quien hizo una presentación temprana de RS junto con análisis matemático básico. RS funciona moviéndose iterativamente a mejores posiciones en el espacio de búsqueda, que se muestrean desde una hiperesfera que rodea la posición actual.
El algoritmo descrito en este documento es un tipo de búsqueda aleatoria local, donde cada iteración depende de la solución candidata de la iteración anterior. Existen métodos de búsqueda aleatorios alternativos que toman muestras de la totalidad del espacio de búsqueda (por ejemplo, búsqueda aleatoria pura o búsqueda aleatoria global uniforme), pero estos no se describen en este artículo.
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 RS básico 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:
- Muestree una nueva posición y de la hiperesfera de un radio dado que rodea la posición actual x (consulte, por ejemplo, la técnica de Marsaglia para muestrear una hiperesfera).
- Si f ( y ) < f ( x ) , muévase a la nueva posición estableciendo x = y
Variantes
Se han introducido varias variantes de RS en la literatura:
- La búsqueda aleatoria de tamaño de paso fijo (FSSRS) es el algoritmo básico de Rastrigin [1] que toma muestras de una hiperesfera de radio fijo.
- La búsqueda aleatoria de tamaño de paso óptimo (OSSRS) de Schumer y Steiglitz [2] es principalmente un estudio teórico sobre cómo ajustar de manera óptima el radio de la hiperesfera para permitir una rápida convergencia al óptimo. Una implementación real del OSSRS necesita aproximarse a este radio óptimo mediante muestreo repetido y, por lo tanto, su ejecución es costosa.
- La búsqueda aleatoria de tamaño de paso adaptativo (ASSRS) de Schumer y Steiglitz [2] intenta adaptar heurísticamente el radio de la hiperesfera: se generan dos nuevas soluciones candidatas, una con el tamaño de paso nominal actual y otra con un tamaño de paso mayor. El tamaño de paso más grande se convierte en el nuevo tamaño de paso nominal si y solo si conduce a una mejora mayor. Si durante varias iteraciones ninguno de los pasos conduce a una mejora, el tamaño de paso nominal se reduce.
- La búsqueda aleatoria de tamaño de paso relativo optimizado (ORSSRS) de Schrack y Choit [3] se aproxima al tamaño de paso óptimo mediante una simple disminución exponencial. Sin embargo, la fórmula para calcular el factor de disminución es algo complicada.
Ver también
- La optimización aleatoria es una familia estrechamente relacionada de métodos de optimización que toman muestras de una distribución normal en lugar de una hiperesfera.
- 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.
Referencias
- ↑ a b Rastrigin, LA (1963). "La convergencia del método de búsqueda aleatoria en el control extremo de un sistema de muchos parámetros". Automatización y Telemando . 24 (10): 1337-1342.
- ^ a b Schumer, MA; Steiglitz, K. (1968). "Búsqueda aleatoria de tamaño de paso adaptativo". Transacciones IEEE sobre control automático . 13 (3): 270–276. CiteSeerX 10.1.1.118.9779 . doi : 10.1109 / tac.1968.1098903 .
- ^ Schrack, G .; Choit, M. (1976). "Búsquedas aleatorias de tamaño de paso relativo optimizado". Programación matemática . 10 (1): 230–244. doi : 10.1007 / bf01580669 .