Analyzing self-★ island-based memetic algorithms in heterogeneous unstable environments

Abstract

Computational environments emerging from the pervasiveness of networked devices offer a plethora of opportunities and challenges. The latter arise from their dynamic, inherently volatile nature that tests the resilience of algorithms running on them. Here we consider the deployment of population-based optimization algorithms on such environments, using the island model of memetic algorithms for this purpose. These memetic algorithms are endowed with self-★ properties that give them the ability to work autonomously in order to optimize their performance and to react to the instability of computational resources. The main focus of this work is analyzing the performance of these memetic algorithms when the underlying computational substrate is not only volatile but also heterogeneous in terms of the computational power of each of its constituent nodes. To this end, we use a simulated environment that allows experimenting with different volatility rates and heterogeneity scenarios (that is, different distributions of computational power among computing nodes), and we study different strategies for distributing the search among nodes. We observe that the addition of self-scaling and self-healing properties makes the memetic algorithm very robust to both system instability and computational heterogeneity. Additionally, a strategy based on distributing single islands on each computational node is shown to perform globally better than placing many such islands on each of them (either proportionally to their computing power or subject to an intermediate compromise).