Parameter Tuning for S-ABCPK: An Improved Service Composition Algorithm Considering Priori Knowledge

Parameter Tuning for S-ABCPK: An Improved Service Composition Algorithm Considering Priori Knowledge

Ruilin Liu (School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China), Zhongjie Wang (School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China) and Xiaofei Xu (School of Computer Science and Technology, Harbin Institute of Technology, Harbin, China)
Copyright: © 2019 |Pages: 22
DOI: 10.4018/IJWSR.2019040105

Abstract

QoS-aware service composition problem has been drawn great attention in recent years. As an NP-hard problem, high time complexity is inevitable if global optimization algorithms (such as integer programming) are adopted. Researchers applied various evolutionary algorithms to decrease the time complexity by looking for a near-optimum solution. However, each evolutionary algorithm has two or more parameters, the values of which are to be assigned by algorithm designers and likely have impacts on the optimization results (primarily time complexity and optimality). The authors' experiments show that there are some dependencies between the features of a service composition problem, the values of an evolutionary algorithm's parameters, and the optimization results. In this article, the authors propose an improved algorithm called Service-Oriented Artificial Bee Colony algorithm considering Priori Knowledge (S-ABCPK) to solve service composition problem and focus on the S-ABCPK's parameter turning issue. The objective is to identify the potential dependency for designers of a service composition algorithm easily setting up the values of S-ABCPK parameters to obtain a preferable composition solution without many times of tedious attempts. Eight features of the service composition problem and the priori knowledge, five S-ABCPK parameters and two metrics of the final solution are identified. Based on a large volume of experiment data, S-ABCPK parameter tuning for a given service composition problem is conducted using C4.5 algorithm and the dependency between problem features and S-ABCPK parameters are established using the neural network method. An experiment on a validation dataset shows the feasibility of the approach.
Article Preview

1. Introduction

In the service era, people’s lives rely more and more on the services delivered via the Internet. An evident trend is that user requirements are increasingly complicated, and no single service could completely fulfill a coarse-grained requirement (Liu and Wang, 2012). It is necessary to compose the functionalities of multiple web services. This is called “service composition” (Zeng, Benatallah et al. 2003; Rao and Su, 2005; Dustdar and Schreiner, 2005). A typical service composition problem is to consider a set of end-to-end QoS constraints (local and global) raised by customers and look for an optimal composite solution to satisfy these QoS constraints or called QoS-aware service composition problem (Zeng, Benatallah et al. 2004; Alrifai and Risse, 2009).

A key issue in solving QoS-aware service composition problem is the time complexity. This is because the number of candidate Web services is likely to be large (Canfora, Di Penta et al. 2005, July), and the selection of the best services from candidates to compose a solution that meets the QoS constraints is time-consuming and has been proven to be NP-hard (Mabrouk, Beauche et al. 2009). Researchers have proposed various algorithms to decrease the time complexity, such as skyline-based approach (Alrifai, Skoutas et al. 2010), approximation-based approaches (Yu, Zhang et al. 2007), fuzzy logic approaches (de Gyves Avila and Djemame, 2013), cuckoo search approaches (Boussalia and Chaoui, 2014), evolutionary algorithm-based approaches, etc. Among them, evolutionary algorithm shows better performance and has been widely applied. There are many frequently used evolutionary algorithms, such as genetic algorithm (Canfora, Di Penta et al. 2005, June), particle swarm optimization (Chen and Wang, 2007; Zhang, 2014). Among them, Artificial Bee Colony (ABC) algorithm is the simplest but a relatively powerful one (Karaboga and Basturk, 2008; Wang, Wang et al. 2013; Liu, Wang et al. 2014). It has only three control parameters, besides the procedure of ABC is simple to understand and implement (Karaboga and Akay, 2009; Akay and Karaboga, 2009). The summary and comparison among the several evolutionary algorithms are shown in Table 1. Researchers have applied ABC into service composition problems and have confirmed its superiority compared with other evolutionary optimization algorithms (Wang, Wang et al. 2013; Xu and Liu, 2014).

Table 1.
A summary of evolutionary algorithms
AlgorithmSearching carrierSolution carrierOptimization methodControl parameters
Particle swarm optimizationparticlesparticle positionusing self-experiences and swarm experiences to amend each particle moveSN, w, C1, C2, Vmax, Vmax, MCN
Ant colony optimizationantspath of antsusing historical paths of the swarm to guide individual ants’ path seekingSN, α, β, ρ, η, MCN
Simulated annealingmoleculesmolecule positiontime-varying probability of accepting inferior new positionsSN, T0, λ, β, MCN
Genetic algorithmindividualsChromosome codingselection, crossing, and mutation of individualsSN, α, β, MCN
Artificial bee colony algorithmforaging beesfood source positionexploration and exploitation to food sourcesSN, Limit, MCN

* SN is the size of searching carriers, MCN stands for the termination condition. The meaning of other parameters can be found in related books.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 16: 4 Issues (2019): 2 Released, 2 Forthcoming
Volume 15: 4 Issues (2018)
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing