ANTabu

Olivier Roux, Laboratoire d'Informatique du Littoral, Université du Littoral, Calais, France
Email: roux@lil.univ-littoral.fr

Cyril Fonlupt, Laboratoire d'Informatique du Littoral, Université du Littoral, Calais, France
Email: fonlupt@lil.univ-littoral.fr

D. Robilliard, Laboratoire d'Informatique du Littoral, Université du Littoral, Calais, France
Email: robillia@lil.univ-littoral.fr

E.-G. Talbi, Laboratoire d'Informatique Fondamentale de Lille, Université des Sciences et Technologies de Lille, France
Email: talbi@lifl.fr

We proposed a powerful and robust resolution method for the QAP called ANTabu, resolution based on the hybridation of a Tabu search and an ants system. This system is based on the natural colony behavior of ants during the search of food. Our algorithm improves the Taillard's HAS-QAP method by using information gathered during the search. The pheromone matrix is used as a short term memory, and we introduce a new structure the frequencies matrix, that is used as a long term memory. Instead of using only the best solution found so far, to update the pheromone matrix, all intermediate solutions participate to the update.

In our algorithm, the local search is based on a Tabu method, that exhibits good performance. Results show a notable increase of performances compared to HAS-QAP. By comparing our results with a robust Tabu search for the QAP, it clearly appears that the information brought ants are really useful and are not only due to the local scheme. Results obtained with this parallel implementation (PVM) plead for a more widely spread use of inter-processes communication in parallel heuristics. Future works will include a modification of the stop criterion of the local research function and a portage on adaptive parallel platform (MARS) so as to provide use of large heterogeneous networks.