Studying the effect of population size in distributed evolutionary algorithms on heterogeneous clusters

• We present a study on the adaptation of the island sizes of a distributed Evolutionary Algorithm to the computational power of the nodes of an heterogeneous cluster.
• Three problems with different characteristics and computational demands (MMDP, OneMax and Rosenbrock Shifted Function), have been used to give an insight of the effects of this proposal and tested in two different hardware systems (homogeneous and heterogeneous cluster).
• As a first step, we have adapted (offline) population sizes proportionally to the attained generations to obtain the optimum with the same population size in all islands.
• We also have adapted the population size during runtime (online) comparing with the current number of generations of the neighbours of the topology.
• Results show that adapting (online and offline) the population sizes to the computational power of the nodes of a heterogeneous cluster can decrease time to obtain the optimum solution.

Distributed Evolutionary Algorithms are traditionally executed on homogeneous dedicated clusters, despite most scientists have access mainly to networks of heterogeneous nodes (e.g., desktop PCs in a lab). Fitting this kind of algorithms to these environments, so that they can take advantage of their heterogeneity to save running time, is still an open problem. The different computational power of the nodes affects the performance of the algorithm, and tuning or fitting it to each node properly could reduce execution time.Since the distributed Evolutionary Algorithms include a whole range of parameters that influence the performance, this paper proposes a study on the population size. This parameter is one of the most important, since it has a direct relationship with the number of iterations needed to find the solution, as it affects the exploration factor of the algorithm. The aim of this paper consists in validating the following hypothesis: fitting the sub-population size to the computational power of the heterogeneous cluster node can lead to an improvement in running time with respect to the use of the same population size in every node.Two parameter size schemes have been tested, an offline and an online parameter setting, and three problems with different characteristics and computational demands have been used.Results show that setting the population size according to the computational power of each node in the heterogeneous cluster improves the time required to obtain the optimal solution. Meanwhile, the same set of different size values could not improve the running time to reach the optimum in a homogeneous cluster with respect to the same size in all nodes, indicating that the improvement is due to the interaction of the different hardware resources with the algorithm. In addition, a study on the influence of the different population sizes on each stage of the algorithm is presented. This opens a new research line on the fitting (offline or online) of parameters of the distributed Evolutionary Algorithms to the computational power of the devices.

Figure optionsDownload as PowerPoint slide