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.

1. Introduction

With the advancement of modern computer technology, monolithic applications have grown larger and more cumbersome. To address this, service-oriented architecture (SOA) has emerged, breaking down large applications into multiple services to enhance reusability and fault tolerance. Against this backdrop of service decomposition, a single service often cannot meet user demands. Therefore, web service composition is required [1].

Web service composition has applications in various domains. For example, in the domain of cloud service, enterprises can combine various cloud services to build customized solutions to meet their specific needs [2]. In the field of the Internet of Things (IoT), service composition can be used to integrate sensors, communication, data analysis, and other services to create intelligent systems [3]. In the healthcare sector, it can integrate medical information, diagnostic tools, and patient monitoring, offering more comprehensive and personalized healthcare solutions [4].

The web service composition problem (WSCP) is a well-known non-deterministic polynomial-time hard (NP-hard) problem [5]. It refers to how to effectively combine multiple web services according to specific requirements and conditions to provide more complex, higher-level functionality. On this basis, the obtained results need to meet diverse user needs and requirements.

The workflow-based model (WM) [6] and input–output dependency-based model (IOM) [7] are two typical models in web service composition. The WM requires a pre-defined workflow and all the composite services must strictly obey the given workflow. 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. Our main objectives are to address the following three research questions:

RQ1: How to develop SPEA2 to handle the IOM-based WSCP;

RQ2: The impact of different data volumes and parameters on the performance of the SPEA2 in solving the IOM-based problem;

RQ3: How to improve SPEA2 to outperform existing methods in the IOM-based WSCP.

Our major contributions are as follows:

• The application of the SPEA2 to the IOM-based WSCP;
• Investigation of the impact of archive size on SPEA2 through conducting experiments on datasets of different sizes;
• Father–child merging, neighborhood crossover, and preference crossover merging in SPEA2 to enhance iteration efficiency and prevent the population from converging to local optima.
• Evaluation of the improved MSPEA2+ algorithm through conducting experiments on the WSC-08 dataset and comparing its performance with SPEA2, SPEA2+, and NSGA2, demonstrating the effectiveness of MSPEA2+.

The remainder of this paper is organized as follows: In Section 2, the literature related to the work of this paper is reviewed, and in Section 3, the basic definition of this work is introduced. In Section 4, we introduce the algorithm in detail. In Section 5, experiments conducted on the WSC-08 dataset are described to illustrate the effectiveness of the proposed method. Finally, we conclude our work with future directions in Section 6.

2. Related Work

In this section, we discuss existing articles with reference to algorithms and problem models. To the best of our knowledge, there has been limited research conducted on the IOM-based WSCP. Therefore, we combine the discussions on SooA and MooA into discussions on IOM-based problems.

Non-heuristic algorithms: Non-heuristic algorithms solve web service composition problems optimally by using an exhaustive search. Grbael et al. proposed a 0–1 linear programming-based optimal approach for QoS and transactional-aware service composition [14]. Chattopadhyay et al. proposed a parameterized search algorithm based on multiple QoS parameters, achieving a balance between search time and solution quality [15]. Sha et al. proposed a functionality-oriented composition technique for composing web services, which helped reach the extreme functionality of each web service in the composition to achieve customer satisfaction [16]. Although non-heuristic algorithms can obtain optimal solutions, their time complexity is exceptionally high, often unacceptably so to users as the number of services increases.

Single-objective heuristic algorithms based on the WM: Heuristic algorithms are semi-automated approaches that require customized optimization of the problem. They can provide feasible solutions within an acceptable time and space but do not guarantee the best solution. Li et al. filtered unreliable component services and constructed a convex hull based on trust-based selection methods, reducing the search space during the service composition process. Heuristic global optimization methods were applied to find near-optimal solutions to the problem [17].

Many works have applied evolution algorithms to the WSCP, such as the intelligent water drops algorithm [18], artificial bee colony optimization [19,20], genetic programming [21,22], particle swarm optimization [23], grey wolf optimizer [24,25], and ant colony optimization [26,27]. To overcome the limitations of single evolutionary algorithms, some studies have utilized hybrid heuristic algorithms. Ibrahim et al. employed a hybrid approach SFGA combining the frog leaping algorithm and genetic programming on top of an energy-aware mechanism to optimize mobile cloud service composition [28]. Ju et al. addressed the issue of slow or premature convergence to some extent by integrating the mutation process from genetic programming into the whale algorithm [29].

Multiple-objective heuristic algorithms based on the WM: However, single-target heuristic algorithms, even when QoS includes multiple attributes, are highly dependent on the weights of each attribute, providing users with limited options. Azouzd et al. proposed a multi-objective meme algorithm (MO-MA) that combined LS and GA methods, effectively utilizing the potential area generated by genetic algorithms [30]. Hosseini et al. treated service cost and multi-cloud risk perspectives as a dual-objective optimization problem. They proposed a dual-objective time-varying particle swarm optimization algorithm, achieving a good balance between exploration and optimization [31]. Yang et al. applied the multi-objective grey wolf algorithm to web service composition. The issues of easily falling into local optima and poor stability were improved through a nonlinear adjustment strategy of control parameters and an enhanced search strategy [32].

Heuristic algorithms based on the IOM: The IOM-based WSCP is more complex than the WM-based WSCP, since the combination results need to encode and decode input–output dependency. Sawczuk et al. proposed an indirect particle swarm optimization (PSO)-based approach. A forward algorithm and backward algorithm were used to decode solutions [33]. Ma et al. proposed a hybrid approach based on genetic programming. The greedy algorithm was utilized to generate valid and locally optimized individuals to populate the initial generation [34]. Chattopadhyay et al. applied NSGA2 for a multi-objective problem in an IOM. The dependency graph was generated by traversing backward starting from the end node [35]. Wang et al. hybridized a local search technique based on an estimation-of-distribution algorithm (EDA) with NSGA2 [36].

3. Background and Problem Formulation

3.1. Running Example

To illustrate the web service composition problem, we take travel planning as an example. As shown in Figure 1, a user (usually advanced) submits a query to obtain travel recommendations. Services that meet users’ partial requirements can be found in the real world. In this case, it is not necessary to define the service composition process in advance. So, services published by different developers or companies can also be automatically composited.

Users provide their GPS location, destination, departure time, and return time. The set of these initial inputs is defined as a start node.

The departure city is obtained by invoking the location–city–transfer service through GPS location.

The air service is called to obtain transportation arrangements by departure time, departure city, return time, and destination.

The hotel service is called to obtain hotel arrangements by departure time, destination, and return time.

The scenic service is used to obtain scenic recommendations through transportation arrangements and hotel arrangements.

The combination of the above information results in transportation arrangements, hotel arrangements, and scenic recommendation. The set of those outputs is defined as an end node.

In this example, GPS location, destination, departure time, and return time represent the user’s input, while transportation arrangements, hotel arrangements, and scenic recommendation represent the required output. Location–city–transfer service, air service, hotel service, and scenic service represent some services in the candidate service set. The algorithm operates by identifying services in the CS that can accept input and produce the desired output. It then constructs the topology of these services to complete the process of service composition.

3.2. Preliminaries

3.2.1. Problem Formulation

This paper explores the topic of the multi-objective QoS-aware WSCP. QoS attributes were mapped to fitness values using fitness functions. The heuristic algorithm was iterated through these fitness values and evolved to obtain Pareto optimal solutions. The formula for the problem is as follows:

$$\left\{\begin{array}{c}\mathrm{M}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e} f\left(L\right)=\left(f_1\left(L\right),f_2\left(L\right),\dots ,f_n\left(L\right)\right)\\ \mathrm{W}\mathrm{i}\mathrm{t}\mathrm{h} L=(S_1,S_2,\dots , S_n)\\ f_i\left(L\right)=W_i\cdot Qo{S}_i,\mathrm{f}\mathrm{o}\mathrm{r} i=1, 2, \dots , 6\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t} \mathrm{t}\mathrm{o} S_j\in CS, \mathrm{for} j=1, 2, \dots ,N_{SR}\end{array}\right.$$

(1)

where L is a composition result constructed by different services S, $f_i$ is an objective function that captures $QoS$, respectively, for every composition result $L$, $Qo{S}_i$ is an objective in $QoS$, $W_i$ is the weight value for $Qo{S}_i$, CS denotes the set of all candidate services, and $N_{CS}$ is the size of CS.

The basic parameters considered for the WSCP in this paper can be described as follows:

• Web services (services for short) $S=\left\{I_s,O_s,{QoS}_s\right\}$;
• For each service, a set of service inputs $I_s$ and a set of service outputs $O_s$;
• The set of all candidate services CS;
• SWCP task with input $I_t$ and required output $O_t$;
• Two special nodes, start node $S_{start}=\left\{\varnothing ,I_t,\varnothing \right\}$ and end node $S_{end}=\left\{O_t,\varnothing ,\varnothing \right\}$;
• A group of web services with the same ontology called service resporsity $S{R}_i$;
• Ontology ${OT}_i=$ $\left\{S{R}_i,{OT}_{subj}\right\}$. ${OT}_{subj}$ is the sub-semantic of ontology, which connects the hierarchical relationship of ontology.

3.2.2. Solution Architecture

The basic parameter considered for MooA can be described as follows:

• Individual ${\mathcal{L}}_i^g$, where g is the generation of optimization;
• Each individual represents the composition result of candidate services ${\mathcal{L}}_i^g=(S_i,S_j,S_k,{\dots S}_l)$;
• The set of individuals in each generation called population $p_g$;
• The size of population $N$;
• Non-dominated solution: the solution which is at least as good as other solutions on at least one objective, and better than other solutions on other objectives;
• Pareto optimal: the solution compared with which no other solution can achieve better results on all objectives at the same time;
• Pareto frontier: the boundary of all Pareto optimal solutions.

3.3. QoS Evalutation

$Q_o{S}_i=\left\{T_i,C_i,A_i,R_i,SI{M}_i,M{T}_i\right\}$ is a set of service functional attributes of $S$. The attributes $T_i,C_i,A_i and R_i$ refer to the response time, cost, availability, and reliability of service $S$, respectively. MT and SIM are matching type and semantic similarity. For the calculation of MT, the formula is as follows:

$$MT=\left\{\begin{array}{cc}1\hfill & \hfill \mathrm{exact} \mathrm{match} \\ 0.75\hfill & \hfill \mathrm{plugin} \\ 0.5\hfill & \hfill \mathrm{subsumes} \\ 0.25\hfill & \hfill \mathrm{fail} \end{array}\right.$$

(2)

For the calculation of MT between the ontology of current services $a$ and given services $b$, we follow the definition in [37]. Exact match means $a$ equals or is a subclass of $b$. Plugin means $a$ is a “subconcept” of $b$. Subsume means $a$ is a “superconcept” of $b$. The rest of the situations are defined as failures. Note that there is a deviation from the definition of “subconcept” and “superconcept” as presented in [37]. We focus solely on the layer difference between two layers to prevent excessive performance losses. Also, MT is not set to 0 in a fail situation. This is connected to our QoS treatment of the overall link, which is elaborated on in detail later. For the calculation of SIM, we refer to [38]. The method is described as follows:

$$SIM=\frac{2N}{N_a+N_b}$$

(3)

where $N$ represents the distance from the nearest common parent of nodes $a$ and $b$ on the semantic tree to the root node, $N_a$ is the distance from $a$ to the root node, and $N_b$ is the distance from $b$ to the root node.

Due to variations in the average value and magnitude of different QoS attributes, a unified normalization process was implemented for these attributes. For those positive QoS attributes, the normalized formula was adopted as follows:

$$Q_i=\left\{\begin{array}{ll}\frac{Q_i-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}}{Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}}& Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}\ne 0\\ 1& Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}=0\end{array}\right.$$

(4)

For those passive QoS attributes, the normalized formula was adopted as follows:

$$Q_i=\left\{\begin{array}{ll}\frac{Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_i}{Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}}& Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}\ne 0\\ 1& Q_{\mathrm{m}\mathrm{a}\mathrm{x}}-Q_{\mathrm{m}\mathrm{i}\mathrm{n}}=0\end{array}\right.$$

(5)

The QoS of the composition result was calculated through the QoS of all the services on the link. The combination structure of entire link was classified as sequential, parallel, and choice.

Table 1. Calculation for The Entire Link.

QQS Attributes	Availability	Reliability	Time	Cost	SIM	MT
Sequential	${\prod }_{k=1}^d a_{ck}$	${\prod }_{k=1}^d r_{ck}$	${\sum }_{k=1}^d t_{ck}$	${\sum }_{k=1}^d c_{ck}$	${\sum }_{k=1}^d w_k\cdot c_{ck}$	$\frac{1}{d}{\sum }_{k=1}^d {\mathrm{s}\mathrm{i}\mathrm{m}}_{{\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}_k}$
Parallel	${\prod }_{k=1}^d a_{ck}$	${\prod }_{k=1}^d r_{ck}$	$\mathrm{M}\mathrm{A}\mathrm{X}\left\{t_{ck}\mid k\in \{1,\dots ,d\}\right\}$	${\sum }_{k=1}^d c_{ck}$	${\sum }_{k=1}^d w_k\cdot c_{ck}$	$\frac{1}{d}{\sum }_{k=1}^d {\mathrm{s}\mathrm{i}\mathrm{m}}_{{\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}_k}$
Choice	${\prod }_{k=1}^d w_k\cdot a_{ck}$	${\prod }_{k=1}^d w_k\cdot r_{ck}$	${\sum }_{k=1}^d w_k\cdot t_{ck}$	${\sum }_{k=1}^d w_k\cdot c_{ck}$	${\sum }_{k=1}^d w_k\cdot c_{ck}$	$\frac{1}{d}{\sum }_{k=1}^d {\mathrm{s}\mathrm{i}\mathrm{m}}_{lin{k}_k}$

shows the formulas of QoS attributes in different combination structures, where $w_1,\dots ,w_d$ with ${\sum }_{k=1}^d w_k=1$ denotes the probabilities of the different options of the choice.

4. Algorithm

In this section, we introduce our MSPEA2+ method. The main loop is shown in Algorithm 1. The method is discussed in terms of initialization, breeding, crossover, and mutation. For an overview of the method, see Figure 2.

4.1. Greedy Search for Initialization and Decoding

An IOM establishes a combination’s structure through the input–output relationships between services. In this paper, a directed acyclic graph (DAG) of combination structure created by greedy search is presented, as follows:

• We started from $S_{start}$ and formed a collection with currently available output $O_{avi}$;
• $O_{avi}$ was used as input for the subsequent search;
• All unused service were traversed and matching services added to the next layer;
• The process was terminated when there was no unused available service.

During initialization, MSPEA2+ conducted a layer-by-layer traversal to filter all services relevant to task requirements. While this process may be time-consuming, as it constructs a graph of all available services, it is a one-time task establishing service relationships, requiring no dynamic tuning. Subsequently, some service combinations were randomly generated from these services according to the DAG structure.

In MSPEA2+, crossover and mutation operations replace services in the combination, causing structural changes. Therefore, before each evaluation, we decoded the combination vector $\left(x_1,x_2,\dots ,x_n\right)$ into a DAG through the greedy search. Figure 3 shows an example of encoding and decoding. The output list of the combination generated during the greedy search is compared with the task output, ensuring that the generated combination satisfies the input–output dependency constraints.

4.2. Breeding

The MSPEA2+ algorithm shares the breeding process introduced in the SPEA2 [11]. The archive is defined as ${\overline{p}}_g$. In each iteration, a batch of individuals selected by the sorting of fitness value is copied and stored in the archive.

If the archive is insufficient, the remaining solutions from the original set are sorted by $R_i$, and the top-ranking solutions are added to the archive until the set’s satisfaction. If the obtained solutions exceed the archive’s capacity, solutions are gradually removed by deleting the solution with shortest ${ \delta }_k^g$ until satisfaction is reached. The fitness calculation is performed according to the following formula:

$$\left\{\begin{array}{l}{R}_i={\displaystyle \sum _{j\in P_g,j\succ i}} S(j)\\ D_i=\frac{1}{{\sigma }_i^k+2}\\ F_i=R\left(i\right)+D\left(i\right)\end{array}\right.$$

(6)

where $S\left(j\right)$ is the number of individual ${\mathcal{L}}_j^g$ domains, ${\sigma }_i^k$ is the $k_{th}$ smallest distance between ${\mathcal{L}}_j^g$ and every individual in $p_g$; in this paper we take $k$ as $\sqrt{N+\sqrt{N}}$.

The mating pool is defined as $M_g$, and individuals are selected through tournament selection without replacement to fill the mating pool.

In SPEA2+ [39], to prevent the loss of information during the tournament selection process, all archives are saved for the next iteration, ensuring the retention of optimal solutions. The process is effective for the WSCP based on WM. However, as discussed in Section 4.1, the information of the combinatorial structure is not preserved in individuals during genetic processes. As a result, many solutions generated by crossover and mutation may not satisfy the input–output dependency constraints after decoding. Consequently, the population quickly converges to a small set of solutions, stuck in local optima.

Based on this, our algorithm incorporates father–child generation selection, which has been proven to be highly effective in NSGA2 [40]. By merging the currently generated parent generation with the previous generation and sorting by SPEA2 fitness, we select the first $n$ (size of population) solutions with smaller fitness, guaranteeing continuously approaching iteration of the optimal solution in our algorithm.

Algorithm 1 MSPEA2+ Main Loop

Input:    $N$ (Population size);    $\overline{N}$ (Archive size);    $g_{max}$ (Maximum number of generations); Output:    A (Non-dominated set); 1: $\mathrm{Initialize} \mathrm{population} p_g$ of m permutations ${\mathcal{L}}_i^g$ and create the empty archive ${\overline{p}}_g$ (where i = 1, 2, …, m and g = 0); 2: While $g\le g_{max}$do 3:    Calculate fitness values of individual in $p_g$; 4:    Copy all nondominated individuals in $p_g$ to ${\overline{p}}_g$; 5:    Adjust the size of ${\overline{p}}_g$ to $\overline{N}$ by fitness sort or ${\sigma }_i^k$; 6:    Perform binary tournament selection on ${\overline{p}}_g$ in order to fill the mating pool $M_g$; 7:    For each individual ${\mathcal{L}}_i^g$ from $M_g$, do 8:        Perform neighbor crossover and mutation to ${\mathcal{L}}_i^g$ and set it to $p_{g+1}$; 9:    End for; 10:    For each individual ${\mathcal{L}}_j^g$ from $p_g$, do 11:        Perform preference crossover and mutation to ${\mathcal{L}}_j^g$ and set it to $p_{g+1}$; 12:    End for; 13:    Merge $p_g$ and $p_{g+1}$ to $p_{g+1}$ and caculate fitness of $p_{g+1}$, adjusting $p_{g+1}$ size by choosing $N$ individuals with better fitness; 14: End while;

4.3. Crossover

Crossover is a pivotal step in the SPEA2 iteration process for generating new individuals. Crossover in MSPEA2+ is shown in Algorithm 2. The WSCP is a discrete combinatorial problem. Applying simple simulated binary crossover (SBX) [41] is quite challenging. While it is possible to convert the results of SBX into integers using rounding repair, the relationship between service index and service quality is minimal. Therefore, this operation becomes close to random selection. To address this, we transform the crossover operation into a double-point crossover between services with the same ontology. Although this operation cannot guarantee that the offspring solutions are functionally valid, it avoids dealing with complex changes in graph structure, thus ensuring algorithm efficiency. Figure 4 shows an example of double-point crossover.

Neighbor crossover has proven to be effective in enhancing the performance of crossover [42]. It performs crossover with individuals neighboring each other in objective space. In neighborhood crossover, individuals that match in the search direction are crossed over to generate offspring that are similar to the parent. In our approach, individuals from the archive are chosen for neighborhood crossover.

For certain non-dominant individuals, it is plausible that these individuals may perform well on some QoS attributes. In each iteration, two targets are randomly selected and, each time, these targets are used as the reference for sorting. After sorting, the first L solutions (not exceeding 50% of the archive size) are randomly selected for crossover. This approach leverages the characteristics of non-dominant solutions by performing crossovers on superior solutions targeting different objectives.

Algorithm 2 Crossover in MSPEA2+

1: $\mathrm{Randomly} \mathrm{choose} \mathrm{two} \mathrm{different} \mathrm{attributes} A_1$$\mathrm{and} A_2$; 2: For each individual ${\mathcal{L}}_i^g$ from $M_g$, do 3:    Find individual ${\mathcal{L}}_j^g$ with closest $A_1$ value to ${\mathcal{L}}_i^g$ in ${\overline{p}}_g$; 4:    Perform crossover between ${\mathcal{L}}_i^g$ and ${\mathcal{L}}_j^g$; 5:    Put result of crossover (${\mathcal{L}}_i^{g+1}$ and ${\mathcal{L}}_j^{g+1}$) into $p_{g+1}$; 6: End for; 7: Clear $M_g$; 8: Sort $p_g$ with value of $A_1$$\mathrm{and} \mathrm{add} \mathrm{the} \mathrm{first} L \mathrm{individuals} \mathrm{into} M_g$; 9: Sort $p_g$ with value of $A_2$; 10: For each individual ${\mathcal{L}}_k^g$ from $M_g$, do 11:    Randomly choose one of the first L individuals ${\mathcal{L}}_h^g$; 12:    Perform crossover between ${\mathcal{L}}_k^g$ and ${\mathcal{L}}_h^g$; 13:    Put result of crossover (${\mathcal{L}}_i^{g+1}$ and ${\mathcal{L}}_j^{g+1}$) into $p_{g+1}$; 14: End for;

4.4. Mutation

After completing the crossover operation, individuals undergo a mutation operation. The mutation operation involves replacing services in the combination result L, such as generating $L^{g+1}=(S_1,S_5,S_3,S_4)$ from $L^g=(S_1,S_2,S_3,S_4)$, where $S_2$ is replaced with a randomly selected service $S_5$ from CS. This process represents one mutation operation in WSCP. Similar to the reason discussed in Section 4.3, PM is not applied for the WSCP in MSPEA2+. Instead, a random section of services is selected for exchange. An example of mutation in MSPEA2+ is shown in Figure 5. This choice was primarily driven by the strong dependence of web services on preceding and following services. If only a single service is replaced, it is likely to lead to a rapid decline in overall fitness, resulting in the discard of the individual in the subsequent iteration. Therefore, we employ this random-length mutation to ensure a better fit for web service composition.

5. Experiment and Discussion

5.1. Experiment Setting

In this work, the standard dataset WSC-08 [43] was used to evaluate the performance of MSPEA2+. It has been used many times in web service composition [33,34,36]. Semantics were represented as ontologies written in OWL-S and services were represented in WSDL, which enabled the dataset to be easily parsed. All of the data in this dataset come from real public web services on the internet. Six representative QoS attributes were evaluated according to the normalized average method and user preference: time, cost, availability, reliability, SIM, and MT. The QoS attribute weights were $\left(W_t=1,W_c=1,W_a=1,W_r=1,W_{MT}=1,W_{SIM}=1\right)$. All experiments were conducted on a MacBook Pro equipped with Apple M1 Pro, 8 core (6 + 2) CPU, 32GB RAM, macOS 13.4 operating system, and IDEA 2023. For the selection of test parameters, the population size was 50, and the number of iterations was 300. For the SPEA2+, NSGA2, and SPEA2 algorithms, the probabilities of crossover and mutation were set to 0.8 and 0.2. The mutation probability for MSPEA2+ was set to 0.2, the probability of preference crossover to 0.1, and crossover to 0.6. In the experiments described in Section 5.3 and Section 5.4, the archive size of the SPEA2, SPEA2+ and MSPEA2+ was set to $40\mathrm{\%}$ of the population size. All experiments were conducted independently 30 times to avoid experimental errors.

The main influencing parameter of the experiment was the inverted generational distance (IGD) [44]. This is a commonly used performance metric in multi-objective evolutionary algorithms. IGD is calculated through measuring the distance from the point on each Pareto front to the most recently generated solution and then averaging these distances. In this way, IGD represents the overall distribution difference between the algorithmically generated solution and the Pareto frontier.

The first experiment studied the effect of archive size, based on tasks WSC-0803 and WSC-0804. In particular, six sets of archive-size settings, which were 5%, $10\mathrm{\%}$, $20\mathrm{\%},40\mathrm{\%},60\mathrm{\%}$, and $100\mathrm{\%}$ of the population size were studied. The second experiment studied the iteration performance of SPEA2, SPEA2+, NSGA2, and MSPEA2+ using the WSC-0801 and WSC-0802 datasets. The third experiment investigated mean IGD based on the WSC-08 experimental set.

5.2. Comparison of the Archive Size

Figure 6 shows the performance using the datasets of WSC-0803 and WSC-0804 with different archive sizes.

Table 2. Mean execution time for different archive sizes (in s for each iteration).

Task\Size	10%	20%	40%	60%	80%	100%
0803	38.01	36.53	35.56	33.35	35.96	36.28
0804	1.76	1.92	1.63	1.59	2.20	2.21

shows the iteration time for the algorithm. It can be seen that the larger the archive size, the higher was the iterative convergence efficiency. For $80\mathrm{\%}$ and $100\mathrm{\%}$ copy sizes, better IGD was obtained when approaching convergence, in line with expectations. Because the larger archive size not only increased the overall population size but also increased the elite distribution, it made it easy to obtain a better population for the next iteration. However, the increase in the size of the archive increased the spatial consumption and it also increased the time consumption when sorting the archived individuals and calculating the non-dominated individuals. It was found that $40\mathrm{\%}$ of the population size in WSC-0804 achieved the optimal IGD at 60–100 iterations, and the iteration rate was also consistent with the $100\mathrm{\%}$ archive size. The archive size of $60\mathrm{\%}$ of the population size also achieved a good descent rate and final convergence IGD with WSC-0803. It is likely that no matter whether a small or large amount of data is available for web service composition, an archive size of half of the population size is considered to be a good size that combines the iteration rate and the end effect.

5.3. Comparison of the Convergence Rate

Figure 7 illustrates that MSPEA2+ incorporating neighborhood crossover and preference crossover ensured an iteration rate comparable to NSGA2 in the early stages. As the number of iterations increased, the algorithm consistently achieved improved IGD. In contrast, the speed of the SPEA2 algorithm gradually diminished after several iterations, lacking population-level iteration mechanisms. While the SPEA2+ algorithm exhibited faster iteration, it also experienced a slowdown after multiple iterations.

In the cases of SPEA2 and SPEA2+, the non-dominated solutions in the archive quickly saturated the entire population, leading to local optimality. In contrast, MSPEA2+ demonstrated high iteration efficiency due to the preservation of domain crossover. The combination of the preferred crossover and father–child merging population algorithm allowed this approach to maintain a robust iteration rate in the first 30 to 50 iterations. This approach mitigated the issue of early nondominated solutions in the SPEA2 algorithm dominating the entire population and impacting overall distribution.

5.4. Comparison of the IGD and Execution Time

Table 3. Mean IGD for WSC-08 tasks (the green number represent optimal results).

Task/Method	MSPEA2+	NSGA2	SPEA2+	SPEA2
0801	0.001262	0.002450	0.003449	0.003957
0802	0.001771	0.003377	0.005384	0.004716
0803	0.000101	0.000289	0.000526	0.000561
0804	0.000921	0.003363	0.004302	0.004287
0805	0.000647	0.003731	0.001097	0.003540
0806	0.000182	0.003470	0.000764	0.000294
0807	0.000617	0.002081	0.000346	0.000740
0808	0.000264	0.002820	0.000671	0.002817

presents the mean IGD values for MSPEA2+, NSGA2, SPEA2+, and SPEA2. It is important to note that the obtained Pareto frontiers from the respective algorithms were directly compared, rather than the final populations. It can been seen from

Table 4. Mean execution time for WSC-08 tasks (in s for each iteration).

Method\Task	0801	0802	0803	0804	0805	0806	0807	0808
MSPEA2+	2.82	0.85	35.56	1.63	44.48	352.8	219.36	206.32
NSGA2	2.71	1.18	36.73	1.59	41.47	387.4	213.80	209.15
SPEA2+	2.88	0.86	37.32	1.65	45.62	357.6	203.35	197.90
SPEA2	2.87	0.87	37.53	1.56	45.62	349.3	210.86	195.63

that the iteration times are similar across different tasks in the IOM-based WSCP for the four algorithms. The main time complexity lay in the computation of semantic matching and the generation of DAG. Therefore, in this chapter, we focus on discussing the mean IGD values for different algorithms. Notably, MSPEA2+ consistently outperformed the other algorithms, except for a single task (WSC-0806). In contrast, SPEA2+ achieved superior IGD values in only one out of eight tasks, while neither NSGA2 nor SPEA2 exhibited favorable outcomes in any of the eight experiments. SPEA2 and SPEA2+ encountered challenges when faced with the datasets WSC-0801 to WSC-0805. This inherent limitation arises from the use of the archive. SPEA2 and SPEA2+ select individuals with better fitness from the archive and perform crossover and mutation operations. This strategy, however, can lead to local optimization, restricting the algorithm’s capacity to further diminish the IGD. For the large datasets of WSC-0806 to WSC-0808, SPEA2 and SPEA2+ leveraged their rapid iteration capabilities, outperforming the NSGA2 algorithm in terms of IGD performance. MSPEA2+ stands out as a promising contender, amalgamating the strengths inherited from NSGA2 and SPEA2+. As anticipated, its performance across various datasets attests to its versatility and effectiveness.

Yet, when dealing with WSC-0806 dataset which had 8226 services, MSPEA2+ did not outperform SPEA2+. This deviation could be attributed to the algorithm’s adeptness at avoiding local optima. Although a preference crossover could bring a better distribution of solutions, it might also delay the iteration speed of MSPEA2+. As a result, MSPEA2+ performed poorly on WSC-0806.

6. Conclusions

6.1. Contributions of Our Work

For RQ1, a greedy search strategy was adopted to select all request-related services and initialize the optimized population. During each evaluation process, the algorithm was iteratively applied to ensure the fulfillment of input–output dependency constraints. The SBX and PM algorithms of SPEA2 were replaced with double-point crossover and random length mutation. Thus, SPEA2 extended its capabilities from handling continuous problems to being able to tackle discrete combinatorial problems.

Regarding RQ2, increasing the archive size commonly improved the algorithm’s final performance for both small and large datasets, albeit at the cost of increased processing time. It is noteworthy that the processing time was longest with worst results when the archive size was too small, as the algorithm quickly converged to local optima due to the small archive size.

For RQ3, MSPEA2+ enhanced the overall performance of the SPEA2 algorithm through father–child merging, neighborhood crossover, and preference crossover. The selection of parent–child generation merges the current and previous generations to ensure the overall fitness improvement of the population during processing. Thus, even if the algorithm fails to find enough combinations satisfying the constraints in the current iteration, the overall diversity of the population can still be preserved. Neighborhood crossover enhances the iteration efficiency, enabling the algorithm to approximate the Pareto frontiers of combinations in a shorter time. Preference crossover is a crucial part of MSPEA2+, as it preserves the characteristics of some excellent QoS attributes in the combination solution, creating better distribution while increasing iteration efficiency. as discussed in Section 5.4, the iteration efficiency and final convergence of IGD obtained with MSPEA2+ was significantly superior to NSGA2, SPEA2, and SPEA2+.

6.2. Future Directions

As we continue to refine and advance multi-objective optimization algorithms, MSPEA2+ stands as a testament to the ongoing quest for finding solutions that can adapt to diverse challenges and datasets in the evolving landscape of optimization algorithms. For future work, we plan to extend our approach to address two important challenging issues:

Dealing with the automated adjustment of probity of crossover and mutation;

Applying QoS prediction before crossover and mutation to obtain further iteration efficiency.