A Multi-memory Multi-population Memetic Algorithm for Dynamic Shortest Path Routing in Mobile Ad-hoc Networks

摘要

This study investigates the dynamic shortest path routing (DSPR) problem in mobile ad-hoc networks. The goal is to find the shortest possible path that connects a source node with the destination node while effectively handling dynamic changes occurring on the ad-hoc networks. The key challenge in DSPR is how to simultaneously keep track changes and search for the global optima. A multi-memory based multi-population memetic algorithm is proposed for DSPR in this paper. The proposed algorithm combines the strength of three different strategies, multi-memory, multi-population and memetic algorithm, aiming to effectively explore and exploit the search space. It divides the search space by multiple populations. The distribution of solutions in each population is kept in the associated memory. The multi-memory multi-population approach is to capture dynamic changes and maintain search diversity. The memetic component, which is a hybrid Genetic Algorithm (GA) and local search, is to find high quality solutions. The performance of the proposed algorithm is evaluated on benchmark DSPR instances under both cyclic and acyclic environments. Our method obtained better results when compared with existing methods in the literatures, showing the effectiveness of the proposed algorithm in handling dynamic optimisation.