COSEARCH: A parallel cooperative metaheuristic

In order to design a well-balanced metaheuristic for robustness, we propose the COSEARCH approach which manages the cooperation of complementary heuristic methods via an adaptive memory which contains a history of the search already done. In this paper, we present the idiosyncrasies of the COSEARCH approach and its application for solving large scale instances of the quadratic assignment problem (QAP). We propose an original design of the adaptive memory in order to focus on high quality regions of the search and avoid attractive but deceptive areas. For the QAP, we have hybridized three heuristic agents of complementary behaviours: a Tabu Search is used as the main search algorithm, a Genetic Algorithm is in charge of the diversification and a Kick Operator is applied to intensify the search. The evaluations have been executed on large scale network of workstations via a parallel environment which supports fault tolerance and adaptive dynamic scheduling of tasks.