La optimización basada en simulación (también conocida como simplemente optimización de simulación ) integra técnicas de optimización en el modelado y análisis de simulación . Debido a la complejidad de la simulación, la función objetivo puede resultar difícil y costosa de evaluar. Por lo general, el modelo de simulación subyacente es estocástico, por lo que la función objetivo debe estimarse mediante técnicas de estimación estadística (lo que se denomina análisis de salida en la metodología de simulación).
Una vez que se modela matemáticamente un sistema, las simulaciones por computadora proporcionan información sobre su comportamiento. Los métodos de simulación paramétrica se pueden utilizar para mejorar el rendimiento de un sistema. En este método, la entrada de cada variable se varía con otros parámetros que permanecen constantes y se observa el efecto sobre el objetivo de diseño. Este es un método que requiere mucho tiempo y mejora parcialmente el rendimiento. Para obtener la solución óptima con un cálculo y tiempo mínimos, el problema se resuelve de forma iterativa donde en cada iteración la solución se acerca a la solución óptima. Estos métodos se conocen como "optimización numérica" u "optimización basada en simulación". [1]
En el experimento de simulación, el objetivo es evaluar el efecto de diferentes valores de variables de entrada en un sistema. Sin embargo, a veces el interés radica en encontrar el valor óptimo para las variables de entrada en términos de los resultados del sistema. Una forma podría ser ejecutar experimentos de simulación para todas las posibles variables de entrada. Sin embargo, este enfoque no siempre es práctico debido a varias situaciones posibles y simplemente hace que sea imposible ejecutar experimentos para cada escenario. Por ejemplo, puede haber demasiados valores posibles para las variables de entrada, o el modelo de simulación puede ser demasiado complicado y costoso de ejecutar para valores de variable de entrada subóptimos. En estos casos, el objetivo es encontrar valores óptimos para las variables de entrada en lugar de probar todos los valores posibles. Este proceso se llama optimización de simulación. [2]
Se pueden elegir métodos de optimización específicos basados en simulación de acuerdo con la Figura 1 en función de los tipos de variables de decisión. [3]
La optimización existe en dos ramas principales de la investigación de operaciones:
Optimización paramétrica (estática) : el objetivo es encontrar los valores de los parámetros, que son "estáticos" para todos los estados, con el objetivo de maximizar o minimizar una función. En este caso, se puede utilizar la programación matemática , como la programación lineal . En este escenario, la simulación ayuda cuando los parámetros contienen ruido o la evaluación del problema demandaría un tiempo excesivo de computadora, debido a su complejidad. [4]
Control de optimización (dinámico) : se utiliza principalmente en informática e ingeniería eléctrica . El control óptimo es por estado y los resultados cambian en cada uno de ellos. Se puede utilizar la programación matemática, así como la programación dinámica. En este escenario, la simulación puede generar muestras aleatorias y resolver problemas complejos y de gran escala. [4]
Métodos de optimización basados en simulación
A continuación se analizan algunos enfoques importantes en la optimización de la simulación. [5] [6]
Clasificación estadística y métodos de selección (R / S)
Los métodos de clasificación y selección están diseñados para problemas en los que las alternativas son fijas y conocidas, y la simulación se utiliza para estimar el rendimiento del sistema. En el entorno de optimización de la simulación, los métodos aplicables incluyen enfoques de zona de indiferencia, asignación de presupuesto de cálculo óptimo y algoritmos de gradiente de conocimiento.
Metodología de superficie de respuesta (RSM)
En la metodología de superficie de respuesta , el objetivo es encontrar la relación entre las variables de entrada y las variables de respuesta. El proceso comienza por intentar ajustar un modelo de regresión lineal. Si el valor P resulta ser bajo, se implementará una regresión polinomial de mayor grado, que suele ser cuadrática. El proceso de encontrar una buena relación entre las variables de entrada y respuesta se realizará para cada prueba de simulación. En la optimización de la simulación, el método de superficie de respuesta se puede utilizar para encontrar las mejores variables de entrada que produzcan los resultados deseados en términos de variables de respuesta. [7]
Métodos heurísticos
Los métodos heurísticos cambian la precisión por la velocidad. Su objetivo es encontrar una buena solución más rápido que los métodos tradicionales, cuando son demasiado lentos o no logran resolver el problema. Por lo general, encuentran el valor óptimo local en lugar del valor óptimo; sin embargo, los valores se consideran lo suficientemente cercanos a la solución final. Ejemplos de este tipo de métodos incluyen la búsqueda tabú y los algoritmos genéticos . [4]
Los metamodelos permiten a los investigadores obtener resultados de modelos aproximados fiables sin ejecutar simulaciones informáticas costosas y que consumen mucho tiempo. Por lo tanto, el proceso de optimización del modelo puede requerir menos tiempo y costo de cálculo. [8]
Aproximación estocástica
La aproximación estocástica se utiliza cuando la función no se puede calcular directamente, solo se estima mediante observaciones ruidosas. En estos escenarios, este método (o familia de métodos) busca los extremos de estas funciones. La función objetivo sería: [9]
- es una variable aleatoria que representa el ruido.
- es el parámetro que minimiza .
- es el dominio del parámetro .
Métodos de optimización sin derivadas
La optimización sin derivadas es un tema de optimización matemática. Este método se aplica a un determinado problema de optimización cuando sus derivados no están disponibles o no son fiables. Los métodos sin derivadas establecen un modelo basado en valores de función de muestra o extraen directamente un conjunto de valores de función de muestra sin explotar un modelo detallado. Dado que no necesita derivados, no se puede comparar con los métodos basados en derivados. [10]
Para problemas de optimización sin restricciones, tiene la forma:
Las limitaciones de la optimización sin derivadas:
1. Algunos métodos no pueden manejar problemas de optimización con más de unas pocas variables; los resultados no suelen ser tan precisos. Sin embargo, existen numerosos casos prácticos en los que los métodos sin derivadas han tenido éxito en problemas de optimización de simulación no triviales que incluyen aleatoriedad que se manifiesta como "ruido" en la función objetivo. Ver, por ejemplo, lo siguiente [5] . [11]
2. Cuando se enfrente a la minimización de funciones no convexas, mostrará su limitación.
3. Los métodos de optimización sin derivadas son relativamente simples y fáciles, pero, como la mayoría de los métodos de optimización, se requiere cierto cuidado en la implementación práctica (por ejemplo, al elegir los parámetros del algoritmo).
Programación dinámica y programación neurodinámica
Programación dinámica
La programación dinámica se ocupa de situaciones en las que las decisiones se toman en etapas. La clave de este tipo de problemas es compensar los costos presentes y futuros. [12]
Un modelo básico dinámico tiene dos características:
1) Tiene un sistema dinámico de tiempo discreto.
2) La función de costo es aditiva con el tiempo.
Para funciones discretas, la programación dinámica tiene la forma:
- representa el índice de tiempo discreto.
- es el estado del tiempo k, contiene la información pasada y la prepara para una optimización futura.
- es la variable de control.
- es el parámetro aleatorio.
Para la función de costo, tiene la forma:
es el costo al final del proceso.
Como el costo no se puede optimizar de manera significativa, se puede utilizar el valor esperado:
Programación neurodinámica
La programación neurodinámica es lo mismo que la programación dinámica, excepto que la primera tiene el concepto de arquitecturas de aproximación. Combina inteligencia artificial , algoritmos basados en simulación y técnicas de enfoque funcional. "Neuro" en este término se origina en la comunidad de inteligencia artificial. Significa aprender a tomar mejores decisiones para el futuro a través de un mecanismo integrado basado en el comportamiento actual. La parte más importante de la programación neurodinámica es construir una red neuronal entrenada para el problema óptimo. [13]
Limitaciones
La optimización basada en simulación tiene algunas limitaciones, como la dificultad de crear un modelo que imite el comportamiento dinámico de un sistema de una manera que se considere suficientemente buena para su representación. Otro problema es la complejidad en la determinación de parámetros incontrolables tanto del sistema del mundo real como de la simulación. Además, solo se puede obtener una estimación estadística de valores reales. No es fácil determinar la función objetivo, ya que es resultado de mediciones, que pueden ser perjudiciales para las soluciones. [14] [15]
Referencias
- ^ Nguyen, Anh-Tuan, Sigrid Reiter y Philippe Rigo. " Una revisión de los métodos de optimización basados en simulación aplicados al análisis del rendimiento de edificios ". Applied Energy 113 (2014): 1043–1058.
- ^ Carson, Yolanda y Anu Maria. " Optimización de la simulación: métodos y aplicaciones ". Actas de la 29ª Conferencia de simulación de invierno . Sociedad de Informática IEEE, 1997.
- ^ Jalali, Hamed e Inneke Van Nieuwenhuyse. " Optimización de la simulación en la reposición de inventarios: una clasificación ". Transacciones IIE 47.11 (2015): 1217-1235.
- ^ a b c Abhijit Gosavi, Optimización basada en simulación: técnicas de optimización paramétrica y aprendizaje por refuerzo , Springer, segunda edición (2015)
- ^ a b Fu, Michael, editor (2015). Manual de optimización de simulación . Saltador.
- ^ Spall, JC (2003). Introducción a la búsqueda y optimización estocásticas: estimación, simulación y control . Hoboken: Wiley.
- ^ Rahimi Mazrae Shahi, M., Fallah Mehdipour, E. y Amiri, M. (2016), Optimización mediante metodología de superficie de respuesta y simulación con una aplicación sobre programación de trenes subterráneos . Intl. Trans. en Op. Res., 23: 797–811. doi : 10.1111 / itor.12150
- ^ Yousefi, Milad; Yousefi, musulmán; Ferreira, Ricardo Poley Martins; Kim, Joong Hoon; Fogliatto, Flavio S. (2018). "Algoritmo genético caótico y enfoque de metamodelado de conjunto Adaboost para la planificación óptima de recursos en los departamentos de emergencia". Inteligencia artificial en Medicina . 84 : 23–33. doi : 10.1016 / j.artmed.2017.10.002 . PMID 29054572 .
- ^ Powell, W. (2011). Programación dinámica aproximada que resuelve las maldiciones de la dimensionalidad (2ª ed., Serie Wiley en Probabilidad y Estadística). Hoboken: Wiley.
- ^ Conn, AR; Scheinberg, K .; Vicente, LN (2009). Introducción a la optimización sin derivadas . Serie de libros MPS-SIAM sobre optimización. Filadelfia: SIAM. Consultado el 18 de enero de 2014.
- ^ Fu, MC, Hill, SD Optimización de sistemas de eventos discretos mediante aproximación estocástica de perturbación simultánea. IIE Transactions 29, 233–243 (1997). https://doi.org/10.1023/A:1018523313043
- ^ Cooper, Leon; Cooper, Mary W. Introducción a la programación dinámica. Nueva York: Pergamon Press, 1981
- ^ Van Roy, B., Bertsekas, D., Lee, Y. y Tsitsiklis, J. (1997). Enfoque de programación neurodinámica para la gestión de inventario de minoristas . Actas de la Conferencia IEEE sobre Decisión y Control, 4 , 4052-4057.
- ^ Prasetio, Y. (2005). Optimización basada en simulación para sistemas estocásticos complejos . Universidad de Washington.
- ^ Deng, G. y Ferris, Michael. (2007). Optimización basada en simulación, disertaciones y tesis de ProQuest