# A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition
###### Abstract  
Service-oriented architectures have become increasingly prevalent in internet application design, leading to a proliferation of services. Managing and composing these web services pose a classic non-deterministic polynomial-time hard problem. The web service composition problem (WSCP) based on the input-output model (IOM) involves the automatic composition of services without relying on a pre-defined workflow. Multi-objective evolutionary algorithms offer a solution that goes beyond simple weighted average calculations for quality of service, catering to diverse user needs in service composition. This paper introduces a multi-objective heuristic algorithm based on the SPEA2 called MSPEA2+. Specific modifications are incorporated in MSPEA2+ to support the breeding, crossover, and mutation processes, tailored for IOM-based WSCP. Validating the algorithm performance through finding suitable combination results for each task in the WSC-08 dataset, our experiments showed that MSPEA2+ has better iterative efficiency than existing multi-objective methods and outperforms them in terms of quality of service. MSPEA2+ achieved the lowest IGD value across all seven tasks, an improvement of 81.7% IGD value compared with the SPEA2 algorithm in WSC-0804. evolutionary computation; large scale computation; meta-heuristic algorithm; web service composition +
Footnote †: journal:  
0000-0001-9991-4000]C.M. However, the IOM does not rely on workflows being provided. It selects and connects services based on the input-output dependencies of services to construct composition results. Thus, the IOM can be a promising model when workflow is hard to determine before composition. Quality of service (QoS) reflects the final performance of the composition result. It is determined by the services involved in the result and the composition structure. QoS typically encompasses multiple attributes, corresponding to the user's requirements for the composition result, such as availability, reliability, and cost. Standards like OWL-S [8] provide the means to integrate semantics into web service descriptions, adhering to ontologies that define relationships among them. Semantics enable the creation of approximate composite services, allowing the assessment of their quality in terms of accuracy [9]. Heuristic algorithms have been widely employed as common solutions for the WSCP. Among them, algorithms for single-objective optimization (SooA) and multi-objective optimization (MooA) can be distinguished. For SooA, each QoS attribute is weighted and averaged to obtain a fitness value. However, satisfying users' preferences for different QoS attributes and accommodating changes in QoS attributes are challenging issues. In MooA, multiple QoS attributes are transferred into multiple fitness values [10]. Thus, the process of obtaining better QoS is transformed into acquiring Pareto frontier solutions. SPEA2 stands out as a classic multi-objective heuristic algorithm [11], employing an enhanced fitness allocation strategy and archive storage along with new techniques for file truncation and density-based selection. In studies on WM-based WSCPs with two or three objectives, it was shown that both SPEA2 and NSGA2 demonstrated strong capabilities in solving the WSCP [12]. Specifically, experiment revealed that SPEA2 outperformed NSGA2 as the number of objectives increased [13]. Therefore, given the growing complexity of user demands, SPEA2 holds tremendous potential for solving the WSCP. To the best of our knowledge, SPEA2 has been rarely studied in the context of the WSCP, especially in the context of the IOM-based WSCP. Therefore, in this paper, we investigate acquiring Pareto frontier solutions to the IOM-based WSCP. Specifically, we focus on developing SPEA2 to handle the QoS-aware WSCP.