An ant system for the maximum independent set problem

Abstract

Early applications of Ant Colony Optimization (ACO) have been mainly concerned with solving ordering problems (e.g., the Traveling Salesperson Problem). More recently, promising results were obtained for solving the Multiple Knapsack Problem by introducing a modification of the standard Ant System algorithm. In this paper we extend our study on the applicability of the ACO approach to subset problems. The computational study involves its applicability for solving the Maximum Independent Set Problem (MISP). The set of instances tested were either randomly generated by specific methods or taken from the so-called DIMACS benchmark graphs. The reported results which are comparable with different state-of-the-art algorithms show the potential of the ACO approach for solving the MISP.