(An) ant colony optimization approach for the maximum independent set problem

Abstract

The ant colony optimization (ACO) is a probabilistic Meta-heuristic algorithm which has been developed in recent years. Originally ACO was used for solving the well-known Traveling Salesperson Problem. More recently, ACO has been used to solve many difficult problems. In this thesis, we develop an ant colony optimization method to solve the maximum independent set problems, which is known to be NP-hard. In this thesis, we suggest a new method for local information of ACO. Parameters of the ACO algorithm are tuned by evolutionary operations which have been used in forecasting and time series analysis. To show the performance of the ACO algorithm, the set of instances from discrete mathematics and computer science (DIMACS) benchmark graphs are tested, and computational results are compared with a previously developed ACO algorithm and other heuristic algorithms.