Automated web service composition is a popular research topic because it can largely reduce human eorts as the business increases. This thesis presents a search-based approach to fully automate web service composition which has a high possibility to satisfy user's functional requirements given certain assumptions. The experiment results show that the accuracy of our composition method using Genetic Programming (GP), in terms of the number of times an expected composition can be derived versus the total number of runs can be over 90%. System designers are users of our method. The system designer begins with a set of available atomic services, creates an initial population containing individuals (i.e. solutions) of candidate

service compositions, then repeatedly evaluates those individuals by a fitness function and selects better individuals to generate the next population until a satisfactory solution is found or a termination condition is met. In the context of web service composition, our algorithm

of genetic programming is highly improved compared to the traditional genetic programming used in web service composition in three ways: 1. We comply with services knowledge rules such as service dependency graph when generating individuals of web service composition in

each population, so we can expect that the convergence process and population quality can be improved. 2. We evaluate the generated individuals in each population through black-box testing. The proportion of successful tests is taken into account by evaluating the fitness

function value of genetic programming, so that the convergence rate can be more effective. 3.We take cross-over or mutation operation based on the parent individuals' input and output analysis instead of just choosing by probability as typically done in related work. In this way, better children can be generated even under the same parents. The main contributions of this approach include three aspects. First, less information is needed for service composition. That is, we do not need the composition work-

ow and the semantic meaning of each atomic web service. Second, we generate web service composition with full automation. Third, we generate the composition with high accuracy owing to the effect of carefully preparing test cases.