Towards an Evolutionary Method — Cooperating Multi-Thread Parallel Tabu Search Hybrid

We present a first version of a hybrid metaheuristic that combines a cooperative multi-thread parallel tabu search procedure and a genetic search engine. The two algorithms evolve independently while systematically and asynchronously exchanging solutions. The method appears to be the first to propose a cooperation scheme where the initial population of the genetic algorithm is an elite set of solutions obtained by the parallel metaheuristic, while the best individuals generated during the genetic search enrich the pool of solutions available to all tabu search threads. Experimentation with instances of a multicommodity, capacitated, fixed cost network design formulation leads to an initial assessment of the performances of the method.