Optimización estocástica

La optimización estocástica ( OE ) comprende métodos de optimización que generan y utilizan variables aleatorias . En los problemas de optimización estocástica , las funciones objetivo o las 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.

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 existe 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 siguientes pasos. Los métodos de esta clase incluyen:

• aproximación estocástica (SA), por Robbins y Monro (1951) ^{[ 4 ]}
• descenso de gradiente estocástico
• SA de diferencias finitas por Kiefer y Wolfowitz (1952) ^{[ 5 ]}
• SA de perturbación simultánea por Spall (1992) ^{[ 6 ]}
• optimización de escenarios

Por otro lado, incluso cuando el conjunto de datos consta de 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 mediante estadísticas de valores extremos. ^{[ 8 ] [ 9 ]} Además, la aleatoriedad introducida puede permitir que el método escape de un óptimo local y eventualmente se aproxime a un óptimo global. De hecho, se sabe que este principio de aleatorización 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:

• recocido simulado por S. Kirkpatrick, CD Gelatt y MP Vecchi (1983) ^{[ 10 ]}
• recocido cuántico
• Colectivos de probabilidad por DH Wolpert, SR Bieniawski y DG Rajnarayan (2011) ^{[ 11 ]}
• Optimización de búsqueda reactiva (RSO) por Roberto Battiti , G. Tecchiolli (1994), ^{[ 12 ]} revisada recientemente en el libro de referencia ^{[ 13 ]}
• método de entropía cruzada de Rubinstein y Kroese (2004) ^{[ 14 ]}
• búsqueda aleatoria por Anatoly Zhigljavsky (1991) ^{[ 15 ]}
• Búsqueda de información ^{[ 16 ]}
• tunelización estocástica ^{[ 17 ]}
• templado paralelo también conocido como intercambio de réplicas ^{[ 18 ]}
• ascenso de colinas estocástico
• algoritmos de enjambre
• algoritmos evolutivos
  • algoritmos genéticos de Holland (1975) ^{[ 19 ]}
  • estrategias de evolución
• algoritmo de optimización y modificación de objetos en cascada (2016) ^{[ 20 ]}

Por el contrario, algunos autores han argumentado que la aleatorización solo puede mejorar un algoritmo determinista si este 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 suelen presentar los resultados de los algoritmos de optimización estocástica (por ejemplo, presentando solo el promedio, o incluso el mejor, de N ejecuciones sin mencionar la dispersión) también puede generar un sesgo positivo hacia la aleatoriedad.

• Optimización global
• Aprendizaje automático
• Optimización de escenarios
• proceso gaussiano
• Modelo de espacio de estados
• Control predictivo basado en modelos
• Programación no lineal
• Valor entrópico en riesgo

• Michalewicz, Z. y Fogel, DB (2000), Cómo resolverlo: Heurísticas modernas , Springer-Verlag, Nueva York.

• COSP