stringtranslate.com

Optimización estocástica

La optimización estocástica ( OE ) son métodos de optimización que generan y utilizan variables aleatorias . Para los problemas de optimización estocástica , las funciones objetivo o restricciones son aleatorias. La optimización estocástica también incluye métodos con iteraciones aleatorias . Algunos métodos híbridos utilizan iteraciones aleatorias para resolver problemas estocásticos, combinando ambos significados de la optimización estocástica. [1] Los métodos de optimización estocástica generalizan los métodos deterministas para problemas deterministas.

Métodos para funciones estocásticas

Los datos de entrada parcialmente aleatorios surgen en áreas como la estimación y el control en tiempo real, la optimización basada en simulación donde se ejecutan simulaciones de Monte Carlo como estimaciones de un sistema real, [2] [3] y problemas donde hay un error experimental (aleatorio) en las mediciones 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 próximos pasos. Los métodos de esta clase incluyen:

Métodos de búsqueda aleatorios

Por otra parte, 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] Dicha aleatoriedad también puede hacer que el método sea menos sensible a los errores de modelado. Otra ventaja es que la aleatoriedad en el proceso de búsqueda se puede utilizar para obtener estimaciones de intervalo del mínimo de una función a través de estadísticas de valores extremos. [8] [9] Además, la aleatoriedad inyectada puede permitir que el método escape de un óptimo local y, finalmente, se acerque a un óptimo global. De hecho, se sabe que este principio de aleatoriedad es una forma simple y efectiva de obtener algoritmos con un rendimiento casi seguro y 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 fue mal diseñado desde el principio. [21] Fred W. Glover [22] sostiene que la dependencia de elementos aleatorios puede impedir el desarrollo de componentes deterministas más inteligentes y mejores. La forma en que se presentan habitualmente 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 de la dispersión), también puede resultar en un sesgo positivo hacia la aleatoriedad.

Véase también

Referencias

  1. ^ Spall, JC (2003). Introducción a la búsqueda y optimización estocástica. Wiley. ISBN 978-0-471-33052-3.
  2. ^ Fu, MC (2002). "Optimización para simulación: teoría vs. práctica". INFORMS Journal on Computing . 14 (3): 192–227. doi :10.1287/ijoc.14.3.192.113.
  3. ^ MC Campi y S. Garatti. La viabilidad exacta de soluciones aleatorias de programas convexos inciertos. SIAM J. on Optimization, 19, no.3: 1211–1230, 2008.[1]
  4. ^ Robbins, H.; Monro, S. (1951). "Un método de aproximación estocástica". 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". IEEE Transactions on Automatic Control . 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. ^ M. de Carvalho (2011). "Intervalos de confianza para el mínimo de una función utilizando estadísticas de valores extremos" (PDF) . Revista Internacional de Modelado Matemático y Optimización Numérica . 2 (3): 288–296. doi :10.1504/IJMMNO.2011.040793.
  9. ^ M. de Carvalho (2012). "Una generalización del método Solis-Wets" (PDF) . Revista de Planificación e Inferencia Estadística . 142 (3): 633‒644. doi :10.1016/j.jspi.2011.08.016.
  10. ^ S. Kirkpatrick; CD Gelatt; MP Vecchi (1983). "Optimización mediante recocido simulado". Science . 220 (4598): 671–680. Bibcode :1983Sci...220..671K. CiteSeerX 10.1.1.123.7607 . doi :10.1126/science.220.4598.671. PMID  17813860. S2CID  205939. 
  11. ^ DH Wolpert; SR Bieniawski; DG Rajnarayan (2011). "Colectivos de probabilidad en optimización". Instituto Santa Fe .
  12. ^ Battiti, Roberto; Gianpietro Tecchiolli (1994). «La búsqueda tabú reactiva» (PDF) . Revista ORSA de Informática . 6 (2): 126-140. doi :10.1287/ijoc.6.2.126.
  13. ^ Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Búsqueda reactiva y optimización inteligente . Springer Verlag . ISBN 978-0-387-09623-0.
  14. ^ Rubinstein, RY ; Kroese, DP (2004). El método de la entropía cruzada . Springer-Verlag. ISBN 978-0-387-21240-1.
  15. ^ Zhigljavsky, AA (1991). Teoría de la búsqueda aleatoria global . Kluwer Academic. ISBN 978-0-7923-1122-5.
  16. ^ Kagan E.; Ben-Gal I. (2014). "Un algoritmo de prueba grupal con aprendizaje informativo en línea". IIE Transactions . 46 (2): 164–184. doi :10.1080/0740817X.2013.803639. S2CID  18588494.
  17. ^ W. Wenzel; K. Hamacher (1999). "Enfoque de tunelización estocástica para la optimización global de paisajes complejos de energía potencial". Phys. Rev. Lett . 82 (15): 3003. arXiv : physics/9903008 . Código Bibliográfico :1999PhRvL..82.3003W. doi :10.1103/PhysRevLett.82.3003. S2CID  5113626.
  18. ^ E. Marinari; G. Parisi (1992). "Templado simulado: un nuevo esquema monte carlo". Eurofis. Lett . 19 (6): 451–458. arXiv : hep-lat/9205018 . Código bibliográfico : 1992EL......19..451M. doi :10.1209/0295-5075/19/6/002. S2CID  12321327.
  19. ^ 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.
  20. ^ 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 .
  21. ^ Yudkowsky, Eliezer. "Peor que el azar - LessWrong".
  22. ^ Glover, F. (2007). "Búsqueda tabú: dominios desconocidos". Anales de investigación de operaciones . 149 : 89–98. CiteSeerX 10.1.1.417.8223 . doi :10.1007/s10479-006-0113-9. S2CID  6854578. 

Lectura adicional

Enlaces externos