Self-healing strategies for memetic algorithms in unstable and ephemeral computational environments

Optimization algorithms deployed on unstable computational environments must be resilient to the volatility of computing nodes. Different fault-tolerance mechanisms have been proposed for this purpose. We focus on the use of island-based multimemetic algorithms, namely memetic algorithms which explicitly represent and evolve memes alongside solutions, endowed with self-scaling capabilities. These strategies dynamically resize populations in order to react to system fluctuations. In this context, we study the joint use of different self-healing strategies, aimed to compensating the harm that the loss of computing nodes produces. Firstly, we consider the use of probabilistic models in order to self-sample the current population when it has to be resized, thus minimizing distortions in the convergence of the population and the progress of the search. Then, we complement the previous approach with the use of rewiring strategies intended to keep a rich connectivity in the system along time. We perform an extensive empirical assessment of those strategies on three different problems, considering a simulated computational environment featuring diverse degrees of instability. It is shown that these self-healing strategies provide a performance improvement and interact synergistically with each other, in particular in scenarios with large volatility.