An improved ACO metaheuristic for solving the MCP

In this paper, an ant colony optimization (ACO) algorithm with local pheromone update strategy for solving maximum clique problem (MCP) is proposed. It is based on iteration. During each iteration cycle, ants in the colony guide their decisions by pheromone trails they deposit on vertices of the MCP graph while building solutions. And when an ant has constructed a clique, the local pheromone update procedure is implemented to ensure diversification in an iteration cycle. Once all ants have constructed their solutions, the pheromone is updated according to global pheromone update rule which increases the amount of pheromone on vertices that have been found in high quality solutions so as to intensify the search towards the “promising” areas in the search space. Experiments on DIMACS benchmark instances are presented and the results show that the improved ACO metaheuristic outperforms other population-based metaheuristics such as EA/G algorithm which is the best genetic algorithm on the problem reported so far.