Mesh partitioning: a multilevel ant-colony-optimization algorithm

Mesh partitioning is an important problem that has extensive applications in many areas. Multilevel algorithms are a successful class of optimization techniques which address the mesh partitioning problem. In this paper we present an enhancement of the technique that uses a nature inspired metaheuristic to achieve higher quality partitions. We apply and study a multilevel ant-colony (MACO) optimization, which is a relatively new metaheuristic search technique for solving optimization problems. The MACO algorithm performed very well and is superior to the classical k-METIS and Chaco algorithms. Furthermore, it is even comparable to the combined evolutionary/multilevel scheme used in the JOSTLE evolutionary algorithm. Our MACO algorithm returned also some solutions that are better than currently available solutions in the graph partitioning archive.