text: 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 bansal2008wsc and WSC-09 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.
  @cite_28: Many enterprises have a growing interest in service composition to construct their business applications. With the increase of alternative services, Quality of Service (QoS) becomes an important indicator of obtaining optimal composite services. Due to the dynamic nature of the service environment, a composite service may not guarantee to deliver an overall optimal QoS. Re-optimization approaches have been developed to handle a dynamic environment. However, these approaches do not consider the diversity of alternative solutions, which may lead to better solutions. In this work, we introduce an adaptive approach, called estimation of distribution algorithm based on Restricted Boltzmann Machine (rEDA). rEDA effectively maintains the diversity of alternative solutions, by leveraging the inference ability of Restricted Boltzmann Machine to capture the potential solutions. It also provides a predictive guidance for the exploration of solution space, by considering the degree of how well a service contributes to the global QoS. The experimental evaluation shows that rEDA has a significant improvement on effectiveness and efficiency over existing approaches.
  @cite_34: In service composition, quality of service is a major criterion for selecting services to collaborate in a process flow to satisfy a certain quality goal. This paper presents an approach for service composition which considers QoS-based service provision schemes and variability of the QoS when planning. The QoS of a service can be stated in terms of complex service provision schemes, e.g. its service cost is offered at different rates for different classes of processing time, or its partnership with another service gives a special class of QoS when they operate in the same plan. We also address that it is desirable for service planning to result in a plan that is durable and reusable since change in the plan, e.g. by deviation of the actual QoS, would incur overheads. Our planning approach takes into account these dynamic situations and is demonstrated by using the Estimation of Distribution Algorithm.
  @cite_12: In a previous paper we proposed a node histogram based sampling algorithm (NHBSA) and compared it with edge histogram based sampling algorithm (EHBSA). The results showed NHBSA outperforms EHBSA on the permutation problems where absolute position of each node in a string is related to its performance. However, we used only a limited variation of sampling methods for NHBSA. In this paper, we propose several variations of sampling methods for NHBSA and explore conditions for them to work well with NHBSA.
  @cite_6: In recent years, quite a few search algorithms have been used to solve Web service composition problem. However, it is still lack of systematic analysis about these methods. In the paper, we attempt to analyze the effect of three typical meta-heuristic search algorithms. The experimental analysis is performed according to the search-based Web service composition framework. In the experiments, we mainly carry out the analysis as follows: different abstract service number, different candidate service number and different QoS constraint strength. Based on the above analysis, some guidelines of realizing Web service composition via search algorithms are yielded. For example, EDA is suitable for the composition problem with large abstract service number. PSO is more effective for the case of large candidate service number. GA is a good choose for the little-scale Web service composition problem. In addition, EDA can effectively settle the composition problem with strong QoS constraint. GA is suitable for the problem with medium constraint strength, and PSO has the poor ability to tackle the QoS constraint with high strength.
summary: The use of EDA has only been investigated for semi-automated web service composition @cite_28 @cite_34 @cite_6 . However, we recently proposed an EDA-based approach for fully automated web service composition, where candidate solutions are represented as permutations over a given service repository. The success of the proposed method strongly depends on the distribution model and the way of learning the distribution model. We employ Node Histogram Matrix (NHM) to learn the distribution of promising solutions in one population, Node Histogram-Based Sampling Algorithm (NHBSA) @cite_12 is empoloyed to produce candidate solutions. Although we started an initial study for fully automated service composition, it remains an opportunity to improve its performance further. EDA is good at global exploration, and local search operators are motivated to be introduced in EDA to enhance its capability in exploitation.