Analyzing the Energy Consumption of Sequential and Parallel Metaheuristics

摘要

Real-life problems are usually time-consuming since they require solving large instances of NP-hard problems. Exact search methods in most of the cases cannot afford practical solutions for such problems. Metaheuristics arise as promising solvers for these problems, by obtaining acceptable solutions in terms of quality and computational cost in a reasonable time bound. Nowadays, energy efficiency is also taken into consideration during the design of new algorithms because of the million times that algorithms run on labs and computation centers. This work presents two novel experiments for investigating the numerical performance and energy efficiency of the sequential and parallel metaheuristics. The main aim of this study is to analyze the energy consumption of three well-known and commonly used metaheuristics (Genetic Algorithm, Variable Neighborhood Search, and Simulated Annealing) and their parallel versions. The discussions reveal the differences/similarities between the different sequential/parallel algorithms, which include trajectory-based and population-based metaheuristics so that this study is useful for the future design of energy-aware algorithms.