An Efficient Ant Colony Optimization Framework for HPC Environments
Use este enlace para citar
http://hdl.handle.net/2183/30140
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución-NoComercial-SinDerivadas 4.0 Internacional
Coleccións
- GI-GAC - Artigos [192]
Metadatos
Mostrar o rexistro completo do ítemTítulo
An Efficient Ant Colony Optimization Framework for HPC EnvironmentsData
2022Cita bibliográfica
GONZÁLEZ, Patricia, OSORIO, Roberto R., PARDO, Xoan C., BANGA, Julio R. and DOALLO, Ramón, 2022. An efficient ant colony optimization framework for HPC environments. Applied Soft Computing. 1 January 2022. Vol. 114, p. 108058. DOI 10.1016/j.asoc.2021.108058
Resumo
[Abstract] Combinatorial optimization problems arise in many disciplines, both in the basic sciences and in applied fields such as engineering and economics. One of the most popular combinatorial optimization methods is the Ant Colony Optimization (ACO) metaheuristic. Its parallel nature makes it especially attractive for implementation and execution in High Performance Computing (HPC) environments. Here we present a novel parallel ACO strategy making use of efficient asynchronous decentralized cooperative mechanisms. This strategy seeks to fulfill two objectives: (i) acceleration of the computations by performing the ants’ solution construction in parallel; (ii) convergence improvement through the stimulation of the diversification in the search and the cooperation between different colonies. The two main features of the proposal, decentralization and desynchronization, enable a more effective and efficient response in environments where resources are highly coupled. Examples of such infrastructures include both traditional HPC clusters, and also new distributed environments, such as cloud infrastructures, or even local computer networks. The proposal has been evaluated using the popular Traveling Salesman Problem (TSP), as a well-known NP-hard problem widely used in the literature to test combinatorial optimization methods. An exhaustive evaluation has been carried out using three medium and large size instances from the TSPLIB library, and the experiments show encouraging results with superlinear speedups compared to the sequential algorithm (e.g. speedups of 18 with 16 cores), and a very good scalability (experiments were performed with up to 384 cores improving execution time even at that scale).
Palabras chave
Combinatorial optimization
Metaheuristics
Ant Colony Optimization
High performance computing
MPI
OpenMP
Metaheuristics
Ant Colony Optimization
High performance computing
MPI
OpenMP
Descrición
Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG
Versión do editor
Dereitos
Atribución-NoComercial-SinDerivadas 4.0 Internacional