The Web service composition refers to the aggregation of Web services to meet customers' needs in the construction of complex applications. The selection among a large number of Web services that provide the desired functionalities for the composition is generally driven by QoS (Quality of Service) attributes, and formulated as a constrained multi-objective optimization problem. However, many equally important QoS attributes exist and in this situation the performance of the multi-objective algorithms can be degraded. To deal properly with this problem we investigate in this chapter a solution based in many-objective optimization algorithms. We conduct an empirical analysis to measure the performance of the proposed solution with the following preference relations: Controlling the Dominance Area of Solutions, Maximum Ranking and Average Ranking. These preference relations are implemented with NSGA-II using five objectives. A set of performance measures is used to investigate how these techniques affect convergence and diversity of the search in the WSC context.
Top1. Introduction
Web services are software programs that operate independently to offer services over the Internet to other programs, including Web applications and other Web services. They are developed to allow interoperability among technologies, as well as, protocols, platforms and operating systems. Web services are a key concept of the ServiceOriented Architecture (SOA), which conceptually defines a structured data exchanging model, providing the applications the ability to be loosely coupled with limited knowledge of each other implementations.
Many times, service compositions, combining the functionality of several Web services, are necessary to fulfill the customers’ requirements. An example of service composition is the travel planer that needs a sequence of flight, hotel and car booking service invocations (Strunk, 2010). Some research questions associated to the Web service composition (WSC) are reported in Dustdar and Schreiner (2005). According to Alrifai et al. (2010), this problem becomes important and challenging as the number of services offered on the web at different QoS levels increases, because of the exponential increase in the number of avaiable web services over the last years.
In general, to develop a composite service there are two main steps (Strunk, 2010). The first one is the identification of the functionalities required (or tasks of the composition) and of their interactions, control, dependencies and data flow. The second one is the selection of the appropriate implementation to the task (or execution plan of the composition). The number of Web services that provide a given functionality can be large, and a quality-driven approach is generally used for selection of execution plans (Zeng et al., 2004, 2003). This approach uses a quality model to characterize non-functional properties inherent to the WS, such as: price, time, reputation, reliability, availability and so on. Constraints and preferences are assigned to the composition, and the Web service selection is formulated as an optimization problem, known in the literature as Quality of Service (QoS) driven Web service composition.
Finding the best composition that satisfy the customer needs by an exhaustive search is unpractical, because the number of possible combinations can be very large. Therefore, it is expected that user will be faced with a huge number of variation of the same services offered at different QoS levels. So, the need for a service selection method is desirable. The QoS-driven service composition problem is NP-hard, hence, its solution take exponential time and cost. According to a recent survey (Strunk, 2010) the use of search based techniques is very promising, as it happens with other problems investigated in the field of Search Based Software Engineering (SSBSE) (Harman and Jones, 2001; Harman et al., 2009). Recent works propose the use of multi-objective algorithms (Li and Yan-xiang, 2010; Wada et al., 2008; Wang and Hou, 2008; Zhang et al., 2010). These algorithms deal with the QoS-driven service composition problem in a more suitable way and provide a set of good solutions for the problem considering Pareto non-dominance concepts. The works differ in the algorithm used, in the representation of the population according to the graph adopted to represent the WSC and, in the number of considered objectives (QoS attributes). Most works do not consider more than three objectives. Other aspect not usually evaluated is the scalability of the algorithms with respect to the number of services and size of the execution plans.
Optimization problems with more than one objective are a subject of intense research. Different algorithms can be used and were proven to be adequate and efficient. However, when four or more objectives are involved, such algorithms have their performance degraded and sometimes can be inadequate (Ishibuchi et al., 2008) due to the increase of non-dominated solutions. In the literature, problems with four or more objectives are often referred as many-objective problems (MaOPs) (Ishibuchi et al., 2008). The use of preference relations were proposed to deal with these cases by Lopez Jaimes and Coello (2009). Preference relations are mechanisms to improve performance of the multi-objective algorithms and to help in the selection between two non-dominated solutions.