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.