The Library
A deterministic agent-based path optimization method by mimicking the spreading of ripples
Tools
Hu, Xiao-Bing, Wang, Ming-Shou , Leeson, Mark S., Di Paolo, Ezequiel A. and Liu, Hao (2015) A deterministic agent-based path optimization method by mimicking the spreading of ripples. Evolutionary Computation, 24 (2). pp. 319-346. doi:10.1162/EVCO_a_00156 ISSN 1063-6560.
|
PDF
WRAP-deterministic-agent-based-path-optimization-mimicking-spreading-Leeson-2015.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution. Download (1131Kb) | Preview |
Official URL: http://dx.doi.org/10.1162/EVCO_a_00156
Abstract
Inspirations from nature have fundamentally contributed to the development of evolutionary computation (EC). This paper, by learning from the natural ripple-spreading phenomenon, 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 will be 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 presented clearly illustrate the advantages of the RSA in terms of effectiveness and efficiency. Thanks to the combination of both agent-based and deterministic features, the RSA opens new opportunities to attack some problems, such as calculating the exact complete Pareto front in multi-objective 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, aswell as the new distinguishing features and capacities of RSA, enriches the theoretical foundations of EC.
Item Type: | Journal Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Engineering > Engineering | |||||||||||||||
Library of Congress Subject Headings (LCSH): | Multiagent systems, Algorithms | |||||||||||||||
Journal or Publication Title: | Evolutionary Computation | |||||||||||||||
Publisher: | M I T Press | |||||||||||||||
ISSN: | 1063-6560 | |||||||||||||||
Official Date: | 13 June 2015 | |||||||||||||||
Dates: |
|
|||||||||||||||
Volume: | 24 | |||||||||||||||
Number: | 2 | |||||||||||||||
Page Range: | pp. 319-346 | |||||||||||||||
DOI: | 10.1162/EVCO_a_00156 | |||||||||||||||
Status: | Peer Reviewed | |||||||||||||||
Publication Status: | Published | |||||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||||||||
Date of first compliant deposit: | 4 January 2018 | |||||||||||||||
Date of first compliant Open Access: | 4 January 2018 | |||||||||||||||
Funder: | China. Guo jia ke xue ji shu bu [Ministry of Science and Technology] (CMST) | |||||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year