Article Preview
Top1. 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
| Algorithm | Searching carrier | Solution carrier | Optimization method | Control parameters |
| Particle swarm optimization | particles | particle position | using self-experiences and swarm experiences to amend each particle move | SN, w, C1, C2, Vmax, Vmax, MCN |
| Ant colony optimization | ants | path of ants | using historical paths of the swarm to guide individual ants’ path seeking | SN, α, β, ρ, η, MCN |
| Simulated annealing | molecules | molecule position | time-varying probability of accepting inferior new positions | SN, T0, λ, β, MCN |
| Genetic algorithm | individuals | Chromosome coding | selection, crossing, and mutation of individuals | SN, α, β, MCN |
| Artificial bee colony algorithm | foraging bees | food source position | exploration and exploitation to food sources | SN, 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.