Enhancing Parallel Cooperative Trajectory Based Metaheuristics with Path Relinking

This paper proposes a novel algorithm combining path re-linking with a set of cooperating trajectory based parallel algorithms to yield a new metaheuristic of enhanced search features. Algorithms based on the exploration of the neigh-borhood of a single solution, like simulated annealing (SA), have offered accurate results for a large number of real-world problems in the past. Because of their trajectory based na-ture, some advanced models such as the cooperative one are competitive in academic problems, but still show many limitations in addressing large scale instances. In addition, the field of parallel models for trajectory methods has not deeply been studied yet (at least in comparison with par-allel population based models). In this work, we propose a new hybrid algorithm which improves cooperative single solution techniques by using path relinking, allowing both to reduce the global execution time and to improve the ef-ficacy of the method. We test here this new model using a large benchmark of instances of two well-known NP-hard problems: MAXSAT and QAP, with competitive results