Multi-objective memetic approach for the optimal web services composition

Service composition is the process of combining a set of elementary or atomic services. The aim is to produce a new composite service to satisfy the user's request that cannot be satisfied by the atomic services. Combining multiple services is a complex problem that has been the subject of several research studies. The meta-heuristic approaches are good techniques that have been used to solve several complex problems in various domains. These techniques are able to discover promising search regions and locate good quality solutions in reasonable time without exploring the whole solution space. In this paper, we deal with the problem of optimal web service composition by using meta-heuristic approaches. Given a set of services and a set of tasks to be completed, the problem is to find the best set of services composition to complete all tasks where each service must be assigned to a given task. This problem can be modelled as a combinatorial optimization problem with a set of objective functions that need to be optimized. We search for a composite service that allows us to execute the considered tasks and offers the best quality of services (QoS). More precisely, we search for an execution plan that indicates for each task the assigned service. First, we propose a multi-objective local search based meta-heuristic (MO-LS) and a multi-objective genetic algorithm (MO-GA) to handle our problem. Then we propose a multi-objective memetic algorithm (MO-MA) that combines the two methods LS and GA. The role of GA is to detect promising regions to be explored. The role of LS is to exploit efficiently the potential regions created by GA. Four objective functions are used to compute the Pareto optimal set of solutions. The main objective is to minimize cost and time and to maximize availability and reputation and produce a good composite service. The three proposed approaches namely MO-LS, MO-GA, and MO-MA are evaluated on some datasets generated randomly and on the well-known QWS dataset to select the best fit services in terms of maximum or minimum aggregated end-to-end QoS parameters. The numerical results are encouraging and demonstrate the effectiveness of the proposed MO-MA for the web service composition.