A multi-population memetic algorithm for dynamic shortest path routing in mobile ad-hoc networks

摘要

Optimisation under dynamic environment is a well known challenge not only because of the difficulties in handling constant changes during the search progress but also because of its real-world implication as many industry environments are dynamic. To tackle the dynamic aspect, optimisation algorithms need to track the changes and adjust for the global optima simultaneously. In this paper, we propose a multi-population memetic algorithm for dynamic optimisation, specially for the dynamic shortest path routing (DSPR) problem in mobile ad-hoc networks. DSPR is to find the shortest possible path that connects a source node with the destination node under a network environment where the topology is dynamic. There are algorithms proposed for DSPR. However handling the dynamic environment while maintaining the diversity is still a major issue. Hence the multi-population memetic algorithm is designed which has four main parts so the balance between exploration and exploitation of the search space could be better maintained. They include a genetic algorithm part which focuses solely on the exploring the search space; a local search component which is to search around the local area; a multi-population mechanism which is to maintain diversity by allocating every sub-population to different search area; and an external archive which is to preserve the current best solutions. The proposed method has been evaluated on DSPR instances that are generated under both cyclic and acyclic environments. Results show that the proposed algorithm can outperform other methods reported in the literature. That indicates the effectiveness of our proposed multi-population memetic approach in dealing with dynamic optimisation problems.