Búsqueda aleatoria

La búsqueda aleatoria (RA) es una familia de métodos de optimización numérica que no requieren el gradiente del problema de optimización, por lo que puede utilizarse con funciones que no son continuas ni diferenciables . Estos métodos de optimización también se conocen como búsqueda directa, sin derivadas o de caja negra.

En 1953, Anderson revisó el progreso de los métodos para encontrar el máximo o el mínimo de problemas utilizando una serie de estimaciones distribuidas con un cierto orden o patrón en el espacio de búsqueda de parámetros, por ejemplo, un diseño confuso con espaciamientos/pasos distribuidos exponencialmente. ^{[ 1 ]} Esta búsqueda se realiza secuencialmente en cada parámetro y se refina iterativamente en las mejores estimaciones de la última secuencia. El patrón puede ser una búsqueda en cuadrícula (factorial) de todos los parámetros, una búsqueda secuencial en cada parámetro o una combinación de ambas. El método fue desarrollado para evaluar las condiciones experimentales en reacciones químicas por varios científicos mencionados en el artículo de Anderson. Un código MATLAB que reproduce el procedimiento secuencial para la regresión no lineal general de un modelo matemático de ejemplo se puede encontrar aquí (JCFit @ GitHub). ^{[ 2 ]}

El nombre "búsqueda aleatoria" se atribuye a Rastrigin ^{[ 3 ]} , quien realizó una presentación temprana de RS junto con un análisis matemático básico. RS funciona moviéndose iterativamente a mejores posiciones en el espacio de búsqueda, las cuales se muestrean de una hiperesfera que rodea la posición actual.

El algoritmo que se describe aquí 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 alternativos de búsqueda aleatoria que muestrean 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.

La búsqueda aleatoria se ha utilizado en redes neuronales artificiales para la optimización de hiperparámetros. ^{[ 4 ]}

Si las buenas partes del espacio de búsqueda ocupan el 5% del volumen, las posibilidades de encontrar una buena configuración en el espacio de búsqueda son del 5%. La probabilidad de encontrar al menos una buena configuración es superior al 95% después de probar 60 configuraciones (${\displaystyle 1-0,95^{60}=0,953>0,95}$, haciendo uso de la contraprobabilidad).

Sea f :  ℝ ⁿ  → ℝ la función de aptitud o de coste que debe minimizarse. Sea x  ∈ ℝ ⁿ una posición o solución candidata en el espacio de búsqueda. El algoritmo RS básico se puede describir entonces como:

1. Inicializa x con una posición aleatoria en el espacio de búsqueda.
2. Hasta que se cumpla un criterio de terminación (por ejemplo, número de iteraciones realizadas o aptitud adecuada alcanzada), repita lo siguiente:
   1. Muestrear una nueva posición y de la hiperesfera de un radio dado que rodea la posición actual x (véase, por ejemplo, la técnica de Marsaglia para muestrear una hiperesfera).
   2. Si f ( y )  < f ( x )  entonces muévase a la nueva posición estableciendo x  = y 

La búsqueda verdaderamente aleatoria depende puramente de la suerte y varía desde muy costosa hasta muy afortunada, pero la búsqueda aleatoria estructurada es estratégica. En la literatura se han introducido varias variantes de RS con muestreo estructurado en el espacio de búsqueda:

• Procedimiento de Friedman-Savage: Buscar secuencialmente cada parámetro con un conjunto de estimaciones que tienen un patrón espacial entre la estimación inicial y los límites. ^{[ 5 ]} Un ejemplo de pasos distribuidos exponencialmente se puede encontrar aquí en un código MATLAB (JCFit @ GitHub). ^{[ 2 ]} Este código de ejemplo converge 1-2 órdenes de magnitud más lento que el algoritmo de Levenberg-Marquardt , con un ejemplo también proporcionado en GitHub.
• La búsqueda aleatoria de tamaño de paso fijo (FSSRS) es el algoritmo básico de Rastrigin ^{[ 3 ]} que toma muestras de una hiperesfera de radio fijo.
• El método de búsqueda aleatoria con tamaño de paso óptimo (OSSRS, por sus siglas en inglés) de Schumer y Steiglitz ^{[ 6 ]} es principalmente un estudio teórico sobre cómo ajustar de forma óptima el radio de la hiperesfera para lograr una convergencia rápida hacia el óptimo. La implementación práctica del OSSRS requiere aproximar este radio óptimo mediante muestreo repetido y, por lo tanto, su ejecución resulta costosa.
• El método de búsqueda aleatoria con tamaño de paso adaptativo (ASSRS, por sus siglas en inglés) de Schumer y Steiglitz ^{[ 6 ]} 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 mayor se convierte en el nuevo tamaño de paso nominal si y solo si produce una mejora mayor. Si durante varias iteraciones ninguno de los pasos produce una mejora, se reduce el tamaño de paso nominal.
• El método de búsqueda aleatoria de tamaño de paso relativo optimizado (ORSSRS) de Schrack y Choit ^{[ 7 ]} aproxima el 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 compleja.

• La optimización aleatoria es una familia de métodos de optimización estrechamente relacionados que toman muestras de una distribución normal en lugar de una hiperesfera.
• 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.