A distributed design of ripple-spreading algorithms for path optimisation problems. (19th June 2021)

• Record Type: Journal Article
• Authors: Wang, Tian-Qi; Zhang, Gong-Peng; Hu, Xiao-Bing; Yang, Hongji
• Is Part Of: International journal of computer applications technology. Volume 65:Number 3(2021)
• Page Start: 209
• Page End: 221
• Publication Date: 2021-06-19
• Subjects: ripple-spreading algorithm -- distributed design -- parallel computation -- paths optimisation -- computational efficiency; Technology -- Data processing -- Periodicals; 620.00285
• Languages: English
• ISSNs: 0952-8091

Abstract

As a relatively new nature-inspired algorithm, Ripple-Spreading Algorithm (RSA) exhibits some advantageous features when resolving various Path Optimisation Problems (POPs) against both traditional deterministic algorithms and evolutionary approaches, e.g., RSA is a multi-agent, bottom-up, simulation model full of flexibility for modifications (like many evolutionary approaches), and it can guarantee optimality (like many deterministic algorithms). Towards real applications to large-scale POPs, RSA still needs to improve its computational efficiency. We used it to take some measures in order to achieve a trade-off between computational efficiency and optimality. This paper, for the first time without sacrificing optimality, proposes a way to significantly improve the computational efficiency of RSA. This is done by taking advantage of the multi-agent nature of RSA, i.e., a multi-agent model is naturally friendly to distributed design and parallel computing. Therefore, this paper reports a distributed design of RSA for POPs. Preliminary experimental results clearly demonstrate the effectiveness and efficiency of the new design of RSA.