Paper 7
A Hybrid Approach using Genetic Programming and Greedy Search for QoS-aware Web Service CompositionAuthors: Hui Ma, Anqi Wang, Mengjie Zhang |
AbstractService compositions build new web services by orchestrating sets of existing web services provided in service repositories. Due to the increasing number of available web services, the search space for finding best service compositions is growing exponentially. Further, there are many available web services that provide identical functionality but differ in their Quality of Service (QoS). Decisions need to be made to determine which services are selected to participate in service compositions with optimized QoS properties. In this paper, a hybrid approach to service composition is proposed that combines the use of genetic programming and random greedy search. The greedy algorithm is utilized to generate valid and locally optimized individuals to populate the initial generation for genetic programming (GP), and to perform mutation operations during genetic programming. A full experimental evaluation has been carried out using public benchmark test cases with repositories of up to 15,000 web services and 31,000 properties. The results show good performance in searching for best service compositions, where the number of atomic web services used and the tree depth are used as objectives for minimization. Further, we extend our approach to the more general problem of finding service composition solutions that have near-optimal QoS. Our experimental evaluation demonstrates that our GP-based greedy algorithm enhanced approach can be applied with good performance to the QoSaware service composition problem. |