Comprehensive Quality-Aware Automated Semantic Web Service Composition

Chen Wang, Hui Ma, Aaron Chen, Sven HartmannAustralasian Conference on Artificial Intelligence 2017 · DOI

TL;DR

This paper tackles the complex problem of automatically composing web services to meet user requirements, optimizing both functional quality (semantic matching) and non-functional quality (performance, cost, etc.). They introduce a novel "memetic EDA" approach that combines evolutionary algorithms with local search, significantly outperforming existing methods in terms of both solution quality and efficiency.

What Problem Does This Paper Address?

The core challenge is automated semantic web service composition. Imagine you need a complex task done, like booking a trip with specific flight and hotel requirements, and you want a system to automatically find and string together the right web services to achieve this. This isn't just about finding services that do the right thing (semantic matching), but also services that meet your quality expectations (like response time, cost, reliability). This problem is computationally hard (NP-hard) because the number of possible service combinations is vast, and the optimal workflow isn't known beforehand. Existing methods often struggle to optimize both semantic and quality aspects simultaneously, or they rely on pre-defined workflows, which isn't always practical.

Methods

The authors propose a memetic EDA-based approach. Here's a breakdown:

  • EDA (Estimation of Distribution Algorithm): This is an evolutionary computation technique that learns a probability model from promising solutions to generate new ones. It's good at exploring the search space broadly.
  • Memetic Algorithm: This approach enhances evolutionary algorithms by incorporating a "local search" component. After EDA generates potential solutions, local search fine-tunes them by making small, targeted improvements.
  • Novelty - Domain-Specific Local Search Operators: A key contribution is the development of specialized "swap" operators for service composition. Instead of generic swaps, these operators are designed to work with the specific structure of service compositions (represented as permutations and DAGs) and leverage "building blocks" and "layer information" to make more effective local improvements.
  • Novelty - Joint Strategy for Local Search: To make the local search efficient, they combine a fitness-based selection of individuals for local search with a stochastic exploration of their neighborhoods. This avoids exhaustively searching all possibilities.
  • Permutation-Based Representation: They use a permutation of service indexes as an intermediate representation, which is then decoded into a Directed Acyclic Graph (DAG) representing the actual service composition. This allows for efficient learning of the probability model and application of local search.

Datasets

The authors used existing benchmarks and created an augmented version:

  • WSC-08 and WSC-09: These are standard benchmarks for web service composition.
  • Augmented Benchmark: They created a more challenging version by combining the functionalities from WSC-08 and WSC-09 with QoS attributes from the QWS dataset. Crucially, they doubled the number of web services in the repository, creating a significantly larger search space to test scalability. This augmented benchmark and the associated code are made publicly available.

Key Insights and Ideas

  • Local Search is Crucial for EDA: While EDA is good at global exploration, it can get stuck in local optima. Hybridizing it with domain-specific local search significantly improves its ability to find better solutions.
  • Domain Knowledge Matters for Local Search: Generic local search operators are not as effective. Designing operators that understand the structure of service compositions (like "building blocks" and "layers") leads to more impactful improvements.
  • Layer Information Improves Efficiency: Using "layer information" (grouping services based on their distance from the start) in their local search operator (MEEDA-LOP) proved particularly effective, leading to better solutions and faster execution.
  • Efficient Selection is Key: Randomly applying local search is inefficient. Selecting individuals for local search based on their fitness and using a stochastic approach to explore their neighborhoods balances quality and speed.
  • Permutation Representation is a Good Compromise: While service compositions are naturally DAGs, using a permutation-based representation for learning and local search, with a bi-directional mapping to DAGs, offers a practical advantage.

Key Results

  • Superior Effectiveness: Their proposed memetic EDA-based approach, particularly MEEDA-LOP, consistently outperformed existing state-of-the-art methods (including PSO, GA, MEGA, and a baseline EDA) in terms of fitness value across various datasets.
  • Improved Efficiency: MEEDA-LOP also achieved significantly lower execution times compared to other methods, demonstrating a better balance between exploration and exploitation.
  • Scalability: The augmented benchmark with a doubled service repository showed that their approach maintains high performance even with larger problem instances.
  • Local Search Operator Performance: MEEDA-LOP, which utilizes layer-based constrained one-point swap, was the best performer, suggesting the effectiveness of incorporating layer information into local search.

Limitations and Future Work

  • Neighborhood Structure: The paper notes that block-based swaps (MEEDA-OB) were less effective, potentially disrupting the learned distribution.
  • Future Work: The authors suggest exploring variable neighborhood search with combinations of multiple local search operators within a single evolutionary process. They also propose investigating memetic EDA for handling multi-objective service composition problems.

Summary updated

BibTeX
@inproceedings{wang2017comprehensive,
  author = {Chen Wang and Hui Ma and Aaron Chen and Sven Hartmann},
  title = {{Comprehensive Quality-Aware Automated Semantic Web Service Composition}},
  booktitle = {Australasian Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1007/978-3-319-63004-5\_16},
}
Figure