بهینه سازی شبیه سازی چند هدفه از طریق جستجوی اکتشافی و تجزیه و تحلیل پایگاه داده رابطه ای

The SimMOp framework for generating solutions to simulation optimization problems containing multiple objectives is presented. The complexity within this subject is the conflicting multiple stochastic outputs whose estimates are only available through simulation. The framework combines a simulation model, a non-exhaustive heuristic search algorithm with an embedded multi-objective optimization technique, and database technologies to generate a set of good quality solutions. The goodness of solutions is measured from a multi-objective and stochastic perspective through analysis after the search phase of the methodology. The methodology has been tested using a discrete-event simulation model based on inventory theory.

Discrete-event simulation is a powerful computational technique for studying dynamic systems containing stochastic elements. Simulation models are constructed to emulate the features of real world systems too complex to be investigated analytically and provide good approximations to the relevant performance measures. Amongst the key aspects of good model development are the processes of verification and validation. These procedures ensure that the designed model works as it is intended and that it is an accurate representation of the system able to provide the desired information to solve formulated problems. The aim of this work is to detail the SimMOp methodology for the optimization of multi-objective simulations and is therefore concerned with model analysis rather than the specific work of a modeller. An overview of all aspects in the field of discrete-event simulation modelling can be found in Law and Kelton [12]. Once a successfully developed simulation model is given relevant values for the input parameters it is run to collect the output data. Due to the stochastic nature each run of a simulation model is made up of multiple replications and data is collected as mean values with variances over these repeat evaluations. Each individual combination of input parameters, known in simulation as a system, represents an individual scenario for the simulation model. If an analyst is using only a few scenarios experiments can be designed to easily obtain the best, however, it is often preferred to find the scenario that optimizes model output from a more extensive set, in which case simulation optimization is required. In general, for a multi-objective minimization problem with m objectives and n input parameters we have min F(Θi(Ψj), ε), where Θi = {θ1(ψ1, ψ2,…, ψn), θ2(ψ1, ψ2,…,ψn),…, θm(ψ1,ψ,…,ψn)} represents a vector of the m objective values evaluated at Ψ a vector of the n simulation input parameters and ε is a term representing the statistical error in the data. Therefore an optimization algorithm is seeking the optimal solution Ψ⋆ that gives the minimum value for E(F(Θi(Ψj), ε)). For each evaluated vector of input parameters an estimation of the set of the model's stochastic output measures is made. Correct output analysis of a simulation model is as crucial to good simulation as is thorough model development. Traditional simulation output analysis involves determining a sufficient level of accuracy within the data through the construction of confidence intervals, the calculation of probability that estimates are within a relative error amount from an exact measure, or measuring the probability of a value being above or below a desired level [9]. For a given desired level of accuracy the number of replications required to achieve this can be found through sampling estimates of the output mean and variance. There has been significant research into the optimization of single objective simulation problems [7] and [11]. The review of Fu [6] shows the four main approaches are those that guarantee asymptotic convergence, approaches which guarantee optimality under the consideration of no sampling variability, those which guarantee optimality within a pre-specified probability and approaches that are based around robust heuristics. Theoretical work is based on the first three approaches, while variations of the last are used in practice. Fu [6] also states there are four categories of techniques used to obtain optimal solutions in simulation optimization problems. These are statistical methods (response surface methodology, ranking and selection and multiple comparison procedures), metaheuristics (simulated annealing, tabu search and genetic algorithms), stochastic optimization (random search and stochastic approximation) and others that include ordinal optimization and sample path optimization. Simulation optimization techniques can be divided between input parameter types, the models with continuous decision parameters and those with discrete decision parameters. Gradient based methods are used for continuous parameters; these include gradient estimation, stochastic approximation and sample path optimization. Techniques for optimizing models with discrete parameters include statistical selection, random search and metaheuristics. A good example of how common heuristic approaches can be adapted to different classes of optimization problems is given by Simulated Annealing [10] and the SimMOp framework draws upon concepts and ideas from this technique. A thorough overview of how this search technique has been adapted for various optimization problems is given by Suman and Kumar [19]. As this paper considers multi-objective optimization adaptations from the Simulated Annealing literature will be discussed in order to provide insight into the requirements of a potential optimization strategy. Simulated annealing has been adapted for multi-objective combinatorial optimization through changing the acceptance probability function to consider potential moves in situations when some objective values improve to the detriment of others. The Multiple Objective Simulated Annealing (MOSA) algorithm [20] uses a weighting scheme, varied over multiple runs, to generate an approximation of the set of non-dominated solutions. The Pareto Simulated Annealing (PSA) algorithm [5] uses annealing on a set of current solutions to simultaneously determine the non-dominated frontier. Weightings are used in this algorithm to ensure solutions are dispersed along the entire frontier. Constraint handling in these two algorithms, and most other adaptations of simulated annealing, is done through penalty functions. These functions consider violations through modifying the decision space to an unconstrained one and allocate a penalty value to the output, based on the magnitude of violation. Simulated Annealing has also been adapted to solve stochastic combinatorial problems, which include discrete-event simulation. Simulated Annealing algorithms are combined with statistical measures to decide on potential moves and to justify solution quality. The papers of Alkhamis and Ahmed [2], Ahmed and Alkhamis [1] and Wang and Zhang [21] use confidence intervals, ranking and selection, and hypothesis testing respectively. Sample estimates of objective value functions are used in these algorithms and the significance tests determine the best solutions. The statistical testing methods used in stochastic optimization are heavily dependent on the number of independent evaluations used. Significant amounts of simulation replications are required to ensure the optimal solutions are found with accurate evaluations. Simulated Annealing is a memoryless heuristic capable of re-evaluating solutions, a feature that is exploited in the work of Alrafaei and Andradottir [3] in which they determine convergence to the optimal solution in two ways. The first selects the solution visited the most during the search and the second, the parameter combination that has the best estimated average performance measure amongst those visited. Features from all these techniques are incorporated into the optimization framework suggested in this work. As the consideration of the SimMOp framework is multi-objective combinatorial simulation problems, the preferred optimization approach will be to develop a metaheuristic search algorithm in combination with a method to analyse the output. Due to the conflicting nature of the multiple outputs there will not exist a single solution capable of simultaneously optimizing the output. Different approaches are utilized to provide a balance amongst the objectives and a set of non-dominated solutions can be provided to a decision-maker known as Pareto optimal [14] solutions. These are the feasible solutions that dominate other solutions by being at least as good with respect to every objective and strictly better with respect to at least one objective. There are two main approaches for obtaining a set of non-dominated solutions, Pareto and scalarization methods. The Pareto front of non-dominated solutions can be obtained in multiple ways including using multiple objective heuristic algorithms. Pareto search algorithms, like PSA, generate an approximation of the Pareto set through maintaining a population of current solutions and determining if the candidate solutions dominate members of the existing set. Although multi-objective optimization heuristics are not common in the simulation optimization literature, a popular area for research is in ranking and selection for models containing multiple performance measures. Ranking and selection (R&S) is used for in problems that contain only a small number of feasible systems (normally less than 30). Variations on R&S include picking the best solution with a certain probability or picking a set of a pre-determined number of the best values for further analysis. For example, Butler et al. [4] compare a set of good solutions to a multiple-objective problem through using multiple attribute theory in combination with multi-objective ranking and selection (MORS) to determine the best configuration of a system. The following sections outline the basis for the designed optimization methodology, describe the framework for storing and analysing significant stochastic data and explain the integration of the above optimization features. This is followed by a test problem to demonstrate the effectiveness of the methodology

The SimMOp optimization framework has been designed to solve complex simulation models with multiple objectives. The method demonstrated uses a search heuristic in combination with database technologies and the SQL to efficiently and effectively handle the significant amount of data needed in this environment. The search phase of the methodology must ensure sufficient evaluations of the simulation model in regions containing the global solutions. Through selection of starting points for multiple search runs and information gained through querying the database the important intensification and diversification of the search can be achieved. The post-analysis stage of this method examines the database to retrieve the desired feasible non-dominated solutions. Through adapting the constraints that occur naturally in a model with information obtained by fixed length search runs good solutions can be found in reasonable computational time with no prior knowledge of the expected output required. The variances for each model output are stored from each independent batch of model replications and are incorporated in the decision-making from the final table of output in statistical testing to demonstrate the non-dominance of the solutions. The post-search phase of the methodology provides confidence to the decision-maker as to the quality of the multi-objective solutions. Areas for further research using the SimMOp framework include the design of a suitable example, with known results, in order to test the rates of convergence for the search algorithm. Also research incorporating different optimization approaches into the search phase would prove beneficial. For example the ability to view the database at the end of each search run would allow the use of an interactive approach in which preference weights can be varied according to decision-maker's requirements