Realization of an Adaptive Memetic Algorithm Using Differential Evolution and Q-Learning: A Case Study in Multirobot Path Planning

摘要

Memetic algorithms (MAs) are population-based meta-heuristic search algorithms that combine the composite benefits of natural and cultural evolutions. An adaptive MA (AMA) incorporates an adaptive selection of memes (units of cultural transmission) from a meme pool to improve the cultural characteristics of the individual member of a population-based search algorithm. This paper presents a novel approach to design an AMA by utilizing the composite benefits of differential evolution (DE) for global search and Q-learning for local refinement. Four variants of DE, including the currently best self-adaptive DE algorithm, have been used here to study the relative performance of the proposed AMA with respect to runtime, cost function evaluation, and accuracy (offset in cost function from the theoretical optimum after termination of the algorithm). Computer simulations performed on a well-known set of 25 benchmark functions reveal that incorporation of Q-learning in one popular and one outstanding variants of DE makes the corresponding algorithm more efficient in both runtime and accuracy. The performance of the proposed AMA has been studied on a real-time multirobot path-planning problem. Experimental results obtained for both simulation and real frameworks indicate that the proposed algorithm-based path-planning scheme outperforms the real-coded genetic algorithm, particle swarm optimization, and DE, particularly its currently best version with respect two standard metrics defined in the literature.