An ant colony algorithm for solving Max-cut problem

Max-cut problem is an NP-complete and classical combinatorial optimization problem that has a wide range of applications in different domains, such as bioinformatics, network optimization, statistical physics, and very large scale integration design. In this paper we investigate the capabilities of the ant colony optimization (ACO) heuristic for solving the Max-cut problem and present an AntCut algorithm. A large number of simulation experiments show that the algorithm can solve the Max-cut problem more efficiently and effectively.