# GAP2WSS: A Genetic Algorithm based on the Pareto Principle for Web Service
Selection

SayedHassan Khatoonabadi, Shahriar Lotfi, and Ayaz Isazadeh The authors are
with the Department of Computer Science, Faculty of Mathematical Sciences,
University of Tabriz, Tabriz, Iran. Email<EMAIL_ADDRESS>{shahriar_lotfi<EMAIL_ADDRESS>
###### Abstract

Despite all the progress in Web service selection, the need for an approach
with a better optimality and performance still remains. This paper presents a
genetic algorithm by adopting the Pareto principle that is called GAP2WSS for
selecting a Web service for each task of a composite Web service from a pool
of candidate Web services. In contrast to the existing approaches, all global
QoS constraints, interservice constraints, and transactional constraints are
considered simultaneously. At first, all candidate Web services are scored and
ranked per each task using the proposed mechanism. Then, the top 20 percent of
the candidate Web services of each task are considered as the candidate Web
services of the corresponding task to reduce the problem search space.
Finally, the Web service selection problem is solved by focusing only on these
20 percent candidate Web services of each task using a genetic algorithm.
Empirical studies demonstrate this approach leads to a higher efficiency and
efficacy as compared with the case that all the candidate Web services are
considered in solving the problem.

###### Index Terms:

M.2.0.b Science of service composition, M.4.0.f Quality of service, M.5.2.g.1
Composition, M.10.0.a Business process modeling and management

##  1 Introduction

AWeb service is an enabling technology for realization of service-oriented
architecture [1] and service-oriented computing [2] paradigms. It provides a
platform-independent framework by means of XML [3] standards, which enables
services to be delivered over the Internet. Formally, a Web service [4] is
defined as a software system which supports interoperable machine-to-machine
interactions over a network, and has an interface described in a machine-
processable format (e.g., WSDL [5]). Meanwhile, interactions with a Web
service are carried out by SOAP-messages [6, 7, 8, 9] as described in its
WSDL.

Service providers develop different Web services and release them in service
registries (e.g., UDDI [10]). The service registries maintain technical
details of the Web services and information of their corresponding service
provider, such as address and contact. Service consumers retrieve and utilize
those information from the registry to make use of their demanded Web
services.

In most cases, a sole Web service provides a limited functionality which is
not adequate to accomplish sophisticated tasks. For reasons like cost, time,
and ease of implementation, many prefer to concentrate on their own core task,
and outsource other tasks through reusing existing Web services. The process
of seamless, flexible, and loosely-coupled integration of various Web services
to fulfill a complex task is called Web service composition, and the resultant
value-added Web service is called a composite Web service. A concrete example
of a composite Web service is a travel planner comprised of a flight booking,
a hotel booking, and a car rental Web service.

###  1.1 Quality of Service (QoS)

QoS, as the name suggests, defines the quality of a Web service, and includes
its quantitative non-functional properties. This can consist of generic as
well as application-specific attributes. In other words, QoS provides a way to
distinguish between Web services with the same functionality.

The W3C defined a number of generic QoS attributes in [11]. In addition, Al-
Masri and Mahmoud [12, 13, 14] provided the QWS dataset
(www.uoguelph.ca/~qmahmoud/qws/) which contains the measured values of nine
QoS attributes for over 2500 actual Web services. A formal definition of these
QoS attributes is presented below:

  * •

Response Time: is defined as the time taken to send a request to a Web service
and receive a response from it, expressed in milliseconds.

  * •

Availability: is defined as the ratio of the number of successful invocations
to the total number of invocations in a Web service, expressed in percentage.

  * •

Throughput: is defined as the total number of invocations per second in a Web
service, expressed as invokes/second.

  * •

Successability: is defined as the ratio of the number of responses to the
number of requests in a Web service, expressed in percentage.

  * •

Reliability: is defined as the ratio of the number of successful messages to
the total number of messages in a Web service, expressed in percentage.

  * •

Compliance: is defined as the extent to which a Web service’s WSDL follows
WSDL Specification [5], expressed in percentage.

  * •

Best Practices: is defined as the extent to which a Web service follows WS-I
Basic Profile [15], expressed in percentage.

  * •

Latency: is defined as the time taken for a Web service to process a request,
expressed in milliseconds.

  * •

Documentation: is defined as the extent to which a Web service is documented
in its WSDL by description tags, expressed in percentage.

Different functionally equivalent Web services provide different trade-offs
between the QoS attributes. In other words, a Web service may be superior to
some other Web services in terms of some QoS attributes, but may not be as
good as them in terms of some other QoS attributes. Accordingly, QoS plays a
significant role in Web service composition.

###  1.2 The Web Service Selection Problem

Given a composition request described in a workflow language (e.g., BPEL [16],
YAWL [17]), the discovery engine searches the registry to detect functional
matching Web services for each task of the workflow using Web service
descriptions. As a result, a set of functionally equivalent candidate Web
services with different QoS values is acquired per each task. The objective of
the Web service selection problem is to select one candidate Web service from
each set, such that the QoS values of the yielded composite Web service become
the best along all the possible combinations, while all the specified
constraints are satisfied. This is also known as the QoS-aware Web service
composition problem in the literature. A conceptual overview of the problem is
shown in Fig. 1.

Figure 1: A conceptual overview of the Web service selection problem

The Web service selection is a highly complicated and challenging problem. On
the one hand, a composite Web service may be comprised of many tasks, and on
the other hand, the number of available candidate Web services for each task
is increasing. According to [12], there has been more than 130 percent growth
in the number of available candidate Web services in the period between
October 2006 to October 2007. In addition, with the spread of cloud computing
[18], a sharp increase in the number of available candidate Web services is
extremely anticipated.

The Web service selection can be modeled as a multidimensional multiple-choice
knapsack problem [19] which is known to be NP-hard [20] in the strong sense.
In a multidimensional multiple-choice knapsack problem, different groups of
items exist, where each item has a certain value. Groups, items, and the value
of each item in this problem corresponds to tasks, candidate Web services, and
the utility value of each candidate Web service in the Web service selection
problem, respectively. Let $n$, $m$ represent the number of tasks and the
number of candidate Web services for each task, respectively. Then, $m^{n}$
distinct combinations of them exist. Therefore, with the growth of problem
size, the computational complexity increases exponentially. Combined with the
constraints, the problem becomes even more complicated.

The significance of the Web service selection problem originates from two
points. Firstly, since the QoS values of a composite Web service strongly
depend on the QoS values of the Web services which comprise it, the efficacy
of the applied approach is of high importance. Secondly, the efficiency of the
applied approach is crucial in real-time applications.

Consequently, an ideal approach to solving the Web service selection problem
shall

  1. 1.

require the minimum possible time to obtain the solution,

  2. 2.

obtain the best possible QoS values for the solution, and

  3. 3.

consider all the required constraints to obtain the solution.

Unfortunately, the performance and the optimality of the approach are in
contrast practically. This means that obtaining the best solution in the
minimum time is virtually impossible. Hereupon, the importance of performance
and optimality totally depends on the application. For instance, some may
prefer performance over optimality and some may prefer otherwise. Intuitively,
it can be inferred that what matters generally is not the performance or the
optimality of the approach separately, but is a reasonable balance between
them.

In addition to the performance and the optimality, an approach should also
consider all the required constraints to enlarge its applicability. This means
that the more constraints considered, the more usability the approach will
have in real and enterprise applications.

It should be noted that in cases which concern is only taken to the optimality
of the solution, exact approaches such as integer linear programming [21, 22,
23] and exhaustive search which obtain the optimal solution can be used.
However, these approaches are not scalable and may face an ultra-high
computational time with respect to the huge number of tasks and candidate Web
services. In addition, other approaches such as [24, 25, 26, 27] are proposed
to increase the scalability which obtain the near-optimal solution. Still,
these approaches are not sufficiently scalable.

###  1.3 Contribution of the Paper

The main contributions of this paper are stated as follows:

  * •

Formulated the Web service selection problem by considering global QoS
constraints, interservice constraints, and transactional constraints.

  * •

Proposed a more efficient and effective approach for solving the Web service
selection problem using the Pareto principle and genetic algorithm.

  * •

Designed a fitness function to support global QoS constraints, interservice
constraints, and transactional constraints in genetic algorithm.

  * •

Designed a mechanism to score and rank candidate Web services of different
tasks to utilize the Pareto principle.

###  1.4 Paper Outline

The rest of the paper is organized as follows. The next section presents a
brief survey of the previous works. Section 3 formulates the Web service
selection problem. Section 4 elaborates GAP2WSS in details. Section 5 presents
the experimental evaluations. Finally, section 6 concludes the paper and puts
forward some future topics of research.

##  2 Related Work

The Web service selection problem is a non-trivial popular research topic
which has received the attention of many researchers for over a decade. There
are two general approaches for the Web service selection problem: evolutionary
and non-evolutionary approaches. Typically, evolutionary approaches have
higher efficiency and lower efficacy than non-evolutionary approaches. In the
following, a brief survey of the previous works is presented.

Figure 2: The workflow of a composite Web service

###  2.1 Evolutionary Approaches

Ai and Tang [28, 29, 30] considered interservice constraints and utilized
genetic algorithm [31] to obtain a near-optimal solution. They encoded each
solution as an integer vector. In [28], a penalty mechanism is used to
penalize solutions which violate the constraints based on the degree of
violation. In [29], a hill climbing repair mechanism is used to fix solutions
which violate the constraints. In [30], a hybrid mechanism is used which
penalizes solutions that violate the constraints based on the degree of
violation, and optimizes all the solutions using a local optimizer. In [28,
29], a single-point crossover and in [30], a knowledge-based crossover is
used. All of them used a random mutation operator which replaces a randomly
selected candidate Web service with another random candidate Web service for
the corresponding task.

Lotfi and Mowlani [32] utilized imperialist competitive algorithm [33] to
obtain a near-optimal solution. Each solution is encoded as an integer vector.
The assimilation operator used is based on a randomly created mask array. The
revolution operator replaces a randomly selected candidate Web service with
another random candidate Web service for the corresponding task.

Wang, Sun, and Zou [34] considered global QoS constraints and used a skyline
operator [35] to prune redundant candidate Web services which cannot be part
of the optimal solution in order to reduce the search space. Finally, by
encoding each solution as an integer vector, particle swarm optimization [36]
is utilized to obtain a near-optimal solution.

Wu and Zhu [37] considered transactional constraints and modeled the problem
as a constrained directed acyclic graph. Finally, they utilized ant colony
optimization [38] to obtain a near-optimal solution.

###  2.2 Non-Evolutionary Approaches

Alrifai, Skoutas, and Risse [26] considered global QoS constraints and used a
skyline operator to eliminate useless candidate Web services which cannot be
part of the optimal solution in order to reduce the search space. To cope with
cases that the number of candidate Web services is still too large to be
practically beneficial, a set of representative candidate Web services is
selected using a hierarchical clustering mechanism for further reducing the
search space. Finally, mixed integer linear programming [39] is utilized to
obtain a near-optimal solution.

Alrifai, Risse, and Nejdl [27, 25] considered global QoS constraints and used
a hybrid approach to obtain a near-optimal solution. The hybrid approach
utilizes mixed integer linear programming to seek the optimal decomposition of
the global QoS constraints into local QoS constraints, and uses them as
thresholds to perform local selection for each task in a distributed fashion.

In spite of all the works done on the Web service selection problem, there is
still need for more research. Firstly, to the best of our knowledge, there is
no approach which supports all the constraints. Secondly, more efficient and
effective approaches are essential for real-time applications. Therefore,
different from the existing works, in this paper all global QoS constraints,
interservice constraints, and transactional constraints are considered
simultaneously, and a more efficient and effective approach using the Pareto
principle and genetic algorithm, namely GAP2WSS, is proposed.

##  3 Problem Formulation

In this section, the Web service selection problem is formulated by
considering global QoS constraints, interservice constraints, and
transactional constraints. And, a formal problem statement is presented at the
end.

###  3.1 Composition Patterns

There are four primary composition patterns which can be used to compose
various Web services and create a composite Web service. These composition
patterns are:

  * •

Serial: a sequence of Web services $\\{s_{1},\dotsc,s_{n}\\}$ are executed
consecutively.

  * •

Loop: a Web service $s$ is executed repeatedly up to a maximum of $it$
iterations.

  * •

Parallel (and split/and join): a set of Web services
$\\{s_{1},\dotsc,s_{n}\\}$ are executed concurrently and merge synchronized.

  * •

Switch (exclusive split/exclusive join): a Web service $s_{i}$ from a set of
Web services $\\{s_{1},\dotsc,s_{n}\\}$ is executed based on the outcome of
the switch condition evaluation at runtime.

Fig. 2 presents the workflow of a composite Web service. As is shown in the
figure, the workflow contains all the serial, loop, parallel, and switch
composition patterns.

TABLE I: Aggregation Functions for Different QoS Attributes [27] | Serial | Loop | Parallel | Switch
---|---|---|---|---
Response Time | $\sum\limits_{i=1}^{n}q(s_{i})$ | ${it}\times q(s)$ | $\max\limits_{i=1}^{n}\\{q(s_{i})\\}$ | $\max\limits_{i=1}^{n}\\{q(s_{i})\\}$
Price | $\sum\limits_{i=1}^{n}q(s_{i})$ | ${it}\times q(s)$ | $\sum\limits_{i=1}^{n}q(s_{i})$ | $\max\limits_{i=1}^{n}\\{q(s_{i})\\}$
Availability | $\prod\limits_{i=1}^{n}q(s_{i})$ | $\prod\limits_{i=1}^{it}q(s)$ | $\prod\limits_{i=1}^{n}q(s_{i})$ | $\min\limits_{i=1}^{n}\\{q(s_{i})\\}$
Throughput | $\min\limits_{i=1}^{n}\\{q(s_{i})\\}$ | $q(s)$ | $\min\limits_{i=1}^{n}\\{q(s_{i})\\}$ | $\min\limits_{i=1}^{n}\\{q(s_{i})\\}$

###  3.2 Composite Web Service

Let $T=\\{T_{1},\dotsc,T_{n^{\prime}}\\}$ be the set of all available tasks,
and $T_{i}=\\{s_{i,1},\dotsc,s_{i,{m_{i}}}\\}$ be the set of all candidate Web
services providing the functionality for the task $i$, where $n^{\prime}$,
$m_{i}$ represent the number of available tasks and the number of available
candidate Web services for the task $i$, respectively.

Now, the composition request is represented by the vector of
$CR=(S_{1},\dotsc,S_{n})$, which denotes the user’s functional requirements
for the composite Web service, where $n$ represents the number of tasks in the
composite Web service, $S_{i}\in T$.

Finally, the composite Web service is represented by the vector of
$CS=(s_{1},\dotsc,s_{n})$, which denotes the selected candidate Web services
for each task of the composition request, where $s_{i}\in S_{i}$.

###  3.3 QoS

The QoS values of a candidate Web service $s$ are represented by the vector of
$Q_{s}=(q_{1}(s),\dotsc,q_{k}(s))$, where $k$ represents the number of QoS
attributes for each candidate Web service. In addition, the vector of
$Q=(Q_{1,1},\dotsc,Q_{1,m_{1}},\dotsc,Q_{i,1},\dotsc,Q_{i,m_{i}})$ is
consisted of the QoS values of all the candidate Web services for all the
tasks. Finally, the QoS values of a composite Web service $CS$ is represented
by the vector of $Q_{CS}=(q^{\prime}_{1}(CS),\dotsc,q^{\prime}_{k}(CS))$,
where $q^{\prime}_{r}(CS)=F_{r}{}_{i=1}^{n}(q_{r}(s_{i}))$, and $F_{r}$
indicates the aggregation function for the $r$th QoS attribute.

The aggregation function depends on the QoS attribute and the composition
pattern used. Table I shows aggregation functions of four different QoS
attributes. It should be noted that for a composite Web service consisting of
multiple tasks and multiple kinds of composition patterns, the aggregation
functions are applied recursively.

QoS attributes’ weights are represented by the vector of
$W=(w_{1},\dots,w_{k})$, which denotes the user’s preferences with respect to
different QoS attributes, where $w_{r}\in[0,1]$, $\sum_{r=1}^{k}w_{r}=1$.

TABLE II: Derivation Rules for Transactional Properties [37, 40] | $\mathbf{\to p}$ | $\mathbf{\to c}$ | $\mathbf{\to r}$ | $\mathbf{\to cr}$ | $\mathbf{*}$ | $\mathbf{\oplus p}$ | $\mathbf{\oplus c}$ | $\mathbf{\oplus r}$ | $\mathbf{\oplus cr}$ | $\mathbf{\otimes p}$ | $\mathbf{\otimes c}$ | $\mathbf{\otimes r}$ | $\mathbf{\otimes cr}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$\mathbf{p}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{p}$ | $\mathrm{p}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{p}$ | $\mathrm{p}$ | $\mathrm{p}$ | $\mathrm{p}$ | $\mathrm{p}$
$\mathbf{c}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{c}$ | $\mathrm{\tilde{a}}$ | $\mathrm{c}$ | $\mathrm{\tilde{a}}$ | $\mathrm{c}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{p}$ | $\mathrm{c}$
$\mathbf{r}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{r}$ | $\mathrm{r}$ | $\mathrm{r}$ | $\mathrm{\tilde{a}}$ | $\mathrm{\tilde{a}}$ | $\mathrm{r}$ | $\mathrm{r}$ | $\mathrm{p}$ | $\mathrm{p}$ | $\mathrm{r}$ | $\mathrm{r}$
$\mathbf{cr}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{r}$ | $\mathrm{cr}$ | $\mathrm{cr}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{r}$ | $\mathrm{cr}$ | $\mathrm{p}$ | $\mathrm{c}$ | $\mathrm{r}$ | $\mathrm{cr}$

###  3.4 Constraints

Global QoS constraints are user’s requirements regarding the values of
different QoS attributes for a composite Web service, typically specified in
the service level agreement [41]. They are represented by the vector of
$QC=(c_{1},\dotsc,c_{k})$, where $c_{r}$ represents the constraint on the
value of the $r$th QoS attribute of the composite Web service.

The set of QoS attributes is consisted of two subsets: positive and negative
attributes. The value of the positive QoS attributes (e.g., availability,
throughput) should be maximized, whereas the value of the negative QoS
attributes (e.g., response time, price) should be minimized. The positive and
negative QoS attributes are represented by $Q^{+},Q^{-}$, respectively. Thus,
for a QoS attribute $r\in Q^{+}$, the constraint is a lower bound constraint
and for a QoS attribute $r\in Q^{-}$, the constraint is an upper bound
constraint. In addition, $c_{r}=\varnothing$ indicates no constraint on the
$r$th QoS attribute.

Interservice constraints are mutual context-based restrictions, such as
technological, business, and partnership limitations between different
candidate Web services. The set of interservice constraints is consisted of
two subsets: dependency and conflict constraints. The interservice
dependencies and interservice conflicts are represented by the set of
$DC=\\{(i,p,j,q):$ if the candidate Web service $p$ is used for the task
$S_{i}$, then the candidate Web service $q$ should be used for the task
$S_{j}\\}$, and $CC=\\{(i,p,j,q):$ if the candidate Web service $p$ is used
for the task $S_{i}$, then the candidate Web service $q$ should not be used
for the task $S_{j}\\}$, respectively.

A composite Web service requires transactional properties to guarantee its
failure atomicity during runtime. A failure-atomic Web service ensures to
succeed or fail as a complete unit. In other words, when it fails, all its
previously committed activities can be rolled back with no effect at all.
There are four primary failure-atomic transactional properties [42, 43]:

  * •

Compensatable: a Web service is compensatable if it provides a compensation
mechanism to roll back its effects when it is completed successfully. A
composite Web service is compensatable if all its Web services are
compensatable.

  * •

Retriable: a Web service is retriable if it can be invoked repeatedly until it
is completed successfully. A composite Web service is retriable if all its Web
services are retriable.

  * •

Pivot: a Web service is pivot if it is neither compensatable nor retriable.
This means that it does not ensure to execute successfully and once it
completes successfully, its effects cannot be rolled back.

  * •

Compensatable and Retriable: a Web service in this class is both compensatable
and retriable.

The transactional constraints are represented by $TC\in\mathcal{P}(TP)$, where
$TP=\\{\mathrm{p,c,r,cr}\\}$ is the set of transactional properties and
$\mathrm{p,c,r,cr}$ indicate the pivot, compensatable, retriable, and,
compensatable and retriable property, respectively. It should be noted that
$TC=\varnothing$ indicates no constraint on the transactional property of the
composite Web service. In addition, the transactional property of a candidate
Web service $s$ is represented by $tp(s)$ and the transactional property of a
composite Web service $CS$ is represented by $tp^{\prime}(CS)$.

The transactional property of a composite Web service depends on the
transactional properties of its Web services and the composition patterns
used. Table II shows derivation rules for different transactional properties,
where $\to$, $\ast$, $\oplus$, $\otimes$ represent the serial, loop, parallel,
and switch composition pattern, respectively, and $\mathrm{\tilde{a}}$ denotes
non-atomicity. It should be noted that for a composite Web service consisting
of multiple tasks and multiple kinds of composition patterns, the derivation
rules are applied recursively.

###  3.5 Utility

In order to map the QoS values of a candidate Web service to a single real
value, for the purpose of sorting and ranking, a utility function is used. The
utility function is defined using the simple additive weighting [44]
technique. It involves a scaling phase to allow a uniform measurement of the
QoS values independent of their ranges, and a weighting phase to represent
user’s preferences with respect to different QoS attributes. The utility value
of a candidate Web service $s\in S_{i}$ is computed as follows:

$\displaystyle U(s)$ $\displaystyle=\sum\limits_{r\in
Q^{+}}\frac{q_{r}(s)-Q_{min}(i,r)}{Q_{max}(i,r)-Q_{min}(i,r)}\cdot w_{r}$ (1)
$\displaystyle+\sum\limits_{r\in
Q^{-}}\frac{Q_{max}(i,r)-q_{r}(s)}{Q_{max}(i,r)-Q_{min}(i,r)}\cdot w_{r}$

with:

$\displaystyle Q_{min}(i,r)$ $\displaystyle=\min\limits_{\forall s\in
S_{i}}\\{q_{r}(s)\\}$ $\displaystyle Q_{max}(i,r)$
$\displaystyle=\max\limits_{\forall s\in S_{i}}\\{q_{r}(s)\\}$

where $Q_{min}(i,r)$, $Q_{max}(i,r)$ represent the minimum and maximum value
for the $r$th QoS attribute of the candidate Web services of the task $S_{i}$,
respectively. Finally, the utility value of a composite Web service
$CS=(s_{1},\dotsc,s_{n})$ with a composition request $CR=(S_{1},\dotsc,S_{n})$
is computed as follows:

$\displaystyle U^{\prime}(CS)$ $\displaystyle=\sum\limits_{r\in
Q^{+}}\frac{q^{\prime}_{r}(CS)-Q^{\prime}_{min}(r)}{Q^{\prime}_{max}(r)-Q^{\prime}_{min}(r)}\cdot
w_{r}$ $\displaystyle+\sum\limits_{r\in
Q^{-}}\frac{Q^{\prime}_{max}(r)-q^{\prime}_{r}(CS)}{Q^{\prime}_{max}(r)-Q^{\prime}_{min}(r)}\cdot
w_{r}$

with:

$\displaystyle Q^{\prime}_{min}(r)$
$\displaystyle=F_{r}{}_{i=1}^{n}(Q_{min}(i,r))$ $\displaystyle
Q^{\prime}_{max}(r)$ $\displaystyle=F_{r}{}_{i=1}^{n}(Q_{max}(i,r))$

where $Q^{\prime}_{min}(r)$, $Q^{\prime}_{max}(r)$ represent the minimum and
maximum possible value for the $r$th QoS attribute of the composite Web
service $CS$, respectively.

It should be noted that the candidate Web services with a higher utility value
are superior to the candidate Web services of the corresponding task with a
lower utility value.

###  3.6 Problem Statement

######  Definition 1 (Feasible Composite Web Service).

Given an octuple $\langle T,CR,Q,W,QC,DC,CC,TC\rangle$, a composite Web
service $CS=(s_{1},\dotsc,s_{n})$ is feasible, if and only if all the global
QoS constraints, interservice constraints, and transactional constraints are
satisfied. Formally:

  1. 1.

$\forall r\in Q^{-}:q^{\prime}_{r}(CS)\leq c_{r}$ and $\forall r\in
Q^{+}:q^{\prime}_{r}(CS)\geq c_{r}$,

  2. 2.

$\forall d=(i,p,j,q)\in DC:\text{if }s_{i}=p\text{ then }s_{j}=q$,

  3. 3.

$\forall c=(i,p,j,q)\in CC:\text{if }s_{i}=p\text{ then }s_{j}\neq q$, and

  4. 4.

$tp^{\prime}(CS)\in TC$.

######  Definition 2 (Optimal Composite Web Service).

Given an octuple $\langle T,CR,Q,W,QC,DC,CC,TC\rangle$, a composite Web
service $CS$ is optimal, if and only if it is a feasible composite Web
service, and its utility value $U^{\prime}(CS)$ is maximized along all the
possible combinations.

Now, with the prerequisite backgrounds in mind, the Web service selection
problem can be formally stated as follows:

######  Definition 3 (The Web Service Selection Problem).

Given an octuple $\langle T,CR,Q,W,QC,DC,CC,TC\rangle$ as input, return an
optimal composite Web service $CS$ as output.

##  4 The Proposed Approach: GAP2WSS

Genetic algorithms are search heuristics which rely on the principles of
evolution by means of natural selection, namely selection, crossover, and
mutation. Since, the Web service selection problem is a constrained
combinatorial optimization problem, genetic algorithms might be efficient and
effective for solving it.

In this section, a genetic algorithm adopted by the Pareto principle, namely
GAP2WSS, is proposed for solving the Web service selection problem. The
pseudocode of the proposed approach is presented in Fig. 3.

score and rank all the candidate Web services per each task;

generate the initial population using the top 20 percent candidate Web
services of each task;

while the termination condition is not satisfied do

probabilistically select parents and apply the crossover operator on them to
create the offsprings;

probabilistically select parents and apply the mutation operator on them to
create the mutants;

probabilistically select individuals from the current population, offsprings,
and mutants to create the new population;

end while

return the best individual of the last iteration.

Figure 3: The pseudocode of GAP2WSS

###  4.1 The Basic Idea

The Pareto principle (a.k.a. the 80-20 rule) [45], states that 20 percent of
causes, inputs, or efforts normally lead to 80 percent of the results,
outputs, or rewards. This principle has many validated cases in economics,
business, society, etc. The most popular case suggests that 80 percent of the
wealth is in the hands of 20 percent of the people.

The Pareto principle can be discreetly used to decrease the search space
extremely, and thereupon increase the efficiency and efficacy of the approach
used for solving the Web service selection problem. In order to utilize this
principle, a mechanism to score and rank different candidate Web services of
different tasks is used. This mechanism consists of two phases: scoring and
ranking.

In the scoring phase, at first, the utility value of a candidate Web service
$s\in S_{i}$ with respect to its QoS values is calculated by (1). Then, the
utility value of the candidate Web service $s$ with respect to the global QoS
constraints is calculated by:

$UC(s)=C_{max}-C(s)$

where $C_{max}$, $C(s)$ represent the maximum possible number of global QoS
constraints violations, and the number of global QoS constraints violations of
the candidate Web service $s$, respectively. Next, the utility value of the
candidate Web service $s$ with respect to the interservice constraints is
calculated by:

$UV(s)=V_{max}-V^{\prime}(s)$

where $V_{max}$, $V^{\prime}(s)$ represent the maximum possible number of
interservice constraints violations, and the number of interservice
constraints on the candidate Web service $s$, respectively. Finally, the
utility value of the candidate Web service $s$ with respect to the
transactional constraints is calculated by:

$UT(s)=\left\\{\begin{array}[]{ll}3,&\text{if }tp(s)=\mathrm{cr}\\\
2,&\text{if }tp(s)=\mathrm{c}\text{ or }\mathrm{r}\\\ 1,&\text{if
}tp(s)=\mathrm{p}\text{.}\end{array}\right.$

The above scores are extracted from [37]. As the authors stated, a
compensatable and retriable candidate Web service is the most suitable to
compose a failure-atomic composite Web service, whereas a pivot candidate Web
service is the least.

In the ranking phase, at first, the rank of the candidate Web service $s$
among all the candidate Web services of the task $i$ is determined. The rank
of the candidate Web service $s$ with respect to the QoS values, global QoS
constraints, interservice constraints, and transactional constraints utility
value is represented by $RQ(s)$, $RC(s)$, $RV(s)$, and $RT(s)$, respectively.

Eventually, the global rank of the candidate Web service $s$ is computed by:

$R(s)=\frac{RQ(s)}{RQ_{max}(i)}+\frac{c\times
RC(s)}{RC_{max}(i)}+\frac{v\times RV(s)}{RV_{max}(i)}+\frac{t\times
RT(s)}{RT_{max}(i)}$ (2)

with:

$\displaystyle RQ_{max}(i)$ $\displaystyle=\max\limits_{\forall s\in
S_{i}}\\{RQ(s)\\}$ $\displaystyle RC_{max}(i)$
$\displaystyle=\max\limits_{\forall s\in S_{i}}\\{RC(s)\\}$ $\displaystyle
RV_{max}(i)$ $\displaystyle=\max\limits_{\forall s\in S_{i}}\\{RV(s)\\}$
$\displaystyle RT_{max}(i)$ $\displaystyle=\max\limits_{\forall s\in
S_{i}}\\{RT(s)\\}$

where if global QoS constraints exist $c=1$ and otherwise $c=0$, if
interservice constraints exist $v=1$ and otherwise $v=0$, and if transactional
constraints exist $t=1$ and otherwise $t=0$.

###  4.2 Initial Population

Each individual in the population represents a composite Web service. An
individual $X$ is encoded as the vector of $X=(x_{1},\dotsc,x_{n})$, where
$x_{i}\in S_{i}$.

In order to generate the initial population, at first, the global rank of all
the candidate Web services for all the tasks is calculated using (2). Then, 20
percent of the candidate Web services with the best ranks are selected as
candidate Web services of each task. Finally, the Web service selection
problem is solved by focusing only on these 20 percent candidate Web services
of each task. More specifically in the genetic algorithm, the genes of each
individual is randomly selected only from these 20 percent candidate Web
services of the corresponding tasks.

Eventually, $n_{pop}$ individuals are generated as the initial population
$P(0)$, where $P(t)$ represents the population at the time $t$.

###  4.3 Fitness Function

TABLE III: Fitness Function Constraints | Function ($\bm{F}$) | Function | Corresponding | Fitness Function ($\bm{FF}$)
---|---|---|---|---
Range ($\bm{fr}$) | Range ($\bm{cr}$)
$\bm{\frac{C(X)}{C_{max}}=0}$ | $\bm{\frac{V(X)}{V_{max}}=0}$ | $\bm{T(X)=0}$ | $U^{\prime}(X)$ | $[0,1]$ | $[0.75,1]$ | $\bm{\frac{3+U^{\prime}(X)}{4}}$
$\bm{\frac{C(X)}{C_{max}}=0}$ | $\bm{\frac{V(X)}{V_{max}}=0}$ | $\bm{T(X)=1}$ | $U^{\prime}(X)$ | $[0,1]$ | $[0.5,0.75)$ | $\bm{\frac{2+U^{\prime}(X)}{4}}$
$\bm{\frac{C(X)}{C_{max}}=0}$ | $\bm{\frac{V(X)}{V_{max}}\in(0,1]}$ | $\bm{T(X)=0}$ | $U^{\prime}(X)-\frac{V(X)}{V_{max}}$ | $[-1,1]$ | $[0.5,0.75)$ | $\bm{\frac{5+U^{\prime}(X)-\frac{V(X)}{V_{max}}}{8}}$
$\bm{\frac{C(X)}{C_{max}}=0}$ | $\bm{\frac{V(X)}{V_{max}}\in(0,1]}$ | $\bm{T(X)=1}$ | $U^{\prime}(X)-\frac{V(X)}{V_{max}}$ | $[-1,1]$ | $[0.25,0.5)$ | $\bm{\frac{3+U^{\prime}(X)-\frac{V(X)}{V_{max}}}{8}}$
$\bm{\frac{C(X)}{C_{max}}\in(0,1]}$ | $\bm{\frac{V(X)}{V_{max}}=0}$ | $\bm{T(X)=0}$ | $U^{\prime}(X)-\frac{C(X)}{C_{max}}$ | $[-1,1]$ | $[0.5,0.75)$ | $\bm{\frac{5+U^{\prime}(X)-\frac{C(X)}{C_{max}}}{8}}$
$\bm{\frac{C(X)}{C_{max}}\in(0,1]}$ | $\bm{\frac{V(X)}{V_{max}}=0}$ | $\bm{T(X)=1}$ | $U^{\prime}(X)-\frac{C(X)}{C_{max}}$ | $[-1,1]$ | $[0.25,0.5)$ | $\bm{\frac{3+U^{\prime}(X)-\frac{C(X)}{C_{max}}}{8}}$
$\bm{\frac{C(X)}{C_{max}}\in(0,1]}$ | $\bm{\frac{V(X)}{V_{max}}\in(0,1]}$ | $\bm{T(X)=0}$ | $U^{\prime}(X)-\frac{C(X)}{C_{max}}-\frac{V(X)}{V_{max}}$ | $[-2,1]$ | $[0.25,0.5)$ | $\bm{\frac{5+U^{\prime}(X)-\frac{C(X)}{C_{max}}-\frac{V(X)}{V_{max}}}{12}}$
$\bm{\frac{C(X)}{C_{max}}\in(0,1]}$ | $\bm{\frac{V(X)}{V_{max}}\in(0,1]}$ | $\bm{T(X)=1}$ | $U^{\prime}(X)-\frac{C(X)}{C_{max}}-\frac{V(X)}{V_{max}}$ | $[-2,1]$ | $[0,0.25)$ | $\bm{\frac{2+U^{\prime}(X)-\frac{C(X)}{C_{max}}-\frac{V(X)}{V_{max}}}{12}}$

Selecting the candidate Web service with the highest utility value for each
task, does not ensure that the specified constraints are satisfied nor the
utility value of the composite Web service is maximized. Hence, a fitness
function is used to enable comparison of different individuals with respect to
their utility values and the degree of constraints satisfaction.

A genetic algorithm can only be applied to unconstrained problems directly.
Hence, to handle the constraints, a penalty mechanism which penalizes the
individuals who violate any constraints is used in defining the fitness
function. It should be noted that the infeasible individuals are not
eliminated from the population, because they may have some schemata which is
required to obtain the optimal solution.

Since, the constraints satisfaction is prior to the utility value, in other
words a higher utility value does not justify the constraints violation, two
principles are considered to define the fitness function. First, all the
feasible individuals should have a higher fitness value than any infeasible
individual. Second, the more constraints violated by an infeasible individual,
the more penalty it receives.

To this aim, the fitness function range $[0,1]$ is divided up into four equal
ranges. If no constraints are violated the fitness value will be in the range
of $[0.75,1]$, if one kind of constraints is violated the fitness value will
be in the range of $[0.5,0.75)$, if two kinds of constraints are violated the
fitness value will be in the range of $[0.25,0.5)$, and if all three kinds of
constraints are violated the fitness value will be in the range of $[0,0.25)$.

Then, a function $F$ is defined to compare individuals with the same kinds of
constraint violations. Each function has its own range, which is mapped to the
corresponding range to obtain the fitness function $FF$ by:

$FF=cr_{min}+\frac{(F-fr_{min})\cdot(cr_{max}-cr_{min})}{fr_{max}-fr_{min}}$

where $cr_{min}$, $cr_{max}$ represent the minimum and maximum value of the
corresponding range, respectively, and $fr_{min}$, $fr_{max}$ represent the
minimum and maximum value of the function’s range, respectively.

Finally, the resultant fitness function is presented in Table III, where
$C(X)$, $V(X)$ represent the number of global QoS constraints violations and
the number of interservice constraints violations for the corresponding
individual, respectively. In addition, $T(X)=1$ represents the violation of
transactional constraints, and $T(X)=0$ represents otherwise.

###  4.4 Crossover

The mechanism used to select parents for the crossover is rank-based, in which
the individuals with the better rank are more likely to be selected. The
probability that an individual $i\in P(t)$ is selected as a parent for the
crossover is determined by:

$p_{i}=\frac{n_{pop}-r_{i}+1}{\sum\limits_{i=1}^{n_{pop}}r_{i}}$

where $r_{i}$ represents the rank of the individual $i$ based on its fitness
value.

Figure 4: Example of applying the crossover operator

The crossover operator used is a single-point crossover which takes two
different individuals as parents and creates two different individuals as
children. Let $X=(x_{1},\dotsc,x_{n})$ and $Y=(y_{1},\dotsc,y_{n})$ represent
two parents and $l$ represent the crossover point. Then, two children $C_{1}$,
$C_{2}$ are created as:

$\displaystyle C_{1}$
$\displaystyle=(x_{1},\dotsc,x_{l},y_{l+1},\dotsc,y_{n})$ $\displaystyle
C_{2}$ $\displaystyle=(y_{1},\dotsc,y_{l},x_{l+1},\dotsc,x_{n}).$

Fig. 4 demonstrates the crossover operator with an example. Eventually,
$n_{c}=2\lceil\frac{p_{c}n_{pop}}{2}\rceil$ individuals are selected as
parents and $n_{c}$ individuals are created as offsprings $Q(t)$, where
$p_{c}$, $Q(t)$ represent the crossover rate and the offsprings at the time
$t$, respectively.

###  4.5 Mutation

The mechanism used to select parents for the mutation is rank-based, in which
the individuals with the better rank are more likely to be selected. The
probability that an individual $i\in Q(t)$ is selected as a parent for the
mutation is determined by:

$p_{i}=\frac{n_{c}-r_{i}+1}{\sum\limits_{i=1}^{n_{c}}r_{i}}$

where $r_{i}$ represents the rank of the individual $i$ based on its fitness
value.

Figure 5: Example of applying the mutation operator

The mutation operator used is a random mutation which takes an individual as a
parent and creates an individual as a child. Let $X=(x_{1},\dotsc,x_{n})$
represent a parent and $l$ represent the mutation point. Then, $x_{l}$ is
replaced by $x_{l}^{new}\in S_{l}-{x_{l}}$ to create a child $C$ as:

$C=(x_{1},\dotsc,x_{l}^{new},\dotsc,x_{n}).$

Fig. 5 demonstrates the mutation operator with an example. Eventually,
$n_{m}=\lceil p_{m}n_{pop}\rceil$ individuals are selected as parents and
$n_{m}$ individuals are created as mutants $R(t)$, where $p_{m}$, $R(t)$
represent the mutation rate and the mutants at the time $t$, respectively.

###  4.6 Replacement

The mechanism used to select individuals of the new population is rank-based
with elitism, in which the individuals with the better rank are more likely to
be selected and the best individual is always transmitted to the new
population. First, the offsprings $Q(t)$, the mutants $R(t)$ and the old
population $P(t)$ are merged to create the temporary population
$P^{\prime}(t)$. Then, the probability that an individual $i\in P^{\prime}(t)$
is selected as an individual of the new population is determined by:

$p_{i}=\frac{n_{pop}+n_{c}+n_{m}-r_{i}+1}{\sum\limits_{i=1}^{n_{pop}+n_{c}+n_{m}}r_{i}}$

where $r_{i}$ represents the rank of the individual $i$ based on its fitness
value.

Eventually, $n_{pop}$ individuals are selected to create the new population
$P(t+1)$, which replaces the old population $P(t)$.

##  5 Empirical Studies

In order to investigate the efficiency and efficacy of GAP2WSS, extensive
experiments are performed. In the following, after describing the experimental
setup, the experiments are presented.

###  5.1 Experimental Setup

According to [30], the penalty-based genetic algorithm [28] is the fastest
among the repairing-based genetic algorithm [29] and the hybrid genetic
algorithm [30] for solving the Web service selection problem. For that reason,
GAP2WSS is compared with the penalty-based genetic algorithm (PGA). Both
GAP2WSS and PGA are implemented in Matlab R2014a, and all the experiments are
conducted on a PC with Intel(R) Core(TM) i7 CPU at 3.40 GHz and 16 Gbytes RAM
running 64-bit Windows 8.1 Enterprise.

How to set the genetic algorithm parameters to enable the best performance is
an optimization problem itself. Since, parameter optimization of genetic
algorithms is problem-specific and is not the focus of this paper, similar to
[30], the population size, crossover rate, and mutation rate of the algorithms
are set to 100, 0.90, and 0.15, respectively. The termination condition of
both the algorithms is exceeding a certain number of fitness function
evaluations. Since, there is no priori knowledge of the number of fitness
function evaluations required for solving different test problems, GAP2WSS is
first executed with a termination condition of no improvement on the best
solution in 15 consecutive iterations for each test problem. Next, the
obtained number of fitness function evaluations is used as the termination
condition of both the algorithms for the corresponding test problem. Since,
unlike PGA, all global QoS constraints, interservice constraints, and
transactional constraints are considered in GAP2WSS, the fitness function
presented in this paper is used as the fitness function of both the
algorithms. Moreover, due to the stochastic nature of genetic algorithms, both
algorithms are executed 30 times for each test problem, and the average
obtained fitness value of each test problem is recorded.

For the purpose of evaluation, the workflow shown in Fig. 2 is considered as
the composite Web service. As is shown in the figure, the composite Web
service is comprised of 10 tasks. To generate a composite Web service with
more number of tasks, a certain number of the workflow is concatenated
together. For example, constructing a composite Web service with 50 tasks is
made by concatenating five copies of the workflow. After generating the tasks,
the candidate Web services of each task are randomly selected from the QWS
dataset. In addition, the transactional property of each candidate Web service
is randomly assigned to one of the transactional properties from the set of
$TP$. For simplicity, the weights of different QoS attributes are set to the
same value. At last, the number of iterations of the loop in the workflow is
fixed to five.

The efficiency and efficacy of different approaches is dependent on the size
and the complexity of the Web service selection problem. The size of the
problem is a function of two factors: the number of tasks and the number of
candidate Web services per each task. Besides, the complexity of the problem
is determined by the number of global QoS constraints, interservice
constraints, and transactional constraints. Therefore, five sets of test
problems are generated to evaluate the impact of these factors independently.
In the following, first, the experiments on the convergence and stability of
the algorithms, and then, the experiments on each of these sets are presented.

###  5.2 Experiments on the Convergence and Stability

In this test, the number of tasks, candidate Web services per each task,
global QoS constraints, interservice constraints, and transactional
constraints is fixed to 10, 100, 1, 500, 4, respectively. In addition, the
termination condition of the algorithms is 250 iterations.

Fig. 6 and Fig. 7 depict the convergence diagram of PGA and GAP2WSS,
respectively. In addition, the stability diagram of PGA and GAP2WSS is shown
in Fig. 8 and Fig. 9, respectively. It can be noticed that GAP2WSS has a
faster convergence and a higher stability than PGA.

Figure 6: The convergence diagram of PGA Figure 7: The convergence diagram of
GAP2WSS Figure 8: The stability diagram of PGA Figure 9: The stability diagram
of GAP2WSS

###  5.3 Experiments on the Number of Tasks

In this set of test problems, the number of tasks is varied from 10 to 100
with an increment step of 10. In addition, the number of candidate Web
services per each task is fixed to 500. In order to make sure that the results
of the experiments are not biased by the constraints, the number of global QoS
constraints, interservice constraints and transactional constraints are all
fixed to zero.

Fig. 10 shows the fitness values obtained by the algorithms for the 10 test
problems of this set. It can be seen that in all the test problems, GAP2WSS
obtained higher fitness values than PGA. The average fitness value of this set
of test problems is 0.9122, 0.8900 for GAP2WSS and PGA, respectively. In other
words, the average fitness value of GAP2WSS to the average fitness value of
PGA, has improved 2.49 percent for this set of test problems.

Figure 10: Comparison of the approaches in terms of Fitness Value with respect
to different Number of Tasks

###  5.4 Experiments on the Number of Candidate Web Services

In this set of test problems, the number of candidate Web services per each
task is varied from 100 to 1000 with an increment step of 100. In addition,
the number of tasks is fixed to 50. In order to make sure that the results of
the experiments are not biased by the constraints, the number of global QoS
constraints, interservice constraints and transactional constraints are all
fixed to zero.

Fig. 11 shows the fitness values obtained by the algorithms for the 10 test
problems of this set. It can be noticed that in all the test problems, GAP2WSS
obtained higher fitness values than PGA. The average fitness value of this set
of test problems is 0.9161, 0.8820 for GAP2WSS and PGA, respectively. In other
words, the average fitness value of GAP2WSS to the average fitness value of
PGA, has improved 3.87 percent for this set of test problems.

Figure 11: Comparison of the approaches in terms of Fitness Value with respect
to different Number of Candidate Web Services

###  5.5 Experiments on the Number of Global QoS Constraints

In this set of test problems, the number of global QoS constraints is varied
from zero to nine with an increment step of one. In addition, the number of
tasks and the number of candidate Web services per each task are fixed to 50
and 500, respectively. In order to make sure that the results of the
experiments are not biased by the number of interservice constraints and
transactional constraints, they are both fixed to zero. It should be noted
that the average of minimum and maximum possible QoS values of the composite
Web service are considered as the global QoS constraints.

Fig. 12 shows the fitness values obtained by the algorithms for the 10 test
problems of this set. It can be observed that in all the test problems,
GAP2WSS obtained higher fitness values than PGA. The average fitness value of
this set of test problems is 0.7153, 0.6681 for GAP2WSS and PGA, respectively.
In other words, the average fitness value of GAP2WSS to the average fitness
value of PGA, has improved 7.06 percent for this set of test problems.

Figure 12: Comparison of the approaches in terms of Fitness Value with respect
to different Number of Global QoS Constraints

###  5.6 Experiments on the Number of Interservice Constraints

In this set of test problems, the number of interservice constraints is varied
from 0 to 5000 with an increment step of 500. In addition, the number of tasks
and the number of candidate Web services per each task are fixed to 50 and
500, respectively. In order to make sure that the results of the experiments
are not biased by the number of global QoS constraints and transactional
constraints, they are both fixed to zero. It should be noted that the
interservice constraints are generated randomly.

Fig. 13 shows the fitness values obtained by the algorithms for the 11 test
problems of this set. It can be seen that in all the test problems, GAP2WSS
obtained higher fitness values than PGA. The average fitness value of this set
of test problems is 0.9153, 0.8822 for GAP2WSS and PGA, respectively. In other
words, the average fitness value of GAP2WSS to the average fitness value of
PGA, has improved 3.75 percent for this set of test problems.

Figure 13: Comparison of the approaches in terms of Fitness Value with respect
to different Number of Interservice Constraints

###  5.7 Experiments on the Number of Transactional Constraints

In this set of test problems, the number of transactional constraints is
varied from zero to four with an increment step of one. In addition, the
number of tasks and the number of candidate Web services per each task are
fixed to 50 and 500, respectively. In order to make sure that the results of
the experiments are not biased by the number of global QoS constraints and
interservice constraints, they are both fixed to zero. It should be noted that
the transactional constraints are picked from the set of $\mathcal{P}(TP)$.

Fig. 14 shows the fitness values obtained by the algorithms for the five test
problems of this set. It can be noticed that in all the test problems, GAP2WSS
obtained higher fitness values than PGA. The average fitness value of this set
of test problems is 0.7155, 0.6823 for GAP2WSS and PGA, respectively. In other
words, the average fitness value of GAP2WSS to the average fitness value of
PGA, has improved 4.87 percent for this set of test problems.

Figure 14: Comparison of the approaches in terms of Fitness Value with respect
to different Number of Transactional Constraints

###  5.8 Discussion

Clearly, it can be observed from the above experiments that GAP2WSS
outperformed PGA in all the test problems, and handled different number of
tasks, candidate Web services per each task, global QoS constraints,
interservice constraints, and transactional constraints pretty good. The
average fitness value of all the test problems is 0.8496, 0.8156 for GAP2WSS
and PGA, respectively. In other words, the average fitness value of GAP2WSS to
the average fitness value of PGA, has improved 4.17 percent for all the test
problems.

The main reason why GAP2WSS achieved far better fitness values than PGA is
that the Pareto principle is adopted. This approach results in a reduced
search space equal to $\nicefrac{{1}}{{5}}$ of the original search space,
which then leads to a quicker convergence to a reasonably good solution.
Therefore, GAP2WSS has better efficiency and efficacy than PGA.

In addition, it can be inferred that a near-optimal solution exists in this
reduced search space, and there is no need to explore the remaining search
space. Therefore, this mechanism can be used in other approaches for solving
the Web service selection problem.

##  6 Conclusion

This paper presented a genetic algorithm based on the Pareto principle, namely
GAP2WSS, for solving the Web service selection problem, which is known to be
NP-hard in the strong sense. In the proposed approach, first, all the
candidate Web services of different tasks are scored and ranked per each task.
Then, using the Pareto principle, the problem search space is reduced to
$\nicefrac{{1}}{{5}}$ of the original search space. Finally, the problem is
solved by focusing only on this reduced search space using a genetic
algorithm.

The efficiency and efficacy of the proposed approach is investigated by
conducting extensive experiments. The results demonstrate that the proposed
approach significantly increased the efficiency and efficacy and hence can be
used in real-time applications. In addition, it can be inferred that a
reasonably good solution exists in this reduced search space, and there is no
need to explore the remaining search space. To the best of our knowledge, this
is the first approach which supports all global QoS constraints, interservice
constraints, and transactional constraints for solving the Web service
selection problem.

For future works, we suggest to propose a benchmark to enable fair comparison
of different approaches for solving the Web service selection problem. By
studying the advantages and disadvantages of different approaches, a more
efficient, effective, and comprehensive approach for solving the problem
should be proposed. In addition, more criteria should be considered for
enterprise application requirements. Finally, we suggest to extend the usage
of the Pareto principle to other approaches for the Web service selection
problem and other problems.

## References

  * [1] T. Erl, _Service-Oriented Architecture: Concepts, Technology, and Design_. Pearson Education India, 2005\.
  * [2] M. Papazoglou, “Service-oriented computing: Concepts, characteristics and directions,” in _Proc. 4th Int’l Conf. Web Information Systems Eng. (WISE 03)_ , Dec. 2003, pp. 3–12.
  * [3] “Extensible markup language (xml) 1.0 (fifth edition), w3c recommendation,” www.w3.org/TR/2008/REC-xml-20081126/, 26 Nov. 2008.
  * [4] “Web services glossary, w3c working group note,” www.w3.org/TR/2004/NOTE-ws-gloss-20040211/, 11 Feb. 2004.
  * [5] “Web services description language (wsdl) 1.1, w3c note,” www.w3.org/TR/2001/NOTE-wsdl-20010315/, 15 Mar. 2001.
  * [6] “Soap version 1.2 part 0: Primer (second edition), w3c recommendation,” www.w3.org/TR/2007/REC-soap12-part0-20070427/, 27 Apr. 2007.
  * [7] “Soap version 1.2 part 1: Messaging framework (second edition), w3c recommendation,” www.w3.org/TR/2007/REC-soap12-part1-20070427/, 27 Apr. 2007.
  * [8] “Soap version 1.2 part 2: Adjuncts (second edition), w3c recommendation,” www.w3.org/TR/2007/REC-soap12-part2-20070427/, 27 Apr. 2007.
  * [9] “Soap version 1.2 specification assertions and test collection (second edition), w3c recommendation,” www.w3.org/TR/2007/REC-soap12-testcollection-20070427/, 27 Apr. 2007.
  * [10] “Uddi version 3.0.2, uddi spec technical committee draft,” http://uddi.org/pubs/uddi-v3.0.2-20041019.htm, 19 Oct. 2004.
  * [11] “Qos for web services: Requirements and possible approaches, w3c working group note,” www.w3c.or.kr/kr-office/TR/2003/ws-qos/, 25 Nov. 2003.
  * [12] E. Al-Masri and Q. H. Mahmoud, “Investigating web services on the world wide web,” in _Proc. 17th Int’l Conf. World Wide Web (WWW 08)_ , Apr. 2008, pp. 795–804.
  * [13] ——, “Qos-based discovery and ranking of web services,” in _Proc. 16th Int’l Conf. Computer Communications and Networks (ICCCN 07)_ , Aug. 2007, pp. 529–534.
  * [14] ——, “Discovering the best web service,” in _Proc. 16th Int’l Conf. World Wide Web (WWW 07)_ , May 2007, pp. 1257–1258.
  * [15] “Basic profile version 2.0, working group draft,” www.ws-i.org/Profiles/BasicProfile-2_0(WGD).html, 25 Oct. 2007.
  * [16] “Web services business process execution language version 2.0, oasis standard,” http://docs.oasis-open.org/wsbpel/2.0/OS/wsbpel-v2.0-OS.html, 11 Apr. 2007\.
  * [17] W. van der Aalst and A. ter Hofstede, “Yawl: Yet another workflow language,” _Information Systems_ , vol. 30, no. 4, pp. 245–275, 2005.
  * [18] M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica, and M. Zaharia, “A view of cloud computing,” _Comm. ACM_ , vol. 53, no. 4, pp. 50–58, 2010.
  * [19] H. Kellerer, U. Pferschy, and D. Pisinger, _Knapsack Problems_. Springer, 2004.
  * [20] S. Arora and B. Barak, _Computational Complexity: A Modern Approach_. Cambridge University Press, 2009\.
  * [21] L. Zeng, B. Benatallah, M. Dumas, J. Kalagnanam, and Q. Z. Sheng, “Quality driven web services composition,” in _Proc. 12th Int’l Conf. World Wide Web (WWW 03)_ , May 2003, pp. 411–421.
  * [22] L. Zeng, B. Benatallah, A. Ngu, M. Dumas, J. Kalagnanam, and H. Chang, “Qos-aware middleware for web services composition,” _IEEE Trans. Software Engineering_ , vol. 30, no. 5, pp. 311–327, 2004.
  * [23] D. Ardagna and B. Pernici, “Adaptive service composition in flexible processes,” _IEEE Trans. Software Engineering_ , vol. 33, no. 6, pp. 369–384, 2007.
  * [24] T. Yu, Y. Zhang, and K.-J. Lin, “Efficient algorithms for web services selection with end-to-end qos constraints,” _ACM Trans. Web_ , vol. 1, no. 1, pp. 1–26, 2007.
  * [25] M. Alrifai and T. Risse, “Combining global optimization with local selection for efficient qos-aware service composition,” in _Proc. 18th Int’l Conf. World Wide Web (WWW 09)_ , Apr. 2009, pp. 881–890.
  * [26] M. Alrifai, D. Skoutas, and T. Risse, “Selecting skyline services for qos-based web service composition,” in _Proc. 19th Int’l Conf. World Wide Web (WWW 10)_ , Apr. 2010, pp. 11–20.
  * [27] M. Alrifai, T. Risse, and W. Nejdl, “A hybrid approach for efficient web service composition with end-to-end qos constraints,” _ACM Trans. Web_ , vol. 6, no. 2, pp. 7:1–7:31, 2012.
  * [28] L. Ai and M. Tang, “A penalty-based genetic algorithm for qos-aware web service composition with inter-service dependencies and conflicts,” in _Int’l Conf. Computational Intelligence for Modelling Control & Automation (CIMCA 08)_, Dec. 2008, pp. 738–743.
  * [29] ——, “Qos-based web service composition accommodating inter-service dependencies using minimal-conflict hill-climbing repair genetic algorithm,” in _IEEE 4th Int’l Conf. eScience (eScience 08)_ , Dec. 2008, pp. 119–126.
  * [30] M. Tang and L. Ai, “A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition,” in _IEEE Congress Evolutionary Computation (CEC 10)_ , 2010, pp. 1–8.
  * [31] D. E. Goldberg, _Genetic Algorithms_. Pearson Education India, 2006.
  * [32] S. Lotfi and K. Mowlani, “Ica-wss: A qos-aware imperialist competitive algorithm for web service selection,” in _Informatics Engineering and Information Science_. Springer, 2011, vol. 254, pp. 135–148.
  * [33] E. Atashpaz-Gargari and C. Lucas, “Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition,” in _IEEE Congress Evolutionary Computation (CEC 07)_ , Sep. 2007, pp. 4661–4667.
  * [34] S. Wang, Q. Sun, H. Zou, and F. Yang, “Particle swarm optimization with skyline operator for fast cloud-based web service composition,” _Mobile Networks and Applications_ , vol. 18, no. 1, pp. 116–121, 2013.
  * [35] S. Borzsony, D. Kossmann, and K. Stocker, “The skyline operator,” in _Proc. 17th Int’l Conf. Data Eng. (ICDE 01)_ , Apr. 2001, pp. 421–430.
  * [36] J. Kennedy, “Particle swarm optimization,” in _Encyclopedia of Machine Learning_. Springer, 2010, pp. 760–766.
  * [37] Q. Wu and Q. Zhu, “Transactional and qos-aware dynamic service composition based on ant colony optimization,” _Future Generation Computer Systems_ , vol. 29, no. 5, pp. 1112–1119, 2013.
  * [38] M. Dorigo and M. Birattari, “Ant colony optimization,” in _Encyclopedia of Machine Learning_. Springer, 2010, pp. 36–39.
  * [39] G. L. Nemhauser and L. A. Wolsey, _Integer and Combinatorial Optimization_. Wiley New York, 1988, vol. 18.
  * [40] J. El Hadad, M. Manouvrier, and M. Rukoz, “Tqos: Transactional and qos-aware selection algorithm for automatic web service composition,” _IEEE Trans. Services Computing_ , vol. 3, no. 1, pp. 73–85, 2010.
  * [41] A. Keller and H. Ludwig, “The wsla framework: Specifying and monitoring service level agreements for web services,” _J. Network and Systems Management_ , vol. 11, no. 1, pp. 57–81, 2003.
  * [42] S. Mehrotra, R. Rastogi, A. Silberschatz, and H. Korth, “A transaction model for multidatabase systems,” in _Proc. 12th Int’l Conf. Distributed Computing Systems (ICDCS 92)_ , Jun. 1992, pp. 56–63.
  * [43] L. Li, C. Liu, and J. Wang, “Deriving transactional properties of composite web services,” in _IEEE Int’l Conf. Web Services (ICWS 07)_ , Jul. 2007, pp. 631–638.
  * [44] M. Zeleny and J. L. Cochrane, _Multiple Criteria Decision Making_. McGraw-Hill New York, 1982, vol. 25.
  * [45] R. Koch, _The 80/20 Principle: The Secret to Achieving More with Less_. Random House LLC, 2011.

|  SayedHassan Khatoonabadi received the BSc degree in computer science from
Shahid Bahonar University of Kerman, Kerman, Iran, in 2012, and the MSc degree
in computer science from University of Tabriz, Tabriz, Iran, in 2015. His
research interests include service-oriented architecture, service-oriented
computing, cloud computing, and Web services.
---|---
|  Shahriar Lotfi received the BEng and MEng degrees in computer engineering
all from University of Isfahan, Esfahan, Iran, in 1998 and 2002, respectively,
and the PhD degree in computer engineering from Iran University of Science and
Technology, Tehran, Iran, in 2008. Since 2008 he has been with the Department
of Computer Science, Faculty of Mathematical Sciences, University of Tabriz,
Tabriz, Iran, where he is currently an Assistant Professor, the Head of the
department, and the Director of Intelligent Systems Laboratory. He has
authored and co-authored over 30 publications. His research interests include
parallel algorithms, supercompilers, and evolutionary algorithms.
---|---
|  Ayaz Isazadeh received the BSc degree in mathematics from University of
Tabriz, Tabriz, Iran, in 1971, and the MSE degree in electrical engineering
and computer science from Princeton University, NJ, US, in 1978, and the PhD
degree in computing and information science from Queen’s University, ON,
Canada, in 1996. From 1981 to 1990, he was a Member of Technical Staff in Bell
Labs. In 1999, he founded and established the Department of Computer Science
in Faculty of Mathematical Sciences, University of Tabriz, Tabriz, Iran, where
he is currently a Full Professor and the Director of Computer Systems
Laboratory. He was a Visiting Professor with the Department of Computer
Engineering, Middle East Technical University Northern Cyprus Campus, Northern
Cyprus, from 2012 to 2013. He has authored and co-authored over 90
publications. His research interests include automata theory and formal
languages, software engineering, management information systems, information
and communication technology, and, data structures and algorithms.
---|---