A memetic NSGA-II with EDA-based local search for fully automated multiobjective web service composition

Abstract

Web service composition aims to provide added values by loosely coupling web services to accommodate users' complex requirements. Evolutionary computation techniques have been used to efficiently find near-optimal composite services to satisfy users' requirements reasonably well. Often, the quality of a composite service is measured by two important quality criteria that are related to the non-functional quality (i.e., Quality of service, QoS for short) and function quality (i.e., Quality of semantic matchmaking, QoSM for short). One recent work [2] proposed a Hybrid method that combines NSGA-II and MOEA/D with swap-based local search to enhance the performance of NSGA-II. This Hybrid method handles two quality criteria in QoS as two trade-off objectives. However, the local search of this method is randomly applied to a predefined large number of subproblems without focusing on the most suitable candidate solutions. In this paper, we propose a memetic NSGA-II with EDA-based local search. Particular, EDA performs the local improvements of a few well-selected composite services in different regions of the Pareto front. We also aim to handle two practical trade-off objectives with respect to QoS and QoSM. Our experiments have shown that our proposed method outperforms the recent state-of-the-art algorithms and the baseline NSGA-II method with respect to effectiveness and efficiency.