Simulation-based optimization: Difference between revisions

Revision as of 23:47, 18 May 2016

Revision as of 09:49, 19 May 2016

Line 3:

Once a system is mathematically modeled, computer-based simulations provide the 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’ or ‘simulation-based optimization’.<ref>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.</ref>

In simulation experiment, the goal is to evaluate the effect of different values of input variables on a system, which is called running simulation experiments. However sometimes there are interest 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 experiment for each scenario. For example, there might be so many possible values for input variables, or simulation model might be so complicated and expensive to run for suboptimal input variable values. In these cases, the goal is to find optimal values for input variables rather than trying all possible values. This process is called simulation optimization.<ref>Carson, Yolanda, and Anu Maria. "Simulation optimization: methods and applications."  ''Proceedings of the 29th conference on Winter simulation''. IEEE Computer Society, 1997.</ref>

Specific simulation based optimization methods can be chosen according to figure 1 based on the decision variable types.<ref>Jalali, Hamed, and Inneke Van Nieuwenhuyse. "Simulation optimization in inventory replenishment: a classification." IIE Transactions 47.11 (2015): 1217-1235.</ref>

Line 11:

''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 maximize or minimize a function. In this case, there is the use of mathematical programming, such as linear programing. In this scenario, simulation helps when the parameters contain noise or the evaluation of the problem would demand excess of computer time, due to its complexity.<ref name=":0" />

''Optimization [[Optimal control|control]] (dynamic)'' – used largely in computer sciences and electrical engineering, what results in many papers and projects in these fields. The optimal control is per state and the results change in each of them. There is use of mathematical programming, as well as dynamic programming. In this scenario, simulation can generate random samples and solve complex and large-scale problems.<ref name=":0">Abhijit Gosavi,  Simulation‐Based Optimization: Parametric Optimization Techniques and Reinforcement Learning,  Springer,  2nd  Edition (2015)</ref>

== Simulation-based optimization methods ==

Line 23:

=== Stochastic approximation ===

[[Stochastic approximation]] is used when the function cannot be computed directly, only estimated via noisy observations. In this scenarios, this method (or family of methods) looks for the extrema of these function. The objective function would be:<ref>Powell, W. (2011).  ''Approximate Dynamic Programming Solving the Curses of Dimensionality''  (2nd ed., Wiley Series in Probability and Statistics). Hoboken: Wiley.</ref>:

<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>

<math>y</math>  is a random variable that represents the noise.

<math>x</math> is the parameter that minimizes <math>f\bigl(\text{x}\bigr)</math>.

Line 34:

=== 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. Derivate-free method establishes model based on sample function values or directly draw a sample set of function values without exploiting detailed model. Since it needs no derivatives, it cannot be compared to derivative-based methods.<ref>Conn, A. R.; Scheinberg, K.; 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 a form:

Line 48:

3. Derivative-free optimization methods is simple and easy, however, it is not so good in theory and in practice.

=== Dynamic programming  and neuro-dynamic programming ===

==== Dynamic programming ====

[[Dynamic programming]] deals with situations where decisions are made in stage. The key to this kind of problems is to trade off the present and future costs.<ref>Cooper, Leon; Cooper, Mary W.  Introduction to dynamic programming. New York: Pergamon Press, 1981</ref>

One dynamic basic model has two features:

1) Has a discrete time dynamic system.

2) The cost function is additive over time.

Line 65:

<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 prepare it for the future optimization.

<math>u_k</math> is the control variable.

<math>w_k</math>  is the random parameter.

For cost function, it has the form:

Line 75:

<math>g_N(X_N) + \sum_{k=0}^{N-1} gk(x_k,u_k,W_k)</math>

<math>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:

Line 82:

==== 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.<ref>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.</ref>

== Limitations ==

Simulation base optimization has some limitations, such as the difficulty of create a model that imitates the dynamic behavior of the system in a way that is considered good enough for its representation. Other problem is how complex it is the determination of uncontrollable parameters of the real-world system and of the simulation. Moreover, only a statistical estimation of the real values can be obtained. It is not easy to determine the objective function, since it is result of measurements, what can be harmful for the solutions.<ref>Prasetio, Y. (2005).  ''Simulation-based optimization for complex stochastic systems''. University of Washington.</ref><ref>Deng, G., & Ferris, Michael. (2007).  ''Simulation-based Optimization,''  ProQuest Dissertations and Theses</ref>

== Application ==

Line 91:

[[File:Model example.jpg|thumb|Fig 2 Simulation-based optimization for building performance studies]]

The literature presents many uses of Simulation Based Optimization. Nguyen et al.,<ref>Nguyen, S., Reiter, P., Rigo, A., & Anh-Tuan Nguyen, S. (2014). A review on simulation-based optimization methods applied to building performance analysis.''Applied Energy,''  ''113'', 1043-1058.</ref>, for example, discuss in their paper the use of simulation-based optimization for supporting the project of high performance buildings, such as green buildings. The figure 2 presents their method simplified.

Saif et al.<ref>Saif, A., Ravikumar Pandi, V., Zeineldin, H., & Kennedy, S. (2013). Optimal allocation of distributed energy resources through simulation-based optimization.  ''Electric Power Systems Research,''  ''104'', 1-8.</ref> present another possible use of Simulation Based Optimization: allocate energy resources in an imperfect power distribution system, in an optimal way, considering ___location and capacity.

==References==