Simulation-based optimization

From HandWiki

Simulation-based optimization (also known as simply simulation optimization) integrates optimization techniques into simulation modeling and analysis. Because of the complexity of the simulation, the objective function may become difficult and expensive to evaluate. Usually, the underlying simulation model is stochastic, so that the objective function must be estimated using statistical estimation techniques (called output analysis in simulation methodology). Once a system is mathematically modeled, computer-based simulations provide information about its behavior. Parametric simulation methods can be used to improve the performance of a system. In this method, the input of each variable is varied with other parameters remaining constant and the effect on the design objective is observed. This is a time-consuming method and improves the performance partially. To obtain the optimal solution with minimum computation and time, the problem is solved iteratively where in each iteration the solution moves closer to the optimum solution. Such methods are known as ‘numerical optimization’, ‘simulation-based optimization’[1] or 'simulation-based multi-objective optimization' used when more than one objective is involved.

In simulation experiment, the goal is to evaluate the effect of different values of input variables on a system. However, the interest is sometimes in finding the optimal value for input variables in terms of the system outcomes. One way could be running simulation experiments for all possible input variables. However, this approach is not always practical due to several possible situations and it just makes it intractable to run experiments for each scenario. For example, there might be too many possible values for input variables, or the simulation model might be too complicated and expensive to run for a large set of input variable values. In these cases, the goal is to iterative find optimal values for the input variables rather than trying all possible values. This process is called simulation optimization.[2]

Specific simulation–based optimization methods can be chosen according to Figure 1 based on the decision variable types.[3]

Fig.1 Classification of simulation based optimization according to variable types

Optimization exists in two main branches of operations research:

Optimization parametric (static) – The objective is to find the values of the parameters, which are “static” for all states, with the goal of maximizing or minimizing a function. In this case, one can use mathematical programming, such as linear programming. In this scenario, simulation helps when the parameters contain noise or the evaluation of the problem would demand excessive computer time, due to its complexity.[4]

Optimization control (dynamic) – This is used largely in computer science and electrical engineering. The optimal control is per state and the results change in each of them. One can use mathematical programming, as well as dynamic programming. In this scenario, simulation can generate random samples and solve complex and large-scale problems.[4]

Simulation-based optimization methods

Some important approaches in simulation optimization are discussed below. [5] [6]

Statistical ranking and selection methods (R/S)

Ranking and selection methods are designed for problems where the alternatives are fixed and known, and simulation is used to estimate the system performance. In the simulation optimization setting, applicable methods include indifference zone approaches, optimal computing budget allocation, and knowledge gradient algorithms.

Response surface methodology (RSM)

In response surface methodology, the objective is to find the relationship between the input variables and the response variables. The process starts from trying to fit a linear regression model. If the P-value turns out to be low, then a higher degree polynomial regression, which is usually quadratic, will be implemented. The process of finding a good relationship between input and response variables will be done for each simulation test. In simulation optimization, response surface method can be used to find the best input variables that produce desired outcomes in terms of response variables.[7]

Heuristic methods

Heuristic methods change accuracy by speed. Their goal is to find a good solution faster than the traditional methods, when they are too slow or fail in solving the problem. Usually they find local optimal instead of the optimal value; however, the values are considered close enough of the final solution. Examples of these kinds of methods include tabu search and genetic algorithms.[4]

Metamodels enable researchers to obtain reliable approximate model outputs without running expensive and time-consuming computer simulations. Therefore, the process of model optimization can take less computation time and cost.[8]

Stochastic approximation

Stochastic approximation is used when the function cannot be computed directly, only estimated via noisy observations. In these scenarios, this method (or family of methods) looks for the extrema of these function. The objective function would be:[9]

[math]\displaystyle{ \underset{\text{x}\in\theta}{\min}f\bigl(\text{x}\bigr) = \underset{\text{x}\in\theta}{\min}\Epsilon[F\bigl(\text{x,y})] }[/math]
[math]\displaystyle{ y }[/math] is a random variable that represents the noise.
[math]\displaystyle{ x }[/math] is the parameter that minimizes [math]\displaystyle{ f\bigl(\text{x}\bigr) }[/math].
[math]\displaystyle{ \theta }[/math] is the domain of the parameter [math]\displaystyle{ x }[/math].

Derivative-free optimization methods

Derivative-free optimization is a subject of mathematical optimization. This method is applied to a certain optimization problem when its derivatives are unavailable or unreliable. Derivative-free methods establish a model based on sample function values or directly draw a sample set of function values without exploiting a detailed model. Since it needs no derivatives, it cannot be compared to derivative-based methods.[10]

For unconstrained optimization problems, it has the form:

[math]\displaystyle{ \underset{\text{x}\in\R^n}{\min}f\bigl(\text{x}\bigr) }[/math]

The limitations of derivative-free optimization:

1. Some methods cannot handle optimization problems with more than a few variables; the results are usually not so accurate. However, there are numerous practical cases where derivative-free methods have been successful in non-trivial simulation optimization problems that include randomness manifesting as "noise" in the objective function. See, for example, the following [5] .[11]

2. When confronted with minimizing non-convex functions, it will show its limitation.

3. Derivative-free optimization methods are relatively simple and easy, but, like most optimization methods, some care is required in practical implementation (e.g., in choosing the algorithm parameters).

Dynamic programming and neuro-dynamic programming

Dynamic programming

Dynamic programming deals with situations where decisions are made in stages. The key to this kind of problem is to trade off the present and future costs.[12]

One dynamic basic model has two features:

1) It has a discrete time dynamic system.

2) The cost function is additive over time.

For discrete features, dynamic programming has the form:

[math]\displaystyle{ x_{k+1} = f_k(x_{k},u_{k},w_{k}) , k=0,1,...,N-1 }[/math]
[math]\displaystyle{ k }[/math] represents the index of discrete time.
[math]\displaystyle{ x_k }[/math] is the state of the time k, it contains the past information and prepares it for future optimization.
[math]\displaystyle{ u_k }[/math] is the control variable.
[math]\displaystyle{ w_k }[/math] is the random parameter.

For the cost function, it has the form:

[math]\displaystyle{ g_N(X_N) + \sum_{k=0}^{N-1} g_k(x_k,u_k,W_k) }[/math]

[math]\displaystyle{ g_N(X_N) }[/math] is the cost at the end of the process.

As the cost cannot be optimized meaningfully, it can be used the expect value:

[math]\displaystyle{ E\{g_N(X_N) + \sum_{k=0}^{N-1} g_k(x_k,u_k,W_k) \} }[/math]

Neuro-dynamic programming

Neuro-dynamic programming is the same as dynamic programming except that the former has the concept of approximation architectures. It combines artificial intelligence, simulation-base algorithms, and functional approach techniques. “Neuro” in this term origins from artificial intelligence community. It means learning how to make improved decisions for the future via built-in mechanism based on the current behavior. The most important part of neuro-dynamic programming is to build a trained neuro network for the optimal problem.[13]

Limitations

Simulation-based optimization has some limitations, such as the difficulty of creating a model that imitates the dynamic behavior of a system in a way that is considered good enough for its representation. Another problem is complexity in the determining uncontrollable parameters of both real-world system and simulation. Moreover, only a statistical estimation of real values can be obtained. It is not easy to determine the objective function, since it is a result of measurements, which can be harmful to the solutions.[14][15]

References

  1. ↑ Nguyen, Anh-Tuan, Sigrid Reiter, and Philippe Rigo. "A review on simulation-based optimization methods applied to building performance analysis."Applied Energy 113 (2014): 1043–1058.
  2. ↑ Carson, Yolanda, and Anu Maria. "Simulation optimization: methods and applications." Proceedings of the 29th Winter Simulation Conference. IEEE Computer Society, 1997.
  3. ↑ Jalali, Hamed, and Inneke Van Nieuwenhuyse. "Simulation optimization in inventory replenishment: a classification." IIE Transactions 47.11 (2015): 1217-1235.
  4. ↑ 4.0 4.1 4.2 Abhijit Gosavi, Simulation‐Based Optimization: Parametric Optimization Techniques and Reinforcement Learning, Springer, 2nd Edition (2015)
  5. ↑ 5.0 5.1 Fu, Michael, ed (2015). Handbook of Simulation Optimization. Springer. https://www.springer.com/us/book/9781493913831. 
  6. ↑ Spall, J.C. (2003). Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Hoboken: Wiley.
  7. ↑ Rahimi Mazrae Shahi, M., Fallah Mehdipour, E. and Amiri, M. (2016), Optimization using simulation and response surface methodology with an application on subway train scheduling. Intl. Trans. in Op. Res., 23: 797–811. doi:10.1111/itor.12150
  8. ↑ Yousefi, Milad; Yousefi, Moslem; Ferreira, Ricardo Poley Martins; Kim, Joong Hoon; Fogliatto, Flavio S. (2018). "Chaotic genetic algorithm and Adaboost ensemble metamodeling approach for optimum resource planning in emergency departments". Artificial Intelligence in Medicine 84: 23–33. doi:10.1016/j.artmed.2017.10.002. PMID 29054572. 
  9. ↑ Powell, W. (2011). Approximate Dynamic Programming Solving the Curses of Dimensionality (2nd ed., Wiley Series in Probability and Statistics). Hoboken: Wiley.
  10. ↑ Conn, A. R.; Scheinberg, K.; Vicente, L. N. (2009). Introduction to Derivative-Free Optimization. MPS-SIAM Book Series on Optimization. Philadelphia: SIAM. Retrieved 2014-01-18.
  11. ↑ Fu, M.C., Hill, S.D. Optimization of discrete event systems via simultaneous perturbation stochastic approximation. IIE Transactions 29, 233–243 (1997). https://doi.org/10.1023/A:1018523313043
  12. ↑ Cooper, Leon; Cooper, Mary W. Introduction to dynamic programming. New York: Pergamon Press, 1981
  13. ↑ Van Roy, B., Bertsekas, D., Lee, Y., & Tsitsiklis, J. (1997). Neuro-dynamic programming approach to retailer inventory management. Proceedings of the IEEE Conference on Decision and Control, 4, 4052-4057.
  14. ↑ Prasetio, Y. (2005). Simulation-based optimization for complex stochastic systems. University of Washington.
  15. ↑ Deng, G., & Ferris, Michael. (2007). Simulation-based Optimization, ProQuest Dissertations and Theses



Retrieved from "https://handwiki.org/wiki/index.php?title=Simulation-based_optimization&oldid=3360590"