Improved Method for Parallelization of Evolutionary Metaheuristics

Diego Díaz, Pablo Valledor, Borja Ena, Miguel Iglesias and César Menéndez
Additional contact information
Diego Díaz: ArcelorMittal Global R&D Asturias, Av. Marques de Suances s/n, 33400 Aviles, Spain
Pablo Valledor: ArcelorMittal Global R&D Asturias, Av. Marques de Suances s/n, 33400 Aviles, Spain
Borja Ena: ArcelorMittal Global R&D Asturias, Av. Marques de Suances s/n, 33400 Aviles, Spain
Miguel Iglesias: ArcelorMittal Global R&D Asturias, Av. Marques de Suances s/n, 33400 Aviles, Spain
César Menéndez: Engineering Projects, University of Oviedo, EIMEM Independencia 13, 33001 Oviedo, Spain

Mathematics, 2020, vol. 8, issue 9, 1-15

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: metaheuristics; genetic algorithm; ant colony optimization; distributed computing (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/9/1476/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/9/1476/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:9:p:1476-:d:407259

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().