Deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples

Authored by Xiao-Bing Hu, Ming Wang, Mark S Leeson, Paolo Ezequiel A Di, Hao Liu

Date Published: 2016

DOI: 10.1162/evco_a_00156

Sponsors: European Union Chinese National Natural Science Foundation National Basic Research Program of China

Platforms: MATLAB

Model Documentation: Other Narrative Mathematical description

Model Code URLs: Model code not found

Abstract

Inspirations from nature have contributed fundamentally to the development of evolutionary computation. Learning from the natural ripple-spreading phenomenon, this article proposes a novel ripple-spreading algorithm (RSA) for the path optimization problem (POP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source is the first to be reached. This very simple principle forms the foundation of the proposed RSA. In contrast to most deterministic top-down centralized path optimization methods, such as Dijkstra's algorithm, the RSA is a bottom-up decentralized agent-based simulation model. Moreover, it is distinguished from other agent-based algorithms, such as genetic algorithms and ant colony optimization, by being a deterministic method that can always guarantee the global optimal solution with very good scalability. Here, the RSA is specifically applied to four different POPs. The comparative simulation results illustrate the advantages of the RSA in terms of effectiveness and efficiency. Thanks to the agent-based and deterministic features, the RSA opens new opportunities to attack some problems, such as calculating the exact complete Pareto front in multiobjective optimization and determining the kth shortest project time in project management, which are very difficult, if not impossible, for existing methods to resolve. The ripple-spreading optimization principle and the new distinguishing features and capacities of the RSA enrich the theoretical foundations of evolutionary computation.

Tags

networks Genetic algorithm Search K shortest paths Optimality Asterisk Front