La búsqueda de patrones (también conocida como búsqueda directa, búsqueda sin derivadas o búsqueda de caja negra) es una familia de métodos de optimización numérica que no requiere un gradiente . Como resultado, se puede utilizar en funciones que no son continuas o diferenciables . Uno de esos métodos de búsqueda de patrones es la "convergencia" (ver más abajo), que se basa en la teoría de bases positivas. La optimización intenta encontrar la mejor coincidencia (la solución que tiene el valor de error más bajo) en un espacio de posibilidades de análisis multidimensional .
Historia
El nombre "búsqueda de patrones" fue acuñado por Hooke y Jeeves. [1] Una variante temprana y simple se atribuye a Fermi y Metropolis cuando trabajaban en el Laboratorio Nacional de Los Alamos . Davidon lo describe [2] de la siguiente manera:
Variaron un parámetro teórico a la vez por pasos de la misma magnitud, y cuando ningún aumento o disminución en ningún parámetro mejoró aún más el ajuste a los datos experimentales, redujeron a la mitad el tamaño del paso y repitieron el proceso hasta que los pasos se consideraron suficientemente pequeña.
Convergencia
La convergencia es un método de búsqueda de patrones propuesto por Yu, quien demostró que converge utilizando la teoría de bases positivas. [3] Más tarde, Torczon , Lagarias y coautores [4] [5] utilizaron técnicas de base positiva para probar la convergencia de otro método de búsqueda de patrones en clases específicas de funciones. Fuera de estas clases, la búsqueda de patrones es una heurística que puede proporcionar soluciones aproximadas útiles para algunos problemas, pero puede fallar en otros. Fuera de estas clases, la búsqueda de patrones no es un método iterativo que converja en una solución; de hecho, los métodos de búsqueda de patrones pueden converger a puntos no estacionarios en algunos problemas relativamente sencillos. [6] [7]
Ver también
- La búsqueda de la sección áurea se parece conceptualmente a PS en su estrechamiento del rango de búsqueda, solo para espacios de búsqueda unidimensionales.
- Método Nelder-Mead también conocido como. El método simplex se parece conceptualmente a PS en su estrechamiento del rango de búsqueda para espacios de búsqueda multidimensionales, pero lo hace manteniendo n + 1 puntos para espacios de búsqueda n -dimensionales, mientras que los métodos PS calculan 2 n + 1 puntos (el punto central y 2 puntos en cada dimensión).
- Luus – Jaakola toma muestras de una distribución uniforme que rodea la posición actual y usa una fórmula simple para disminuir exponencialmente el rango de muestreo.
- La búsqueda aleatoria es una familia relacionada de métodos de optimización que toman muestras de una hiperesfera que rodea la posición actual.
- La optimización aleatoria es una familia relacionada de métodos de optimización que toman muestras de una distribución normal que rodea la posición actual.
Referencias
- ^ Hooke, R .; Jeeves, TA (1961). " " Solución de búsqueda directa "de los numérica y problemas estadísticos". Revista de la ACM . 8 (2): 212-229. doi : 10.1145 / 321062.321069 .
- ^ Davidon, WC (1991). "Método de métrica variable para la minimización". Revista SIAM de Optimización . 1 (1): 1-17. CiteSeerX 10.1.1.693.272 . doi : 10.1137 / 0801001 .
- ^ * Yu, Wen Ci. 1979. “ Base positiva y una clase de técnicas de búsqueda directa ”. Scientia Sinica [ Zhongguo Kexue ]: 53—68.
- Yu, Wen Ci. 1979. “ La propiedad convergente de la técnica evolutiva simplex ”. Scientia Sinica [ Zhongguo Kexue ]: 69–77.
- ^ Torczon, VJ (1997). "Sobre la convergencia de algoritmos de búsqueda de patrones" (PDF) . Revista SIAM de Optimización . 7 (1): 1–25. CiteSeerX 10.1.1.50.3173 . doi : 10.1137 / S1052623493250780 .
- ^ Dolan, ED; Lewis, RM; Torczon, VJ (2003). "Sobre la convergencia local de la búsqueda de patrones" (PDF) . Revista SIAM de Optimización . 14 (2): 567–583. CiteSeerX 10.1.1.78.2407 . doi : 10.1137 / S1052623400374495 .
- ^ * Powell, Michael JD 1973. " Sobre las direcciones de búsqueda para algoritmos de minimización ". Programación matemática 4: 193-201.
- ^ * McKinnon, KIM (1999). "Convergencia del método simplex de Nelder-Mead a un punto no estacionario". SIAM J. Optim . 9 : 148-158. CiteSeerX 10.1.1.52.3900 . doi : 10.1137 / S1052623496303482 . (resumen del algoritmo en línea).