Investigations of combinatorial approaches for QoS driven web service selection using metaheuristic algorithms

Abstract

Web Services provide interoperability between diverse applications using platform and language independent interfaces for easily integrating heterogeneous systems. Selection of most suitable web service is very crucial for successful execution of applications due to the rapid growth of web service providers in the internet. Dynamic selection of web services involves getting user requirements and matching them with the registered service description. The user requirements may vary from description of service and Quality of Service (QoS). Service consumer requests the provider for an upper and lower value for each QoS parameter. In particular the lower bound is preferred for execution price and execution time, and upper bound is preferred for reliability, reputation and availability. Since the optimization problem is NP-hard many heuristic approaches have been carried out to solve this. Use of machine learning algorithms such as Genetic algorithm have been proposed to solve QoS global optimal. However these algorithms have several shortcomings.  Firstly, most of the methods only obtain local optimal solution for the problem and cannot obtain global optimal solution effectively.  Secondly, the complexity of algorithm is high and it requires long running time is especially with the increase of candidate services.  Third, it is difficult to ensure the convergence of the algorithm time and it cannot adapt to the needs of real-time systems. To solve these problems this thesis proposes combinatorial approach based dynamic selection algorithm with QoS global optimal thereby transforming the service composition in to optimization problem and solving with the help of soft computing techniques. The major contributions of this research work are as follows: The first part of the thesis focuses on identifying the suitable algorithm that can be used with other heuristic algorithms which attains convergence at faster rate. Several soft computing techniques such as Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant-Colony Optimization (ACO), Memetic Algorithm (MA) and Cuckoo search (CS) were examined. The GA scores out of other algorithms due to its ease of implementation and better result accuracy. The second part of the thesis presents the first hybridization approach in which genetic algorithm is combined with fuzzy logic that helps in finding the better match for the service request. At first , Genetic algorithm is made to run on a random set of population that has fitness function to calculate the efficiency of individuals in the population. Induviduals with higher fitness values are promoted to next generation and the fuzzy logic controller is used to adjust the crossover and mutation rates dynamically thereby increasing the solution quality. Also, Fuzzy Gaussian membership function is used instead of triangular membership function to increase the reliability and robustness of the system in fuzzy logic design. The third part of the thesis discusses the genetic search methodology used for the weight optimization on a pre-specified neural network topology. Usually Neural Network uses Gradient Descent algorithm to train the network but this fails by getting trapped in local minima. Here the chromosomes are represented as weights and it is optimized through genetic search. By doing so the GA finds a set of optimized weights that minimizes the error function of network. In evolutionary neural learning the genetic algorithm is used to find the optimal set of weights in a network that minimizes the error function. The fourth part addresses the issue of selecting services based on user preferences and QoS characteristics with the help of combined strategies of evolutionary algorithms, namely GA and ACO. Here attributes are represented in a Directed Acylic Graph (DAG). At each iteration ACO chooses local best solution and GA is used to select global best solution among the solutions produced by ACO. Also ACO utilizes the convergence property of GA to converge quickly. Also the mutation in GA guides ACO to avoid trapping in local optimal solution. Finally we have applied GA on PSO to measure efficiency on retrieving accurate search results. The hybrid PSO converges to local optimal solution that divides the population into cluster, thereby selecting the best services in each cluster and replacing the worst service with better service at each run to produce optimal service selection. The performance of proposed approaches has been evaluated using convergence rate and execution time. Experimental results indicate the effectiveness of proposed approaches over existing schemes.