GP-Based Approach to Comprehensive Quality-Aware Automated Semantic Web Service Composition

Comprehensive quality-aware semantic web service composition aims to optimise semantic matchmaking quality and Quality of service (QoS) simultaneously. It is an NP-hard problem due to its huge search space. Therefore, heuristics have to be employed to generate near-optimal solutions. Existing works employ Evolutionary Computation (EC) techniques to solve combinatorial optimisation problems in web service composition. In particular, Genetic Programming (GP) has shown its promise. The tree-based representation utilised in GP is flexible to represent different composition constructs as inner nodes, but the semantic matchmaking information can not be directly obtained from the representation. To overcome this disadvantage, we propose a tree-like representation to directly cope with semantic matchmaking information. Meanwhile, a GP-based approach to comprehensive quality-aware semantic web service composition is proposed with explicit support for our representation. We also design specific genetic operation that effectively maintain the correctness of solutions during the evolutionary process. We conduct experiments to explore the effectiveness and efficiency of our GP-based approach using a benchmark dataset with real-world composition tasks.