Parameter Control Strategies of Parallel Hybrid Metaheuristics Applied to the Quadratic Assignment Problem

Abstract

ABSTRACT : The Quadratic Assignment Problem (QAP) is one of the most challenging combinatorial optimization problems with many real-life applications. Multiple methods have been created to solve QAP, exact and approximate methods, among others. Meta- heuristics are a subset of approximative methods which have shown to be very efficient in solving QAP. Their behavior can be controlled by a set of parameters. Currently, the best solvers are based on hybrid and parallel metaheuristics. However, the design of parallel hybrid methods requires even more the fine tuning of a larger number of parameters. The parameter setting problem (PSP) is the task of finding the correct values of the metaheuristic parameters that results in the best possible performance. It is possible to identify four main ways for solving the PSP, these are: Parameter Tuning Strategies, Parameter Control Strategies, Instance-specific Parameter Tuning Strategies and HyperHeuristics. Several methods for solving the PSP have been proposed. However, there is a need for parameter control strategies for single-solution metaheuristics, more notorious in parallel hybrid metaheuristics. To solve this problem, we have proposed PACAS, a framework to configure the PArameter Control Adaptation for Single solution metaheuristics in a parallel hybrid solver for the efficient solution of combinatorial optimization problems. We proposed a Java implementation of framework J-PACAS, which implemented the functionality for solving the QAP. Our implementation uses three popular metaheuristics applied to QAP: the Ro- bust Tabu Search, the Extremal Optimization method and a simple Multi-start Local Search. J-PACAS also supplies three different strategies to perform the adaptation of the parameters. We present the results obtained by executing an experimental evaluation on a set of very difficult instances of QAPLIB. We explore different parameter control strategies, with different parallel configurations (independent or cooperative). We compare the best J-PACAS configuration identified in the experimental evaluation against a competitive state-of-the-art parameter control method, finding that our implementation presents a similar performance in small instances and a better performance in hard instances of the QAPLIB benchmark.