Using parallelism in experimenting and fine tuning of parameters for metaheuristics

We address the issue of using parallel implementations as a mean for efficient experimenting and fine tuning of parameters for metaheuristics --a very difficult and especially time consuming process. This is particularly of great impact to the metaheuristics, at least for two reasons: (a) measuring the performance of a metaheuristic implementation requires testing on a large set of instances and on real world instances usually of big and very big size-- a considerable amount of time is needed to accomplish it; (b) the finding of right values for the search parameters of the metaheuristic is almost indispensable for the success of the metaheuristic implementation. Due to this, considerable efforts have been done by researchers and practitioners to provide, on the one hand, a methodology and rigorous basis for experimental evaluation of heuristics (e.g. Rardin and Uzsoy 2001, Barr et al. 1995) and, on the other, to find efficient approaches for fine tuning of parameters such as developing specific software (e.g. Adenso-Diaz and Laguna 2002), use of experimental design (e.g. Coy et al. 2000) and self-adaptive procedures (e.g. Kivijarvi et al.2003). In this paper we show that parallel implementations of metaheuristics based on simple parallel models are efficient tools for both experimenting and fine tuning of parameters. Our proposal is based on two parallel models: the Independent Runs (IR) and the Independent Runs with Autonomous Strategies (IRAS). To illustrate our proposal, we implement the Tabu Search for the 0-1 Multidimensional Knapsack Problem in both models. We use the two implementations for experimenting and fine tuning of parameters obtaining high quality solutions as compared with best known up-to-date results for the problem.Postprint (published version