A distributed design of ripple-spreading algorithms for path optimisation problems

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.