Content deleted Content added
Citation bot (talk | contribs) m Removed parameters. | You can use this bot yourself. Report bugs here. | User-activated. |
m remove nowiki |
||
| (17 intermediate revisions by 13 users not shown) | |||
Line 1:
'''Simulation-based optimization''' (also known as simply '''simulation optimization''') integrates [[optimization (mathematics)|optimization]] techniques into [[computer simulation|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’
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
Specific simulation–based optimization methods can be chosen according to
[[File:Slide1 1.jpg|thumb|Fig.1 Classification of simulation based optimization according to variable types]]
[[Optimization (computer science)|Optimization]] exists in two main branches of
''Optimization [[Parametric programming|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.<ref name=":0" />
Line 14:
== Simulation-based optimization methods ==
<ref name=Fu>{{cite book|editor-last=Fu|editor-first=Michael
<ref>Spall, J.C. (2003). ''Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control''. Hoboken: Wiley.</ref>
=== Statistical ranking and selection methods (R/S) ===
Line 21 ⟶ 23:
In the simulation optimization setting, applicable methods include indifference zone approaches, optimal computing budget allocation, and knowledge gradient algorithms.
=== Response surface
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.<ref>Rahimi Mazrae Shahi, M., Fallah Mehdipour, E. and Amiri, M. (2016), [https://onlinelibrary.wiley.com/doi/abs/10.1111/itor.12150 Optimization using simulation and response surface methodology with an application on subway train scheduling]. Intl. Trans. in Op. Res., 23: 797–811. {{doi
=== Heuristic methods ===
[[Heuristic (computer science)|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
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.
=== Stochastic approximation ===
[[Stochastic approximation]] is used when the function cannot be computed directly, only estimated via noisy observations. In
:<math>\underset{\text{x}\in\theta}{\min}f\bigl(\text{x}\bigr) = \underset{\text{x}\in\theta}{\min}\Epsilon[F\bigl(\text{x,y})]</math>
Line 41 ⟶ 43:
=== 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.<ref>Conn, A. R.; [[Katya Scheinberg|Scheinberg, K.]]; [[Luis Nunes Vicente|Vicente, L. N.]] (2009). [http://www.mat.uc.pt/~lnv/idfo/ ''Introduction to Derivative-Free Optimization'']. MPS-SIAM Book Series on Optimization. Philadelphia: SIAM. Retrieved 2014-01-18.</ref>
For unconstrained optimization problems, it has the form:
Line 49 ⟶ 51:
The limitations of derivative-free optimization:
1.
<ref name=Fu/>
.<ref>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</ref>
2. When confronted with minimizing non-convex functions, it will show its limitation.
3. Derivative-free optimization methods are relatively simple and easy
=== 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
One dynamic basic model has two features:
Line 72 ⟶ 76:
:<math>k</math> represents the index of discrete time.
:<math>x_k</math> is the state of the time k, it contains the past information and
:<math>u_k</math> is the control variable.
Line 80 ⟶ 84:
For the cost function, it has the form:
:<math>g_N(X_N) + \sum_{k=0}^{N-1}
<math>g_N(X_N)</math> is the cost at the end of the process.
Line 92 ⟶ 96:
== Limitations ==
Simulation
==References==
| |||