Solving the mesh-partitioning problem with an ant-colony algorithm
Many real-world engineering problems can be expressed in terms of partial differential equations and solved by using the finite-element method, which is usually parallelised, i.e. the mesh is divided among several processors. To achieve high parallel efficiency it is important that the mesh is partitioned in such a way that workloads are well balanced and interprocessor communication is minimised. In this paper we present an enhancement of a technique that uses a nature-inspired metaheuristic approach to achieve higher-quality partitions. The so-called multilevel ant-colony algorithm, which is a relatively new metaheuristic search technique for solving optimisation problems, was applied and studied, and the possible parallelisation of this algorithm is discussed. The multilevel ant-colony algorithm performed very well and is superior to classical k-METIS and Chaco algorithms; it is even comparable with the combined evolutionary/multilevel scheme used in the JOSTLE evolutionary algorithm and returned solutions that are better than the currently available solutions in the Graph Partitioning Archive. (C) 2004 Elsevier B.V. All rights reserved.
algorithms finite-element method mesh partitioning ant-colony optimsation