Comprehensive Quality-Aware Automated Semantic Web Service Composition

Abstract

Automated web service composition is one of the ultimate goals of service-oriented computing. It loosely couples web services to accommodate users' complex requirements. Evolutionary Computation (EC) techniques combined with AI planning have been successfully proposed to efficiently produce composite services with near-optimal Quality of Semantic Matchmaking (QoSM) and/or Quality of Service (QoS), which measure the satisfaction of the functional and non-functional requirements from users, respectively. Despite some recent progress, both the effectiveness and efficiency of existing approaches need further improvement to enhance the competitive advantage of service providers. The overall goal of this thesis is to propose novel EC-based fully automated service composition approaches that can effectively and efficiently solve challenging single-objective, multi-objective, and dynamic service composition problems.

Firstly, this thesis proposes two novel Estimation of Distribution Algorithm (EDA) based approaches (called EDA-NHM and EDA-EHM) and one memetic EDA-based approach with four different local search operators to single-objective fully automated web service composition that jointly optimizes QoSM and QoS. EDA-NHM and EDA-EHM are proposed with novel permutation-based and DAG-based representations to model the distribution of composition solutions with respect to varied service composition workflows. Two sampling techniques are also studied in EDA-NHM and EDA-EHM to effectively and efficiently sample new promising permutations and functionally valid DAGs, respectively. These two EDA-based approaches are compared to state-of-the-art works. The comparisons reveal that EDA-NHM produces better-quality composite services than EDA-EHM and the state-of-the-art works. On the other hand, EDA-EHM achieves the highest efficiency among all the competing EC-based methods, delivering moderate effectiveness. Furthermore, one proposed memetic approaches built upon EDA-NHM (called MEEDA-LOP) pushes the cutting-edge performance in terms of effectiveness and efficiency.

Secondly, this thesis studies two categories of multi-objective service composition problems: one category aims to generate a set of approximated Pareto optimal solutions for users to choose from, while the other category aims to generate multiple composite services for multiple user segments with distinctive preferences on QoSM. To effectively and efficiently handle the first category of problems, a memetic approach based on Non-dominated Sorting Genetic Algorithm II (NSGA-II), called MNSGA2-EDA, is proposed by enhancing NSGA-II with EDA-based local search. The novelty of this method lies in the innovative use of EDA for effective and efficient local improvements, rather than for global exploration. MNSGA2-EDA is compared to state-of-the-art multi-objective works, for studying its performance. We found that MNSGA2-EDA achieves much higher effectiveness and efficiency in finding Pareto optimal solutions. The second category of problems can be naturally treated as multitasking problems. Two novel multi-factorial evolutionary algorithms (called PMFEA and PMFEA-EDA) are proposed to effectively and efficiently solve this category of problems. These two algorithms implicitly or explicitly learn and share the knowledge of good solutions evolved so far for different tasks. We compare PMFEA and PMFEA-EDA with state-of-the-art works. We found that both PMFEA-EDA and PMFEA are performed at the cost of only a fraction of time compared to the single-tasking state-of-the-art works, which solve one task at a time. We also found that PMFEA-EDA yields solutions with the highest quality, confirming that learning and sharing knowledge explicitly is superior to learning and sharing knowledge implicitly.

Thirdly, this thesis studies a new dynamic service composition problem, focusing on handling stochastic service failures. We effectively handle this problem via two stages --- the design stage and the execution stage. Particularly, two accurate robustness measures are proposed based on Monte Carlo sampling and a lower bound estimation, respectively. These robustness measures are utilized in two proposed GA-based approaches (called GA-MC and GA-RE) at the design stage, to generate baseline composite solutions with high robustness. These baseline solutions can cope with the stochastic service failures robustly via a repairing process that supports continued high-quality execution of a composite service at the execution stage. Meanwhile, we propose a GA-2Stage algorithm by introducing a new adaptive evolutionary control mechanism, which supports two sequential evolutionary stages with two different fitness evaluation methods. These approaches are compared to each other to determine the most suitable method. Our experimental comparisons reveal that GA-RE algorithm with lower bound estimation outperforms GA-MC algorithm with Monte Carlo sampling estimation in finding composition solutions with high robustness, regardless of the size of the service repositories. Besides, compared to GA-RE, GA-2Stage achieves the highest efficiency with a negligible impact on the effectiveness at the execution stage, regardless of the service repositories' size.