Since the birth of web service composition, minimizing the number of web services of the resulting composition while satisfying the user request has been a significant perspective of research. With the increase of the number of services released across the Internet, seeking efficient algorithms for this research is an urgent need. In this paper we present an efficient mechanism to solve the problem of web service composition. For the given request, a service dependency graph is firstly generated with the relevant services picked from an external repository. Then, each search step on the graph is transformed into a dynamic knapsack problem by mapping services to items whose volume and cost is changeable, after which a knapsack-variant algorithm is applied to solve each problem after transformation. Once the last search step is completed, the minimal composition that satisfies the request can be obtained. Experiments on eight public datasets proposed for the Web Service Challenge 2008 shows that the proposed mechanism outperforms the state-of-the-art ones by generating solutions containing the same or smaller number of services with much higher efficiency.
A heuristic A* search algorithm is proposed in @cite_6 for the problem of automatic web service composition. For a given request, a digraph called service dependency graph is constructed firstly with a part of the original services chosen from an external repository. Meanwhile, some techniques are applied to reduce the useless nodes in the graph. Then the heuristic-based search algorithm named A* is executed over the optimized graph to seek the minimal composition which fulfills the user request. Though it can obtain compositions with minimal number of services on WSC-2008's datasets, it may show a poor performance in large-scale and real-time environments. On one hand, different kinds of optimizations on the service dependency graph may spend large quantities of time. On the other hand, quite a few iterations of A* search algorithm aren't applicable to real-time scenarios.
@cite_6
2130281899 2605603844 1973467201 2115449863
Service Oriented Architectures and web service technology are becoming popular in recent years. As more web services can be used over the Internet, the need to find efficient algorithms for web services composition that can deal with large amounts of services becomes important. These algorithms must deal with different issues like performance, semantics or user restrictions. In this paper we present an A* algorithm which solves the problem of semantic input-output message structure matching for web service composition. Given are quest, a service dependency graph with a subset of the original services from an external repository is dynamically generated. Then, the A*search algorithm is used to find a minimal composition that satisfies the user request. Moreover, in order to improve the performance, a set of dynamic optimization techniques has been implemented over the search process. A full experimental validation with eight different public repositories has been done showing a good performance as in all tests as the algorithm finds a valid solution with minimal number of services and execution path. Web services have become increasingly popular in recent years, and they are especially suitable to the process of Web service composition, which is when several services are combined to create an application that accomplishes a more complex task. In recent years, significant research efforts have been made on developing approaches for performing Quality of Service -aware Web service composition. Evolutionary computing (EC) techniques have been widely used for solving this problem, since they allow for the quality of compositions to be optimised, meanwhile also ensuring that the solutions produced have the required functionality. Existing EC-based composition approaches perform constrained optimisation to produce solutions that meet those requirements, however these constraints may hinder the effectiveness of the search. To address this issue, a novel framework based on an indirect representation is proposed in this work. The core idea is to first generate candidate service compositions encoded as sequences of services. Then, a decoding scheme is developed to transform any sequence of services into a corresponding feasible service composition. Given a service sequence, the decoding scheme builds the workflow from scratch by iteratively adding the services to proper positions of the workflow in the order of the sequence. This is beneficial because it allows the optimisation to be carried out in an unconstrained way, later enforcing functionality constraints during the decoding process. A number of encoding methods and corresponding search operators, including the PSO, GA, and GP-based methods, are proposed and tested, with results showing that the quality of the solutions produced by the proposed indirect approach is higher than that of a baseline direct representation-based approach for twelve out of the thirteen datasets considered. In particular, the method using the variable-length sequence representation has the most efficient execution time, while the fixed-length sequence produces the highest quality solutions. In this paper we present a theoretical analysis of graph-based service composition in terms of its dependency with service discovery. Driven by this analysis we define a composition framework by means of integration with fine-grained I O service discovery that enables the generation of a graph-based composition which contains the set of services that are semantically relevant for an input-output request. The proposed framework also includes an optimal composition search algorithm to extract the best composition from the graph minimising the length and the number of services, and different graph optimisations to improve the scalability of the system. A practical implementation used for the empirical analysis is also provided. This analysis proves the scalability and flexibility of our proposal and provides insights on how integrated composition systems can be designed in order to achieve good performance in real scenarios for the web. We present an optimization approach for service compositions in large-scale service-oriented systems that are subject to Quality of Service (QoS) constraints. In particular, we leverage a composition model that allows a flexible specification of QoS constraints by using constraint hierarchies. We propose an extensible met heuristic framework for optimizing such compositions. It provides coherent implementation of common met heuristic functionalities, such as the objective function, improved mutation or neighbor generation. We implement three met heuristic algorithms that leverage these improved operations. The experiments show the efficiency of these implementations and the improved convergence behavior compared to purely randomized met heuristic operators.