GraphEvol: A Graph Evolution Technique for Web Service Composition

Web service composition can be thought of as the combination of reusable functionality modules available over the network to create applications that accomplish more complex tasks, and Evolutionary Computation (EC) techniques have been applied with success to this problem. Genetic Programming (GP) is a traditionally employed EC technique in this domain, and it encodes solutions as trees instead of their natural Directed Acyclic Graph (DAG) form. This complicates the enforcement of dependencies between service nodes, which is much easier to accomplish in a DAG. To overcome this we propose GraphEvol, an evolutionary technique that uses DAGs directly to represent and evolve Web service composition solutions. GraphEvol is analogous to GP, but it implements the mutation and crossover operators differently. Experiments were carried out comparing GraphEvol with GP for a series of composition tasks, with results showing that GraphEvol solutions either match or surpass the quality of those obtained using GP, at the same time relying on a more intuitive representation.