Reactive prohibition-based ant colony optimization (RPACO): a new parallel architecture for constrained clique sub-graphs

We introduce a new algorithm that combines the stigmergetic capabilities of the ant colony optimization (AGO) with local search heuristics to solve the maximum and maximum-weighted clique problem. Our new algorithm: A reactive prohibition-based ant colony optimization (RPACOMCP), complements the intelligent ant colony search with a prohibition-based diversification technique, where the amount of diversification is determined in an automated way through a feedback (history-sensitive) scheme. Based on prohibition, some local moves are temporarily prohibited in order to avoid repeated cycles in the search trajectory and to explore new parts of the total search space. Diversification could be enforced and the ACO search continued beyond local optimal points. One of the main advantages of this approach is the use of parallelism both to have a number of ant colonies searching simultaneously and to have a function distribution of local search procedures. This architecture thus provides a powerful tool to tackle difficult problems using all available processing power. The algorithm is tested on many representative DIMACS benchmark graph instances and results are compared with GLS [E. Marchiori, (2002)], a genetic local search approach for MCP. It is shown that the proposed PACO algorithm finds larger cliques in reasonable time, on average, on a wide majority of benchmark instances of the DIMACS library, even though it does not reach the best known results on a few benchmark instances. We also showed that the PACO algorithm outperforms the nonprohibition version on most hard graph instances.