title: Deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples.
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.
authors.affiliation: State Key Laboratory of Earth Surface Processes and Resource Ecology, Beijing Normal University, Beijing, 100875, China; School of Engineering, University of Warwick, Coventry, CV4 7AL, UK dr_xiaobinghu@hotmail.co.uk.
authors.forename: Xiao-Bing
authors.initials: XB
authors.lastname: Hu
authors.affiliation: State Key Laboratory of Earth Surface Processes and Resource Ecology, Beijing Normal University, Beijing, 100875, China wangming@bnu.edu.cn.
authors.forename: Ming
authors.initials: M
authors.lastname: Wang
authors.affiliation: School of Engineering, University of Warwick, Coventry, CV4 7AL, UK Mark.Leeson@warwick.ac.uk.
authors.forename: Mark S
authors.initials: MS
authors.lastname: Leeson
authors.affiliation: Ikerbasque, Basque Science Foundation, Centre for Research on Life, Mind and Society, University of the Basque Country, San Sebastian, 20080, Spain ezequiel_dipaolo@ehu.es.
authors.forename: Ezequiel A
authors.initials: EA
authors.lastname: Di Paolo
authors.affiliation: Beijing Metropolitan Traffic Information Center, Beijing, 100161, China hao.liu@bjjtw.gov.cn.
authors.forename: Hao
authors.initials: H
authors.lastname: Liu
mesh_terms: D000465:Algorithms; D008962:Models, Theoretical
keywords: Agent-based model; deterministic algorithms; path optimization.; ripple-spreading algorithm