# A Novel Ant Colony Optimization Algorithm for Large Scale QoS-Based Service Selection Problem

Authors: Changsheng Zhang; Hao Yin; Bin Zhang
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

To tackle the large scale QoS-based service selection problem, a novel efficient clustering guided ant colony service selection algorithm called CASS is proposed in this paper. In this algorithm, a skyline query process is used to filter the candidates related to each service class, and a clustering based shrinking process is used to guide the ant to the search directions. We evaluate our approach experimentally using standard real datasets and synthetically generated datasets and compared it with the recently proposed related service selection algorithms. It reveals very encouraging results in terms of the quality of solution and the processing time required.


---

## Body

## 1. Introduction

With the proliferation of the Cloud Computing and Software as a Service (SaaS) concepts, more and more web services will be offered on the web at different levels of quality [1]. There may be multiple service providers competing to offer the same functionality with different quality of service. Quality of service (QoS) has become a central criterion for differentiating these competing service providers and plays a major role in determining the success or failure of the composed application. Therefore, a Service Level Agreement (SLA) is often used as a contractual basis between service consumers and service providers on the expected QoS level. The QoS-based service selection problem aims at finding the best combination of web services that satisfy a set of end-to-end QoS constraints in order to fulfill a given SLA, which is an NP-hard problem [2].This problem becomes especially important and challenging as the number of functionally equivalent services offered on the web at different QoS levels increases exponentially [3]. As the number of possible combinations can be very huge, based on the number of subtasks comprising the composite process and the number of alternative services for each subtask, using the proposed exact search algorithms [4, 5] to perform an exhaustive search to find the best combination that satisfies a certain composition level SLA is impractical. So, most of the researches are concentrated on heuristic-based algorithms especially the metaheuristic approaches aiming to find near-optimal compositions [6]. In [5], the authors propose heuristic algorithms that can be used to find a near-optimal solution efficiently. The authors propose two models for the QoS-based service composition problem and introduce a heuristic for each model. In [7], the authors present a genetic algorithm for this problem, in which a special relation matrix coding scheme of chromosomes and an evolution function of population are designed. A simulated annealing process is introduced to increase the population diversity. In [8], a new cooperative evolution (coevolution) algorithm consisting of a stochastic particle swarm optimization (SPSO) and a simulated annealing (SA) is presented to solve this problem. As a metaheuristic approach, the ACO algorithm is defined by Dorigo et al. [9], motivated by the intelligent behavior of ant system. It has been applied to solve many problems and obtained satisfying results [10, 11]. The research of its applications for service selection has been also made by several researchers. In [12, 13], the basic principle of ACO is expounded and the service selection based on the QoS is transformed into the problem of finding the optimization path. In [14], a service composition graph is applied to model this problem and an extended ant colony system using a novel ant clone rule is applied to solve it. In [15], an algorithm named multipheromone and dynamically updating ant colony optimization algorithm (MPDACO) is put forward to solve this problem, which includes a global optimization process and a local optimizing process. In [16], the ACO is combined with genetic algorithm to the service selection problem. But, these existing researches for this problem have the following shortcomings. (1) The used construction graphs are static and their information granularities for this problem are too coarse, which makes these algorithms excessively rely on their local search processes. (2) The efficiency of these existing service selection algorithms is not satisfying when the number of candidates becomes large. This is mainly because many redundant candidates exist. If they are not filtered beforehand, lots of search efforts will be wasted at running. Furthermore, if the promising areas are identified early, lots of searching efforts will be saved.In this paper, the ACO algorithm is extended for solving the QoS based service selection problem, in which an unsupervised clustering process is used for constructing a directed clustering graph to guide the ants making exploration, and a dynamic expanding process is used to enlarge this path for ants making exploitation based on the obtained global information. Furthermore, the Multicriteria Dominance Relationships [17] are introduced to reduce the problem space for ant-based clustering [18] to further improve the service selection efficiency. We have compared our approach with the recently proposed service selection algorithms DiGA [7], SPSO [8], and MPDACO [15]. The performance of these algorithms has been tested on a variety of data sets provided from several real-life situations and synthetically generated datasets. The computational results demonstrate the effectiveness of our approach in comparison to these approaches. This paper is organized as follows. In Section 2, we give the definition of the QoS-based service selection problem and the basic ant colony algorithm. The CASS algorithm including its model and concrete algorithm description is provided in Section 3. Section 4 present experimental studies and compared the CASS with some other recently proposed algorithms. Finally, Section 5 summarizes the contribution of this paper along with some future research directions.


## 2. Problem Definition and Ant Colony Algorithm

### 2.1. The QoS-Based Service Selection Problem

For a composite application composed of a set of abstract services𝕊 that is specified as abstract workflow ℑ, each abstract service i,i∈[0,∥𝕊∥-1] corresponds to a service class Si={si1,si2,…,sin}, and Si consists of all services that deliver the same functionality but potentially differ in terms of QoSvalues. Since the value of a QoS attribute is published by the service provider, its value may be positive or negative. We use the vector Qs={q1(s),q2(s),…,qr(s)} to represent the QoS values of service s, and the function qi(s) determines the published value of the ith attribute of the service s. Then, the QoS vector for a composite service consisting of n service components CS={s1,s2,…,sn},n∈[1,∥𝕊∥] is defined as QCS={q1′(CS),q2′(CS),…,qr′(CS)}, where the qi′(CS) is the estimated end-to-end value of the ith QoS attribute. Although many different service composition structures may exist in the workflow, we only focus on the sequential structure, since the other structures can be reduced or transformed to the sequential structure, using for example, techniques for handling multiple execution paths and unfolding loops [18]. So the qi′(CS) can be computed by aggregating the corresponding published values of component services.Definition 1 (abstract metaworkflow).
For an abstract workflowℑ′, it is an abstract metaworkflow if all its contained abstract services need to bind with a candidate service.Definition 2 (abstract subworkflow).
For an abstract metaworkflowℑ′′⊆ℑ, it is an abstract sub-workflow of ℑ  ifthe solution of composite application corresponding to ℑ′′ is also a solution of composite application corresponding to ℑ.Definition 3 (feasible selection).
For a given abstract workflowℑ and a vector of global QoS constraints C′={c1′,c2′,…,cm′},1≤m≤r, which refer to the user’s requirements are and expressed in terms of a vector of upper (or lower) bounds for different QoS criteria, we consider a selection of concrete services CS to be a feasible selection, if and only if it contains exactly one service for each service class Si of a sub-workflow of ℑ and its aggregated QoS values satisfy the global QoS constraints; that is, q1′(CS)≤ck′,   for all  k∈[1,m].In order to evaluate the overall quality of a given feasible selectionCS, a utility function U′ is used which maps the quality vector QCS into a single real value, which is defined as follows:
(1)U′(CS)=∑k=1rQmax′(k)-qk′(CS)Qmax′(k)-Qmin′(k)·wk
with wk∈R0+,∑k=1rwk=1 being the weight of qk′ to represent user’s priorities,
(2)Qmin′(k)=Fj=1n(min∀s∈Sjqk(s)),Qmax′(k)=Fj=1n(max∀s∈Sjqk(s))
being the minimum and maximum aggregated values of the kth QoS attribute for composite service CS, and F denoting an aggregation function that depends on QoS criteria shown as in Table 1.Table 1
The considered attributes, their priorities, and aggregation functions.
Type
Attributes (priority)
Function
Summation
Response time (0.2)Latency (0.1)
q
′
(
CS
)
=
∑
j
=
1
n
q
(
s
j
)
Compliance (0.1)Best practices (0.1)Documentation (0.1)
q
′
(
CS
)
=
1
/
n
∑
j
=
1
n
q
(
s
j
)
Multiplication
Availability (0.1)Reliability (0.1)Successability (0.1)
q
′
(
CS
)
=
∏
j
=
1
n
q
(
s
j
)
Minimum
Throughput (0.1)
q
′
(
CS
)
=
min
j
=
1
n
q
(
s
j
)Definition 4 (service selection).
For a given abstract processℑ and a vector of global QoS constraints C′={c1′,c2′,…,cm′},1≤m≤r, the service selection is to find the feasible selection that maximizes the overall utility function U′ value.


### 2.2. The Ant Colony Optimization Algorithm

In nature, foraging ants communicate indirectly by depositing and sensing pheromone trails. This sets up a positive feedback loop that reinforces promising paths. The ACO algorithm is inspired by this behavior of real ants, in which the artificial ants complete a series of walks of a data structure, known as a construction graph. They lay pheromone trails on this graph edges and choose their path with respect to probabilities that depend on pheromone trails and these pheromone trails progressively decrease by evaporation. In most cases, pheromone trails are updated only after having constructed a complete path and not during the walk, and the amount of pheromone deposited is usually a function of the quality of the path. Furthermore, the probability for an artificial ant to choose an edge often depends not only on pheromones, but also on some problem-specific local heuristics. The classical ACO algorithm is shown as Algorithm1.Algorithm 1:ACO_Basic.
Set parameters and Initialize pheromone trails
Begin
bestA = {};    //Take cost({})=∞;
repeat
for each ant kdo
construct an assignment Ak;
iffit(Ak) < fit(bestA) then
bestA=Ak;
endfor;
update pheromone trails;
until the maximum evaluation number is arrived or
the other termination condition is satisfied;
return  bestA;
EndAt each cycle, each ant constructs a complete assignment and then pheromone trails are updated including the pheromone depositing and evaporating. Thefit is a fitness function used to evaluate an assignment. We can see that when using the ACO metaheuristic to solve a new combinatorial optimization problem, one of the main tasks is to model the problem as the search of a feasible minimum cost path over a weighted graph, where the feasibility is defined with respect to a set of constraints.


## 2.1. The QoS-Based Service Selection Problem

For a composite application composed of a set of abstract services𝕊 that is specified as abstract workflow ℑ, each abstract service i,i∈[0,∥𝕊∥-1] corresponds to a service class Si={si1,si2,…,sin}, and Si consists of all services that deliver the same functionality but potentially differ in terms of QoSvalues. Since the value of a QoS attribute is published by the service provider, its value may be positive or negative. We use the vector Qs={q1(s),q2(s),…,qr(s)} to represent the QoS values of service s, and the function qi(s) determines the published value of the ith attribute of the service s. Then, the QoS vector for a composite service consisting of n service components CS={s1,s2,…,sn},n∈[1,∥𝕊∥] is defined as QCS={q1′(CS),q2′(CS),…,qr′(CS)}, where the qi′(CS) is the estimated end-to-end value of the ith QoS attribute. Although many different service composition structures may exist in the workflow, we only focus on the sequential structure, since the other structures can be reduced or transformed to the sequential structure, using for example, techniques for handling multiple execution paths and unfolding loops [18]. So the qi′(CS) can be computed by aggregating the corresponding published values of component services.Definition 1 (abstract metaworkflow).
For an abstract workflowℑ′, it is an abstract metaworkflow if all its contained abstract services need to bind with a candidate service.Definition 2 (abstract subworkflow).
For an abstract metaworkflowℑ′′⊆ℑ, it is an abstract sub-workflow of ℑ  ifthe solution of composite application corresponding to ℑ′′ is also a solution of composite application corresponding to ℑ.Definition 3 (feasible selection).
For a given abstract workflowℑ and a vector of global QoS constraints C′={c1′,c2′,…,cm′},1≤m≤r, which refer to the user’s requirements are and expressed in terms of a vector of upper (or lower) bounds for different QoS criteria, we consider a selection of concrete services CS to be a feasible selection, if and only if it contains exactly one service for each service class Si of a sub-workflow of ℑ and its aggregated QoS values satisfy the global QoS constraints; that is, q1′(CS)≤ck′,   for all  k∈[1,m].In order to evaluate the overall quality of a given feasible selectionCS, a utility function U′ is used which maps the quality vector QCS into a single real value, which is defined as follows:
(1)U′(CS)=∑k=1rQmax′(k)-qk′(CS)Qmax′(k)-Qmin′(k)·wk
with wk∈R0+,∑k=1rwk=1 being the weight of qk′ to represent user’s priorities,
(2)Qmin′(k)=Fj=1n(min∀s∈Sjqk(s)),Qmax′(k)=Fj=1n(max∀s∈Sjqk(s))
being the minimum and maximum aggregated values of the kth QoS attribute for composite service CS, and F denoting an aggregation function that depends on QoS criteria shown as in Table 1.Table 1
The considered attributes, their priorities, and aggregation functions.
Type
Attributes (priority)
Function
Summation
Response time (0.2)Latency (0.1)
q
′
(
CS
)
=
∑
j
=
1
n
q
(
s
j
)
Compliance (0.1)Best practices (0.1)Documentation (0.1)
q
′
(
CS
)
=
1
/
n
∑
j
=
1
n
q
(
s
j
)
Multiplication
Availability (0.1)Reliability (0.1)Successability (0.1)
q
′
(
CS
)
=
∏
j
=
1
n
q
(
s
j
)
Minimum
Throughput (0.1)
q
′
(
CS
)
=
min
j
=
1
n
q
(
s
j
)Definition 4 (service selection).
For a given abstract processℑ and a vector of global QoS constraints C′={c1′,c2′,…,cm′},1≤m≤r, the service selection is to find the feasible selection that maximizes the overall utility function U′ value.


## 2.2. The Ant Colony Optimization Algorithm

In nature, foraging ants communicate indirectly by depositing and sensing pheromone trails. This sets up a positive feedback loop that reinforces promising paths. The ACO algorithm is inspired by this behavior of real ants, in which the artificial ants complete a series of walks of a data structure, known as a construction graph. They lay pheromone trails on this graph edges and choose their path with respect to probabilities that depend on pheromone trails and these pheromone trails progressively decrease by evaporation. In most cases, pheromone trails are updated only after having constructed a complete path and not during the walk, and the amount of pheromone deposited is usually a function of the quality of the path. Furthermore, the probability for an artificial ant to choose an edge often depends not only on pheromones, but also on some problem-specific local heuristics. The classical ACO algorithm is shown as Algorithm1.Algorithm 1:ACO_Basic.
Set parameters and Initialize pheromone trails
Begin
bestA = {};    //Take cost({})=∞;
repeat
for each ant kdo
construct an assignment Ak;
iffit(Ak) < fit(bestA) then
bestA=Ak;
endfor;
update pheromone trails;
until the maximum evaluation number is arrived or
the other termination condition is satisfied;
return  bestA;
EndAt each cycle, each ant constructs a complete assignment and then pheromone trails are updated including the pheromone depositing and evaporating. Thefit is a fitness function used to evaluate an assignment. We can see that when using the ACO metaheuristic to solve a new combinatorial optimization problem, one of the main tasks is to model the problem as the search of a feasible minimum cost path over a weighted graph, where the feasibility is defined with respect to a set of constraints.


## 3. The Clustering Based Ant Colony Algorithm for Service Selection

Obviously, for an application request withn service classes and l candidate services per class, there are ln possible combinations to be examined. So, when the number of functionally-equivalent services offered becomes large, how to effectively shrink the solution space and make the search quickly go right direction is very important. In the CASS algorithm, a skyline query process is used to filter the candidates related to each service class, and an unsupervised clustering process is introduced to partition the skyline services in per service class. Then a directed clustering graph is constructed based on clustering result to abstract the search space and used to guide the ants global searching.Definition 5 (skyline services).
The skyline of a service classS, denoted by SLS, comprises the set of those services in S that are not dominated by any other service; that is, SLS={i∈S∣¬∃j∈S;j≺i}. We regard these services as the skyline services of S.Definition 6 (dominance).
Consider a service classS and two services i,j∈S, characterized by a set of Q of QoS attributes. i dominates j, denoted as i≺j, if i is as good as or better than j in all parameters in Q and better in at least one parameter in Q, that is, for all  k∈[1,|Q|]:qk(x)⩽qk(y) and ∃k∈[1,|Q|]:qk(x)<qk(y).Since not all services are potential candidates for the solution. Thus, a skyline query can be performed on the services in each class to identify those potential candidates for composition. In the CASS algorithm, the skyline query process is implemented using the fast nondominated process in [19]. If the candidate service number in the skyline li⊂Si of a service class Si is more than T, an unsupervised clustering process is used to discover the similar candidate services, and the candidate service ci,j∈Si nearest to the cluster center Ci,j is chosen to represent the service candidates in the jth cluster. Then, a directed clustering graph CG(V,E) which is used as a represented construction graph for ant colony searching is defined, V={vi,j∣vi,j∈(li∧ci,j),i∈[0,∥𝕊∥-1],j∈[0,∥Si∥-1]}∨{vs,vd} and E={〈vi,j,vk,h〉∣(〈Si,Sk〉∈ℑ)∧(vi,j∈V)∧(vk,h∈V),k∈[0,∥𝕊∥-1],h∈[0,∥Sk∥-1]}∨{〈vs,vi,j〉  ∣  fin(vi,j)=0,vi,j∈V}{〈vi,j,vd〉∣fout(vi,j)=0,vi,j∈V}, with vs, vd representing the start point and end point and fin(vi,j) and fout(vi,j) being the in-degree and out-degree of node vi,j. When eighty percent ants deposit the pheromone along the same path p=(Vp,Ep) in CG, an expanding process is used to rebuild a construction graph EG(V,E) based on this path for ants making exploitation, where V={vi,k∣(vi,k∈Ci,j∧ci,j∈Vp),i∈[0,∥𝕊∥-1,k∈[0,∥Si∥-1]]}∨{vs,vd} and E={〈vi,k,vh,q〉  ∣  〈ci,j,ch,m〉∈Ep∧vi,k∈Ci,j∧vh,q∈Ch,m}∨{〈vs,vi,k〉∨〈vi,k,vd〉∣(〈vs,ci,j〉∈Ep∨〈ci,j,vd〉)∧vi,k∈Ci,j}. The pheromone of the new add vertex vi,k is set the same as its related cluster center ci,j. We can see that each vertex in these two graphs is associated with a binding relationship of a service class and its service instance.In the CASS algorithm, the ants communicate by laying pheromone on graph vertices. The amount of pheromone on vertexvi,j is denoted by τ(vi,j). Intuitively, the amount of pheromone represents the learnt desirability of binding the service class Si with its jth service instance. As proposed in the MAX-MIN ant system [10], we explicitly impose lower and upper bounds τmin and τmax on pheromone trails (0<τmin<τmax). The goal is to favor a larger exploration of the search space by preventing the relative differences between pheromone trails from becoming too extreme during processing. Also, pheromone trails are set to τmax at the beginning of the algorithm to achieve a higher exploration of the search space during the first cycle. The way for an ant constructing a complete assignment is outlined in Procedure 1.For a given antk that is building the assignment Ak and is currently at the vertex vij, its feasible neighborhood in the construction G(V,E) (i.e., CG or EG defined above) is defined as Nbrk(vi,j)={vp,q∣〈vij,vp,q〉∈E∧vp,q∈V}. The probability for this ant to select the vertex vp,q in its feasible neighborhood is computed as follows:
(3)pro(〈vp,q,Ak,vi,j〉)=[τ(vp,q)]α[η(vp,q)]β∑v∈Nbrk(vi,j)[τ(v)]α[η(v)]β,
where τ(vp,q) is the pheromone factor of vertex vp,q, η(vp,q) is its heuristic factor, and α and β are the parameters that determine their relative weights. A main difference with many ACO algorithms is that the heuristic factor η(vp,q) depends on the whole current set of visited vertices in Ak. It is inversely proportional to the number of new violated constraints when adding vp,q to Ak and computed as follows:
(4)η(vp,q)=11+vcons(Ak∪vp,q)-vcons(Ak).After every ant has constructed a complete assignment, the pheromone trails are updated. All pheromone trails are decreased uniformly in order to simulate evaporation and allow ants to forget bad assignments, and then the best ants of the cycle deposit pheromone. More formally, at the end of each cycle, the quantity of pheromone on each vertex is updated as in Procedure2, where ρ is the evaporation rate, 0≤ρ≤1, and ElitistsofCycle contains the best N assignments constructed during the current cycle. The Δτ(Ak,v) is the quantity of pheromone that should be deposited on vertex v. It is defined as follows:
(5)Δτ(Ak,v)={11+fit(Ak),ifv∈Ak,0,otherwise,fit(Ak)={1-U′(Ak),ifvcons(Ak)=0,1,otherwise.
We can see that the fitness value of an assignment is decided by both its utility value and whether any constraint has been violated by it. Based on the above descriptions, the framework of CASS algorithm can be formulated as Algorithm 2.Algorithm 2:CASS.
Set parameters and Initialize pheromone trails
Begin
for  each service class  do
use the skyline query process to identify its skyline services;
Clustering the skyline services into several different clusters;
endfor;
build the clustering graph and make it as the initial construct graph;
repeat
ElitistsofCycle = {};
for  each ant k  do
construct an assignmentAk using Procedure 1;
iffit(Ak)<fit(bestA) then
bestA = Ak;
endfor;
find the bestN assignments and add them intoElitistsofCycle;
update pheromone trails using Procedure2;
if  (eighty percent ants obtained the same assignment) then
use the expanding process to fractionize the construction graph;
endif.
until the maximum evaluation number is arrived or
the other termination condition is satisfied;
return  bestA;
EndProcedure 1:Updating the pheromones.
Begin
for  each vertex v in the construction graph  do
τ(v)=(1-ρ)·τ(v)+∑Ak∈ElitistofCycleΔτ(Ak,v)
if  τ(v)<τmin  then  τ(v)=τmin;
if  τ(v)<τmax  then  τ(v)=τmax;
endfor
EndProcedure 2:Construct assignment by ant k.
Begin
Ak={vs};
repeat
Select a vertexv from the ant feasible neighborhood with a probability;
Move the ant to this vertex,Ak = Ak∨{v};
until (v==vd)
EndIn this paper, the ant-based clustering algorithm proposed in [18] is used for the clustering process. Based on the clustering result, a cluster graph is constructed which provides insight into the large scale service selection problem space and is exploited to predict the subspace crucial to search. When a promising search area is identified, a dynamically expanding process is used to fractionize it for ants exploitation, which greatly improves the solving quality.


## 4. Experimental Evaluation

In this section, we present an experimental evaluation of our approach, focusing on its efficiency in terms of execution time and the quality in terms of the obtained best solution fitness value, and compare it with the recently proposed related algorithms DiGA [7], SPSO [8], and MPDACO [15] on different scale test instances. All algorithms are implemented in C++ language and executed on a Core (i7), 2.93 GHZ, 2 GB RAM computer.


### 4.1. Experimental Setup

In our evaluation we experimented with two types of datasets. The first is the publicly available updated data set called QWS (http://www.uoguelph.ca/~qmahmoud/qws/index.html), which comprises measurements of nine QoS attributes for 2507 real-world web services used in this paper. These attributes, priorities, and their aggregation functions are shown in Table 1. These services were collected from public sources on the web, including UDDI registries, search engines, and service portals, and their QoS values were measured using commercial benchmark tools. More details about this dataset can be found in [3]. We also experimented with three synthetically generated datasets in order to test our approach with larger number of services and different distributions through a publicly available synthetic generator (http://randdataset.projects.postgresql.org/): (a) a correlated data set (cQoS), in which the values of QoS parameters are positively correlated, (b) an anticorrelated (aQoS) data set, in which the values of the QoS parameters are negatively correlated, and (c) an independent dataset, in which the QoS values are randomly set. Each dataset contains 25000 QoS vectors, and each vector represents the nine QoS attributes of the one web service. Since all other models can be reduced or transformed to the sequential model using the techniques for handling multiple execution paths and unfolding loops [20], the sequential composition model is focused on in this paper. For the purpose of our evaluation, we considered a scenario, where a composite application comprises 10 different service classes. Each of the aforementioned datasets is randomly partitioned into the 10 service classes. Through this way, six different scale test instances are created and shown as in Table 2. The T1, T2, and T3 are built from QWS data set, and the other three are built from our synthesized datasets. Tc4 (2500) denotes a composite application with ten service classes, and each service class contains 2500 candidate services from the correlated data set. We then created several QoS vectors of up to 9 random values to represent the user end-to-end QoS constraints. Each QoS vector corresponds to one QoS based composition request, for which one concrete service needs to be selected from each class, such that the overall utility value is maximized, while all end-to-end constraints are satisfied.Table 2
The obtained fitness values for the compared algorithms (best/worst/average).
Instances
DiGA
SPSO
MPDACO
CASS
T1(150)
0.1455/0.1614/0.1555
0.1468/0.1573/0.1536
0.1455/0.1501/0.1481
0.1455/0.1529/0.1481
T2(200)
0.1595/0.1798/0.1677
0.1546/0.1561/0.1549
0.1521/0.1562/0.1539
0.1521/0.1559/0.1533
T3(250)
0.1474/0.1637/0.1562
0.1469/0.1519/0.1476
0.1426/0.1503/0.1464
0.1415/0.1470/0.1447
Tc4(2500)
0.1705/0.1884/0.1808
0.1694/0.1829/0.1796
0.1724/0.1865/0.1780
0.1676/0.1819/0.1742
Ta5(2500)
0.1753/0.1899/0.1818
0.1621/0.1845/0.1732
0.1683/0.1862/0.1795
0.1597/0.1763/0.1698
Ti6(2500)
0.1768/0.1890/0.1834
0.1689/0.1775/0.1746
0.1792/0.1860/0.1829
0.1627/0.1740/0.1685


### 4.2. Comparative Results

We run each algorithm twenty times on each test instance. The termination condition for all the algorithms on each test instance is set based on the maximum candidate evaluation number, which is set as3*104. The colony size is set as 50 and the other parameters of the CASS algorithm are set as follows: α=2,β=8,ρ=0.02,τmax=4.0,τmin=0.01, and N=5. The parameters of the other three compared algorithms are set as the same as the original papers. We do not made much effort in finding the best parameter settings and leave this task for a future study based on the I-race package [21]. We run each algorithm twenty times on each test instance. The obtained best, worst, and average fitness values are given in Table 2, and the average consuming time for the compared algorithms on each test instance is shown in Figure 1. In order to show the solutions distribution more clearly, the fitness value fi obtained by an algorithm for ith run is converted to a value ri using the following rule:
(6)ri=fi-fbestfworst-fbest,
where fworst and fbest are the minimum fitness value and maximum fitness value found by all the compared algorithms for this test instance. Then the solutions distribution based on r value is shown as in Figure 2. The comparisons of their convergence properties for different scale problem are given in Figure 3.Figure 1
The compare of the time consumed.The Boxplots of ther value distributions.
(a)
T1
(b)
T2
(c)
T3
(d)
Tc4
(e)
Ta5
(f)
Ti6The comparison of the convergent speed on different instances.
(a)
T1
(b)
T2
(c)
T3
(d)
Tc4
(e)
Ta5
(f)
Ti6From Figure1, we can see that the CASS algorithm is faster than the other three compared algorithms for the test instances Tc4, Ta5, and Ti6 and slower than the other algorithms for T1, T2, and T3. The larger the test instance scale is, the faster it is than the other algorithms. This is mainly because the preprocessing phrase for skyline query process and the clustering process will occupy more proportion of the consuming time when the test instance is not large enough. From Table 2, we can clearly get that the proposed CASS algorithm performed greatly better than the compared algorithms. It obtained smaller upper bound, smaller average and smaller lower bound of fitness value which can be further proved by Figure 2. From this figure, we can see that the r values of most solutions obtained by CASS algorithm are better than the average r values of the solutions obtained by the other algorithms. The average convergence rate in 20 runs for each algorithm on different scale test instances are shown as in Figure 3 which can indicate the convergence properties of these algorithms explicitly. We can obtain that the CASS algorithm converges not faster than the compared other algorithms, but it is not easily trapped into local optimum and its convergent point is the best. So, we can conclude that the proposed CASS algorithm outperforms the compared methods in terms of the utility score, as well as execution time, and possesses competitive performance for the large scale service selection problem.


## 4.1. Experimental Setup

In our evaluation we experimented with two types of datasets. The first is the publicly available updated data set called QWS (http://www.uoguelph.ca/~qmahmoud/qws/index.html), which comprises measurements of nine QoS attributes for 2507 real-world web services used in this paper. These attributes, priorities, and their aggregation functions are shown in Table 1. These services were collected from public sources on the web, including UDDI registries, search engines, and service portals, and their QoS values were measured using commercial benchmark tools. More details about this dataset can be found in [3]. We also experimented with three synthetically generated datasets in order to test our approach with larger number of services and different distributions through a publicly available synthetic generator (http://randdataset.projects.postgresql.org/): (a) a correlated data set (cQoS), in which the values of QoS parameters are positively correlated, (b) an anticorrelated (aQoS) data set, in which the values of the QoS parameters are negatively correlated, and (c) an independent dataset, in which the QoS values are randomly set. Each dataset contains 25000 QoS vectors, and each vector represents the nine QoS attributes of the one web service. Since all other models can be reduced or transformed to the sequential model using the techniques for handling multiple execution paths and unfolding loops [20], the sequential composition model is focused on in this paper. For the purpose of our evaluation, we considered a scenario, where a composite application comprises 10 different service classes. Each of the aforementioned datasets is randomly partitioned into the 10 service classes. Through this way, six different scale test instances are created and shown as in Table 2. The T1, T2, and T3 are built from QWS data set, and the other three are built from our synthesized datasets. Tc4 (2500) denotes a composite application with ten service classes, and each service class contains 2500 candidate services from the correlated data set. We then created several QoS vectors of up to 9 random values to represent the user end-to-end QoS constraints. Each QoS vector corresponds to one QoS based composition request, for which one concrete service needs to be selected from each class, such that the overall utility value is maximized, while all end-to-end constraints are satisfied.Table 2
The obtained fitness values for the compared algorithms (best/worst/average).
Instances
DiGA
SPSO
MPDACO
CASS
T1(150)
0.1455/0.1614/0.1555
0.1468/0.1573/0.1536
0.1455/0.1501/0.1481
0.1455/0.1529/0.1481
T2(200)
0.1595/0.1798/0.1677
0.1546/0.1561/0.1549
0.1521/0.1562/0.1539
0.1521/0.1559/0.1533
T3(250)
0.1474/0.1637/0.1562
0.1469/0.1519/0.1476
0.1426/0.1503/0.1464
0.1415/0.1470/0.1447
Tc4(2500)
0.1705/0.1884/0.1808
0.1694/0.1829/0.1796
0.1724/0.1865/0.1780
0.1676/0.1819/0.1742
Ta5(2500)
0.1753/0.1899/0.1818
0.1621/0.1845/0.1732
0.1683/0.1862/0.1795
0.1597/0.1763/0.1698
Ti6(2500)
0.1768/0.1890/0.1834
0.1689/0.1775/0.1746
0.1792/0.1860/0.1829
0.1627/0.1740/0.1685


## 4.2. Comparative Results

We run each algorithm twenty times on each test instance. The termination condition for all the algorithms on each test instance is set based on the maximum candidate evaluation number, which is set as3*104. The colony size is set as 50 and the other parameters of the CASS algorithm are set as follows: α=2,β=8,ρ=0.02,τmax=4.0,τmin=0.01, and N=5. The parameters of the other three compared algorithms are set as the same as the original papers. We do not made much effort in finding the best parameter settings and leave this task for a future study based on the I-race package [21]. We run each algorithm twenty times on each test instance. The obtained best, worst, and average fitness values are given in Table 2, and the average consuming time for the compared algorithms on each test instance is shown in Figure 1. In order to show the solutions distribution more clearly, the fitness value fi obtained by an algorithm for ith run is converted to a value ri using the following rule:
(6)ri=fi-fbestfworst-fbest,
where fworst and fbest are the minimum fitness value and maximum fitness value found by all the compared algorithms for this test instance. Then the solutions distribution based on r value is shown as in Figure 2. The comparisons of their convergence properties for different scale problem are given in Figure 3.Figure 1
The compare of the time consumed.The Boxplots of ther value distributions.
(a)
T1
(b)
T2
(c)
T3
(d)
Tc4
(e)
Ta5
(f)
Ti6The comparison of the convergent speed on different instances.
(a)
T1
(b)
T2
(c)
T3
(d)
Tc4
(e)
Ta5
(f)
Ti6From Figure1, we can see that the CASS algorithm is faster than the other three compared algorithms for the test instances Tc4, Ta5, and Ti6 and slower than the other algorithms for T1, T2, and T3. The larger the test instance scale is, the faster it is than the other algorithms. This is mainly because the preprocessing phrase for skyline query process and the clustering process will occupy more proportion of the consuming time when the test instance is not large enough. From Table 2, we can clearly get that the proposed CASS algorithm performed greatly better than the compared algorithms. It obtained smaller upper bound, smaller average and smaller lower bound of fitness value which can be further proved by Figure 2. From this figure, we can see that the r values of most solutions obtained by CASS algorithm are better than the average r values of the solutions obtained by the other algorithms. The average convergence rate in 20 runs for each algorithm on different scale test instances are shown as in Figure 3 which can indicate the convergence properties of these algorithms explicitly. We can obtain that the CASS algorithm converges not faster than the compared other algorithms, but it is not easily trapped into local optimum and its convergent point is the best. So, we can conclude that the proposed CASS algorithm outperforms the compared methods in terms of the utility score, as well as execution time, and possesses competitive performance for the large scale service selection problem.


## 5. Conclusions

To tackle the large scale service problem, we propose the CASS algorithm in this paper which is based on the ACO algorithm, the skyline query technique, and the clustering technique. The results of experiment evaluation indicate that our approach excels in both utility and execution time. It not only provides a useful way to solve the service selection problem but also can give a reference for solving other optimization problem. There are a number of research directions that can be considered as useful extensions of this research. We can combine it with some local search strategy or hybrid it with other meteheuristic algorithms. Furthermore, how to tackle the QoS uncertainty during service selection in the CASS algorithm is our next studying problem.



---

*Source: 815193-2013-07-10.xml*