An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem.

Abstract: The minimum weight vertex cover problem is an interesting and applicable NP-hard problem that has been investigated from many different aspects. The ant colony optimization metaheuristic is a relatively new technique that was successfully adjusted and applied to many hard combinatorial optimization problems, including the minimum weight vertex cover problem. Some kind of hybridization or exploitation of the knowledge about specific problem often greatly improves the performance of standard evolutionary algorithms. In this article we propose a pheromone correction heuristic strategy that uses information about the best-found solution to exclude suspicious elements from it. Elements are suspicious if they have some undesirable properties that make them unlikely members of the optimal solution. This hybridization improves pure ant colony optimization algorithm by avoiding early trapping in local convergence. We tested our algorithm on numerous test-cases that were used in the previous research of the same problem and our algorithm uniformly performed better, giving slightly better results in significantly shorter time. [Copyright &y& Elsevier]