An extended artificial bee colony with local search for solving the Skyline-based web services composition under interval QoS properties

Abstract

In this paper, we introduce an extended version of artificial bee colony with a local search method (EABC) for solving the QoS uncertainty-aware web service composition (IQSC) problem, where the ambiguity of the QoS properties are represented using the interval-number model. At first, we formulate the addressed problem as an interval constrained single-objective optimization model. Then, we use the skyline operator to prune the redundant and dominated web services from their sets of functionally equivalent ones. Whereas, EABC is employed to solve the IQSC problem in a reduced search space more effectively and more efficiently. For the purpose of validation of the performance and the efficiency of the proposed approach, we present the experimental comparisons to an existing skyline-based PSO, an efficient discrete gbest-guided artificial bee colony and a recently provided Harris Hawks optimization with an elite evolutionary strategy algorithms on an interval extended version of the public QWS dataset.

Keywords

Web service composition Quality of Service (QoS)interval number skyline operator artificial bee colony

1 Introduction

As far as the Service Oriented Architecture (SOA) is concerned, any hardware or software resource can be easily provided as a web service to the end-users. However, with the increasing number of the web services, it offers the same functionalities but with different values in their nonfunctional properties, known by the Quality of Service (QoS) parameters such as response time, price, availability, …, etc. Therefore, selecting the best web services from their sets of functionally equivalent ones to build the best Composite Service (CS), which should satisfy the end-users’ local and global QoS requirements, becomes a challenging problem for both industrial and academic researchers [3, 29]. This addressed issue, known by the QoS-aware web service composition (QSC), is an NP-hard optimization problem, where many optimization methods including exact, heuristic and meta-heuristic web service composition approaches have been provided to unravel it [12].

From the systematic literature review of [12], most of the existing exact web services selection algorithms modeled the QSC problem as an integer/mixed-integer linear programming model [3, 4], where solvers such as LpSolve 1 and CPLEX 2 have been utilized to solve the modeled QSC. These solvers can get the optimal solutions of QSC, but they need the linearization of the QSC’s objective functions and constraints. Moreover, as the QSC scale increases, the efficiency of the exact web services selection algorithms decreases. Therefore, those based on the evolutionary and bio-inspired algorithms like Genetic Algorithm (GA) [7], Particle Swarm Optimization (PSO) [17], Artificial Bee Colony (ABC) [11, 25], Harris Hawks Optimization (HHO) [16] and so on, have drawn the attention of the QSC researchers. These algorithms can get near-optimal solutions within reasonable processing times and without any linearization of objective functions and users’ QoS constraints of the QSC problem.

All the above QSC studies consider the advertised QoS values as non-ambiguous, but in real-world environments and due to some unconditional factors of the SOAs such as the network topological changes and economic policies. Therefore, the QoS values of web services are uncertain in nature [21]. For this reason, some recent QoS-aware web service composition approaches have been proposed to solve the QSC problem under uncertain QoS parameters that have been modeled as interval numbers [13, 23], probabilistic variables [30] or fuzzy numbers [22, 27]. In the web services selection process of these approaches, all the provided web services are considered as potential candidates to construct the final CS solution. However, some of them are not possible candidates to build this final solution. Therefore, some existing studies [2 , 28] have used the Skyline operator [6] to reduce the search space of QSC by pruning the web services that cannot be part of the final solutions, since they are dominated by some of their functionally equivalent web services partners. However, in all the aforementioned Skyline-based QSC studies, the QoS parameters are considered with precise and exact values. Hence, the motivation behind this work is to provide an efficient approach for solving the QoS uncertainty-aware web service composition in a reduced search space, where the main contributions of our study can be summarized as follows:

We first propose an interval constrained single objective optimization model to the QoS uncertainty-aware web service composition, denoted as IQSC, where its QoS parameters are expressed as interval numbers;

Then, to address the formulated IQSC, we propose an approach including two components. (1) The first one (Skyline operator) is used to reduce the search space of IQSC; and, thus, its best CS can be found very quickly with high solution quality. (2) The second component is an extended version of the basic ABC algorithm with an effective local search method, named EABC, which is performed to solve the formulated IQSC in a reduced search space more effectively and more efficiently.

Finally, to demonstrate the performance and the efficiency of the proposed approach, we have compared it to the ones of references [11 , 24], where the comparison experiments are performed on a new interval-valued based version of the public QWS dataset [1].

The remainder part of this paper is organized as follows. In Section 2, we review and summarize some relevant and notable works to ours. In Section 3, we give some mathematical operator definitions on interval numbers to be used throughout the rest of this study. In Section 4, we mathematically formulate the QoS uncertainty-aware web service composition under interval QoS properties, denoted by IQSC, as an interval constrained single-objective optimization model. To address the formulated IQSC, our proposed approach, which includes two components Skyline operator and EABC, is described with details in Section 5. Section 6 is devoted to discuss the comparison results of our experiments. Finally, our conclusion and future work are given in Section 7.

2 Related work

From the literature, the QSC has been addressed by two main categories of web service selection approaches, including (1) Exact and (2) Meta-heuristic (i.e., evolutionary and bio-inspired) optimization methods [12]. Moreover, to improve the efficiency of the QSC approaches, the Skyline operator [6] has been used by some researchers to reduce the time of web services selection [2 , 28]. In addition, due to some unconditional factors of the SOA environments, such as the network topological changes and economic policies [21], some QSC studies have considered the QoS parameters to be taken with ambiguous values [13 , 30]. Here in this section, we have only reviewed and discussed a small batch of works related to ours.

The exact optimization methods have modeled the QSC problem as an Integer Linear Programming (ILP) model [29] or a Mixed ILP (MILP) one [3, 4] and have solved it by using existing ILP/MILP solvers such as LpSolve and CPLEX. For the QSC problem instances with small search spaces, these methods yield good performance in terms of running time and solution quality of the obtained final CSs solutions. However, the computation time of these methods increases exponentially with the increasing number of the provided functionally equivalent web services. Moreover, the exact optimization approaches require the linearization of the QSC objective functions and the users’ global QoS constraints. Therefore, those based on evolutionary and bio-inspired optimization algorithms like GA [7], PSO [17], ABC [11, 25], and so on, have drawn the attention of the QSC researchers. Compared to the exact optimization methods that can obtain optimal CSs solutions, the meta-heuristic algorithms can get near-optimal ones, but with reasonable processing times and without any linearization of the objective functions and the users’ global QoS constraints of the QSC problem.

To improve the efficiency of the QSC optimization approaches, a representative mechanism named Skyline operator [6] has been employed to reduce the search space of the QSC problem. Hence, the computation time cost of these approaches is shortened. For instance, authors of [2] were the initiators that apply the Skyline operator to reduce the QSC search space where a new service dominance based on the QoS attributes of web services has been performed, among web services, to prune the dominated ones. In this study, the QSC problem was formulated as an ILP model and solved more efficiently using the existing LpSolve solver in a reduced search space. In [24], the corresponding authors proposed a fast cloud-based web service composition approach, which prunes the redundant and dominated candidate web services by an adopted Skyline operator and performs the PSO algorithm to find out a more powerful final CS solution. In [28], the authors have used the mathematical programming language (AMPL) [10] to formulate the QSC problem as a nonlinear integer programming model, which has been solved by the existing Bonmin 3 solver. In this study, and similar to the ones of [2] and [24], the Skyline operator has been employed to reduce the search space of the QSC problem.

However, all the above studies consider the advertised QoS values as non-ambiguous ones, which is fictional for dynamic SOA environments since some unconditional factors, like network topological changes and economic policies, render the QoS values uncertain in nature. Therefore, some researchers have formulated the QSC problem as a non-deterministic optimization model using interval numbers [13, 23], fuzzy numbers [22, 27], or probabilistic models [30].

Table 1 summarizes the aforementioned studies according to the QoS parameters representation model, the QSC mathematical formulation and its proposed solution approach, where, differently to most of the cited papers, we have represented the QoS uncertainty with the interval number model. Hence, the QSC problem is formulated as an interval constrained single-objective optimization one. The latter is solved by an extended artificial bee colony algorithm, while an interval-valued based version of the existing crisp Skyline operator is employed to reduce the search space of IQSC that will improve the efficiency of the provided algorithm.

Table 1
Summary of some related QoS-aware service composition studies

Study Year QoS parameters representation model QSC mathematical formulation Proposed QSC solution approach

[29] 2004 Real numbers ILP ILP solver (CPLEX)

[4] 2007 Real numbers MILP ILP solver (CPLEX)

[3] 2012 Real numbers MILP ILP solver (LpSolve)

[2] 2010 Real numbers ILP LpSolve with Skyline operator

[24] 2013 Real numbers Single objective optimization PSO with Skyline operator

[28] 2020 Real numbers Nonlinear integer programming Bonmin with Skyline operator

[7] 2005 Real numbers Constrained single objective optimization GA-based approach

[17] 2014 Real numbers Single objective optimization PSO-based approach

[27] 2018 Fuzzy numbers Fuzzy single objective optimization GA-based approach

[23] 2019 Interval numbers Interval constrained multiple objectives optimization Interval multi-objectives artificial bee colony (IM_ABC)

[11] 2015 Real numbers Single objective optimization discrete gbest-guided artificial bee colony (DGABC)

[25] 2019 Real numbers Single objective optimization Discrete ABC-based approaches

[13] 2016 Interval numbers Interval single objective optimization GA with PROMETHEE method

[22] 2020 Fuzzy numbers Fuzzy constrained multiple objectives optimization Fuzzy Discrete multi-objectives artificial bee colony (FDMOABC)

[16] 2021 Real numbers Single objective optimization An improved Harris Hawks Optimization algorithm by a developed Elite Evolutionary Strategy (HHOEES)

Our study 2021 Interval numbers Interval constrained single objective optimization EABC with Skyline operator

Study	Year	QoS parameters representation model	QSC mathematical formulation	Proposed QSC solution approach
[29]	2004	Real numbers	ILP	ILP solver (CPLEX)
[4]	2007	Real numbers	MILP	ILP solver (CPLEX)
[3]	2012	Real numbers	MILP	ILP solver (LpSolve)
[2]	2010	Real numbers	ILP	LpSolve with Skyline operator
[24]	2013	Real numbers	Single objective optimization	PSO with Skyline operator
[28]	2020	Real numbers	Nonlinear integer programming	Bonmin with Skyline operator
[7]	2005	Real numbers	Constrained single objective optimization	GA-based approach
[17]	2014	Real numbers	Single objective optimization	PSO-based approach
[27]	2018	Fuzzy numbers	Fuzzy single objective optimization	GA-based approach
[23]	2019	Interval numbers	Interval constrained multiple objectives optimization	Interval multi-objectives artificial bee colony (IM_ABC)
[11]	2015	Real numbers	Single objective optimization	discrete gbest-guided artificial bee colony (DGABC)
[25]	2019	Real numbers	Single objective optimization	Discrete ABC-based approaches
[13]	2016	Interval numbers	Interval single objective optimization	GA with PROMETHEE method
[22]	2020	Fuzzy numbers	Fuzzy constrained multiple objectives optimization	Fuzzy Discrete multi-objectives artificial bee colony (FDMOABC)
[16]	2021	Real numbers	Single objective optimization	An improved Harris Hawks Optimization algorithm by a developed Elite Evolutionary Strategy (HHOEES)
Our study	2021	Interval numbers	Interval constrained single objective optimization	EABC with Skyline operator

3 Mathematical operators on interval numbers

Here in this section, we have introduced the following mathematical definitions related to the interval numbers that have been employed throughout the remainder part of this article.

Definition 1. (Interval number) Given any two real numbers a^l and a^u with a^l ≤ a^u. The set $A = {x : x \in ℝ$ and a^l ≤ x ≤ a^u} denoted by A = [a^l, a^u] is named an interval number, where a^l and a^u are called its lower and upper limits, respectively.

Definition 2. (Arithmetic operations on interval numbers [18]) Let A = [a^l, a^u] and B = [b^l, b^u] be any two interval numbers, then the arithmetic operations on A and B are defined as follows:

Addition ⊕: A ⊕ B = [a^l, a^u] ⊕ [b^l, b^u] = [a^l + b^l, a^u + b^u]

Subtraction ⊖: A ⊖ B = [a^l, a^u] ⊖ [b^l, b^u] = [a^l - b^u, a^u - b^l]

Multiplication ⊗: A ⊗ B = [a^l, a^u] ⊗ [b^l, b^u]= [m^l, m^u] with m^l = min(a^lb^l, a^lb^u, a^ub^l, a^ub^u) and m^u = max(a^lb^l, a^lb^u, a^ub^l, a^ub^u)

Scalar multiplication: $\forall λ \in ℝ$ , λ ⊗ A = λ ⊗ [a^l, a^u] $= {\begin{matrix} [λ * a^{l}, λ * a^{u}] if λ > = 0 \\ [λ * a^{u}, λ * a^{l}] if λ < 0 \end{matrix}$

Moreover, let A = [a^l, a^u] and B = [b^l, b^u] be any two interval numbers, the three possible overlapping types between A and B, as shown in Fig. 1, are used in the following definitions for ordering and ranking interval numbers of the maximization (minimization) optimization problems with objective functions modeled as interval numbers.

Fig. 1

Types of overlapping between interval numbers [15].

Definition 3. (Interval greater ranking operator for maximization optimization problems with interval objectives: >_max [23]) For any two interval numbers A = [a^l, a^u] and B = [b^l, b^u], the interval greater ranking operator >_max between A and B is defined as follows:

For interval numbers of Type I or Type II, A > _maxB if (a^l > b^l) and (a^u > b^u);

For interval numbers of Type III, A > _maxB if:

(a^l - b^l) > (b^u - a^u);

or ((a^l - b^l) = (b^u - a^u)) and (a^u < b^u)

Definition 4. (Interval smaller ranking operator for minimization optimization problems with interval objectives: <_min) [23]) For any two interval numbers A = [a^l, a^u] and B = [b^l, b^u], the interval smaller ranking operator <_min between A and B is defined as follows:

For interval numbers of Type I or Type II, A < _minB if (a^l < b^l) and (a^u < b^u);

For interval numbers of Type III, A < _minB if:

(a^l - b^l) < (b^u - a^u);

or ((a^l - b^l) = (b^u - a^u)) and (a^u < b^u)

Definition 5. (Interval equal ranking operator for maximization (minimization) optimization problems with interval objectives: =) For any two interval numbers A = [a^l, a^u] and B = [b^l, b^u], if a^l = b^l and a^u = b^u then A and B are equal interval numbers represented as A = B.

Definition 6. For any two interval numbers A and B, the interval greater or equal (≥_max) and the interval smaller or equal (≤_min) ranking operators for the maximization and the minimization optimization problems with interval objectives, respectively, are defined as follows:

A ≥ _maxB ⇔ (A > _maxB) or (A = B)

A ≤ _minB ⇔ (A < _minB) or (A = B)

Definition 7. (The interval minimum Min and maximum Max operators) let {A_j, j = 1, 2, …, m} be a set of m interval numbers, then the minimum and the maximum interval numbers of {A_j, j = 1, 2, …, m} for the minimization and the maximization optimization problems with interval objectives, respectively, are defined as follows:

If A_q ≤ _minA_j for all j = 1, 2, …, m with j ≠ q then $A_{q} = {Min}_{j = 1}^{m} {A_{j}}$ is the minimum interval number of {A_j, j = 1, 2, …, m}.

If A_p ≥ _maxA_j for all j = 1, 2, …, m with j ≠ p then $A_{p} = {Max}_{j = 1}^{m} {A_{j}}$ is the maximum interval number of {A_j, j = 1, 2, …, m}.

4 Interval model of the QoS uncertainty-aware web service composition problem

Let’s give a tremendous set of atomic web services, where each web service, denoted by ws, is characterized by two types of properties, functional and nonfunctional ones. The functional parameters (i.e., input and output attributes) of a ws are used to represent its supported functionality. Whereas, the nonfunctional properties (i.e. QoS attributes) of a ws, such as response time, availability, reputation, price, …, etc, represent its parameters quality. Each QoS attribute, denoted by q_t with t = 1, 2, …, r and r is the number of the considered QoS parameters, can be either positive or negative parameter, where a ws with larger (lower) values in its positive q_ts, the better (worse) is, whereas a ws with lower (larger) values in its negative q_ts, the better (worse) is. Here in this study, the positive list of q_ts is denoted by QoS⁺ and the negative one is represented by QoS^-. For example, the reputation and availability attributes belong to the QoS⁺ list, whereas the price and response time parameters belong to the QoS^- list. Furthermore, a web services class, denoted by S = {ws₁, ws₂, …, ws_m}, is a set of m atomic web services that have similar functionalities but with different values in their q_ts.

As seen in Fig. 2, which represents the graphic depiction of the QSC problem. For a given abstract composite service, denoted by ACS = {S₁, S₂, …, S_n}, which represents the n needed web services classes to reply a user request, and a list of k user’s global QoS requirements, denoted by Cst_{q
_t}s with t = 1, 2, …, k and k ≤ r. A concrete composite service, denoted by CS that represents the user request response, is built by selecting from each web services class $S_{i} = {{ws}_{i}^{1}, {ws}_{i}^{2}, \dots, {ws}_{i}^{m_{i}}}$ a unique web service ${ws}_{i}^{j}$ with j ≤ m_i, where the global QoS values of CS that have been evaluated by aggregating the QoS values of their atomic wss should meet the considered Cst_{q
_t}s. In this study, as shown in Fig 3, four basic connection structures, i.e., sequential, parallel, branch and loop, have been considered to compose the atomic wss of CSs. Furthermore, due to some unconditional factors of the SOAs like network architectures changes and economic policies, the QoS values of the elementary wss are uncertain in nature [21]. Therefore, motivated by the fact that the interval number is an efficient, general and easy representative model to express perfectly the uncertain QoS values [13, 23], and by considering the four mostly used QoS parameters in solving the QSC problem [3] including two positive QoS attributes: availability (q₁) and throughput (q₂), and two negative ones: response time (q₃) and price (q₄). Hence, the interval constrained single objective optimization model of QSC, denoted by IQSC, can be stated as follows:

Fig. 2

Graphic depiction of the QoS-aware web service composition problem.

Fig. 3

Connection structures between atomic web services.

Determine the best CS solution among all the possible ones 4 , which maximizes $\begin{matrix} Maximize IU (CS) = \sum_{t = 1}^{r} w_{q_{t}} \otimes \bar{{CS}_{q_{t}}} \end{matrix}$ (1) Subject to k global QoS constraints $\forall t = 1 \dots k {\begin{matrix} {CS}_{q_{t}} \leq_{min} {Cst}_{q_{t}}, if q_{t} \in {QoS}^{-} \\ {CS}_{q_{t}} \geq_{max} {Cst}_{q_{t}}, if q_{t} \in {QoS}^{+} \end{matrix}$ (2) Where CS_{q
_t} is the global QoS interval-valued of the CS solution in the q_t attribute that can be evaluated, as seen in Table 2, using the interval arithmetic operations given in Definitions 2 and 7, the four basic connection structures as depicted in Fig. 3, and the interval-valued ${ws}_{i, q_{t}} = [{ws}_{i, q_{t}}^{l}, {ws}_{i, q_{t}}^{u}]$ of each atomic web service ws_i of CS in the q_t attribute. IU (CS) is the interval utility function of CS that maps the CS_{q
_t}s values into a single interval-valued. This function adopts the well-known Simple Additive Weighting (SAW) method [20] through scaling the interval values CS_{q
_t}s into their normalized interval ones $\bar{{CS}_{q_{t}}}$ s. Then afterwards, these normalized interval values are weighted and summed-up using the weights w_{q
_t}s with w_{q
_t} ∈ [0, 1] and $\sum_{t = 1}^{r} w_{q_{t}} = 1$ , which represent the importance and priority of each q_t by the user. The normalized interval-valued $\bar{{CS}_{q_{t}}}$ of its related original one ${CS}_{q_{t}} = [{CS}_{q_{t}}^{l}, {CS}_{q_{t}}^{u}]$ is calculated according to the type of the used q_t criterion, i.e., positive or negative parameter, as given in the following interval positive and negative normalization Equations 3 and 4, receptively.

Interval positive normalization $\begin{matrix} \forall q_{t} \in {QoS}^{+}, \bar{{CS}_{q_{t}}} = \\ {\begin{matrix} [\frac{{CS}_{q_{t}}^{l} - \min_{q_{t}}^{l}}{\max_{q_{t}}^{u} - \min_{q_{t}}^{l}}, \frac{{CS}_{q_{t}}^{u} - \min_{q_{t}}^{l}}{\max_{q_{t}}^{u} - \min_{q_{t}}^{l}}] if \max_{q_{t}}^{u} \neq \min_{q_{t}}^{l} \\ [1, 1] if \max_{q_{t}}^{u} = \min_{q_{t}}^{l} \end{matrix} \end{matrix}$ (3)

Interval negative normalization $\begin{matrix} \forall q_{t} \in {QoS}^{-}, \bar{{CS}_{q_{t}}} = \\ {\begin{matrix} [\frac{\max_{q_{t}}^{u} - {CS}_{q_{t}}^{u}}{\max_{q_{t}}^{u} - \min_{q_{t}}^{l}}, \frac{\max_{q_{t}}^{u} - {CS}_{q_{t}}^{l}}{\max_{q_{t}}^{u} - \min_{q_{t}}^{l}}] if \max_{q_{t}}^{u} \neq \min_{q_{t}}^{l} \\ [1, 1] if \max_{q_{t}}^{u} = \min_{q_{t}}^{l} \end{matrix} \end{matrix}$ (4)

Where the real limit values

\min_{q_{t}}^{l}

and

\max_{q_{t}}^{u}

for an ACS = (S₁, S₂, …, S_n) with ∀i ∈ {1, 2 … , n},

S_{i} = {{ws}_{i}^{1}, {ws}_{i}^{2}, \dots, {ws}_{i}^{mi}}

and ∀j ∈ {1, 2 … , m_i},

{ws}_{i, q_{t}}^{j} = [{ws}_{i, q_{t}}^{j, l}, {ws}_{i, q_{t}}^{j, u}]

are evaluated as follows

\max_{q_{t}}^{u} = {Agg}_{q_{t} i = 1}^{n} (\max_{j = 1}^{m_{i}} {{ws}_{i, q_{t}}^{j, u}})

(5)

\min_{q_{t}}^{l} = {Agg}_{q_{t} i = 1}^{n} (\min_{j = 1}^{m_{i}} {{ws}_{i, q_{t}}^{j, l}})

(6) Where

{Agg}_{q_{t} i = 1}^{n}

denotes the related crisp QoS aggregation formula, i.e., ∑, ∏, min and max, for the q_t attribute, as defined in Table 2, that has been employed to aggregate the n obtained real values

\max {{ws}_{i, q_{t}}^{j, u}} / \min {{ws}_{i, q_{t}}^{j, l}}

from each web services class S_i with j = 1, 2, …, m_i.

Table 2

Interval QoS aggregation formulas for evaluating the global QoS interval-valued of concrete composite services CSs

QoS	n sequential web services ws_i	m parallel web services ws_i	branch^a of m web services ws_is with their pr_is probabilities	call a web service ws with p times
q ₁	$\prod_{i = 1}^{n} [{ws}_{i, q_{1}}^{l}, {ws}_{i, q_{1}}^{u}]$	$\prod_{i = 1}^{m} [{ws}_{i, q_{1}}^{l}, {ws}_{i, q_{1}}^{u}]$	${Min}_{i = 1}^{m} {[{ws}_{i, q_{1}}^{l}, {ws}_{i, q_{1}}^{u}]}$	$\prod_{i = p}^{n} [{ws}_{i, q_{1}}^{l}, {ws}_{i, q_{1}}^{u}]$
q ₂	${Min}_{i = 1}^{n} {[{ws}_{i, q_{2}}^{l}, {ws}_{i, q_{2}}^{u}]}$	${Min}_{i = 1}^{m} {[{ws}_{i, q_{2}}^{l}, {ws}_{i, q_{2}}^{u}]}$	${Min}_{i = 1}^{m} {[{ws}_{i, q_{2}}^{l}, {ws}_{i, q_{2}}^{u}]}$	$[{ws}_{i, q_{2}}^{l}, {ws}_{i, q_{2}}^{u}]$
q ₃	$\sum_{i = 1}^{n} [{ws}_{i, q_{3}}^{l}, {ws}_{i, q_{3}}^{u}]$	${Max}_{i = 1}^{m} {[{ws}_{i, q_{3}}^{l}, {ws}_{i, q_{3}}^{u}]}$	${Max}_{i = 1}^{m} {[{ws}_{i, q_{3}}^{l}, {ws}_{i, q_{3}}^{u}]}$	$p * [{ws}_{i, q_{3}}^{l}, {ws}_{i, q_{3}}^{u}]$
q ₄	$\sum_{i = 1}^{n} [{ws}_{i, q_{4}}^{l}, {ws}_{i, q_{4}}^{u}]$	$\sum_{i = 1}^{m} [{ws}_{i, q_{4}}^{l}, {ws}_{i, q_{4}}^{u}]$	${Max}_{i = 1}^{m} {[{ws}_{i, q_{4}}^{l}, {ws}_{i, q_{4}}^{u}]}$	$p * [{ws}_{i, q_{4}}^{l}, {ws}_{i, q_{4}}^{u}]$

^aIn the branch connection structure, according to the pr_is of ws_is, only one web service among them is executed. q₁:Availability, q₂:Throughput, q₃:Response time and q₄:Price

5 Proposed approach

To solve the IQSC problem, we propose an approach including two components. The first one, which uses the Skyline operator [6], is employed to reduce the search space of IQSC by pruning the dominated candidate web services. The second component is to quickly find out the near-optimal solution of IQSC by performing an extended version of the basic ABC algorithm with an effective local search method, named EABC.

5.1 Skyline service

Our main goal in this study is to find a near-optimal CS solution for the IQSC problem that maximizes the interval utility value as defined in Equation 1 and satisfies the user’s overall QoS constraints as given in Equation 2. This near-optimal solution contains a set of atomic wss, where each one is selected from its related web services class. However, not all wss of each web services class are potential candidates to construct the final near-optimal solutions of IQSC. Hence, some existing studies [2 , 28] have used the Skyline operator [6] to reduce the search space of QSC by pruning the wss that cannot take a place in the construction of their final solutions, since they are dominated by some of their functionally equivalent wss partners. However, in the whole aforesaid skyline-based studies, the QoS parameters are considered with precise and exact values. Therefore, we extend the crisp Service Dominance and Skyline Service definitions of [2 , 28] to consider the QoS properties representation with the interval-number model, as give in the following.

Definition 8. (Service Dominance) Let’s consider a web services class S and two web services ws₁, ws₂ ∈ S, where each one has a set of QoS parameters q_ts. We say ws₁ dominates ws₂, denoted as ws₁ ≺ ws₂, if and only if: (1) ∀q_t ∈ QoS⁺: ws_{1,q_t} ≥ _maxws_{2,q_t}, and (2) ∀q_t ∈ QoS^-: ws_{1,q_t} ≤ _minws_{2,q_t}, and (3) ∃q_t ∈ QoS⁺, ws_{1,q_t} > _maxws_{2,q_t} or ∃q_t ∈ QoS^- , ws_{1,q_t} < _minws_{2,q_t}.

Definition 9. (Skyline Service) For a given web services class S = {ws₁, ws₂, …, ws_m} of m functionally equivalent wss. The skyline service of S, denoted by SkS, contains the candidate wss in S that cannot be dominated by any other ws of S. i.e, SkS = {ws_i ∈ S ∣ ∄ ws_j ∈ S : ws_j ≺ ws_i}.

To define the skyline service SkS of each web services class S, the skyline computation process performs pair-wise comparisons between the interval values ws_{q
_t}s of the compared web services wss of S. This calculation process can be expensive in terms of evaluation time, especially, if S has a very large number of functionally equivalent wss. However, for the IQSC problem, the skyline service calculation is independent from any online user request [2]. Therefore, the skyline computation can be performed offline by any of the exiting efficient skyline algorithms [6]. Here in our study, to calculate each skyline service of IQSC, we have adapted the well-known non-dominated method of [9] through using the service dominance operator ≺ given in Definition 8. The pseudo-code of the interval non-dominated procedure for evaluating each skyline service SkS of its associated web services class S is presented in Algorithm 1.

Algorithm 1 Interval non-dominated procedure for evaluating skyline service.

Input: The web service class S

Output: The calculated skyline service SkS of S

1: SkS =∅

2: for each web service ws ∈ S do

3: N_ws ← 0 N_ws: is the number of web services in S dominating ws

4: for each web service ws′ ∈ S that differs to ws do

5: if ws′ ≺ ws then

6: N_ws ← N_ws + 1

7: end if

8: end for

9: if N_ws = 0 then

10: SkS ← SkS ∪ {ws}

11: end if

12: end for

5.2 Extended artificial bee colony: EABC

The ABC algorithm is a well-known bio-inspired optimization algorithm that mimics the smart work of honey bees to find out the near-optimal solution of an optimization problem [14]. It has been widely applied to solve the QSC problem for several service-based environments like service-oriented applications [25] and cloud computing [11]. Similar to the basic ABC algorithm, in order to find out the near-optimal CS solution of IQSC, denoted by CS_best, EABC performs repetitively and successively three types of bees (Employees, Onlookers and Scouts) on each explored food sources area src_g to find a new better one src_g+1 with g ∈ {0, 1, 2, …, MITR} and MITR is a maximum iteration number of the EABC algorithm. The initial food sources area of Z solutions {CS₁, CS₂, …, CS_Z} with their initial positions ${src}_{0} = {{CS}_{1}^{0}, {CS}_{2}^{0}, \dots, {CS}_{Z}^{0}}$ is generated randomly, where the dimensional values, i.e., web services, of each food source position ${CS}_{z}^{0}$ with z = 1, 2, …, Z are defined according to the encoding schema given in the next subsection and its nectar amount, i.e. fitness value, is evaluated through using the interval utility function, i.e., $IU ({CS}_{z}^{0})$ , as defined in Equation 1. Moreover, for each generated food source CS_z, an integer variable trial_z, which is initialized to zero, is assigned to it. Besides, in order to enhance the local search ability of the EABC algorithm, a local search method is performed to the best food source position of each new discovered food sources area src_g+1, denoted as ${CS}_{best}^{g + 1}$ . The flowchart of the introduced EABC is presented in Fig 4, while in the following subsections, we describe in details the encoding schema of CSs, generation of the initial food sources area src₀, the works of the three types of bees for searching good food sources areas, which are Employees work, Onlookers work and Scouts work, as well as the incorporated local search method and the ending criterion of the proposed EABC algorithm.

Fig. 4

The flowchart of EABC.

5.2.1 Encoding schema of food sources positions and generation of the initial food sources area

Here, in this study, an n-dimensional array of integers is used to represent each food source position ${CS}_{z}^{g}$ of the g^th food sources area src_g, where z = 1, 2, …, Z and Z is the number of food sources solutions, i.e., population size of EABC. The g^th food source position ${CS}_{z}^{g}$ of the solution CS_z, denoted as ${CS}_{z}^{g} = ({CS}_{z, 1}^{g}, {CS}_{z, 2}^{g}, \dots, {CS}_{z, n}^{g})$ , has n integer elements indicating the selected candidate wss from their skylines services SkS_i, i = 1, 2, …, n. For the initial food sources area src₀, each integer element of each food source position ${CS}_{z}^{0} = ({CS}_{z, 1}^{0}, {CS}_{z, 2}^{0}, \dots, {CS}_{z, n}^{0})$ was randomly generated as follows $\begin{matrix} \forall : i = 1, 2, \dots, n \\ {CS}_{z, i}^{0} = 1 + ⌈ rand (0, 1) * (m_{i} - 1) ⌉ \end{matrix}$ (7) Where ${CS}_{z, i}^{0}$ is an integer number representing the i^th selected ws from the i^th skyline service SkS_i that has m_i functionally equivalent wss, rand (0, 1) is a real number, which was randomly generated from the range [0, 1], and ⌈ ⌉ is the rounding up integer function.

5.2.2 Employees work

The employee bees explore each current food sources area src_g to find a new better one ${src}_{g}^{Emp}$ , where similar to the ABC’s conventional updating positions of food sources [14], only one dimension (i.e., a unique web service) of each food source position ${CS}_{z}^{g} = ({CS}_{z, 1}^{g}, {CS}_{z, 2}^{g}, \dots, {CS}_{z, j}^{g}, \dots, {CS}_{z, n}^{g})$ with n atomic web services is considered to update the ${CS}_{z}^{g}$ position of CS_z. Hence, the new food source position ${CS}_{z}^{Emp} = ({CS}_{z, 1}^{g}, {CS}_{z, 2}^{g}, \dots, {CS}_{z, j}^{Emp}, \dots,$ ${CS}_{z, n}^{g})$ has the same atomic web services as its old one ${CS}_{z}^{g}$ , except for the j^th web service (i.e., the ${CS}_{z, j}^{Emp}$ value), which is defined using the following Equation. ${CS}_{z, j}^{Emp} = ⌈ {CS}_{z, j}^{g} + φ_{j} * ({CS}_{z, j}^{g} - {CS}_{l, j}^{g}) ⌉$ (8) Where for each explored ${CS}_{z}^{g}$ , j is a randomly-selected dimension, i.e., the j^th skyline service SkS_j, from the range [1, n], ${CS}_{l}^{g}$ with l ≠ z represents a randomly-selected food source position from src_g, φ_j is a random generated real value within the range [- 1, 1] for every selected skyline service SkS_j and ⌈ ⌉ is the rounding up integer function. If the ${CS}_{z, j}^{Emp}$ value is out of the range [1,m j ] with m_j is the total number of the functionally equivalent wss of SkS_j, then the ${CS}_{z, j}^{Emp}$ value will be updated by the nearest one of the two bounds {1, m_j}.

After the definition of the new food sources positions ${CS}_{z}^{Emp}$ s with z = 1, 2, …, Z, their interval utility values, i.e., $IU ({CS}_{z}^{Emp})$ , are calculated using Equation 1. And finally, in order to update each old food source position ${CS}_{z}^{g}$ of CS_z by its new defined one ${CS}_{z}^{Emp}$ , the greedy selection mechanism of ABC [14] is adapted through using the following Deb’s solutions selection rules [8].

[R 1.] If ${CS}_{z}^{Emp}$ and ${CS}_{z}^{g}$ are feasible food sources positions, i.e., the user’s global QoS constraints as given in Equation 2 are satisfied, then:

[R 1.1.] If $IU ({CS}_{z}^{Emp}) >_{max} IU ({CS}_{z}^{g})$ then ${CS}_{z}^{Emp}$ is the new food source position of CS_z and its trial_z is reset to zero;

[R 1.2.] Otherwise, the old food source position ${CS}_{z}^{g}$ of CS_z is maintained and its trial_z is incremented by one.

[R 2.] If ${CS}_{z}^{Emp}$ is a feasible food source position and ${CS}_{z}^{g}$ is an infeasible one, then ${CS}_{z}^{Emp}$ is the new food source position of CS_z and its trial_z is reset to zero.

[R 3.] If ${CS}_{z}^{Emp}$ is an infeasible food source position and ${CS}_{z}^{g}$ is a feasible one, then the old food source position ${CS}_{z}^{g}$ of CS_z is maintained and its trial_z is incremented by one.

[R 4.] If ${CS}_{z}^{Emp}$ and ${CS}_{z}^{g}$ are infeasible food sources positions then:

[R 4.1.] If the normalized global constraint violation of CS_z by considering its new food source position ${CS}_{z}^{Emp}$ , as will be given by Equation 11 in the next paragraph, is larger than its one by considering its old food source position ${CS}_{z}^{g}$ , then ${CS}_{z}^{Emp}$ is the new food source position of CS_z and its trial_z is reset to zero;

[R 4.2.] Otherwise, the old food source position ${CS}_{z}^{g}$ of CS_z is maintained and its trial_z is incremented by one.

Normalized global constraint violation of an infeasible food source position Given any infeasible food source position, denoted by ICS, the constraint violation amounts of its violated user’s overall QoS requirements, denoted by ${ICS}_{q_{k}}^{cst}$ s, are evaluated as follows. $\begin{matrix} \forall q_{k} \in {QoS}^{+} : if {Cst}_{q_{k}} >_{max} {ICS}_{q_{k}} then \\ {ICS}_{q_{k}}^{cst} = {Cst}_{q_{k}} ⊖ {ICS}_{q_{k}} \end{matrix}$ (9) $\begin{matrix} \forall q_{k} \in {QoS}^{-} : if {Cst}_{q_{k}} <_{min} {ICS}_{q_{k}} then \\ {ICS}_{q_{k}}^{cst} = {ICS}_{q_{k}} ⊖ {Cst}_{q_{k}} \end{matrix}$ (10) By adapting the SAW method [20] to support the interval numbers’ calculations, the ${ICS}_{q_{k}}^{cst}$ s interval-values are aggregated into a single interval value ICS_cst through using the following equation. ${ICS}_{cst} = \frac{1}{V} \otimes \sum_{t = 1}^{k} \bar{{ICS}_{q_{t}}^{cst}}$ (11) Where V is the total number of the violated overall QoS constraints by ICS, $\bar{{ICS}_{q_{k}}^{cst}}$ is the normalized interval-valued of its associated original one ${ICS}_{q_{k}}^{cst} = [{ICS}_{q_{k}}^{l, cst}, {ICS}_{q_{k}}^{u, cst}]$ for the k^th violated user’s global QoS constraint ${Cst}_{q_{k}} = [{Cst}_{q_{k}}^{l}, {Cst}_{q_{k}}^{u}]$ . Since the lower ${ICS}_{q_{k}}^{cst}$ s are, the lower its global constraint violation amount is (i.e., in other words, the higher its aggregated normalized interval-valued ICS_cst is). Therefore, the lower and upper limit values of the interval-valued $\bar{{ICS}_{q_{k}}^{cst}} = [\bar{{ICS}_{q_{k}}^{l, cst}}, \bar{{ICS}_{q_{k}}^{u, cst}}]$ are calculated by using the interval negative normalization process as given in the following Equations 12 and 13, respectively. $\begin{matrix} \bar{{ICS}_{q_{k}}^{l, cst}} = {\begin{matrix} \frac{\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l} - {ICS}_{q_{k}}^{u, cst}}{(\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) - (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u})} & if (\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) \neq (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u}) \\ 1 & if (\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) = (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u}) \end{matrix} \end{matrix}$ (12) $\begin{matrix} \bar{{ICS}_{q_{k}}^{u, cst}} = {\begin{matrix} \frac{\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l} - {ICS}_{q_{k}}^{l, cst}}{(\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) - (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u})} & if (\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) \neq (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u}) \\ 1 & if (\max_{q_{k}}^{u} - {Cst}_{q_{k}}^{l}) = (\min_{q_{k}}^{l} - {Cst}_{q_{k}}^{u}) \end{matrix} \end{matrix}$ (13) Where $\max_{q_{k}}^{u}$ and $\min_{q_{k}}^{l}$ have been previously defined in Equations 5 and 6, respectively.

5.2.3 Onlookers work

The onlooker bees select Z food sources positions from the discovered ones by the employee bees, i.e., ${src}_{g}^{Emp}$ , to be explored again. In the basic ABC algorithm, the selection criterion of the Z food sources positions is based on the roulette wheel selection [14]. However, the latter has the local optima stagnation problem [26]. Therefore, in our study, the binary tournament selection method [19] is employed to define the new selected food sources positions, denoted by ${src}_{g}^{Sel}$ . The same Deb’s solutions selection rules as given in the above subsection is used to define ${src}_{g}^{Sel}$ by repeating this selection procedure Z times for each two randomly-selected food sources positions from ${src}_{g}^{Emp}$ .

Again, ${src}_{g}^{Sel}$ is explored to find a new food sources area ${src}_{g}^{Onl}$ through using the same updating formula of food sources positions, as given in Equation 8, where the aforesaid Deb’s solutions selection rules, which are itemized in the Employees work Subsection, are used to update the explored food sources positions ${src}_{g}^{Sel}$ by its new discovered ones ${src}_{g}^{Onl}$ .

5.2.4 Scouts work

Like the scouts work of the basic ABC algorithm, here, the scout bees of EABC are used to update one randomly-selected food source position from the discovered ones by the onlooker bees, i.e., ${src}_{g}^{Onl}$ , that have not updated theirs positions after limit iterations, where the limit parameter of EABC indicates the criterion to identify an abandoned food source position. The latter is updated using Equation 7 and its associated trial variable is reinitialized to zero. As result, by performing the above works of Employee, Onlooker and Scout bees, a new food sources area src_g+1 is discovered to replace the old one src_g.

5.2.5 Local search method

In order to enhance the quality of the final best CS solution (CS_best). Therefore, for each new discovered food sources area src_g+1, a local search method is applied for its best food source position, represented by ${CS}_{best}^{g + 1} = ({CS}_{best, 1}^{g + 1}, {CS}_{best, 2}^{g + 1}, \dots, {CS}_{best, n}^{g + 1})$ , where n indicates the number of its skylines services and ${CS}_{best, i}^{g + 1}$ with i ≤ n represents the subscript value of the i^th selected web service from its associated skyline services SkS_i. The following steps describe the incorporated local search method to the EABC algorithm.

[Step 1.] Select randomly an integer number j from the set {1, 2, …, n} that represents the selected skyline service SkS_j form the n existing ones.

[Step 2.] Generate L different new food source positions ${CS}_{best, l}^{g + 1}$ with l ∈ {1, 2, …, L} from ${CS}_{best}^{g + 1}$ , where each ${CS}_{best, l}^{g + 1}$ is created with the same atomic web services of ${CS}_{best}^{g + 1}$ except for its j^th web service, which has been randomly selected from its related SkS_j.

[Step 3.] Evaluate the interval utility values of the generated ${CS}_{best, l}^{g + 1}$ s, as given in Equation 1, and determine the best one among the new generated ${CS}_{best, l}^{g + 1}$ s and ${CS}_{best}^{g + 1}$ to update the food source position of CS_best by the determined one.

5.2.6 Ending criterion of EABC

The aforesaid works of Employee, Onlooker and Scout bees as well as the incorporated local search method are repeated for each new discovered food sources area until the stopping criterion of the EABC algorithm is satisfied, i.e., the maximum iteration number MITR is reached. The best feasible food source position among the ones of the last discovered food sources area that has the highest interval utility value is the final near-optimal CS solution in solving IQSC by EABC.

6 Experiments

In order to validate the effectiveness of our proposed approach, we have used two comparison metrics: (a) Running time and (b) Optimality. The first one indicates the needed computation time by each performed algorithm to find out its near-optimal solutions in solving the IQSC problem. Whereas, the second one shows the quality of these obtained solutions in terms of their interval utility values as defined in Equation 1.

6.1 Interval version of the public QWS dataset

In the comparison experiments, as the public QWS dataset [1] was published with 2507 atomic web services, where each web service has 09 non-ambiguous QoS values for 09 QoS properties including (1) Response Time, (2) Availability, (3) Throughput, (4) Successability, (5) Reliability, (6) Compliance, (7) Best Practices, (8) Latency and (9) Documentation. Therefore, an interval version of QWS, denoted by IQWS, is provided to be used in our experiments, where the QoS interval values of IQWS are generated via multiplying the precise QoS values of each considered QoS parameter of QWS by the random interval number [r₁, r₂] with r₁ = 0.9 + 0.1 * rand (0, 1), r₂ = 1.0 + 0.1 * rand (0, 1), and rand (0, 1) is a uniformly distributed random real number in the range [0, 1]. Since the QWS dataset dos not contain the web service price parameter, and as we said previously, only the availability (q₁), throughput (q₂), response time (q₃) and service price (q₄) attributes are considered to generate the IQWS dataset. Hence, the interval values of the IQSW’s web services in the price attribute have been randomly generated by r3 ⊗ [r₁, r₂] with r3 is a random generated real number from the range [2, 5]$. Moreover, the importance and priorities of the four considered QoS attributes were set to the same value, i.e, $\forall t \in {1, 2, 3, 4}, w_{q_{t}} = \frac{1}{4}$ , and each considered user’s global QoS requirement Cst_{q
_t} for the q_t attribute was set as given in the following Equation. $\begin{matrix} {Cst}_{q_{t}} = \\ [max (r_{1} * {SU}_{q_{t}}, \min_{q_{t}}^{l}), min (r_{2} * {SU}_{q_{t}}, \max_{q_{t}}^{u})] \\ With {SU}_{q_{t}} = \\ {\begin{matrix} μ_{q_{t}} * (\max_{q_{t}}^{u} - \min_{q_{t}}^{l}) + \min_{q_{t}}^{l} if q_{t} \in {QoS}^{+} \\ \max_{q_{t}}^{u} - μ_{q_{t}} * (\max_{q_{t}}^{u} - \min_{q_{t}}^{l}) if q_{t} \in {QoS}^{-} \end{matrix} \end{matrix}$ (14) Where μ_{q
_t} ∈ [0, 1] is a severity factor, which is used to adjust the considered user’s global QoS constraint Cst_{q
_t}, and $\max_{q_{t}}^{u}$ and $\min_{q_{t}}^{l}$ are calculated as given by Equations 5 and 6, respectively.

Here, only two global QoS constraints Cst_{q
₃} and Cst_{q
₄} of the response time and price attributes are considered in solving IQSC by setting their severity factors μ_{q
₃} and μ_{q
₄} to 0.3 and 0.2, respectively, whereas, μ_{q
₁} and μ_{q
₂} of the availability and throughput properties are set to the zero values.

6.2 Parameters setting of the compared algorithms

To investigate the performance and the efficiency of our proposed EABC, we have compared it to the one we obtained using the PSO algorithm with skyline operator [24], the proposed Discrete Gbest-guided Artificial Bee Colony (DGABC) approach in [11] and the improved Harris Hawks Optimization (HHO) algorithm by a developed Elite Evolutionary Strategy (EES) in [16] that has been named by its authors EESHHO. The compared approaches to ours (i.e., PSO, DGABC and EESHHO) were proposed to solve the QSC problem with non-ambiguous QoS parameters. Hence, we have adapted these approaches to support interval utility calculations of solutions as defined in Equation 1. To simplify things, the interval extended versions of the PSO-based approach [24], the DGABC [11] and the EESHHO [16] algorithms are named IPSO, IDGABC and IEESHHO, respectively. For the parameters setting of the compared algorithms, EABC, IPSO, IDGABC and IEESHHO share the same population size (Z = 40) and the same stopping criterion, which is the number of solutions evaluations that was set to 50000. However, for their appropriate parameters, the inertia weight (w) and the two accelerating coefficients (c₁ and c₂) of IPSO were set to w = 0.8 and c₁ = c₂ = 2.0, as they were recommended in their related reference [24]. The limit parameter for both EABC and IDGABC, which indicates the criterion to identify an abandoned food source position, was set to 80. Whereas, the L parameter of our EABC that represents the number of neighbor food source positions of the best solution in the EABC’s local search method was set to 3. Moreover, the control parameters E and sp of IEESHHO, which are used to switch between the exploration and exploitation phases, and controls the proportion of the best parental genes in EES, respectively, were set by Equations 15 and 16 as designed by the authors of EESHHO [16]. $sp = rand (- 1, 1) \times (1 - \frac{t}{T})$ (15) $E = 2 E_{0} \times (1 - \frac{t}{T})$ (16) Where t and T are respectively the current and the maximum number of the IEESHHO’s iterations cycles, rand (-1, 1) and E₀ are random generated numbers between -1 and 1 with E₀ is updated by each agent (solution) for each population evolution.

The aforementioned algorithms are performed to solve five abstract composite services ${ACS}_{n}^{m}$ s, with (n, m) ∈ {(5, 501) , (10, 250) , (15, 167) , (20, 125),(25, 100)}, where each ${ACS}_{n}^{m}$ consists of solving IQSC with n web services classes per m functionally equivalent web services that have been randomly selected from the 2507 ones of IQWS. The compared algorithms are implemented with Matlab R2016b, and performed on the same personnel computer, which runs Windows 7 and has an Intel(R) Core(TM) i5-4570, CPU 3.20 GHz and 4 Go of memory as a hardware configuration. For each ${ACS}_{n}^{m}$ , the compared EABC, IPSO, IDGABC and IEESHHO are carried out 30 independent times to define the best, worst and average optimality values, and average running times of their obtained near-optimal solutions.

6.3 Comparison results discussion

For each solved ${ACS}_{n}^{m}$ , the best, worst and average interval utility values of the obtained near-optimal solutions by the compared algorithms have been written down in Tables 3, 4 and 5, respectively. As we can show from the results of solving the five ${ACS}_{n}^{m}$ s listed in these Tables that our proposed EABC reach very higher interval optimality values compared to the ones of its compared approaches. Furthermore, as seen in Table 6, listing the interval variances (IVs), as calculated by Equation 17 of the compared algorithms in solving each ${ACS}_{n}^{m}$ over the 30 independent running times, and which EABC and IDGABC have obtained two optimal IVs in solving the five ${ACS}_{n}^{m}$ s, IPSO has obtained one optimal IVs in solving the five ${ACS}_{n}^{m}$ s. Whereas, the IEESHHO algorithm has not obtained any optimal IV for the five solved ${ACS}_{n}^{m}$ s. Moreover, the average IVs for the five solved ${ACS}_{n}^{m}$ s of the EABC algorithm is better than the ones of the other compared algorithms. Therefore, EABC has better stability than IDGABC, IPSO and IEESHHO. $IV = \frac{1}{30} \otimes \sum_{i = 1}^{30} ({IU}_{best}^{i} ⊖ \bar{IU}) \otimes ({IU}_{best}^{i} ⊖ \bar{IU})$ (17) Where ${IU}_{best}^{i}$ is the i^th interval utility value of the i^th obtained near-optimal solution by a compared algorithm, $\bar{IU} = \sum_{i = 1}^{30} {IU}_{best}^{i}$ is the average interval-valued of the all obtained near-optimal solutions.

Table 3

Comparison results of the best interval utility values of the obtained near-optimal solutions by the compared approaches in solving each ${ACS}_{n}^{m}$ of IQSC with n web services classes per m functionally equivalent web services

${ACS}_{n}^{m}$	EABC	IPSO	IDGABC	IEESHHO
${ACS}_{5}^{501}$	[0.7075,0.8234]	[0.6849,0.7894]	[0.6825,0.8080]	[0.7156,0.8037]
${ACS}_{10}^{250}$	[0.6240,0.7140]	[0.5690,0.7051]	[0.5843,0.7102]	[0.5980,0.7006]
${ACS}_{15}^{167}$	[0.5603,0.7116]	[0.5079,0.6015]	[0.5482,0.6935]	[0.5440,0.6412]
${ACS}_{20}^{125}$	[0.5305,0.6839]	[0.4753,0.5477]	[0.5126,0.6454]	[0.4898,0.5664]
${ACS}_{25}^{100}$	[0.5141,0.6239]	[0.4813,0.5208]	[0.5231,0.5624]	[0.5107,0.5396]

The best interval utility values are in boldface.

Table 4

Comparison results of the worst interval utility values of the obtained near-optimal solutions by the compared approaches in solving each ${ACS}_{n}^{m}$ of IQSC with n web services classes per m functionally equivalent web services

${ACS}_{n}^{m}$	EABC	IPSO	IDGABC	IEESHHO
${ACS}_{5}^{501}$	[0.6936,0.8024]	[0.6337,0.7443]	[0.6623,0.7615]	[0.6474,0.7584]
${ACS}_{10}^{250}$	[0.5826,0.7303]	[0.5296,0.6487]	[0.5705,0.6793]	[0.5377,0.6227]
${ACS}_{15}^{167}$	[0.5407,0.7106]	[0.4616,0.5295]	[0.5413,0.6421]	[0.4825,0.5924]
${ACS}_{20}^{125}$	[0.5273,0.6529]	[0.4605,0.5002]	[0.4929,0.6003]	[0.4573,0.5059]
${ACS}_{25}^{100}$	[0.5122,0.5839]	[0.4430,0.4631]	[0.5016,0.5247]	[0.4579,0.4840]

The best interval utility values are in boldface.

Table 5

Comparison results of the average interval utility values of the obtained near-optimal solutions by the compared approaches in solving each ${ACS}_{n}^{m}$ of IQSC with n web services classes per m functionally equivalent web services

${ACS}_{n}^{m}$	EABC	IPSO	IDGABC	IEESHHO
${ACS}_{5}^{501}$	[0.7039,0.8164]	[0.6742,0.7711]	[0.6742,0.7885]	[0.6769,0.7829]
${ACS}_{10}^{250}$	[0.5924,0.7366]	[0.5626,0.6691]	[0.5727,0.7022]	[0.5646,0.6631]
${ACS}_{15}^{167}$	[0.5545,0.7102]	[0.4949,0.5718]	[0.5422,0.6714]	[0.5133,0.6015]
${ACS}_{20}^{125}$	[0.5279,0.6722]	[0.4566,0.5287]	[0.5028,0.6177]	[0.4636,0.5442]
${ACS}_{25}^{100}$	[0.5245,0.5947]	[0.4640,0.4940]	[0.5091,0.5447]	[0.4893,0.5212]

The best interval utility values are in boldface.

Table 6

Comparison results of the interval variances of the obtained near-optimal solutions by the compared approaches in solving each ${ACS}_{n}^{m}$ of IQSC with n web services classes per m functionally equivalent web services

${ACS}_{n}^{m}$	EABC	IPSO	IDGABC	IEESHHO
${ACS}_{5}^{501}$	[-0.0130,0.0149]	[-0.0096,0.0116]	[-0.0135,0.0153]	[-0.0115,0.0136]
${ACS}_{10}^{250}$	[-0.0216,0.0221]	[-0.0117,0.0136]	[-0.0174,0.0190]	[-0.0100,0.0120]
${ACS}_{15}^{167}$	[-0.0251,0.0259]	[-0.0060,0.0079]	[-0.0173,0.0189]	[-0.0080,0.0100]
${ACS}_{20}^{125}$	[-0.0215,0.0227]	[-0.0055,0.0066]	[-0.0137,0.0151]	[-0.0067,0.0085]
${ACS}_{25}^{100}$	[-0.0052,0.0060]	[-0.0008,0.0017]	[-0.0013,0.0019]	[-0.0009,0,0019]
Average	[-0.0173 0.0183]	[-0.0067 0.0083]	[-0.0126 0.0140]	[-0.0074 0.0092]

The best interval variances are in boldface.

In addition, as we can see from Fig. 5, which plots the average running times of the compared approaches to get their near-optimal solutions in solving the listed ${ACS}_{n}^{m}$ s in Table 6 over the 30 independent executions when the number of web services classes n was set with small values, i.e., n ≤ 5, the average running times of IPSO are slightly better than the ones of EABC. However, when n was set with medium or large values, n ≥ 10, our proposed EABC algorithm obtained near-optimal solutions with less average running times compared to the ones of IPSO. Besides, for all the solved ${ACS}_{n}^{m}$ s, EABC is very faster than IEESHHO and slightly better than IDGABC in terms of computation time.

Fig. 5

The average running times of the compared algorithms in solving the ${ACS}_{n}^{m}$ s of n web services classes per m functionally equivalent web services (for colors, see online version).

From this discussion, EABC outperforms the compared IPSO, IDGABC and IEESHHO algorithms in terms of final CS solutions optimality as-well-as efficiency, especially in solving users’ requests that need the composition of an important number of elementary web services.

6.4 Effectiveness of the local search method

In this subsection, to investigate the feasibility of the employed local search method (see Subscetion 5.2.5), the aforementioned ${ACS}_{n}^{m}$ s of Table 6 have been solved by the EABC algorithm without the local search method (i.e., the basic ABC algorithm) over 30 independent executions where its obtained results are compared to the obtained ones by the developed EABC. As shown in Table 7 that illustrates the obtained results by EABC and ABC algorithms, it is obvious that the best, worst and average interval utility values of the obtained near-optimal solutions by EABC, as listed previously in Tables 3, 4 and 5, are better than the ones of the basic ABC algorithm. Moreover, for comparing the convergence of EABC to that of the basic ABC algorithm, Fig. 6 plots the average mid-points 5 of the interval utility values of the obtained near-optimal solutions of both EABC and ABC in solving the ${ACS}_{20}^{125}$ instance over 30 independent running times. In this experiment, the stopping criterion of each compared algorithm is set to 15 seconds. It is clear from this figure that EABC gives out a better convergence rate compared to the basic ABC algorithm. Therefore, by integrating the proposed local search method into EABC, its convergence to get near-optimal solutions with high quality is improved.

Table 7
Comparison results of the best, worst and average interval utility values of the obtained near-optimal CSs solutions by the EABC and the basic ABC algorithms in solving each ${ACS}_{n}^{m}$ of IQSC with n web services classes per m functionally equivalent web services

${ACS}_{n}^{m}$ EABC Basic ABC

Best Worst Average Best Worst Average

${ACS}_{5}^{501}$ [0.7075,0.8234] [0.6936,0.8024] [0.7039,0.8164] [0.7075,0.8234] [0.7043,0.7777] [0.7000,0.8049]

${ACS}_{10}^{250}$ [0.6240,0.7140] [0.5826,0.7303] [0.5924,0.7366] [0.6109,0.7219] [0.5788,0.7265] [0.5885,0.7317]

${ACS}_{15}^{167}$ [0.5603,0.7116] [0.5407,0.7106] [0.5545,0.7102] [0.5518,0.7137] [0.5340,0.7069] [0.5512,0.7028]

${ACS}_{20}^{125}$ [0.5305,0.6839] [0.5273,0.6529] [0.5279,0.6722] [0.5294,0.6662] [0.4998,0.6539] [0.5143,0.6583]

${ACS}_{25}^{100}$ [0.5141,0.6239] [0.5122,0.5839] [0.5245,0.5947] [0.5183,0.5956] [0.51389,0.5556] [0.5181,0.5757]

${ACS}_{n}^{m}$	EABC	Basic ABC
${ACS}_{5}^{501}$	[0.7075,0.8234]	[0.6936,0.8024]	[0.7039,0.8164]	[0.7075,0.8234]	[0.7043,0.7777]	[0.7000,0.8049]
${ACS}_{10}^{250}$	[0.6240,0.7140]	[0.5826,0.7303]	[0.5924,0.7366]	[0.6109,0.7219]	[0.5788,0.7265]	[0.5885,0.7317]
${ACS}_{15}^{167}$	[0.5603,0.7116]	[0.5407,0.7106]	[0.5545,0.7102]	[0.5518,0.7137]	[0.5340,0.7069]	[0.5512,0.7028]
${ACS}_{20}^{125}$	[0.5305,0.6839]	[0.5273,0.6529]	[0.5279,0.6722]	[0.5294,0.6662]	[0.4998,0.6539]	[0.5143,0.6583]
${ACS}_{25}^{100}$	[0.5141,0.6239]	[0.5122,0.5839]	[0.5245,0.5947]	[0.5183,0.5956]	[0.51389,0.5556]	[0.5181,0.5757]

The best interval utility values are in boldface.

Fig. 6

The convergence of the EABC and the basic ABC algorithms to find-out their near optimal solutions in solving ${ACS}_{20}^{125}$ over 30 independent running times (for colors, see online version).

7 Conclusion and future works

In this study, the interval number, which is a simple and general uncertain model, is used to represent the ambiguity of the QoS values in solving the QoS uncertainty-aware web service composition problem. The latter is modeled as an interval constrained single-objective optimization (IQSC) model, while a new approach that combines two components: skyline operator and an extended artificial bee colony algorithm with a local search method (EABC), is introduced to address the formulated IQSC. The first component (skyline operator) is used to reduce the search space of IQSC by pruning the redundant and dominated web services from their sets of functionally equivalent ones. Whereas, the second component (EABC) is performed to find out more effectively and more efficiently, in a reduced search space, the near-optimal composite service of IQSC. The experimental results, which have been performed on an interval extended version of the public QWS dataset, of comparing our proposed approach to an existing skyline-based PSO, an efficient discrete gbest-guided artificial bee colony and a recently provided Harris Hawks optimization with an elite evolutionary strategy algorithms, demonstrate and validate the performance and the efficiency of our introduced approach.

In the IQSC mathematical model of this study, the well-known simple additive weighting method has been adapted to aggregate the multiple interval QoS values of composite services (i.e. multiple objective functions) into a single interval-valued (i.e. single objective function). Hence, the development of an efficient interval multi-objective version of the introduced ABC-based approach and evaluating it in real scenarios will be considered in future works. Moreover, we are planning to solve the QoS uncertainty-aware web service composition problem for the Internet of Things, and Cloud and Fog computing environments that consider more specialized QoS parameters under context-aware information such as geographical location of both users and provided web services.

Footnotes

For an ACS of n web services classes, where each one has m candidate web services, then mⁿ different CSs can be obtained.

A mid-point (i.e., center) of an interval number A = [a^l, a^u], which represents its performance, is calculated as (a^l + a^u)/2 [].

References

Al-Masri

and Mahmoud

Q.H.

, Investigating web services on the world wide web, In Proceedings of the 17th international conference on World Wide Web, pages 795–804. ACM, (2008).

Alrifai

, Skoutas

and Risse

, Selecting skyline services for qos-based web service composition, In Proceedings of the 19th international conference onWorld wide web, pages 11–20, (2010).

Alrifai

, Risse

and Nejdl

, A hybrid approach for efficient web service composition with endto-end qos constraints, ACM Transactions on the Web (TWEB) 6(2) (2012), 7.

Ardagna

and Pernici

, Adaptive service composition in flexible processes, IEEE Transactions on software engineering 33(6) (2007), 369–384.

Bhunia

A.K.

and Samanta

S.S.

, A study of interval metric and its application in multi-objective optimization with interval objectives, Computers & Industrial Engineering 74 (2014), 169–178.

Borzsony

, Kossmann

and Stocker

, The skyline operator. In Proceedings 17th international conference on data engineering, pages 421–430. IEEE, (2001).

Canfora

, Di Penta

, Esposito

and Villani

M.L.

, An approach for qos-aware service composition based on genetic algorithms, In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 1069–1075. ACM, (2005).

Deb

, An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering 186(2–4) (2000), 311–338.

Deb

, Pratap

, Agarwal

and Meyarivan

, A fast and elitist multiobjective genetic algorithm: Nsga-ii,182–197, IEEE transactions on evolutionary computation 6(2) (2002).

10.

Gay

D.M.

, The ampl modeling language: An aid to formulating and solving optimization problems, In Numerical analysis and optimization, pages 95–116. Springer, (2015).

11.

Huo

, Zhuang

, Gu

, Ni

and Xue

, Discrete gbest-guided artificial bee colony algorithm for cloud service composition, Applied Intelligence 42(4) (2015), 661–678.

12.

Jatoth

, Gangadharan

G.R.

and Buyya

, Computational intelligence based qos-aware web service composition: A systematic literature review, IEEE Transactions on Services Computing 10(3) (2017), 475–492. doi: 0.1109/TSC.2015.2473840

13.

Jian

, Zhu

and Xia

, An interval-based fuzzy ranking approach for qos uncertainty-aware service composition, Optik-International Journal for Light and Electron Optics 127(4) (2016), 2102–2110.

14.

Karaboga

and Basturk

, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (abc) algorithm, Journal of Global Optimization 39(3) (2007), 459–471.

15.

Karmakar

and Bhunia

A.K.

, A comparative study of different order relations of intervals, Reliable Computing 16(2) (2012), 38–72.

16.

C.Y.

, Li

, Chen

H.L.

and Heidari

A.A.

, Memetic harris hawks optimization: Developments and perspectives on project scheduling and qos-aware web service composition, Expert Systems with Applications 171 (2021), 114529.

17.

Liao

, Liu

, Zhu

and Wang

, Accurate sub-swarms particle swarm optimization algorithm for service composition, Journal of Systems and Software 90 (2014), 191–203.

18.

Mahato

S.K.

and Bhunia

A.K.

, Interval-arithmetic-oriented interval computing technique for global optimization, Applied Mathematics Research Express 2006 (2006).

19.

Miller

B.L.

, Goldberg

D.E.

, et al., Genetic algorithms, tournament selection, and the effects of noise, Complex Systems 9(3) (1995), 193–212.

20.

Rao

R.V.

, Introduction to multiple attribute decisionmaking (madm) methods, Decision Making in the Manufacturing Environment: Using Graph Theory and Fuzzy Multiple Attribute Decision Making Methods, pages 27–41, (2007).

21.

Razian

, Fathian

and Buyya

, Arc: Anomaly-aware robust cloud-integrated iot service composition based on uncertainty in advertised quality of service values, Journal of Systems and Software 164 (2020), 110557.

22.

Seghir

, Fdmoabc: fuzzy discrete multi-objective artificial bee colony approach for solving the non-deterministic qosdriven web service composition problem, Expert Systems with Applications 167 (2021), 114413.

23.

Seghir

, Khababa

and Semchedine

, An interval-based multi-objective artificial bee colony algorithm for solving the web service composition under uncertain qos, The Journal of Supercomputing (2019). doi: https://doi.org/10.1007/s11227-019-02814-9.

24.

Wang

, Sun

, Zou

and Yang

, Particle swarm optimization with skyline operator for fast cloud-based web service composition, Mobile Networks and Applications 18(1) (2013), 116–121.

25.

wang

, Xu

, Sheng

Q.Z.

, Wang

and Yao

, Novel artificial bee colony algorithms for qos-aware service selection, IEEE Transactions on Services Computing 12(2) (2019), 247–261. doi: 10.1109/TSC.2016.2612663

26.

Xiang

W.-L.

and An

M.-Q.

, An efficient and robust artificial bee colony algorithm for numerical optimization, Computers & Operations Research 40(5) (2013), 1256–1265.

27.

, Guo

, Zhang

, Hu

, Wang

and Pei

, Qos-aware service composition using fuzzy set theory and genetic algorithm, Wireless Personal Communications 102(2) (2018), 1009–1028.

28.

Ying

and Jiande

, A nonlinear service composition method based on the skyline operator, Journal of Systems Engineering and Electronics 31(4) (2020), 743–750.

29.

Zeng

, Benatallah

, Ngu

A.H.H.

, Dumas

, Kalagnanam

and Chang

, Qos-aware middleware for web services composition, IEEE Transactions on software engineering 30(5) (2004), 311–327.

30.

Zheng

, Yang

and Zhao

, Probabilistic qos aggregations for service composition, ACM Transactions on the Web (TWEB) 10(2) (2016), 12.