Open AccessArticle

A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition

Hanting Wang

Yugen Du

^* and

Fan Chen

Faculty of Software Engineering, East China Normal University, Shanghai 200062, China

Author to whom correspondence should be addressed.

Appl. Sci. 2024, 14(10), 4157; https://doi.org/10.3390/app14104157

Submission received: 22 February 2024 / Revised: 27 April 2024 / Accepted: 2 May 2024 / Published: 14 May 2024

(This article belongs to the Section Computing and Artificial Intelligence)

Download

Browse Figures

Versions Notes

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.

Keywords:

evolutionary computation; large scale computation; meta-heuristic algorithm; web service composition

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:

\{\begin{matrix} M i n i m i z e f (L) = (f_{1} (L), f_{2} (L), \dots, f_{n} (L)) \\ W i t h L = (S_{1}, S_{2}, \dots, S_{n}) \\ f_{i} (L) = W_{i} \cdot Q o S_{i}, f o r i = 1, 2, \dots, 6 \\ s u b j e c t t o S_{j} \in C S, for j = 1, 2, \dots, N_{S R} \end{matrix}

(1)

where L is a composition result constructed by different services S,

f_{i}

is an objective function that captures

Q o S

, respectively, for every composition result

L

Q o S_{i}

is an objective in

Q o S

W_{i}

is the weight value for

Q o S_{i}

, CS denotes the set of all candidate services, and

N_{C S}

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 = \{I_{s}, O_{s}, {Q o S}_{s}\}$ ;
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_{s t a r t} = \{\emptyset, I_{t}, \emptyset\}$ and end node $S_{e n d} = \{O_{t}, \emptyset, \emptyset\}$ ;
A group of web services with the same ontology called service resporsity $S R_{i}$ ;
Ontology ${O T}_{i} =$ $\{S R_{i}, {O T}_{s u b j}\}$ . ${O T}_{s u b j}$ 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 $L_{i}^{g}$ , where g is the generation of optimization;
Each individual represents the composition result of candidate services $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} = \{T_{i}, C_{i}, A_{i}, R_{i}, S I M_{i}, M T_{i}\}

is a set of service functional attributes of

S

. The attributes

T_{i}, C_{i}, A_{i} a n d 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:

M T = \{\begin{matrix} 1 & exact match \\ 0.75 & plugin \\ 0.5 & subsumes \\ 0.25 & fail \end{matrix}

(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:

S I M = \frac{2 N}{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} = \{\begin{array}{l} \frac{Q_{i} - Q_{m i n}}{Q_{m a x} - Q_{m i n}} & Q_{m a x} - Q_{m i n} \neq 0 \\ 1 & Q_{m a x} - Q_{m i n} = 0 \end{array}

(4)

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

Q_{i} = \{\begin{array}{l} \frac{Q_{m a x} - Q_{i}}{Q_{m a x} - Q_{m i n}} & Q_{m a x} - Q_{m i n} \neq 0 \\ 1 & Q_{m a x} - Q_{m i n} = 0 \end{array}

(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 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_{s t a r t}$ and formed a collection with currently available output $O_{a v i}$ ;
$O_{a v i}$ 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

(x_{1}, x_{2}, \dots, x_{n})

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

{\bar{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

δ_{k}^{g}

until satisfaction is reached. The fitness calculation is performed according to the following formula:

\{\begin{array}{l} R_{i} = \sum_{j \in P_{g}, j ≻ i} S (j) \\ D_{i} = \frac{1}{σ_{i}^{k} + 2} \\ F_{i} = R (i) + D (i) \end{array}

(6)

where

S (j)

is the number of individual

L_{j}^{g}

domains,

σ_{i}^{k}

is the

k_{t h}

smallest distance between

L_{j}^{g}

and every individual in

p_{g}

; in this paper we take

k

\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);

\bar{N}

(Archive size);

g_{m a x}

(Maximum number of generations);
Output:
A (Non-dominated set);

1:: $Initialize population p_{g}$ of m permutations $L_{i}^{g}$ and create the empty archive ${\bar{p}}_{g}$ (where i = 1, 2, …, m and g = 0);
2:: While $g \leq g_{m a x}$ do
3:: Calculate fitness values of individual in $p_{g}$ ;
4:: Copy all nondominated individuals in $p_{g}$ to ${\bar{p}}_{g}$ ;
5:: Adjust the size of ${\bar{p}}_{g}$ to $\bar{N}$ by fitness sort or $σ_{i}^{k}$ ;
6:: Perform binary tournament selection on ${\bar{p}}_{g}$ in order to fill the mating pool $M_{g}$ ;
7:: For each individual $L_{i}^{g}$ from $M_{g}$ , do
8:: Perform neighbor crossover and mutation to $L_{i}^{g}$ and set it to $p_{g + 1}$ ;
9:: End for;
10:: For each individual $L_{j}^{g}$ from $p_{g}$ , do
11:: Perform preference crossover and mutation to $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:: $Randomly choose two different attributes A_{1}$ $and A_{2}$ ;
2:: For each individual $L_{i}^{g}$ from $M_{g}$ , do
3:: Find individual $L_{j}^{g}$ with closest $A_{1}$ value to $L_{i}^{g}$ in ${\bar{p}}_{g}$ ;
4:: Perform crossover between $L_{i}^{g}$ and $L_{j}^{g}$ ;
5:: Put result of crossover ( $L_{i}^{g + 1}$ and $L_{j}^{g + 1}$ ) into $p_{g + 1}$ ;
6:: End for;
7:: Clear $M_{g}$ ;
8:: Sort $p_{g}$ with value of $A_{1}$ $and add the first L individuals into M_{g}$ ;
9:: Sort $p_{g}$ with value of $A_{2}$ ;
10:: For each individual $L_{k}^{g}$ from $M_{g}$ , do
11:: Randomly choose one of the first L individuals $L_{h}^{g}$ ;
12:: Perform crossover between $L_{k}^{g}$ and $L_{h}^{g}$ ;
13:: Put result of crossover ( $L_{i}^{g + 1}$ and $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

(W_{t} = 1, W_{c} = 1, W_{a} = 1, W_{r} = 1, W_{M T} = 1, W_{S I M} = 1)

. 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 %

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 %

20 %, 40 %, 60 %

, and

100 %

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 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 %

and

100 %

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 %

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 %

archive size. The archive size of

60 %

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 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 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.

Author Contributions

Conceptualization, H.W. and Y.D.; methodology, H.W.; software, H.W.; validation, H.W.; formal analysis, Y.D.; investigation, H.W.; resources, H.W.; data curation, H.W.; writing—original draft preparation, H.W.; writing—review and editing, H.W., Y.D. and F.C.; visualization, F.C.; supervision, Y.D.; project administration, H.W. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Data Availability Statement

The original data presented in the study are openly available in [43].

Conflicts of Interest

The authors declare no conflict of interest.

References

Oh, S.C.; Lee, D.; Kumara, S.R.T. Effective web service composition in diverse and large-scale service networks. IEEE Trans. Serv. Comput. 2008, 1, 15–32. [Google Scholar] [CrossRef]
Jula, A.; Sundararajan, E.; Othman, Z. Cloud computing service composition: A systematic literature review. Expert Syst. Appl. 2014, 41, 3809–3824. [Google Scholar] [CrossRef]
Asghari, P.; Rahmani, A.M.; Javadi, H.H.S. Service composition approaches in IoT: A systematic review. J. Netw. Comput. Appl. 2018, 120, 61–77. [Google Scholar] [CrossRef]
Wang, P.; Ding, Z.; Jiang, C.; Zhou, M. Web service composition techniques in a health care service platform. In Proceedings of the 2011 IEEE International Conference on Web Services, Washington, DC, USA, 4–9 July 2011; pp. 355–362. [Google Scholar]
Sadeghiram, S.; Ma, H.; Chen, G. A novel repair-based multi-objective algorithm for QoS-Constrained distributed data-intensive Web service composition. In Web Information Systems Engineering–WISE 2020, Proceedings of the 21st International Conference, Amsterdam, The Netherlands, 20–24 October 2020; Proceedings, Part I 21; Springer International Publishing: Cham, Switzerland, 2020; pp. 489–502. [Google Scholar]
Chifu, V.R.; Pop, C.B.; Salomie, I.; Dinsoreanu, M.; Niculici, A.N.; Suia, D.S. Selecting the optimal web service composition based on a multi-criteria bee-inspired method. In Proceedings of the 12th International Conference on Information Integration and Web-Based Applications & Services, Paris, France, 8–10 November 2010; pp. 40–47. [Google Scholar]
Yao, Y.; Chen, H. Qos-aware service composition using NSGA-II1. In Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human, Seoul, Republic of Korea, 24–26 November 2009; pp. 358–363. [Google Scholar]
George, T.; George, B. OWL-S: Semantic Markup for Web Services; Computer Science Department University of Crete: Heraklion, Greece, 2004. [Google Scholar]
Rhayem, A.; Mhiri, M.B.A.; Gargouri, F. Semantic web technologies for the internet of things: Systematic literature review. Internet Things 2020, 11, 100206. [Google Scholar] [CrossRef]
Wang, C.; Ma, H.; Chen, G.; Hartmann, S. Using an estimation of distribution algorithm to achieve multitasking semantic web service composition. IEEE Trans. Evol. Comput. 2023, 27, 490–504. [Google Scholar] [CrossRef]
Singh, J. A review and comparison of two archive based Algorithms: SPEA2 and PAES. AIP Conf. Proc. 2023, 2819, 090003. [Google Scholar]
Cremene, M.; Suciu, M.; Pallez, D.; Dumitrescu, D. Comparative analysis of multi-objective evolutionary algorithms for QoS-aware web service composition. Appl. Soft Comput. 2016, 39, 124–139. [Google Scholar] [CrossRef]
Zitzler, E.; Laumanns, M.; Thiele, L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm; TIK Report; ETH Zurich: Zurich, Switzerland, 2001; Volume 103. [Google Scholar]
Gabrel, V.; Manouvrier, M.; Murat, C. Optimal and automatic transactional web service composition with dependency graph and 0–1 linear programming. In Service-Oriented Computing, Proceedings of the 12th International Conference, ICSOC 2014, Paris, France, 3–6 November 2014; Proceedings 12; Springer: Berlin/Heidelberg, Germany, 2014; pp. 108–122. [Google Scholar]
Chattopadhyay, S.; Banerjee, A.; Banerjee, N. A fast and scalable mechanism for web service composition. ACM Trans. Web 2017, 11, 26. [Google Scholar] [CrossRef]
Sha, M.; Alameen, A. Functionality Aware Dynamic Composition of Web Services. Comput. Syst. Sci. Eng. 2021, 36, 201–211. [Google Scholar] [CrossRef]
Barkat, A.; Kazar, O.; Seddiki, I. Framework for web service composition based on QoS in the multi cloud environment. Int. J. Inf. Technol. 2021, 13, 459–467. [Google Scholar] [CrossRef]
Li, J.; Zheng, X.-L.; Chen, S.-T.; Song, W.-W.; Chen, D.-R. An efficient and reliable approach for quality-of-service-aware service composition. Inf. Sci. 2014, 269, 238–254. [Google Scholar] [CrossRef]
Arunachalam, N.; Amuthan, A. Integrated probability multi-search and solution acceptance rule-based artificial bee colony optimization scheme for web service composition. Nat. Comput. 2021, 20, 23–38. [Google Scholar] [CrossRef]
Huo, Y.; Zhuang, Y.; Gu, J.; Ni, S.; Xue, Y. Discrete gbest-guided artificial bee colony algorithm for cloud service composition. Appl. Intell. 2015, 42, 661–678. [Google Scholar] [CrossRef]
Li, T.; He, T.; Wang, Z.; Zhang, Y. SDF-GA: A service domain feature-oriented approach for manufacturing cloud service composition. J. Intell. Manuf. 2020, 31, 681–702. [Google Scholar] [CrossRef]
Chen, M.; Wang, Q.; Sun, W.; Song, X.; Chu, N. GA for QoS satisfaction degree optimal web service composition selection model. In Proceedings of the 2019 6th International Conference on Behavioral, Economic and Socio-Cultural Computing (BESC), Beijing, China, 28–30 October 2019; pp. 1–4. [Google Scholar]
Kashyap, N.; Kumari, A.C.; Chhikara, R. Service Composition in IoT using Genetic algorithm and Particle swarm optimization. Open Comput. Sci. 2020, 10, 56–64. [Google Scholar] [CrossRef]
Xu, X.; Zhang, X.; Xiao, Y.; Cao, Z. Large-scale Web service composition based on optimized grey wolf optimizer. J. Comput. Appl. 2022, 42, 3162. [Google Scholar]
Jalal, S.; Yadav, D.K. Transaction and QoS-Driven Composition of Web Services Using Modified Grey Wolf Optimization with TOPSIS and AHP. In Advances in Distributed Computing and Machine Learning: Proceedings of ICADCML 2022; Springer Nature: Singapore, 2022; pp. 109–119. [Google Scholar]
Dahan, F.; El Hindi, K.; Ghoneim, A.; Alsalman, H. An enhanced ant colony optimization based algorithm to solve QoS-aware web service composition. IEEE Access 2021, 9, 34098–34111. [Google Scholar] [CrossRef]
El Allali, N.; Fariss, M.; Asaidi, H.; Bellouki, M. Semantic web services composition model using ant colony optimization. In Proceedings of the 2020 Fourth International Conference On Intelligent Computing in Data Sciences (ICDS), Fez, Morocco, 21–23 October 2020; pp. 1–5. [Google Scholar]
Ibrahim, G.J.; Rashid, T.A.; Akinsolu, M.O. An energy efficient service composition mechanism using a hybrid meta-heuristic algorithm in a mobile cloud environment. J. Parallel Distrib. Comput. 2020, 143, 77–87. [Google Scholar] [CrossRef]
Ju, C.; Ding, H.; Hu, B. A hybrid strategy improved whale optimization algorithm for web service composition. Comput. J. 2023, 66, 662–677. [Google Scholar] [CrossRef]
Azouz, Y.; Boughaci, D. Multi-objective memetic approach for the optimal web services composition. Expert Syst. 2023, 40, e13084. [Google Scholar] [CrossRef]
Hosseini Shirvani, M. Bi-objective web service composition problem in multi-cloud environment: A bi-objective time-varying particle swarm optimisation algorithm. J. Exp. Theor. Artif. Intell. 2021, 33, 179–202. [Google Scholar] [CrossRef]
Yang, Y.; Yang, B.; Wang, S.; Jin, T.; Li, S. An enhanced multi-objective grey wolf optimizer for service composition in cloud manufacturing. Appl. Soft Comput. 2020, 87, 106003. [Google Scholar] [CrossRef]
Sawczuk da Silva, A.; Mei, Y.; Ma, H.; Zhang, M. Particle swarm optimisation with sequence-like indirect representation for web service composition. In Evolutionary Computation in Combinatorial Optimization, Proceedings of the 16th European Conference, EvoCOP 2016, Porto, Portugal, 30 March–1 April 2016; Proceedings 16; Springer International Publishing: Cham, Switzerland, 2016; pp. 202–218. [Google Scholar]
Ma, H.; Wang, A.; Zhang, M. A hybrid approach using genetic programming and greedy search for QoS-aware web service composition. In Transactions on Large-Scale Data- and Knowledge-Centered Systems XVIII: Special Issue on Database- and Expert-Systems Applications; Springer: Berlin/Heidelberg, Germany, 2015; pp. 180–205. [Google Scholar]
Chattopadhyay, S.; Banerjee, A. QoS-aware automatic Web service composition with multiple objectives. ACM Trans. Web 2020, 14, 12. [Google Scholar] [CrossRef]
Wang, C.; Ma, H.; Chen, G.; Hartmann, S. Memetic EDA-Based Approaches to QoS-Aware Fully Automated Semantic Web Service Composition. IEEE Trans. Evol. Comput. 2021, 26, 570–584. [Google Scholar] [CrossRef]
Ruta, M.; Scioscia, F.; Bilenchi, I.; Gramegna, F.; Loseto, G.; Ieva, S.; Pinto, A. A multiplatform reasoning engine for the Semantic Web of Everything. J. Web Semant. 2022, 73, 100709. [Google Scholar] [CrossRef]
Chalkiadakis, G.; Ziogas, I.; Koutsmanis, M.; Streviniotis, E.; Panagiotakis, C.; Papadakis, H. A novel hybrid recommender system for the tourism domain. Algorithms 2023, 16, 215. [Google Scholar] [CrossRef]
Song, Y.; Fang, X. An Improved Strength Pareto Evolutionary Algorithm 2 with Adaptive Crossover Operator for Bi-Objective Distributed Unmanned Aerial Vehicle Delivery. Mathematics 2023, 11, 3327. [Google Scholar] [CrossRef]
Kashyap, N.; Kumari, A.C.; Chhikara, R. Multi-objective Optimization using NSGA II for service composition in IoT. Procedia Comput. Sci. 2020, 167, 1928–1933. [Google Scholar] [CrossRef]
Deb, K.; Agrawal, R.B. Simulated binary crossover for continuous search space. Complex Syst. 1995, 9, 115–148. [Google Scholar]
Fan, Y.; Wang, Z.; Xiong, X.; Panchal, S.; Fraser, R.; Fowler, M. Multi-Objective Optimization Design and Experimental Investigation for a Prismatic Lithium-Ion Battery Integrated with a Multi-Stage Tesla Valve-Based Cold Plate. Processes 2023, 11, 1618. [Google Scholar] [CrossRef]
Bansal, A.; Blake, M.B.; Kona, S.; Bleul, S.; Weise, T.; Jaeger, M.C. WSC-08: Continuing the web services challenge. In Proceedings of the 2008 10th IEEE Conference on E-Commerce Technology and the Fifth IEEE Conference on Enterprise Computing, E-Commerce and E-Services, Arlington, VA, USA, 21–24 July 2008; pp. 351–354. [Google Scholar]
Mejía-de-Dios, J.A.; Rodríguez-Molina, A.; Mezura-Montes, E. Multiobjective Bilevel Optimization: A Survey of the State-of-the-Art. IEEE Trans. Syst. Man Cybern. Syst. 2023, 53, 5478–5490. [Google Scholar] [CrossRef]

Figure 1. An example of web service composition.

Figure 2. Overview of MSPEA2+.

Figure 3. Example of encoding and decoding.

Figure 4. Example of double-point crossover in WSCP.

Figure 5. An Example of Mutation in MPSEA2+.

Figure 6. Mean IGD over generation for different archive sizes: (a) WSC-0803; (b) WSC-0804.

Figure 7. Mean IGD over generation for non-dominated set: (a) WSC-0801; (b) WSC-0802.

Table 1. Calculation for The Entire Link.

QQS Attributes	Availability	Reliability	Time	Cost	SIM	MT
Sequential	$\prod_{k = 1}^{d} a_{c k}$	$\prod_{k = 1}^{d} r_{c k}$	$\sum_{k = 1}^{d} t_{c k}$	$\sum_{k = 1}^{d} c_{c k}$	$\sum_{k = 1}^{d} w_{k} \cdot c_{c k}$	$\frac{1}{d} \sum_{k = 1}^{d} {s i m}_{{l i n k}_{k}}$
Parallel	$\prod_{k = 1}^{d} a_{c k}$	$\prod_{k = 1}^{d} r_{c k}$	$M A X \{t_{c k} ∣ k \in {1, \dots, d}\}$	$\sum_{k = 1}^{d} c_{c k}$	$\sum_{k = 1}^{d} w_{k} \cdot c_{c k}$	$\frac{1}{d} \sum_{k = 1}^{d} {s i m}_{{l i n k}_{k}}$
Choice	$\prod_{k = 1}^{d} w_{k} \cdot a_{c k}$	$\prod_{k = 1}^{d} w_{k} \cdot r_{c k}$	$\sum_{k = 1}^{d} w_{k} \cdot t_{c k}$	$\sum_{k = 1}^{d} w_{k} \cdot c_{c k}$	$\sum_{k = 1}^{d} w_{k} \cdot c_{c k}$	$\frac{1}{d} \sum_{k = 1}^{d} {s i m}_{l i n k_{k}}$

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

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

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

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Wang, H.; Du, Y.; Chen, F. A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition. Appl. Sci. 2024, 14, 4157. https://doi.org/10.3390/app14104157

AMA Style

Wang H, Du Y, Chen F. A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition. Applied Sciences. 2024; 14(10):4157. https://doi.org/10.3390/app14104157

Chicago/Turabian Style

Wang, Hanting, Yugen Du, and Fan Chen. 2024. "A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition" Applied Sciences 14, no. 10: 4157. https://doi.org/10.3390/app14104157

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu