Predatory Search-based Chaos Turbo Particle Swarm Optimisation (PS-CTPSO): A new particle swarm optimisation algorithm for Web service combination problems

摘要

Web service combinatorial optimisation is an NP problem (that is, characterised by a nondeterministic polynomial time solution), based on the logical relationship between each service pair. As a consequence, obtaining the best Web service composition scheme is typically a complex task. In this article, we propose the Predatory Search-based Chaos Turbo Particle Swarm Optimisation (PS-CTPSO) algorithm, a chaotic particle swarm optimisation algorithm based on the predatory search strategy, which has significant potential to enhance the overall performance of the Autonomous Cloud.This is achieved by integrating a predatory search and cotangent sequence strategies with the particle swarm optimisation algorithm. More specifically, the PS-CTPSO algorithm identifies a feasible service via a global search, and subsequently, it obtains suitable candidate services within the corresponding chain. The different Web services are grouped into the same class, depending on whether they have the same input and output sets, thus reducing the number of combinations and improving the searching efficiency. In the initialisation phase, the PS-CTPSO component introduces the cotangent method, rather than a random one, which defines individual candidate services within the corresponding classes, creating a feasible service chain. In the update phase, a novel set of rules is used to perturb the velocities and positions of particles for assessing the ideal global search capabilities and adaptability. This effectively overcomes any premature problem, which commonly occurs in traditional PSO (Particle Swarm Optimisation) algorithms, and logic optimisation ensures the diversity of the final combination scheme. In this article, a prototype system (BestWS) is created, based on the directed graph generated by the logic relationships between Web services and the PS-CTPSO, Graph-Based Particle Swarm Optimisation (GB-PSO), Chaos Particle Swarm Optimisation (CS-PSO) and Chaos Particle Swarm Optimisation with Predatory Search strategy (PS-CSPSO) algorithms. The experimental results demonstrate that the cotangent sequence is more suitable than the chaotic one in the field of Web service combination optimisation. Furthermore, compared with the typical implementation of GB-PSO and PS-CSPSO, PS-CTPSO obtains better results, whilst attaining the global optimum with fewer iterations, and with an improved overall ergodicity.