Studying self-balancing strategies in island-based multimemetic algorithms

摘要

Multimemetic algorithms (MMAs) are memetic algorithms that explicitly exploit the evolution of memes, i.e., non-genetic expressions of problem-solving strategies. We aim to study their deployment on an unstable environment with complex topology and volatile resources. We analyze their behavior and performance on environments with different churn rates, and how they are affected by the use of self-balancing strategies aiming to compensate the loss of existing islands and react to the apparition of new ones. We investigate two such strategies, one based on quantitative balance (in which populations are resized dynamically to cope with node failure/recoveries) and another on qualitative balance (in which genetic/memetic information is actually exchanged to achieve balance). We evaluate these on scale-free network topologies and compare them to an unbalanced strategy that keeps island sizes constant. Experimentation firstly focuses on memetic takeover, carried out on an idealized selecto-Lamarckian model of MMAs (used as a surrogate of the latter) and indicating that the two balancing strategies exhibit complementary profiles in terms of diversity preservation. The results also indicate that the qualitative version is more robust to churn than both the unbalanced and the quantitatively balanced counterpart. This is subsequently confirmed with an empirical evaluation of full-fledged MMAs on a benchmark composed of four hard pseudo-Boolean problems. The qualitative version provides the best performance in global terms, significantly outperforming the remaining variants.