marcos oliveira
Beyond exploitation: Measuring the impact of local search in swarm-based memetic algorithms through the interactions of individuals in the population


Memetic algorithms are known for their enhanced solution refinement capabilities. These capabilities are a result of incorporating local-search methods into population-based metaheuristics such as swarm and evolutionary algorithms. However, designing a memetic algorithm is not a trivial task. The inclusion of local-search procedures must consider the exploitation–exploration balance and its interplay with other algorithm operators. Due to these variables, there is no universal methodology to design a memetic algorithm. Although previous works have investigated the impact of local search procedures on genetic and ant colony algorithms, we have limited knowledge about the impact of these procedures on other types of swarm-based algorithms. For swarm-based algorithms, the interactions within the population are vital to the emergence of collective intelligence and shape the algorithm’s behaviour. Here, we model these interactions into a network and analyse the impact of local search in swarm-based algorithms. We selected the Particle Swarm Optimization (PSO), the Artificial Bee Colony (ABC), and one memetic version of each algorithm as a case study. We examined the effects of the modifications proposed in the memetic variants. The results obtained indicate that the networks of interactions capture several characteristics of the algorithms and the impact of the local search strategies. The impact of local search operators can be gauged by the temporal analysis of the changes in the structural properties of the algorithm’s network (e.g. study of the weight and distribution of the network’s connections). These changes are linked to the algorithms’ convergence signature and can be used as a proxy to assess the differences between the algorithms studied and their memetic versions.

[Link to publication]