论文部分内容阅读
Abstract: The paper is a contribution to more effective using of simulation optimization. The paper presents the results of the comparison study of selected algorithms of simulation optimization. The authors have tested several algorithms on various simulation models. The simulation models of systems were created in simulator Witness. The main goal was to give the general procedure for effective usage of simulation optimization. The authors point out that the realization of simulation optimization is a compromise between acceptable time and accuracy of found solution. The final procedure involves the process of selection of algorithm, input variables, their set up of range and step selection. The proposal of the authors has already been realized and has brought significant time reduction.
Key words: Simulation, optimization, model, algorithm.
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.
There also exist many barriers which have to be overcome for broader simulation optimization using. Great scepticism predominates to the results of simulation optimization in concrete applications [1].
2. The Methods of Simulation Optimization
Understandably, there are a lot of methods that could be used for simulation optimization. The major simulation optimization methods are displayed in Fig. 2 [2]. 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 [2].
We want to mention a few important heuristic algorithms. Here belong genetics algorithms, evolutionary strategies, simulated annealing, simplex search, tabu search [3].
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 (See Fig. 1). The optimizer chooses a set of values for the input parameters. The optimizer uses the responses generated by the simulation model to make decisions regarding the selection of the next trial solution.
The software available today does not guarantee that it locates the optimal solution in the shortest amount of time for all possible problems that it may encounter. That would be a monumental accomplishment. However, the target was to develop and provide algorithms that could consistently find good solutions to problems that are better than the solutions found by analysts on their own (manually). It is evident that the current software has demonstrated its usefulness.
3. Comparison of Selected Algorithms
In spite of the progresses, it is necessary to emphasize that the realization of simulation optimization will always be a compromise between acceptable time and accuracy of found solution.
The authors have 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 parameters change of algorithms for optimal solution finding.
The authors have tested several algorithms on four different simulation models. Three simulation models represented the manufacturing systems and one simulation model was the model of the business process oriented system. Two models were stochastic and two models were deterministic systems.
The main goal was to evaluate selected algorithms not only from the point of view of accuracy of found global extreme of objective function but also from the point of view of time which was necessary for searching of the global extreme.
The authors have searched such sequence of steps that the selected algorithm will find the best result in the shortest time.
The process of simulation optimization is limited by many factors. Here belong [4]:
? The number of possible combination;
? Constrains—The definition of constrains can dramatically decreased the number of combinations. Constrains have to be defined on the base of knowledge about the simulated system;
? The number of input variables—This number has considerable influence on accuracy and the time of the optimum searching;
? The range of input variables—The limitation of range of variables is very important part of simulation optimization;
? The number of runs that is needed to obtain one
value of objective function. It is typical for stochastic simulation models;
? Time of simulation run;
? Warm up period.
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 the 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 (See Fig. 3).
The flexible manufacturing system consisted of four machine groups. There were two relative kinds of products named VD1 and VD2 in the manufacturing system produced at the same time. The lot sizes were set up to 5 pieces. The schedule of operations was created for every type of product. The sequence of operations was created for every machine group but the realization of operation on the concrete machine in the group was decided by immediate situation.
The basic advantage of simulation optimization is that the objective function can be defined in a simple way and it does not need to contain input values. The objective function is defined inside the simulation model.
The procedure was defined as follows [4]:
IF No_out_parts () ? default value of finished parts AND Machine utilisation ()? default value of machine utilisation AND Flow time ()? default value of flow time
Unit_Costs = SumCosts / No_out_parts
RETURN Unit_Costs
ELSE
Unit_Costs = SumCosts / No_out_parts
RETURN Unit_Costs
ENDIF
The objective function returns the value of costs per finished part when quantitative values of defined manufacturing goals are fulfilled. At the beginning it is necessary to define default values of flow time, machine utilization and number of finished parts. These values were found out by simulation way from so called preparatory experiments. And these preparatory experiments were specially designed for this purpose:
? Default value of finished parts—400 parts;
? Default value of machine utilisation—75%;
? Default value of flow time—80 minutes.
The realization of simulation optimization has been realized in plug-in module Optimizer.
These algorithms were included into the comparison:
? All combinations (All com.)—brute force algorithm;
? Random solutions (RS)—to enable an appreciation of the shape of the solution space;
? Min/Mid/Max (M/M/M)—tests the extremes and mid points of all parameter settings. Covers all options for non-range parameters;
? Hill Climb—a simple algorithm. Fast but prone to get stuck in local optima;
? Adaptive Thermostatistical simulated annealing(SA)—the main algorithm, a variant of simulated annealing with extra adaptive nature. Developed by Lanner.
Understandably, the authors have respected individual parameters of selected algorithms. These were mainly maximum evaluations and maximum moves without improvement with the exception of algorithms All combinations and Min/Mid/Max. These algorithms have no individual settings. The rest of
algorithms had set maximum evaluations = 800 and maximum moves without improvement = 300.
The simulation model has 4 input variables—lot sizes for both products (LS1, LS2 in tables) and input intervals for both products (P1, P2 in tables). The right values of input intervals of the lot sizes also have to be connected because lot size and their input interval hang together. It is very important to constrain the input parameters meaningfully. Accurate setting up of the input intervals markedly reduces the optimization time.
Experiments:
The number of optimization variables and of their ranges is defined in Table 1.
The number of all possible combinations for this model is 78400. It is too much because variables are just four. Ranges of variables are too big so in the experiment size of step will be changed.
We are searching for the minimum of the objective function (minimal value of total costs). The simulation run takes 2400 minutes (41 hours) and warm up period lasts 60 minutes.
There are a large number of combinations of optimal times of algorithms. The fastest algorithm is the Hill Climb. The worst value found by a solution is probably a local minimum. The best value is achieved by All combinations algorithm but it lasts 4 hours and 10 minutes. Quite good value is found for a short time by Random Solutions algorithm, which is the best in this experiment. Algorithm Min/Mid/Max does not prove good results in the models with large ranges because it makes a very small number of valuation(total number of all combinations is 21205 but the algorithm runs through 81). Consequently this algorithm is more suitable to use in the models with a big number of values and small ranges. The results are in Table 2.
The following experiments with used narrow ranges of optimization variables are in Table 3.
However, better value that has been found allows reducing the range of input variables. Here is important to remark that when the global extreme was found on the border of input variable range then it is necessary to repeat the experiment. In this case it is needed to increase the range of input variables. The searched optimum has to be inside of the definition scope of input variables.
The number of combinations is reduced to 4725 from total 74800. New ranges of variables are obtained by many experiments. In Table 4, there are the latest results of experiment to correct the obtained results.
The found value 194 is the real minimum of the objective function. This value was reached by algorithm All combination and also algorithm Random solution, but their time was too long. Algorithm Hill climb probably get stuck in a local extreme.
In this experiment, the range of variables is modified on the basis of the results obtained in previous experiment by algorithms Random Solution and Adaptive Thermostatistical simulated annealing.
If the better value of variable exist which is not included in the range, it will always be situated on the border of the range. Then it is important to modify the ranges.
In this experiment the authors verify the sequence of steps for the fastest finding final value. By combination of more algorithms and by reduction of ranges, the time of optimization is shortened in the comparison with algorithm All Combinations.
At first, the optimization is realized by algorithm Adaptive Thermostatistical simulated annealing with step 2 for the variables with big range. After the using of algorithm Random Solutions with step 1, the results are acquired and subsequently the ranges of variables are reduced. It is necessary to modify new ranges twice according to the rules from the previous experiment. The process proposed in previous experiment is confirmed just here. The results which meet requirement (the best acquired values are not marginal values of new ranges) are optimized by algorithm All Combinations, with the finding of the optimal result of the objective function. The results for this experiment are stated in Table 5.
4. The Evaluation of Tested Algorithms
Although simulation optimization represents powerful tool, its real usage needs complex knowledge and appropriate procedure. The selection of the proper algorithm is the important part of this procedure.
The brute force algorithm All combinations always guarantees optimal value finding, but the time of optimum searching is too long and unacceptable in many cases. It is usually impossible to use this algorithm at the beginning of optimization process.
The algorithm Adaptive Thermostatistical simulated annealing was the best in majority of experiments from the point of view of accuracy and the searching time. This algorithm had also very good results at bigger searching step. We recommend usage of Adaptive Thermostatistical simulated annealing algorithm if the total number of input values combination is great and also if the searching step is bigger.
The algorithm Random Solutions chooses random values from set of variables. It has reached good results when the total number of input values combination was big and the searching step was 1. It is advantageous to use the algorithm Random Solutions at the beginning of optimization process. It offers overview of scanned space. Then it is possible to reduce this space according to the results of the algorithm.
The algorithm Min/Mid/Max have tested only minimal, middle and maximal values of input variables, therefore the number of tested combinations was relatively small. The short searching time was up to the small sample but the accuracy was low. The efficiency of the algorithm Min/Mid/Max is better for narrow ranges of input variables.
The algorithm Hill Climb was the fastest from all tested algorithms. It has to get on local extreme very often therefore its results were the worst. It is possible to use this algorithm in the final step of optimization when the ranges of input variables are narrow and only one extreme is expected.
The Next Factors Which Influence Simulation Optimization:
The next factors which influence simulation optimization are
? The length of simulation runs: It directly influences the time of simulation optimization realization;
? The input variables and their ranges: The appropriate definition of input variables is the one of the most important steps of simulation optimization. The selection of variables that influences the objective function has to follow knowledge of solved problem and its representation in simulation model. Understandably the number of input variable and their ranges markedly influence the time of simulation optimization process. We recommend verification of ranges of input variables by specially designed preparatory experiments. The goal of these experiments is very sensitively set up the range of variables so that the total number of possible combinations will be minimal;
? The search step: It influences the quality of optimization. The search step should be defined on dependence on the number and ranges of input variables. We suggest set up the search step 2 or 3 for wide range(30 and more values). The bigger step is usually defined for the first optimization experiment. Here exist two criteria for search step determination—the reduction of the number of combination and the reduction of time of optimization. The determination of search step is related to algorithm selection;
? The number of simulation runs for the objective function evaluation: It directly influences the time of optimization process. The number of simulation runs depends on the character of simulation model. It is necessary to realized more simulation runs when the model is stochastic. Only one simulation run is needed for deterministic model.
5. The Proposal of Final Procedure
The authors recommend the following procedure(simplified) for algorithm selection and realization of optimization process based on extensive research.
To reduce the range of inputs variables by specially designed preparing 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 Adaptive Thermostatistical simulated annealing with searching step 1 for model with many input variables but their range is small. The value of searching extreme is very near to optimum, however the searching time is very often shorter than when used with the algorithm All combinations.
We suggest the following procedure for models with few input variables (less than 5) but their range is very huge (permissible combination can be from several hundred thousands to several million):
(1) Use algorithm Random solutions;
(2) Use Adaptive Thermostatistical simulated annealing with bigger step (2 and more);
(3) Compare both results;
(4) Reduce the range of input variables on the base of the best result of both algorithms;
(5) Repeat experiment by using the Adaptive Thermostatistical simulated annealing algorithm with searching step 1;
(6) Reduce again the range of input variables and repeat experiment by using the Adaptive Thermostatistical simulated annealing algorithm.(Important note: When the extreme is found on the border of input variable range then it is necessary to repeat the experiment);
(7) If it is possible to reduce the range of input parameters again or if time of obtained result is acceptable, then repeat the experiment by using All combinations algorithm or Hill Climb algorithm, else repeat the experiment by using the Adaptive Thermostatistical Simulated Annealing algorithm.
The whole process is illustrated on the following Business Process Model (Fig. 4).
Important Remarks:
If the objective function contains a condition and its dissatisfaction returns a constant (e.g., null) for the differentiation of unsuitable values some optimization algorithms (e.g., algorithm Adaptive Thermostatistical simulated annealing) will not have to find a searched extreme. These algorithms use the principle of adaptive
learning and are based on assumptions of finding better result. Usually the algorithms have set the number of consecutive evaluations without any improvement in the best found result after which the optimization run stops. It means the algorithm does not have to provide the results suitable for next analysis.
The problem can also be caused by strictly defined ranges of input variables. It is important to set them in the way that it is possible to find the first acceptable solution already in the first step of the proposed process. Under benevolent conditions, there can occur such situation that the best results are on the borders of ranges which arises out of their additional enlarging and thus extension of optimizing. This problem can be solved by addition of the next contradictory condition to the objective function.
6 Conclusions
There are more areas where simulation optimization can be used. Of course the choice of the procedure used in simulation optimization depends on the analyst and the solved problem. The simulation optimization seems as proper method for the various problems solutions, but it requires the existence of simulation model. The model has to be very detail and also validated. Just the process of “correct” model building and its validation may be iffy. On the other hand, the simulation model allows research the real processes in the detail way. The length of duration seems as the greatest problem of simulation optimization usage. Our research made a contribution to practical usage of simulation optimization. The final procedure allows reducing the time of global extreme searching, but the accuracy of finding solution is very high. Usually we have found the global extreme of the objective function precisely. We believe that the increasing of the efficiency and simplicity of applications of simulation optimization can be valuable.
References
[1] J. Boesel, F. Glover, O.R. Bowden, J.P. Kelly, E. Westvig, Future of simulation optimization, in: Proceedings of the 2001 Winter Simulation Conference, ACM, New York, 2001, pp. 1466-1469.
[2] J. April, F. Glover, J.P. Kelly, M. Laguna, Practical introduction to simulation optimization, in: Proceedings of the WSC 2003, New Orleans, pp. 71-77.
[3] P. Schreiber, Applications of genetic algorithms, in: Proceedings of 19th CECIIS, Croatia, 2008.
[4] M. Mrva, The comparison of selected algorithms of simulation optimization, Diploma Thesis, Slovak University of Technology in Bratislava, 2008.
Key words: Simulation, optimization, model, algorithm.
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.
There also exist many barriers which have to be overcome for broader simulation optimization using. Great scepticism predominates to the results of simulation optimization in concrete applications [1].
2. The Methods of Simulation Optimization
Understandably, there are a lot of methods that could be used for simulation optimization. The major simulation optimization methods are displayed in Fig. 2 [2]. 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 [2].
We want to mention a few important heuristic algorithms. Here belong genetics algorithms, evolutionary strategies, simulated annealing, simplex search, tabu search [3].
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 (See Fig. 1). The optimizer chooses a set of values for the input parameters. The optimizer uses the responses generated by the simulation model to make decisions regarding the selection of the next trial solution.
The software available today does not guarantee that it locates the optimal solution in the shortest amount of time for all possible problems that it may encounter. That would be a monumental accomplishment. However, the target was to develop and provide algorithms that could consistently find good solutions to problems that are better than the solutions found by analysts on their own (manually). It is evident that the current software has demonstrated its usefulness.
3. Comparison of Selected Algorithms
In spite of the progresses, it is necessary to emphasize that the realization of simulation optimization will always be a compromise between acceptable time and accuracy of found solution.
The authors have 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 parameters change of algorithms for optimal solution finding.
The authors have tested several algorithms on four different simulation models. Three simulation models represented the manufacturing systems and one simulation model was the model of the business process oriented system. Two models were stochastic and two models were deterministic systems.
The main goal was to evaluate selected algorithms not only from the point of view of accuracy of found global extreme of objective function but also from the point of view of time which was necessary for searching of the global extreme.
The authors have searched such sequence of steps that the selected algorithm will find the best result in the shortest time.
The process of simulation optimization is limited by many factors. Here belong [4]:
? The number of possible combination;
? Constrains—The definition of constrains can dramatically decreased the number of combinations. Constrains have to be defined on the base of knowledge about the simulated system;
? The number of input variables—This number has considerable influence on accuracy and the time of the optimum searching;
? The range of input variables—The limitation of range of variables is very important part of simulation optimization;
? The number of runs that is needed to obtain one
value of objective function. It is typical for stochastic simulation models;
? Time of simulation run;
? Warm up period.
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 the 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 (See Fig. 3).
The flexible manufacturing system consisted of four machine groups. There were two relative kinds of products named VD1 and VD2 in the manufacturing system produced at the same time. The lot sizes were set up to 5 pieces. The schedule of operations was created for every type of product. The sequence of operations was created for every machine group but the realization of operation on the concrete machine in the group was decided by immediate situation.
The basic advantage of simulation optimization is that the objective function can be defined in a simple way and it does not need to contain input values. The objective function is defined inside the simulation model.
The procedure was defined as follows [4]:
IF No_out_parts () ? default value of finished parts AND Machine utilisation ()? default value of machine utilisation AND Flow time ()? default value of flow time
Unit_Costs = SumCosts / No_out_parts
RETURN Unit_Costs
ELSE
Unit_Costs = SumCosts / No_out_parts
RETURN Unit_Costs
ENDIF
The objective function returns the value of costs per finished part when quantitative values of defined manufacturing goals are fulfilled. At the beginning it is necessary to define default values of flow time, machine utilization and number of finished parts. These values were found out by simulation way from so called preparatory experiments. And these preparatory experiments were specially designed for this purpose:
? Default value of finished parts—400 parts;
? Default value of machine utilisation—75%;
? Default value of flow time—80 minutes.
The realization of simulation optimization has been realized in plug-in module Optimizer.
These algorithms were included into the comparison:
? All combinations (All com.)—brute force algorithm;
? Random solutions (RS)—to enable an appreciation of the shape of the solution space;
? Min/Mid/Max (M/M/M)—tests the extremes and mid points of all parameter settings. Covers all options for non-range parameters;
? Hill Climb—a simple algorithm. Fast but prone to get stuck in local optima;
? Adaptive Thermostatistical simulated annealing(SA)—the main algorithm, a variant of simulated annealing with extra adaptive nature. Developed by Lanner.
Understandably, the authors have respected individual parameters of selected algorithms. These were mainly maximum evaluations and maximum moves without improvement with the exception of algorithms All combinations and Min/Mid/Max. These algorithms have no individual settings. The rest of
algorithms had set maximum evaluations = 800 and maximum moves without improvement = 300.
The simulation model has 4 input variables—lot sizes for both products (LS1, LS2 in tables) and input intervals for both products (P1, P2 in tables). The right values of input intervals of the lot sizes also have to be connected because lot size and their input interval hang together. It is very important to constrain the input parameters meaningfully. Accurate setting up of the input intervals markedly reduces the optimization time.
Experiments:
The number of optimization variables and of their ranges is defined in Table 1.
The number of all possible combinations for this model is 78400. It is too much because variables are just four. Ranges of variables are too big so in the experiment size of step will be changed.
We are searching for the minimum of the objective function (minimal value of total costs). The simulation run takes 2400 minutes (41 hours) and warm up period lasts 60 minutes.
There are a large number of combinations of optimal times of algorithms. The fastest algorithm is the Hill Climb. The worst value found by a solution is probably a local minimum. The best value is achieved by All combinations algorithm but it lasts 4 hours and 10 minutes. Quite good value is found for a short time by Random Solutions algorithm, which is the best in this experiment. Algorithm Min/Mid/Max does not prove good results in the models with large ranges because it makes a very small number of valuation(total number of all combinations is 21205 but the algorithm runs through 81). Consequently this algorithm is more suitable to use in the models with a big number of values and small ranges. The results are in Table 2.
The following experiments with used narrow ranges of optimization variables are in Table 3.
However, better value that has been found allows reducing the range of input variables. Here is important to remark that when the global extreme was found on the border of input variable range then it is necessary to repeat the experiment. In this case it is needed to increase the range of input variables. The searched optimum has to be inside of the definition scope of input variables.
The number of combinations is reduced to 4725 from total 74800. New ranges of variables are obtained by many experiments. In Table 4, there are the latest results of experiment to correct the obtained results.
The found value 194 is the real minimum of the objective function. This value was reached by algorithm All combination and also algorithm Random solution, but their time was too long. Algorithm Hill climb probably get stuck in a local extreme.
In this experiment, the range of variables is modified on the basis of the results obtained in previous experiment by algorithms Random Solution and Adaptive Thermostatistical simulated annealing.
If the better value of variable exist which is not included in the range, it will always be situated on the border of the range. Then it is important to modify the ranges.
In this experiment the authors verify the sequence of steps for the fastest finding final value. By combination of more algorithms and by reduction of ranges, the time of optimization is shortened in the comparison with algorithm All Combinations.
At first, the optimization is realized by algorithm Adaptive Thermostatistical simulated annealing with step 2 for the variables with big range. After the using of algorithm Random Solutions with step 1, the results are acquired and subsequently the ranges of variables are reduced. It is necessary to modify new ranges twice according to the rules from the previous experiment. The process proposed in previous experiment is confirmed just here. The results which meet requirement (the best acquired values are not marginal values of new ranges) are optimized by algorithm All Combinations, with the finding of the optimal result of the objective function. The results for this experiment are stated in Table 5.
4. The Evaluation of Tested Algorithms
Although simulation optimization represents powerful tool, its real usage needs complex knowledge and appropriate procedure. The selection of the proper algorithm is the important part of this procedure.
The brute force algorithm All combinations always guarantees optimal value finding, but the time of optimum searching is too long and unacceptable in many cases. It is usually impossible to use this algorithm at the beginning of optimization process.
The algorithm Adaptive Thermostatistical simulated annealing was the best in majority of experiments from the point of view of accuracy and the searching time. This algorithm had also very good results at bigger searching step. We recommend usage of Adaptive Thermostatistical simulated annealing algorithm if the total number of input values combination is great and also if the searching step is bigger.
The algorithm Random Solutions chooses random values from set of variables. It has reached good results when the total number of input values combination was big and the searching step was 1. It is advantageous to use the algorithm Random Solutions at the beginning of optimization process. It offers overview of scanned space. Then it is possible to reduce this space according to the results of the algorithm.
The algorithm Min/Mid/Max have tested only minimal, middle and maximal values of input variables, therefore the number of tested combinations was relatively small. The short searching time was up to the small sample but the accuracy was low. The efficiency of the algorithm Min/Mid/Max is better for narrow ranges of input variables.
The algorithm Hill Climb was the fastest from all tested algorithms. It has to get on local extreme very often therefore its results were the worst. It is possible to use this algorithm in the final step of optimization when the ranges of input variables are narrow and only one extreme is expected.
The Next Factors Which Influence Simulation Optimization:
The next factors which influence simulation optimization are
? The length of simulation runs: It directly influences the time of simulation optimization realization;
? The input variables and their ranges: The appropriate definition of input variables is the one of the most important steps of simulation optimization. The selection of variables that influences the objective function has to follow knowledge of solved problem and its representation in simulation model. Understandably the number of input variable and their ranges markedly influence the time of simulation optimization process. We recommend verification of ranges of input variables by specially designed preparatory experiments. The goal of these experiments is very sensitively set up the range of variables so that the total number of possible combinations will be minimal;
? The search step: It influences the quality of optimization. The search step should be defined on dependence on the number and ranges of input variables. We suggest set up the search step 2 or 3 for wide range(30 and more values). The bigger step is usually defined for the first optimization experiment. Here exist two criteria for search step determination—the reduction of the number of combination and the reduction of time of optimization. The determination of search step is related to algorithm selection;
? The number of simulation runs for the objective function evaluation: It directly influences the time of optimization process. The number of simulation runs depends on the character of simulation model. It is necessary to realized more simulation runs when the model is stochastic. Only one simulation run is needed for deterministic model.
5. The Proposal of Final Procedure
The authors recommend the following procedure(simplified) for algorithm selection and realization of optimization process based on extensive research.
To reduce the range of inputs variables by specially designed preparing 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 Adaptive Thermostatistical simulated annealing with searching step 1 for model with many input variables but their range is small. The value of searching extreme is very near to optimum, however the searching time is very often shorter than when used with the algorithm All combinations.
We suggest the following procedure for models with few input variables (less than 5) but their range is very huge (permissible combination can be from several hundred thousands to several million):
(1) Use algorithm Random solutions;
(2) Use Adaptive Thermostatistical simulated annealing with bigger step (2 and more);
(3) Compare both results;
(4) Reduce the range of input variables on the base of the best result of both algorithms;
(5) Repeat experiment by using the Adaptive Thermostatistical simulated annealing algorithm with searching step 1;
(6) Reduce again the range of input variables and repeat experiment by using the Adaptive Thermostatistical simulated annealing algorithm.(Important note: When the extreme is found on the border of input variable range then it is necessary to repeat the experiment);
(7) If it is possible to reduce the range of input parameters again or if time of obtained result is acceptable, then repeat the experiment by using All combinations algorithm or Hill Climb algorithm, else repeat the experiment by using the Adaptive Thermostatistical Simulated Annealing algorithm.
The whole process is illustrated on the following Business Process Model (Fig. 4).
Important Remarks:
If the objective function contains a condition and its dissatisfaction returns a constant (e.g., null) for the differentiation of unsuitable values some optimization algorithms (e.g., algorithm Adaptive Thermostatistical simulated annealing) will not have to find a searched extreme. These algorithms use the principle of adaptive
learning and are based on assumptions of finding better result. Usually the algorithms have set the number of consecutive evaluations without any improvement in the best found result after which the optimization run stops. It means the algorithm does not have to provide the results suitable for next analysis.
The problem can also be caused by strictly defined ranges of input variables. It is important to set them in the way that it is possible to find the first acceptable solution already in the first step of the proposed process. Under benevolent conditions, there can occur such situation that the best results are on the borders of ranges which arises out of their additional enlarging and thus extension of optimizing. This problem can be solved by addition of the next contradictory condition to the objective function.
6 Conclusions
There are more areas where simulation optimization can be used. Of course the choice of the procedure used in simulation optimization depends on the analyst and the solved problem. The simulation optimization seems as proper method for the various problems solutions, but it requires the existence of simulation model. The model has to be very detail and also validated. Just the process of “correct” model building and its validation may be iffy. On the other hand, the simulation model allows research the real processes in the detail way. The length of duration seems as the greatest problem of simulation optimization usage. Our research made a contribution to practical usage of simulation optimization. The final procedure allows reducing the time of global extreme searching, but the accuracy of finding solution is very high. Usually we have found the global extreme of the objective function precisely. We believe that the increasing of the efficiency and simplicity of applications of simulation optimization can be valuable.
References
[1] J. Boesel, F. Glover, O.R. Bowden, J.P. Kelly, E. Westvig, Future of simulation optimization, in: Proceedings of the 2001 Winter Simulation Conference, ACM, New York, 2001, pp. 1466-1469.
[2] J. April, F. Glover, J.P. Kelly, M. Laguna, Practical introduction to simulation optimization, in: Proceedings of the WSC 2003, New Orleans, pp. 71-77.
[3] P. Schreiber, Applications of genetic algorithms, in: Proceedings of 19th CECIIS, Croatia, 2008.
[4] M. Mrva, The comparison of selected algorithms of simulation optimization, Diploma Thesis, Slovak University of Technology in Bratislava, 2008.