This paper explores highly efficient cooperative strategies for population-based parallel metaheuristics, focusing on the integration of shared memory and Remote Memory Access (RMA) operations provided by MPI-3. Most parallel metaheuristic proposals use island-based models with point-to-point communications in their cooperative strategies. These communications can saturate the network and buffers by sending information that often will not be used at the destination, thus resulting in a waste of resources when dealing with these types of applications. In this paper we evaluate other alternative communication protocols that use shared memory windows and RMA operations. Under these new models, the movement of information over the network is on-demand and requested by the source, maximizing resource efficiency. Although the approaches and descriptions in the paper are generic, a particular metaheuristic, the Ant Colony Optimization (ACO), is used to carry out the experiments. The results obtained draw interesting conclusions that can serve to guide the future parallelization of other metaheuristics.
AbdelhafezALuqueGAlbaE (2020) Parallel execution combinatorics with metaheuristics: comparative study. Swarm and Evolutionary Computation55: 100692. https://doi.org/10.1016/j.swevo.2020.100692
2.
Abed-alguniBHPaulD (2022) Island-based Cuckoo search with elite opposition-based learning and multiple mutation methods for solving optimization problems. Soft Computing26(7): 3293–3312. https://doi.org/10.1007/s00500-021-06665-6
3.
AhmadFMat IsaNAHussainZ, et al. (2015) A GA-based feature selection and parameter optimization of an ANN in diagnosing breast cancer. Pattern Analysis & Applications18: 861–870. https://doi.org/10.1007/s10044-014-0375-9
4.
AlbaELuqueGNesmachnowS (2013) Parallel metaheuristics: recent advances and new trends. International Transactions in Operational Research20(1): 1–48. https://doi.org/10.1111/j.1475-3995.2012.00862.x
5.
BakerBMAyechewM (2003) A genetic algorithm for the vehicle routing problem. Computers & Operations Research30(5): 787–800.
6.
BañosROrtegaJGilC, et al. (2016) Analysis of OpenMP and MPI implementations of meta-heuristics for vehicle routing problems. Applied Soft Computing43: 262–275. https://doi.org/10.1016/j.asoc.2016.02.035
7.
BeheshtiZShamsuddinSMH (2013) A review of population-based meta-heuristic algorithms. International Journal of Advances in Soft Computing and its Applications5(1): 1–35.
8.
CarrascoJGarcíaSRuedaM, et al. (2020) Recent trends in the use of statistical tests for comparing swarm and evolutionary computing algorithms: practical guidelines and a critical review. Swarm and Evolutionary Computation54: 100665. https://doi.org/10.1016/j.swevo.2020.100665
9.
CastilloEJainNCasasM, et al. (2019) Optimizing computation-communication overlap in asynchronous task-based programs. In: Proceedings of the ACM International Conference on Supercomputing, pp. 380–391.
10.
ChandraR (2001) Parallel Programming in Openmp. Morgan kaufmann.
CzarnulP (2018) Parallel Programming for Modern High Performance Computing Systems. CRC Press.
13.
DepolliMTrobecRFilipičB (2013) Asynchronous master-slave parallelization of differential evolution for multi-objective optimization. Evolutionary Computation21(2): 261–291. https://doi.org/10.1162/EVCO_a_00076
14.
DerracJGarcíaSMolinaD, et al. (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation1(1): 3–18. https://doi.org/10.1016/j.swevo.2011.02.002
15.
DiazJMunoz-CaroCNinoA (2012) A survey of parallel programming models and tools in the multi and many-core era. IEEE Transactions on Parallel and Distributed Systems23(8): 1369–1386. https://doi.org/10.1109/tpds.2011.308
16.
DinanJBalajiPBuntinasD, et al. (2016) An implementation and evaluation of the mpi 3.0 one-sided communication interface. Concurrency and Computation: Practice and Experience28(17): 4385–4404. https://doi.org/10.1002/cpe.3758
17.
DorigoMGambardellaLM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation1(1): 53–66. https://doi.org/10.1109/4235.585892
18.
DorigoMStützleT (2019) Ant Colony Optimization: Overview and Recent Advances. Springer.
DurilloJJNebroAJLunaF, et al. (2008) A study of master-slave approaches to parallelize NSGA-II. In: 2008 IEEE International Symposium on Parallel and Distributed Processing. IEEE, pp. 1–8.
22.
FangJHuangCTangT, et al. (2020) Parallel programming models for heterogeneous many-cores: a comprehensive survey. CCF Transactions on High Performance Computing2: 382–400. https://doi.org/10.1007/s42514-020-00039-4
23.
GmysJCarneiroTMelabN, et al. (2020) A comparative study of high-productivity high-performance programming languages for parallel metaheuristics. Swarm and Evolutionary Computation57: 100720. https://doi.org/10.1016/j.swevo.2020.100720
24.
GonzálezPArgüeso-AlejandroPPenasDR, et al. (2019) Hybrid parallel multimethod hyperheuristic for mixed-integer dynamic optimization problems in computational systems biology. The Journal of Supercomputing75(7): 3471–3498. https://doi.org/10.1007/s11227-019-02871-0
25.
GonzálezPOsorioRRPardoXC, et al. (2022a) An efficient ant colony optimization framework for HPC environments. Applied Soft Computing114: 108058. https://doi.org/10.1016/j.asoc.2021.108058
26.
GonzálezPPrado-RodriguezRGáborA, et al. (2022b) Parallel ant colony optimization for the training of cell signaling networks. Expert Systems with Applications208: 118199. https://doi.org/10.1016/j.eswa.2022.118199
27.
González-ÁlvarezDLVega-RodríguezMARubio-LargoÁ (2017) A hybrid MPI/OpenMP parallel implementation of NSGA-II for finding patterns in protein sequences. The Journal of Supercomputing73: 2285–2312. https://doi.org/10.1007/s11227-016-1916-3
28.
GroppWLuskESkjellumA (1999) Using MPI: portable parallel programming with the message-passing interface. MIT press, Vol. volume 1.
29.
HjelmN (2016) An evaluation of the one-sided performance in open mpi. In: Proceedings of the 23rd European MPI Users’ Group Meeting, pp. 184–187.
30.
HuoJLiuLZhangY (2018) An improved multi-cores parallel artificial bee colony optimization algorithm for parameters calibration of hydrological model. Future Generation Computer Systems81: 492–504. https://doi.org/10.1016/j.future.2017.07.020
31.
HussainKMohd SallehMNChengS, et al. (2019) Metaheuristic research: a comprehensive survey. Artificial Intelligence Review52: 2191–2233. https://doi.org/10.1007/s10462-017-9605-z
32.
IzzoDRucinskiMAmpatzisC (2009) Parallel global optimisation meta-heuristics using an asynchronous island-model. In: 2009 IEEE Congress on Evolutionary Computation. IEEE, pp. 2301–2308.
33.
JungSHaghaniA (2001) Genetic algorithm for the time-dependent vehicle routing problem. Transportation Research Record1771(1): 164–171. https://doi.org/10.3141/1771-21
34.
KennedyJEberhartR (1995) Particle swarm optimization. In: Proceedings of ICNN’95-international Conference on Neural Networks. IEEE, Vol. 4, pp. 1942–1948. https://doi.org/10.1109/icnn.1995.488968
35.
KhanASimHVazhkudaiSS, et al. (2021) An analysis of system balance and architectural trends based on top500 supercomputers. In: The International Conference on High Performance Computing in Asia-Pacific Region, pp. 11–22.
36.
KruskalWHWallisWA (1952) Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association47(260): 583–621. https://doi.org/10.1080/01621459.1952.10483441
37.
LiuJSarkerRElsayedS, et al. (2024) Large-scale evolutionary optimization: a review and comparative study. Swarm and Evolutionary Computation85: 101466. https://doi.org/10.1016/j.swevo.2023.101466
38.
NavauxPOALorenzonAFda Silva SerpaM (2023) Challenges in high-performance computing. Journal of the Brazilian Computer Society29(1): 51–62. https://doi.org/10.5753/jbcs.2023.2219
39.
NedjahNde Moraes CalazanRde Macedo MourelleL (2017) A fine-grained parallel particle swarm optimization on many-core and multi-core architectures. In: Parallel Computing Technologies: 14Th International Conference, PaCT 2017, Nizhny Novgorod, Russia, September 4-8, 2017, Proceedings 14. Springer, pp. 215–224.
40.
OmidvarMNLiXYaoX (2021a) A review of population-based metaheuristics for large-scale black-box global optimization—part i. IEEE Transactions on Evolutionary Computation26(5): 802–822. https://doi.org/10.1109/tevc.2021.3130838
41.
OmidvarMNLiXYaoX (2021b) A review of population-based metaheuristics for large-scale black-box global optimization—part ii. IEEE Transactions on Evolutionary Computation26(5): 823–843. https://doi.org/10.1109/tevc.2021.3130835
PearceO (2019) Exploring utilization options of heterogeneous architectures for multi-physics simulations. Parallel Computing87: 35–45. https://doi.org/10.1016/j.parco.2019.05.003
44.
PenasDRBangaJRGonzálezP, et al. (2015a) Enhanced parallel differential evolution algorithm for problems in computational systems biology. Applied Soft Computing33: 86–99. https://doi.org/10.1016/j.asoc.2015.04.025
45.
PenasDRGonzálezPEgeaJA, et al. (2015b) Parallel metaheuristics in computational biology: an asynchronous cooperative enhanced scatter search method. Procedia Computer Science51: 630–639. https://doi.org/10.1016/j.procs.2015.05.331
46.
PenasDRGonzálezPEgeaJA, et al. (2017) Parameter estimation in large-scale systems biology models: a parallel and self-adaptive cooperative strategy. BMC Bioinformatics18(1): 1–24. https://doi.org/10.1186/s12859-016-1452-4
47.
Prado-RodríguezRGonzálezPBangaJR, et al. (2023) Improved cooperative ant colony optimization for the solution of binary combinatorial optimization applications. Expert Systems41: e13554. https://doi.org/10.1111/exsy.13554
48.
Prado-RodríguezRGonzálezPBangaJR (2025) A parameter control strategy for parallel island-based metaheuristics. Expert Systems42(6): e70061. https://doi.org/10.1111/exsy.70061
49.
PriceKV (1999) An introduction to differential evolution. In: New Ideas in Optimization, pp. 79–108.
50.
SchryenG (2020) Parallel computational optimization in operations research: a new integrative framework, literature review and research directions. European Journal of Operational Research287(1): 1–18. https://doi.org/10.1016/j.ejor.2019.11.033
51.
SchuchartJBouteillerABosilcaG (2019) Using MPI-3 RMA for active messages. In: 2019 IEEE/ACM Workshop on Exascale MPI (ExaMPI). IEEE, pp. 47–56.
SkakovskiAJȩdrzejowiczP (2019) An island-based differential evolution algorithm with the multi-size populations. Expert Systems with Applications126: 308–320. https://doi.org/10.1016/j.eswa.2019.02.027
54.
SongYZhaoGZhangB, et al. (2023) An enhanced distributed differential evolution algorithm for portfolio optimization problems. Engineering Applications of Artificial Intelligence121: 106004. https://doi.org/10.1016/j.engappai.2023.106004
55.
StarzecMStarzecGByrskiA, et al. (2020) Desynchronization in distributed Ant Colony Optimization in HPC environment. Future Generation Computer Systems109: 125–133. https://doi.org/10.1016/j.future.2020.03.045
56.
SterlingTBrodowiczMAndersonM (2017) High Performance Computing: Modern Systems and Practices. Morgan Kaufmann.
57.
StornRPriceK (1997) Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization11: 341–359. https://doi.org/10.1023/a:1008202821328
58.
StrofylasGAPorfyriKNNikolosIK, et al. (2018) Using synchronous and asynchronous parallel differential evolution for calibrating a second-order traffic flow model. Advances in Engineering Software125: 1–18. https://doi.org/10.1016/j.advengsoft.2018.08.011
SuarezEEickerNLippertT (2019) Modular supercomputing architecture: from idea to production. In: Contemporary High Performance Computing. CRC Press, pp. 223–255.
61.
TalbiEG (2009) Metaheuristics: From Design to Implementation. John Wiley & Sons.
62.
TurgutMSTurgutOEEliiyiDT (2020) Island-based crow search algorithm for solving optimal control problems. Applied Soft Computing90: 106170. https://doi.org/10.1016/j.asoc.2020.106170
63.
WangLLiL (2010) An effective differential evolution with level comparison for constrained engineering design. Structural and Multidisciplinary Optimization41: 947–963. https://doi.org/10.1007/s00158-009-0454-5
WangZShenYLiS, et al. (2023) A fine-grained fast parallel genetic algorithm based on a ternary optical computer for solving traveling salesman problem. The Journal of Supercomputing79(5): 4760–4790. https://doi.org/10.1007/s11227-022-04813-9
66.
WeiseTChenYLiX, et al. (2020) Selecting a diverse set of benchmark instances from a tunable model problem for black-box discrete optimization algorithms. Applied Soft Computing92: 106269. https://doi.org/10.1016/j.asoc.2020.106269
YangBChenYZhaoZ (2007) Survey on applications of particle swarm optimization in electric power systems. In: 2007 IEEE International Conference on Control and Automation. IEEE, pp. 481–486.
69.
ZhouYHeFHouN, et al. (2018) Parallel ant colony optimization on multi-core SIMD CPUs. Future Generation Computer Systems79: 473–487. https://doi.org/10.1016/j.future.2017.09.073
