Hybridizing Artificial Bee Colony with Bat Algorithm for Web Service Composition

1  Introduction

The service-oriented architecture represents the user needs as business processes and uses a composition of reusable Web Services (WSs) based on the standard protocols [1]. In case of these needs are complex, a set of WSs are integrated to fulfill them. The task of integrating the WSs and optimizing their selection based on the user needs with the different QoS constraints is called web service composition (WSC). To this end, different WSs are retrieved from different providers, producing WSs achieve similar functional and non-functional constraints, such as quality of services (QoS).

In WSC, the clients submit their needs, represented as workflow (business processes) containing a set of tasks (n); each task represents a specific task of these needs. Then, a set of WSs (m) are retrieved according to the functionality of the task with different QoS features. As a result, The WSC has mn possible solutions, so it is represented as an NP-hard problem [2]. Fig. 1 shows the model of the WSC problem.

Figure 1: The WSC problem representative model

To solve the WSC problem, different nature-inspired improvements were proposed, such as Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), artificial bee colony (ABC), Whale Optimization Algorithm (WOA), bat algorithm (BA), Cuckoo Search (CS),.. etc. The main concerns on these improvements are convergence rate and execution time to search for the best solutions while the available WSs/task increases.

In the Internet of things (IoT), the users have complex needs, and the WSC problem was introduced to address these needs, especially since these needs increased while the disease outbreak [3,4]. The search for optimal WSs combination to satisfy these needs requires high computation time that increases while the WSC scale increases. In this work, we introduce an extension of our previous works on improving the ABC [5–7] and BA [8]. A new hybrid algorithm was proposed between the ABC and BA to achieve a better tradeoff between local exploitation and global search. The bat agent is used to improve the solution of exhausted bees after a threshold (limits), and also an elitist strategy (ES) is added to BA to increase the convergence rate.

The paper is organized as follows: Related work is explained in Section 2. The basic algorithms background and the proposed hybrid algorithm are presented in Section 3. The experiment and analysis are represented in Section 4. Section 5 describes the paper’s conclusion.

2  Related Work

Different nature-inspired approaches have been used to address the WSC problem and obtain the near-optimal web service combination. In the following sub-section, a review of the state-of-the-art research was introduced.

2.1 ABC Related Work

Seghir [9] proposed an enhancement to the ABC algorithm based on the fuzzy distance and ranking methods. This enhancement aims to enhance the search diversity of the bees. The neighborhood search is introduced in [10] to enhance the ABC search, and the opposition learning method is applied to initialize the population. The proposed algorithm is named Optimized Artificial Bee Colony (OABC). Arunachalam et al. [11] proposed an enhancement to the ABC algorithm based on the integrated probability with rule-based acceptance. This enhancement aims to maintain the exploration and exploitation of ABC.

An enhancement-based neighborhood search was proposed by Dahan et al. [5]. The proposed algorithm used an adaptive neighborhood search based on the distance of the neighbors. Dahan et al. [6] use an additional step to improve the exploitation of the search space knowledge of the best bees using the swapped method. Chandra et al. [12] introduce the enhancement of ABC exploration and exploitation mechanism based on the search procedure and differential evolution. Seghir et al. [13] also enhanced the neighborhood selection using the interval-based method. Arunachalam et al. [14] used the combinatorial strategical method and cosine similarity to improve the ABC search. This cosine similarity supports ABC exploitation combinatorial strategical search for exploration. Li et al. [15] added the genetic algorithm to the ABC to improve the ABC searching. Karthikeyan et al. [16] introduced an enactment to ABC based on the genetic algorithm. Dahan et al. [7] introduced an enactment to ABC based on the cuckoo search. The ABC with Pareto dominance is used in Zhou et al. [17,18]. The proposed algorithm used the CS Lévy flight in the employed phase to enhance the search in [17], the onlookers phase in [18], and an adaptive parameter strategy is also introduced.

2.2 BA Related Work

Boussalia et al. [19] proposed an extension for the BA algorithm. The proposed algorithm had three different features. The first feature was an adaptation for BA to work with the WSC problem. Next, a constructive heuristic method was used to initialize the population. Finally, a transformation for the real solutions to binary vectors was proposed, and heuristic reparation was to verify and correct the transformation of real solutions. Podili et al. [1] introduced an evaluation of BA and hybrid BA against particle swarm optimization and genetic algorithm. Boussalia et al. [20] introduced two multi-objective algorithms based on CS and BA. For the CS-inspired, quantum computing integrates with CS where the measurement operator, the quantum mutation, and the qubit representation from quantum computing were added to the core of the CS to improve the CS performance. An adaptation for BA was adapted to work with the WSC problem for the BA-inspired. Xu et al. [21] introduced a bat algorithm with a Fuzzy operator. The Fuzzy operator is used for coding and encoding the obtained solution to redefine the velocity. Whereas virtual bats are created based on each bat, a crossover operator is between them. Xu et al. [22] introduced a bat algorithm with three flight behaviors. Two behaviors are introduced based on the local and global resetting mechanisms to improve exploration and exploitation. The third one is the investigation of the differences between the flying and resetting mechanisms. Dahan [8] proposed an enhancement to BA based on three strategies: improved the initialization and searching of BA agents. The self-adaptive Doppler with local search is introduced in [23] to enhance the BA search mechanism.

2.3 Nature-Inspired Algorithms Related Work

Recently, various researchers applied other nature-inspired algorithms in the face of finding the best possible web services path. Allali et al. [24] proposed enhancing the ACO-based algorithm based on mobile agents. Wang [25] added the genetic algorithm to enhance the search process of the ACO. The multi-pheromone with a neighboring selection process was added to ACO [26]. The multi-agent ACO is introduced by Dahan [27]. The improved eagle algorithm is introduced in [28]. Dogani et al. [29] enhanced the PSO based on the genetic algorithm.

Subbulakshmi et al. [30] introduced an enhancement to the CS based on the genetic algorithm. Ghobaei-Arani et al. [31] introduced an enhancement to the CS based on the distributed network. The e Lévy flight enhancement was added to the CS Kouchi et al. [32]. Wang et al. [33] enhanced the CS using local optimization and the credibility of service. Zhao et al. [34] enhanced the CS using linear population reduction and parameter adaption. Thangaraj et al. [35] used CS to address the WSC. Kurdi et al. [36] proposed a multi-cuckoo to address the WSC. The eagle strategy uniform mutation was added to WOA by Jin et al. [37]. The potential energy convergence with aggregation logarithmic was introduced to enhance the WOA [38]. Dahan [39] proposed an enhancement to WOA based on three strategies: improved the initialization and searching of WOA agents.

The nature-inspired algorithms proposed above have a stochastic behavior which leads to no guarantees of finding the best solution. Based on the No-Lunch-Free theorem (NLF) [40], the different optimization algorithms cannot obtain enough good solutions for optimization problems.

3  Basic Algorithms Background and Proposed Algorithm

3.1 Artificial Bee Colony (ABC)

ABC is a nature-inspired algorithm introduced by Karaboga [41] in 2005. It has the advantages of a few numbers of parameters and easy-to-use. The ABC parameters are maximum iterations (T), searching limitations (limits), and population size (N). The bees in ABC are divided into three searching procedures: employed procedure, onlooker procedure, and scout procedure. These procedures started after the initialization of all bees randomly. Then, the solution quality is measured based on the problem-based fitness function, and the ABC algorithm memorizes the best solution. This step is common between the initialization and these procedures, where the ABC memorizes the best solution after comparing the best solution memorized with the current solution.

In the first procedure, the bees start exploring and recording the nectar of their food sources based on the neighborhood search using Eq. (1). Afterward, they return to the beehive and share the food source information with the onlooker bees using the swing dance. Then, the food source value is calculated.

vij=xij+φ(xij−xkj)(1)

where vij denotes the candidate food position, xij is the current solution, xkj represents the solution selected from neighborhood search, and φ∈[−1,1].

In the second procedure, each bee is recruited by an employed bee based on the probability of the employed bee’s solution quality calculated using Eq. (2). Similar to employed bees, the onlooker bees search for new solutions based on the neighborhood search using Eq. (1). Then, the food source value is calculated.

pi=fit(xi)∑l=1Nfit(xl)(2)

where fit represents the solution quality of ith food source. N is the source number.

In the third procedure, the bees monitor the searching process of employed and onlooker bees, and the exhausted solution (poorer bees) is abandoned. Then the scout bees re-initialize the poorer bees into a new food source using Eq. (3).

xij=xmin,j+rand(0,1)(xmax,j−xmin,j)(3)

where xij represents the new jth solution for ith bees. xmax,j,xmin,j are the maximum and minimum fitness values of the jth solution during the search in the iteration.

3.2 Bat Algorithm (BA)

BA [42] simulates the bats’ echolocation behavior, where it builds a scenario of three-dimensional surroundings based on the echo emission and detection time delay, two ears time difference, and echo loudness variations. The BA process is started by initializing the loudness (Ait) and pulse emission rate (rit) of the bats using Eqs. (4) and (5), respectively. Then, the solution quality is measured based on the problem-based fitness function, and the BA memorizes the best solution Eqs. (5) and (6)

Ait+1=∝(Ait)(4)

rit+1=[1−exp⁡(−α)](5)

where t is a timestamp, α represents a user-specified variable between [0–1].

In each iteration, the bats’ positions are updated using Eqs. (6)–(8).

fit=fmint+(fmaxt−fmint)∗rand()(6)

where fmint, fmaxt are the minimum and maximum frequencies. rand () is a random variable between [0–1].

vit=vit−1+(xit−x∗)fit(7)

where vit−1 is the previous velocity. xit, x∗ are the current and best bat positions, respectively.

xit+1=xnew+vit(8)

where xnew denotes the new bats’ positions that are computed using Eq. (9)

xnew=xit+randi[−1,1]Ait(9)

Then, the food source value is calculated, the best solution will be compared with the best solution memorized, and the BA algorithm will memorize the best one.

3.3 The Proposed Hybrid Algorithm (ABC-BA)

The proposed algorithm combines the ABC and BA algorithms with an elitist strategy. We selected ABC because it has the advantage of few control parameters and easy implementation [6]. The idea behind this combination is to help the ABC algorithm to overcome its slow convergence disadvantages. The scout procedure is replaced by the BA with the ES algorithm in the proposed algorithm to avoid ABC’s slow convergence limitation. Fig. 2 presents the process of the proposed algorithm, and in the following subsections, we will describe the main process in detail.

Figure 2: ABC-BA Flowchart

3.3.1 Step1: Initialization

The initialization step of the proposed algorithm is to generate a solution for each bee randomly. This solution contains a web service for each task in the total of m web services. The random selection is a number between 1 and m, where m is the number of WS retrieved for each task. To calculate the fitness of each solution, the WSC is represented as a multi-bjective optimization problem where the QoS constraint values either need to be maximized or minimized. In this work, four QoS constraints have adopted the Cost (C), Response Time (RT) (Their objective values are to be minimized), Reliability (R), and Throughput (T) (Their objective values are to be maximized). The reference-based method [37] is adopted in this work. In the reference-based method, the multi-objective optimization vectors are converted into single-objective based on the QoS constraints aggregation function shown in Table 1. The fitness formula of each solution calculation is shown in Eq. (10). For clarity, the user preferences regarding the QoS constraints are unified, so they aren’t reflected in Eq. (10).

Fi=(∏j=1nTjb+∏j=1nRjb−∑j=1nCjb−∑j=1nRTjb)(10)

where n is the number of tasks, Fi is the solution’s fitness, and i represents the ith bee/bat.

3.3.2 Step2: Employed Procedure

In the employed procedure, each bee searches for a new solution based on the neighborhood search. The employed bees are initialized in step 1 and use Eq. (1) to select the new solutions. In WSC, the solutions represent a complete path, which contains a web service for each task as WS1,x′b,WS2,x′b,WS3,x″b,…WSn,xb where b the ith bee, 1,2,3,..n are the task sequence, and x′, x″, x″, .., x are web services between 1 and m.

In Eq. (1), a loop from 1 to the n tasks is used to create a new solution path for each bee. For each path, the current web service is replaced based on the current web service and another web service from another selected solution represented by k with a random value represented by φ.

The solution fitness is obtained using Eq. (10), and the best solution of the employed bees will be compared with the best solution memorized, and the proposed algorithm will memorize the best one.

3.3.3 Step3: Onlooker Procedure

In the onlooker procedure, the bees monitor the employed bees after their tour. The employed bees share their solution quality and recruit the onlooker bees based on the fitness probability. Eq. (2) calculates the employed bees' fitness probability. After the recruitment, the onlooker bees repeat the same process as an employed procedure for searching for a new solution.

The solution fitness is obtained using Eq. (10). The best solution for the onlooker bees will be compared with the best solution memorized, and the proposed algorithm will memorize the best one.

3.3.4 Step4: BA Optimization

In the proposed algorithm, the process of the scout procedure is replaced by the BA with ES. The process of the BA is described in Section 3.2 with modification based on the ES [43] applied. The idea behind ES is to enhance the convergence rate of the proposed algorithm. In ES, the two best solutions are allowed to be survived in the next iterations; these are the best local solution in each iteration (SIbest) and the best global solution among all bats (SGbest). The SIbest and SGbest are calculated based on the solutions’ fitness, and the selection formulas are shown in Eqs. (11) and (12).

SIbest=max(iteration−based fitness value)(11)

SGbest=max(distance fitness value)(12)

The SIbest and SGbest values are obtained using Eq. (10).

After selecting SIbest and SGbest, their values will be compared with new values based on the iteration or bats. Then, SIbest and SGbest will be updated using Eqs. (13) and (14), respectively.

SIbest={SIbestt−1=SIbesttiff(t)≥f(t−1)SIbestt=SIbestt−1iff(t)≤f(t−1)(13)

SGbest={SGbestt−1=SGbesttifD(t)≥D(t−1)SGbestt=SGbestt−1ifD(t)≤D(t−1)(14)

Based on the ES, a modification of bats’ basic formulas search, velocity, and frequency equations are required to attain a better tradeoff among searching mechanisms using Eqs. (15)–(18) [43].

fit=min(SGbestt)+(max(SGbestt)−min(SGbestt))rand()max(SIbestt)(15)

vit=vit−1+(SGbestt−SIbestt)fit(16)

xnew=SGbestt+randi[−1,1](17)

xit+1={SGbesttif rand>rixnew+vitotherwise(18)

where i refer to ith bat at iteration t and rand is a random value between 0 and 1.

4  Results and Discussion

Several experimental aspects are used to evaluate the performance competitiveness and effectiveness of the ABC-BA algorithm compared to the different nature-inspired algorithms.

4.1 Experimental Settings

Different datasets resources were used to compare the proposed algorithm’s performance with other real-world datasets called QWS 2.0 [44] and generated randomly [45].

From the QWS 2.0, we created the small-size datasets (first dataset group) where the number of tasks size is kept constant, and the WSs in each task are different in a total of 23000 WSs. The experiments on small-size datasets aim to show the proposed algorithm’s capabilities compared to the competitors on the local exploitation [46] because these datasets’ dimensionality (search space) is small.

From the generated random datasets, we created the medium-size and large-size datasets (second dataset group) where the number of WSs in each task is kept constant, and the tasks are different in a total of 52000 WSs. The experiments using these datasets aim to show the proposed algorithm’s capabilities compared to the competitors on the global search [46] because the dimensionality of these datasets is large compared to the first dataset group. A description of the datasets used in this work is shown in Table 2.

To ensure a level of unbiased and fair experiments, we implemented all algorithms in Java using Windows 10 with Intel(R) Core(TM) i7-7500U CPU @ 2.70 GHz and 8.0 GB RAM. In addition, four algorithms were used to compare the ABC-BA performance, which are ABC_CS [7], MOHABC [17], SABC [6], and OABC [10]. The parameters setting of these algorithms is set based on their works preferences. Table 3 presents the initial values of the ABC-BA parameters. There are some common parameters between the ABC-BA and other algorithms: the iteration numbers (Z) set to 500 and the population (P) set to 100.

4.2 Comparative Results Discussion

According to the dataset groups, two types of experiments are conducted to validate the performance competitiveness of ABC-BA. The first experiment is conducted on the first group of the dataset to validate the local exploitation capabilities of the ABC-BA, while the second experiment is conducted on the second group of the dataset to validate the global search capabilities of the ABC-BA. In the 30 different runs, the Average Fitness Value (AFV) of each algorithm, best fitness values (BFV), and execution time were measured. These three criteria were the comparison evaluation criteria for ABC-BA compared to the competitors.

The notched boxplot is used to visualize the empirical distribution of results obtained by all competitors in terms of the AFV, as shown in Figs. 3–5. More detailed results can be observed using notched boxplots, which show the numerical data distribution. Figs. 3–5 show the average fitness value distributions over all competitors for small, medium, and large datasets, respectively. In addition, Table 4 presents the empirical results of all competitors in terms of best fitness value and average execution time over all datasets.

Figure 3: The AFV of compared algorithms for the small-size datasets

Figure 4: The AFV of compared algorithms for the medium-size dataset

Figure 5: The AFV of compared algorithms for the large-size dataset

4.2.1 Local Exploitation Validation Experiments

In this experiment, the local exploitation capabilities of the proposed algorithm compared to other algorithms are verified on small-size datasets. Fig. 3 presents the AFV of the proposed algorithm and competitors in 30 independent runs. As seen from the figure, the ABC-BA has a concentrated AFV, which means that the AFV is better because the median value is larger than others. In addition, the ABC-BA hasn’t an outlier value and better stability.

Fig. 3 also shows that the ABC_BA results significantly differ because the AFV of ABC_BA has no notches overlapping over all datasets. In addition, the boxplots of ABC_BA are significantly higher than others.

As seen in Table 4, the proposed algorithm has the best BFV values of competitors’ on all small datasets, which indicates the competitive performance of ABC_BA in convergence accuracy.

Table 4 shows that the proposed algorithm is not the best in terms of execution time because the proposed enhancement needs more time. However, the convergence accuracy of these algorithms’ average and best fitness values are worse than that of the ABC_BA.

4.2.2 Global Search Validation Experiments

In this experiment, the global search capabilities of the proposed algorithm compared to other algorithms are verified on medium-size and large-size datasets, as shown in Figs. 4 and 5, respectively. Figs. 4 and 5 present the AFV of the proposed algorithm and competitors in 30 independent runs. As seen from the figure, the ABC-BA has a concentrated AFV, which means that the AFV is better because the median value is larger than others. In addition, the ABC-BA hasn’t an outlier value and better stability.

Figs. 4 and 5 also show that the ABC_BA results significantly differ because the AFV of ABC_BA has no notches overlapping over all datasets. In addition, the boxplots of ABC_BA are significantly higher than others except for DS 9.

Table 4 shows that the proposed algorithm is not the best in terms of execution time because the proposed enhancement needs more time. However, the convergence accuracy of these algorithms’ average and best fitness values are worse than that of the ABC_BA.

4.3 Result Significance Test

The Wilcoxon signed-rank test with a p-value shown in Table 5 presents the statistically significant results of ABC_BA and competitors over all datasets in terms of average fitness value. The last row in the table shows the test summary, where the s indicates the number of datasets where the results are significant, and w means the opposite. Table 5 shows that ABC_BA significantly differs from other algorithms on all datasets.

5  Conclusion

WSC problem aims to find the optimal web services combination to meet user needs. The complexity of this problem is the many services that achieve the functions with different QoS Constraints. The WSC is an NP-hard problem. This work proposes an extension of our previous work for the WSC problem. Previously, we introduced different enhancements for ABC and BA algorithms, and recently, we introduced a hybridization algorithm between these two algorithms and applied the ES to enhance the convergence of the proposed method. In the proposed work, the scout procedure of ABC was replaced by the BA process, and the process of BA was updated to adopt the ES process. The performance and convergence behavior of the proposed hybrid algorithm was tested using extensive comparative experiments with current state-of-the-art nature-inspired algorithms on 12 benchmark datasets using three evaluation criteria (average fitness values, best fitness values, and execution time) that were measured for 30 different runs. The benchmark datasets were based on real measurements of web services and artificial-based datasets. The results show that the proposed algorithm enhances the search performance and increases the convergence rate on finding the near-optimal web services combination compared to competitors. The results also show a limitation of the proposed algorithm, where it is slower in terms of execution time compared to other algorithms. In future work, we plan to investigate other nature-inspired algorithms, such as the whale optimization algorithm, to address such a problem and keep the superiority of the results in terms of the average fitness and best fitness values.

Acknowledgement: The authors would like to express their gratitude to Prince Sattam bin Abdulaziz University, Al-Kharj 11942, Saudi Arabia for providing the support.

Funding Statement: The authors extend their appreciation to the Deputyship for Research and Innovation, Ministry of Education in Saudi Arabia for funding this research work through the project number 2022/01/22636.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.