De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

Los métodos de optimización estocástica ( SO ) son métodos de optimización que generan y utilizan variables aleatorias . Para problemas estocásticos, las variables aleatorias aparecen en la formulación del problema de optimización en sí, que involucra funciones objetivas aleatorias o restricciones aleatorias. Los métodos de optimización estocástica también incluyen métodos con iteraciones aleatorias. Algunos métodos de optimización estocástica utilizan iteraciones aleatorias para resolver problemas estocásticos, combinando ambos significados de optimización estocástica. [1] métodos de optimización estocásticos generalizar deterministas métodos para problemas deterministas.

Métodos para funciones estocásticas

Los datos de entrada parcialmente aleatorios surgen en áreas tales como la estimación y el control en tiempo real, la optimización basada en simulación donde las simulaciones de Monte Carlo se ejecutan como estimaciones de un sistema real, [2] [3] y problemas donde hay un error experimental (aleatorio) en las medidas del criterio. En tales casos, el conocimiento de que los valores de la función están contaminados por "ruido" aleatorio conduce naturalmente a algoritmos que utilizan herramientas de inferencia estadística para estimar los valores "verdaderos" de la función y / o tomar decisiones estadísticamente óptimas sobre los siguientes pasos. Los métodos de esta clase incluyen:

Métodos de búsqueda aleatorios

Por otro lado, incluso cuando el conjunto de datos consiste en mediciones precisas, algunos métodos introducen aleatoriedad en el proceso de búsqueda para acelerar el progreso. [7] Tal aleatoriedad también puede hacer que el método sea menos sensible a los errores de modelado. Además, la aleatoriedad inyectada puede permitir que el método escape a un óptimo local y eventualmente se acerque a un óptimo global. De hecho, se sabe que este principio de aleatorización es una forma simple y eficaz de obtener algoritmos con un buen rendimiento casi seguro de manera uniforme en muchos conjuntos de datos, para muchos tipos de problemas. Los métodos de optimización estocástica de este tipo incluyen:

Por el contrario, algunos autores han argumentado que la aleatorización solo puede mejorar un algoritmo determinista si el algoritmo determinista estaba mal diseñado en primer lugar. [19] Fred W. Glover [20] sostiene que la dependencia de elementos aleatorios puede impedir el desarrollo de componentes más inteligentes y mejor deterministas. La forma en que generalmente se presentan los resultados de los algoritmos de optimización estocástica (por ejemplo, presentando solo el promedio, o incluso el mejor, de N ejecuciones sin ninguna mención del margen), también puede resultar en un sesgo positivo hacia la aleatoriedad.

Ver también

  • Optimización global
  • Aprendizaje automático
  • Optimización de escenarios
  • Proceso gaussiano
  • Modelo de espacio de estado
  • Modelo de control predictivo
  • Programación no lineal
  • Valor entrópico en riesgo

Referencias

  1. ^ Spall, JC (2003). Introducción a la búsqueda y optimización estocásticas . Wiley. ISBN 978-0-471-33052-3.
  2. ^ Fu, MC (2002). "Optimización para simulación: teoría vs. práctica". INFORMA Revista de Computación . 14 (3): 192-227. doi : 10.1287 / ijoc.14.3.192.113 .
  3. ^ MC Campi y S. Garatti. La factibilidad exacta de soluciones aleatorias de programas convexos inciertos. SIAM J. on Optimization, 19, n. ° 3: 1211-1230, 2008. [1]
  4. ^ Robbins, H .; Monro, S. (1951). "Un método de aproximación estocástico" . Anales de estadística matemática . 22 (3): 400–407. doi : 10.1214 / aoms / 1177729586 .
  5. ^ J. Kiefer ; J. Wolfowitz (1952). "Estimación estocástica del máximo de una función de regresión" . Anales de estadística matemática . 23 (3): 462–466. doi : 10.1214 / aoms / 1177729392 .
  6. ^ Spall, JC (1992). "Aproximación estocástica multivariante utilizando una aproximación de gradiente de perturbación simultánea" . Transacciones IEEE sobre control automático . 37 (3): 332–341. CiteSeerX 10.1.1.19.4562 . doi : 10.1109 / 9.119632 . 
  7. ^ Holger H. Hoos y Thomas Stützle, Búsqueda local estocástica: fundamentos y aplicaciones , Morgan Kaufmann / Elsevier , 2004.
  8. ^ S. Kirkpatrick; CD Gelatt; MP Vecchi (1983). "Optimización por recocido simulado" . Ciencia . 220 (4598): 671–680. Código Bibliográfico : 1983Sci ... 220..671K . CiteSeerX 10.1.1.123.7607 . doi : 10.1126 / science.220.4598.671 . PMID 17813860 .  
  9. ^ DH Wolpert; SR Bieniawski; DG Rajnarayan (2011). "Colectivos de probabilidad en optimización" . Instituto Santa Fe .
  10. ^ Battiti, Roberto; Gianpietro Tecchiolli (1994). "La búsqueda tabú reactiva" (PDF) . Revista ORSA de Computación . 6 (2): 126–140. doi : 10.1287 / ijoc.6.2.126 .
  11. ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Búsqueda reactiva y optimización inteligente . Springer Verlag . ISBN 978-0-387-09623-0.
  12. ^ Rubinstein, RY; Kroese, DP (2004). El método de la entropía cruzada . Springer-Verlag. ISBN 978-0-387-21240-1.
  13. ^ Zhigljavsky, AA (1991). Teoría de la búsqueda aleatoria global . Académico Kluwer. ISBN 978-0-7923-1122-5.
  14. ^ Kagan E .; Ben-Gal I. (2014). "Un algoritmo de prueba grupal con aprendizaje informativo en línea". Transacciones IIE . 46 (2): 164–184. doi : 10.1080 / 0740817X.2013.803639 .
  15. ^ W. Wenzel; K. Hamacher (1999). "Enfoque de tunelización estocástica para la optimización global de complejos paisajes energéticos potenciales". Phys. Rev. Lett . 82 (15): 3003. arXiv : física / 9903008 . Código Bibliográfico : 1999PhRvL..82.3003W . doi : 10.1103 / PhysRevLett.82.3003 .
  16. ^ E. Marinari; G. Parisi (1992). "Templado simulado: un nuevo esquema de monte carlo". Europhys. Lett . 19 (6): 451–458. arXiv : hep-lat / 9205018 . Código Bibliográfico : 1992EL ..... 19..451M . doi : 10.1209 / 0295-5075 / 19/6/002 .
  17. ^ Goldberg, DE (1989). Algoritmos genéticos en búsqueda, optimización y aprendizaje automático . Addison-Wesley. ISBN 978-0-201-15767-3. Archivado desde el original el 19 de julio de 2006.
  18. ^ Tavridovich, SA (2017). "COOMA: un algoritmo de optimización estocástica orientado a objetos" . Revista Internacional de Estudios Avanzados . 7 (2): 26–47. doi : 10.12731 / 2227-930x-2017-2-26-47 .
  19. ^ http://lesswrong.com/lw/vp/worse_than_random/
  20. ^ Glover, F. (2007). "Búsqueda tabú: dominios inexplorados". Anales de investigación operativa . 149 : 89–98. CiteSeerX 10.1.1.417.8223 . doi : 10.1007 / s10479-006-0113-9 . 

Lectura adicional

  • Michalewicz, Z. y Fogel, DB (2000), How to Solve It: Modern Heuristics , Springer-Verlag, Nueva York.
  • " PSA: un algoritmo de optimización novedoso basado en las reglas de supervivencia de porcellio scaber ", Y. Zhang y S. Li

Enlaces externos

  • COSP