  Comprehensive quality-aware automated semantic web service composition is an
NP-hard problem, where service composition workflows are unknown, and
comprehensive quality, i.e., Quality of services (QoS) and Quality of semantic
matchmaking (QoSM) are simultaneously optimized. The objective of this problem
is to find a solution with optimized or near-optimized overall QoS and QoSM
within polynomial time over a service request. In this paper, we proposed novel
memetic EDA-based approaches to tackle this problem. The proposed method
investigates the effectiveness of several neighborhood structures of composite
services by proposing domain-dependent local search operators. Apart from that,
a joint strategy of the local search procedure is proposed to integrate with a
modified EDA to reduce the overall computation time of our memetic approach. To
better demonstrate the effectiveness and scalability of our approach, we create
a more challenging, augmented version of the service composition benchmark
based on WSC-08 \cite{bansal2008wsc} and WSC-09 \cite{kona2009wsc}.
Experimental results on this benchmark show that one of our proposed memetic
EDA-based approach (i.e., MEEDA-LOP) significantly outperforms existing
state-of-the-art algorithms.
