Improved Method for Parallelization of Evolutionary Metaheuristics
Open Access
- 1 September 2020
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 8 (9) , 1476
Abstract
This paper introduces a method for the distribution of any and all population-based metaheuristics. It improves on the naive approach, independent multiple runs, while adding negligible overhead. Existing methods that coordinate instances across a cluster typically require some compromise of more complex design, higher communication loads, and solution propagation rate, requiring more work to develop and more resources to run. The aim of the new method is not to achieve state-of-the-art results, but rather to provide a better baseline method than multiple independent runs. The main concept of the method is that one of the instances receives updates with the current best solution of all other instances. This work describes the general approach and its particularization to both genetic algorithms and ant colony optimization for solving Traveling Salesman Problems (TSPs). It also includes extensive tests on the TSPLIB benchmark problems of resulting quality of the solutions and anytime performance (solution quality versus time to reach it). These tests show that the new method yields better solutions for about two thirds of the problems and equivalent solutions in the remaining third, and consistently exhibits better anytime performance.Keywords
Funding Information
- Gobierno del Principado de Asturias (FC-GRUPIN-IDI/2018/000225)
This publication has 15 references indexed in Scilit:
- Handbook of Metaheuristics2019
- Ant Colony Optimization: Overview and Recent Advances2018
- Ant Colony Optimization on a Budget of 10002014
- Scheduling a Galvanizing Line by Ant Colony Optimization2014
- Parallel Ant Colony Optimization on Graphics Processing UnitsJournal of Parallel and Distributed Computing, 2013
- A survey on parallel ant colony optimizationApplied Soft Computing, 2011
- Parallel Metaheuristics for Combinatorial Optimization2002
- Popular Ensemble Methods: An Empirical StudyJournal of Artificial Intelligence Research, 1999
- Ant Algorithms for Discrete OptimizationArtificial Life, 1999
- Parallel Genetic Algorithms Applied to the Traveling Salesman ProblemSIAM Journal on Optimization, 1991