Using Genetic Algorithms to Navigate Partial Enumerable Problem Space for Web Services Composition

Web services have received much interest to support business-to-business or enterprise application integration but how to combine these services optimally in a continually growing search space is always a challenge. This paper investigates composing business processes from individual services as a planning problem where a planner determines the execution order and other constraints among services in a process. When there are a large number of Web services available, it is not easy to find an execution path of Web services composition that can satisfy the given request, since the search space for such a composition problem is in general exponentially increasing. The planner has to work with a problem space that is not fully enumerable. This paper presents a method that combines genetic algorithms (GA) with planning to optimize composition results within an incompletely observed problem space. GA helps to navigate the search in the whole space. At each loop of GA, Web service data are queried and a new subspace is built. The planner works with the subspace and calculates a feasible solution. We test our method on a travel domain. The result is an optimized solution, though global optimization is not guaranteed.