A Parallel Ant Colony Optimization for the Maximum-Weight Clique Problem

Didier El Baz (1) , Mhand Hifi (2) , Lei Wu (2) , Xiaochuan Shi (3)

1 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme
2 EPROAD - Eco-Procédés Optimisation et Aide à la Décision - UR UPJV 4669
3 Wuhan University [China]

In this paper, we proposes a parallel ant colony optimization based heuristic for solving the maximum weight clique problem, which is a variation of the classical maximum clique problem. The proposed parallel computing model is based on a cooperation concept with consideration of a multiple ant colonies system. In the cooperation system, we are given a message center and a number of ant colonies. The ant colonies aim at exploring the solution space with their own search strategies. The message center first collects the solution information from the different ant colonies, and then it shares the best solution with them. The performance of the proposed method was evaluated on a set of the standard benchmark instances from literature. The obtained results are compared to those reached by the Cplex solver and the best solutions reported in the literature. As shown from the experimental results, encouraging results have been obtained.

Mots clés: Parallel algorithms; weight clique; cooperative; ant colony

Domaines: Intelligence artificielle [cs.AI]; Calcul parallèle, distribué et partagé [cs.DC]; Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]; Analyse numérique [cs.NA]; Robotique [cs.RO]; Recherche opérationnelle [math.OC]

Didier El Baz, Mhand Hifi, Lei Wu, Xiaochuan Shi. A Parallel Ant Colony Optimization for the Maximum-Weight Clique Problem. IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW 2016), May 2016, Chicago, United States. pp.796-800, ⟨10.1109/IPDPSW.2016.111⟩. ⟨hal-02115761⟩