The comparison of selected algorithms of simulation optimization.

Vazan, Pavel ; Moravcik, Oliver ; Krizanova, Gabriela 等

1. INTRODUCTION

The simulation optimization is the most significant simulation technology in the last years according to many authors. It eliminates one of disadvantages of simulation and it is used to find the best solution from many simulation experiments.

The combination of simulation and optimization has already been expected for a long time, but only in the last decade it has achieved real development.

Today, leading simulation software vendors have introduced optimizers that are fully integrated into their simulation packages. Now simulation practitioners have access to robust optimization algorithms and they are using them to solve a variety of "real world" simulation optimization problems (Waller, 2006).

There also exist many barriers which have to be over-came for broader simulation optimization using. Great scepticism predominates to the results of simulation optimization in concrete applications (Boesel, 2001).

2. SIMULATION OPTIMIZATION METHODS

Understandably there are a lot of methods that could be used for simulation optimization. The major simulation optimization methods are displayed on Fig. 1. However, most developers have involved heuristic search methods into the software packages for simulation optimization. The heuristic search algorithms provide good, reasonably fast results on a wide variety of problems.

We want to mention a few important heuristic algorithms. Here belong genetics algorithms, evolutionary strategies, simulated annealing, simplex search, tabu search (Tanuska & Kopcek, 2007).

The computational demands of simulation optimization cause, that the practical usage of simulation optimization is possible without software support. The software packages are solved as plug-in modules which are added to the basic simulation platform. The approach to simulation optimization is based on viewing of the simulation model as a black box function evaluator. The optimizer chooses a set of values for the input parameters and uses the responses generated by the simulation model to make decisions regarding the selection of the next trial solution (April, 2003).

[FIGURE 1 OMITTED]

3. COMPARISON OF SELECTED ALGORITHMS

In spite of the progress it is necessary to emphasize that the realization of simulation optimization will be a compromise between acceptable time and accuracy of found solution.

The authors realized the research oriented to comparison of selected algorithms of simulation optimization. The following criteria were compared:

* Time for optimal solution finding

* Success of optimal value finding

* Number of runs for evaluation

* The influence of change of parameters of algorithms for optimal solution finding

The authors have tested several algorithms on various simulation models. The limited range of this paper does not allow present the whole extensive work. This is why we show the problem of successful usage of simulation optimization only on chosen example. This process was used for searching of optimal values of lot size in the real production system.

The simulation model of system was created in simulator Witness. The basic advantage of simulation optimization is that the objective function can be simply defined and it does not need to contain input values. The objective function is defined inside the simulation model. In this case if quantitative values of other defined manufacturing goals are fulfilled, the objective function will return the value of costs per finished part. (Vazan, 2008). The realization of simulation optimization has been realized in plug-in module Optimizer.

These algorithms were included into the comparison:

--All combinations--brute force algorithm.

--Random solutions--to enable an appreciation of the shape of the solution space

--Min/Mid/Max--tests the extremes and mid points of all parameter settings.

--Hill Climb--a simple algorithm. Fast but prone to get stuck in local optima.

--Adaptive Thermostatistical simulated annealing--the main algorithm, a variant of simulated annealing with extra adaptive nature. Developed by Lanner.

Lot size is an input parameter (LS1, LS2 in tables) in our solving procedure. The right values of input intervals to the lot sizes also have to be connected, because lot sizes and their input interval hang together. It is very important to constrain the input parameters meaningfully.

The number of optimization variables and their ranges is defined by the following table 1. It is not possible to use the algorithm All combination because of long time, this arises from the results. Other algorithms were only approximated to searching optimum. See table 2. In the next experiments we have tried to reduce scanned set and then bigger step 3 has been chosen for variables P1 and P2 and step 2 for variables LS1 and LS2. The number of possible combinations has been decreased to 8280. The results of these experiments are presented in table 3. The dramatic reduction of the number of combinations allowed to use algorithm All combinations as is shown by the results of experiment. Then better value of objective function has been found in previous experiment. The found value need not to be the searched minimum. This has been caused by the reduction of the number of combinations.

The found better value allows the range reduction of input variables. If the range of input variables is reduced enough, it will be possible to use step 1. If the number of combinations allows using of algorithm All combinations then it will be possible to find the global extreme of the objective function in relatively short time. It is possible to declare that the solution is really the searched global minimum of objective function. The tables 4 and 5 document the last step of this procedure.

4. THE PROPOSAL OF FINAL PROCEDURE

The selection of the proper algorithm is the important part of this procedure. We can notice that the selection of algorithm has to respect mainly two basic factors:

1. What data will include individual sets of variables--it includes whether we know all data files of given range or whether we only know the min., mean and max. value.

2. Time of optimization process.

The authors recommend the following procedure (simplified) for algorithm selection and realization of optimization process based on extensive research:

* Reduce the range of inputs variables by specially designed preparatory experiments. The right range represents such states of the system that will be explored. The constraints of inputs variables represent upper and lower limits for system loading in the presented example.

* Use algorithm Random solutions or Adaptive Thermostatistical SA with bigger step (2 and more).

* Reduce again the range of input variables and repeat experiment by using the Adaptive Thermostatistical SA algorithm.

* If it is possible to reduce again the range of input parameters or if time of obtained result is acceptable, and then repeat the experiment by using All combinations algorithm or Hill Climb algorithm, else repeat the experiment by using the Adaptive T. SA algorithm.

Although simulation optimization represents powerful tool, its real usage needs complex knowledge and appropriate procedure. This procedure is only a part of bigger project which is realized by authors. The proposal of the authors has already been realized and has brought significant time reduction. This result will contribute to more effective using of simulation optimization.

This paper has been supported as a part of a solution of projects VEGA 1/0170/08.

5. REFERENCES

April, J.; Glover, F.; Kelly, J.P. & Laguna M.(2003). Practical introduction to simulation optimization, Proceedings of the WSC 2003, Chick, P. J. Sanchez, D. (Eds.), pp. 71-77, ISBN: 0-7803-8131-9 New Orleans, 12. 2003, WSC.

Boesel J., Glover F., Bowden O.R., Kelly J. P. & Westvig E. (2001). Future of simulation optimization. Proceedings of the 2001 Winter Simulation Conference, pp. 1466-1469, ISBN 0-7803-7309-X 12,2001, ACM, New York.

Tanuska P., & Kopcek M. (2007). The technological process control through the use of virtual controllers. Proceedings of the XIV Mezdunarodnja naucno techniceskaja konferencia. ISBN 966-7907-22-8. Sevastopol. Ukraine.

Vazan, P., Schreiber, P. & Krizanova G. (2008). The Simulation Optimization in Simulator Witness, Proceedings of the Third Conference: Ecumict pp. 461-469, ISBN 9-78908082-553-6 Gent, 3, 2008. Nevelland

Waller A.P. (2006). Optimization of simulation experiments, Available from : http://www.solventure.be/web/Jahia/pid/9 Accessed: 2008-06-02

Tab. 1. The number and range
of input variables.

Var. Range No No
name of var.s values combinations

P1 5 az 30 26 26
P2 5 az 70 66 1716
LS1 1 az 10 10 17160
LS2 1 az 10 10 171600

Tab. 2. Results of experiment

Algorithm Found Estimated Real No
 optimum time time evaluations

Adaptive T.SA 202 0:16:23 0:05:15 658
All Comb. -- 2days23h -- --
Random Sol. 216 0:17:29 0:17:51 800
Min/Mid/Max 271 0:01:48 0:01:48 81
Hill Climb 239 0:18:24 0:00:26 312

Tab. 3. Results of experiment (2).

Algorithms Found Estimated Real No
 optimum time time evaluations

Adaptive T.SA 189 0:27:51 0:06:59 627
All Combin. 189 2:58:17 2:56:48 8280
Random Sol. 249 0:24:16 0:23:56 800
Min/Mid/Max 271 0:01:50 0:01:40 81
Hill Climb 252 0:25:00 0:00:36 317

Tab. 4. New ranges of variables

Var. Old range New range
name of var. of var.

P1 5-30 8-14
P2 5-70 7-13
LS1 1-10 1-3
LS2 1-10 1-3

Tab. 5. Final results

Algorithm Found Estimated Real No
 optimum time time evaluations

Adaptive T.SA 162 0:18:09 0:01:34 321
All Comb. 155 0:25:00 0:22:28 990
Random S. 155 0:17:48 0:12:39 800
M/M/M 170 0:01:49 0:01:48 81
Hill Climb 1114 0:27:07 0:00:23 311