Handling Branched Web Service Composition with a QoS-Aware Graph-Based Method

The concept of Service-Oriented Architecture, where individual services can be combined to accomplish more complex tasks, provides a flexible and reusable approach to application development. Their composition can be performed manually, however doing so may prove to be challenging if many service alternatives with differing qualities are available. Evolutionary Computation (EC) techniques have been employed successfully to tackle this problem, especially Genetic Programming (GP), since it is capable of encoding conditional constraints on the composition's execution paths. While compositions can naturally be represented as Directed Acyclic Graphs (DAGs), GP needs to encode candidates as trees, which may pose conversion difficulties. To address that, this work proposes an extension to an existing EC approach that represents solutions directly as DAGs. The tree-based and extended graph-based composition approaches are compared, showing significant gains in execution time when using graphs, sometimes up to two orders of magnitude. The quality levels of the solutions produced, however, are somewhat higher for the tree-based approach. This, in addition to a convergence test, shows that the genetic operators employed by the graph-based approach can be potentially improved. Nevertheless, the extended graph-based approach is shown to be capable of handling compositions with multiple conditional constraints, which is not possible when using the tree-based approach.