تنظیم مته یورایستیکس : رویکرد مبتنی بر داده کاوی برای بهینه سازی ازدحام ذرات

The paper is concerned with practices for tuning the parameters of metaheuristics. Settings such as, e.g., the cooling factor in simulated annealing, may greatly affect a metaheuristic’s efficiency as well as effectiveness in solving a given decision problem. However, procedures for organizing parameter calibration are scarce and commonly limited to particular metaheuristics. We argue that the parameter selection task can appropriately be addressed by means of a data mining based approach. In particular, a hybrid system is devised, which employs regression models to learn suitable parameter values from past moves of a metaheuristic in an online fashion. In order to identify a suitable regression method and, more generally, to demonstrate the feasibility of the proposed approach, a case study of particle swarm optimization is conducted. Empirical results suggest that characteristics of the decision problem as well as search history data indeed embody information that allows suitable parameter values to be determined, and that this type of information can successfully be extracted by means of nonlinear regression models

The support of managerial decision making is a key area of interest in many scientific domains and several qualitative and quantitative planning methods have been developed to support various types of operational, tactical and strategic planning problems. Especially well-structured and repetitive decision tasks are commonly approached by translating the problem into a mathematical program whose optimal solution is then determined by an optimization procedure like, e.g., linear programming. Over the past decades, heuristic procedures from the field of intelligent search have received much attention and nowadays represent a well-established approach towards solving complex optimization problems. Offering high-quality solutions in a timely manner, they complement classical mathematical programming methods, especially in large, combinatorial settings where optimal solutions are usually unattainable. Respective techniques have been developed in several domains (e.g., Operational Research, Engineering, Soft Computing, etc.) and include algorithms like simulated annealing (Kirkpatrick, Gelatt, & Vecchi, 1983), tabu-search (Glover & Laguna, 1997), cross-entropy (Boer, Kroese, Mannor, & Rubinstein, 2005) as well as nature-inspired methods like genetic algorithms (Goldberg, 1989 and Holland, 1975), evolution strategies (Beyer & Schwefel, 2002) and, more recently, ant colony optimization (Dorigo & Stützle, 2005) and particle swarm optimization (PSO, Kennedy & Eberhart, 1995). The umbrella term metaheuristics is used throughout the paper to subsume respective approaches (see, e.g., Glover, 1986 for a formal definition of a metaheuristic). A large body of literatures evidences the success of metaheuristics in various applications (see, e.g., Blum and Roli, 2003, Caserta and Voß, 2009 and Glover and Kochenberger, 2003 for a survey). One key factor that seems to have a strong impact on the algorithmic performance is the fine tuning of the method; that is, the determination of the metaheuristic’s parameters (e.g., the number of generations in genetic algorithms, the length of the tabu-list in tabu-search or the cooling factor in simulated annealing, etc.). According to Adenso-Diaz and Laguna (2006), there is evidence that 10% of the time required to develop a new metaheuristic is devoted to the actual development and that the remaining 90% is spent on fine tuning of algorithmic parameters. Consequently, it is of paramount importance to make a concerted effort in identifying and establishing a set of “standard” techniques to fine-tune a metaheuristic. One of the major achievements of such an effort would be to offset parameter specific issues in evaluating an algorithm. In addition, reproducibility of results would also be enhanced by such an approach, by making transparent the way in which parameter values should be set to tackle a given problem instance. Some work has been carried out to develop elaborate parameterization approaches. For example, adaptations of individual metaheuristics have been proposed to tune parameters in a self-adaptive fashion (see, e.g., Battiti et al., 2009 and Beyer and Schwefel, 2002). Whereas the potential of such reactive metaheuristics is undoubted, the objective of this paper is to lay ground for an orthogonal approach towards parameter tuning. In particular, we examine whether a formal relationship between effective parameter values and characteristics of the underlying optimization problem exist and whether it is sufficiently strong to be exploited for an automated tuning approach. Most metaheuristics operate in an iterative manner: Given a starting solution to an optimization problem, neighboring solutions are evaluated and used in some way to improve the present one, i.e., find better solutions to the problem. Consequently, data concerning the assessed candidate solutions and their appropriateness naturally becomes available during the execution of a metaheuristic. The particular way in which a solution is altered or a new solution is obtained on the basis of a present one, respectively, depends upon settings of the metaheuristic’s parameters. Hence, we consider a parameter setting to be effective, if it facilitates improving a candidate solution’s fitness. Employing the data produced, we aim at constructing a prediction model capable of estimating suitable parameter values for a subsequent iteration by means of regression. It is argued that if such a model shows high forecasting accuracy, it could be employed as a tuningagent to predict effective parameter settings on the basis of the metaheuristic’s current status and problem-specific information. This differs from previous approaches to achieve self-adaptivity in the sense that it does not depend upon any particular search algorithm. Therefore, the paper contributes to the literature by proposing a data mining based solution to the problem of tuning metaheuristics’ parameters and providing empirical evidence of its efficacy. To that end, a case study is undertaken to systematically explore the feasibility of forecasting effective parameter settings for one particular metaheuristic, the PSO algorithm. The study comprises established as well as state-of-the-art regression methods to scrutinize the nature of the relationship between the employed independent variables and effective parameter values (e.g., linear versus nonlinear) and identifies promising candidate models. Since embedding a forecasting model as tuning agent into PSO – or any other metaheuristic – would involve processing batches of data that become available throughout successive PSO iterations, a learningcurve analysis is conducted to explore the forecasting models’ sensitivity towards data size and simulate online learning. This complements the assessment of different candidate models and lays ground for future research to develop and assess a hybrid metaheuristic with integrated tuning agent. The paper is organized as follows: Related work concerning the tuning of metaheuristics as well as hybrid procedures at the interface of metaheuristics and data mining is reviewed in the following section, before the proposed tuning approach together with some background on PSO and regression modeling is elaborated in Section 3. Section 4 explains the design of the empirical study; respective results are reported in Section 5. Limitations and opportunities for future research are discussed in Section 6, before conclusions are drawn in Section 7.

The paper offers a novel perspective on the task of tuning parameter settings in metaheuristics. Employing information concerning the particular decision task and the heuristic’s past search operations, an automated tuning approach on the basis of regression has been proposed. The approach is generic in principle and has been evaluated empirically in conjunction with the PSO algorithm and one particular problem instance. The empirical results indicate that the efficacy of parameter settings can indeed be related to problem-specific information (i.e., particle’s signatures), so that a regression-based tuning approach appears to be promising in general. An important result of the experiment is that this particular application of regression requires nonlinear forecasting techniques, whereas linear regression, considered in previous work on metaheuristic tuning, is less suitable. In particular, the REGFOR procedure has been identified as most promising approach, so that subsequent work to integrate PSO with a regression-based tuning agent should initially consider this type of model