北京师范大学地表过程与资源生态国家重点实验室
  中文|English  
 
您的位置: 首页» 实验室新闻» 室内研究进展» 区域可持续发展模拟
Deterministic Agent-Based Path Optimization by Mimicking the Spreading of Ripples
发布时间: 2016-09-18  

Hu Xiaobing; Wang Ming; Leeson Marks.; Di paolo Ezequiela.; Liu Hao;

[Hu, Xiao-Bing; Wang, Ming] Beijing Normal Univ, State Key Lab Earth Surface Proc & Resource Ecol, Beijing 100875, Peoples R China.

[Hu, Xiao-Bing; Leeson, Mark S.] Univ Warwick, Sch Engn, Coventry CV4 7AL, W Midlands, England.

[Di Paolo, Ezequiel A.] Univ Basque Country, Ikerbasque, Basque Sci Fdn, Ctr Res Life Mind & Soc, San Sebastian 20080, Spain.

[Liu, Hao] Beijing Metropolitan Traff Informat Ctr, Beijing 100161, Peoples R China.

 

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.

 

Published in EVOLUTIONARY COMPUTATION.2016,24(2):319-346,

DOI: 10.1162/EVCO_a_00156


浏览次数: