Neighborhood Search Based Improved Bat Algorithm for Web Service Composition

1  Introduction

Service-Oriented Architecture is a software architecture where compassable functional units, self–contained, and stateless services are utilized to build distributed systems with loosely-coupled styles [1]. The user needs are represented using a business process where these services deal with these processes and may be combined and interacted with other services to deal with the business process [2]. However, the users’ needs and the services created and published by various organizations are overgrowing. A composite service can be integrated to address this issue, called web service composition (WSC) [3]. The WSC can be initiated through the users’ needs as a workflow submission; each need is represented as a task in the workflow along with quality of service (QoS) requirements such as availability, cost, response time, and so on [4].

In the WSC illustrated in Fig. 1, the workflow has a sequence of tasks n, and each task has a set of candidate web services m. Each web service is represented as WSij where i refers to the task serial number and j refers to the candidate web service to carry out the ith task. The solution of the WSC is a concrete path of web services as vector WS1,X, WS2,X’,…, WSn,X’’ where the vector dimension equals the number of tasks.

Figure 1: The WSC problem representation

Each web service in the cloud is associated with non-functional constraints and functionality. Therefore, these constraints represent the preference criteria when selecting web services. The non-functional constraints could be QoS, semantic functional, energy consumption, etc. In this work, four QoS constraints are considered as follows:

■   Cost (C): represents the fee for using the service, and it is measured in any currency.

■   Response Time (RT): represents the time to send and receive the service request and response. It is measured in milliseconds.

■   Availability (A): represents the successful call to the total calls of services, measured in percentage.

■   Reliability (R): represents the ratio of the number of errors to the total number of messages of services. It is measured in percentage.

For optimizing the WSC problem, the QoS constraints values are aggregated into a single value to estimate the solution quality based on their objective value. The C and RT objective values are minimized, while the A and R objective values are maximized. The aggregation formulas of QoS constraints are illustrated in Tab. 1.

Recently, nature-inspired algorithms have been widely adopted in service composition to search for optimal service composition. These algorithms are meta-heuristics that inspired the insects’ swarm intelligence behavior, such as ant colony optimization [5], particle swarm optimization [6], and artificial bee colony [7]. The difference between these algorithms is the local and global search mechanisms, and the balance of these mechanisms is required for getting an optimal solution [8]. In this work, an existing nature-inspired algorithm was considered, i.e., the bat algorithm (BA), for solving to solve WSC problem. In the research community, the BA has become more popular optimize searching for an optimal solution to various optimization problems [9]. BA was introduced by Yang et al. [9] that was inspired by the microbats’ echolocation behavior, especially prey obstacle avoidance and detection. The microbats use the echolocation feature for food (prey) detection and obstacle avoidance. For food detection, the bat emits a short pulse to produce an echo where the bat can determine the prey size and shape. The BA performance has several issues associated with global searches, local optima, convergence rate, tradeoff factor among local, and population initialization [8].

In this work, the contribution to addressing the BA shortcomings is given as:

- Population initialization: The nature-inspired algorithms’ performance is significantly impacted by the population initialization [10,11]. The bad initialization can lead to premature convergence for future iterations [8]. Therefore, a cooperative and adaptive population initialization mechanism is introduced in this work.

- Convergence rate: The nature-inspired algorithms search for an optimal solution through a cooperative behavior of exploration and exploitation search mechanism. The convergence rate can be affected if a lack of collective behavior is found. An elitist mechanism is utilized to address the BA convergence rate by maintaining the cooperative behavior of the exploration and exploitation search mechanism.

- Local optima: An efficient neighborhood search mechanism is proved to achieve a better tradeoff between exploration and exploitation of nature-inspired algorithms [12]. In addition, it is an effective tool to overcome the local optima [8]. Therefore, an updated variant of the neighborhood search mechanism proposed in our previous works [12,13] is proposed.

2  Related Works

The recent research reported on BA-inspired algorithms for the WSC problem is summarized in this section. To the best of our knowledge, few works are developed to address the WSC problem using BA, discussed below.

Boussalia et al. [14] 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 vector was proposed, and heuristic reparation to verify and correct the transformation of real solutions. Podili et al. [15] introduced an evaluation of BA and hybrid BA against genetic algorithm and particle swarm optimization. Boussalia et al. [16] proposed two multi-objective algorithms based on cuckoo search and BA. For the cuckoo search inspired, quantum computing integrates with cuckoo search where the measurement operator, the quantum mutation, and the qubit representation from quantum computing were added to the core of the cuckoo search to improve the cuckoo search performance. For the BA-inspired, an adaptation for BA was adapted to work with the WSC problem. Xu et al. [17] introduced a bat algorithm with a Fuzzy operator to address the WSC problem in the cloud. 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. [18] proposed a self-adaptive bat algorithm with three flight behaviors. Two behaviors are introduced to improve the exploration and exploitation based on the local and global resetting mechanisms. The third one is the investigation of the differences between the flying and resetting mechanisms.

Recently, various researchers applied other swarm intelligence algorithms in the face of finding the best possible web services path. El Allali et al. [19] introduce a framework to address the WSC problem based on the ant colony optimization and the mobile agents. A hybrid algorithm ant colony optimization and the genetic algorithm is introduced in [20]. Li et al. [21] improved the convergence speed of the artificial bee colony algorithm using the genetic algorithm. Seghir [22] proposed an improved artificial bee colony algorithm based on the fuzzy ranking method to improve the artificial bee colony algorithm diversity. Teng et al. [23] proposed enhancing the whale optimization algorithm based on the logarithmic convergence factor and aggregation potential energy. The authors in [6] applied the mutation, nonlinear convergence factor, and chaos initialization to improve the whale optimization algorithm performance. The improved eagle algorithm is introduced in [24]. Dogani et al. [25] introduced a hybrid particle swarm optimization and genetic algorithm where the genetic algorithm is used to enhance the exploration and exploitation of particle swarm optimization.

The aforementioned bat-inspired algorithms have a limitation of guaranteeing the best web services path because of the stochastic behavior of the nature-inspired algorithms. In addition, the No-Lunch-Free theorem (NLF) [26] states that the optimizers are unable to find good enough to address all optimization problems. Therefore, the algorithms mentioned above cannot efficiently solve large-scale datasets and suffer from degraded performance. This discussion motivates the work of developing new optimization algorithms to address the WSC that introduces better evaluation factors for optimization algorithms which are the efficient performance and execution time [27,28].

3  Bat Algorithm (BA)

BA is inspired by the microbats’ echolocation behavior, especially prey obstacle avoidance and detection [9]. The microbats determine the size and shape of the prey by emitting a short pulse to get the nearby objects’ echoes. The BA simulates the prey detection of the microbats as follows:

First: initialize the pulse emission rate ( rit ) and bat loudness ( Ait ) using Eqs. ‎(1) and (2)

Ait+1= ∝(Ait) (1)

rit+1=[1−exp(−α)] (2)

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

Second: The bats’ velocity ( vit ) and frequency ( fit ) are computed using Eqs. ‎(3) and (4)

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

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

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

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

Third: The bats’ positions are updated using Eq. ‎(5)

xit+1=xnew+vit (5)

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

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

4  Improved Bat Algorithm (IBA) for WSC

The BA proposed improvements are presented in this section and shown in Fig. 2. These improvements are (1) a proposed population initialization method, (2) achieving a better convergence rate using an elitist method (3) achieving a better tradeoff between search mechanisms to avoid local optima using the neighborhood method.

Figure 2: IBA flowchart

4.1 Initialization Cooperative Method

The best initialization of the bats affects the search performance in future iterations, and the most used initialization approach is the random approach. To improve the performance of the proposed algorithm, an adaptive and cooperative initialization method is proposed based on the divide and conquer paradigm. In the proposed initialization method, the workflow is divided into sub workflows based on the number of tasks where each sub-workflow can be solved individually. Then these sub workflows solutions will be combined to obtain the final solution.

The Sub Workflows (SW) are obtained adaptively based on the size of the tasks in the workflow, as mentioned in Eq. ‎(7).

SW=(nP) (7)

where n is the number of tasks, and P is the population size.

The population size is duplicated according to the number of the sub workflows where each population searches for a solution in the sub workflows sequentially. The sub-population sizes are obtained as mentioned in Eq. ‎(8).

{P1=1toPP2=P+1toP∗2P3=P∗2+1toP∗3..Pn=P∗(n−1)+1toP∗β (8)

where β is the number of population partitions.

Each subpopulation’s solution is computed using Eq.‎ (9) to initialize the main bat population. Then the probability of each bat in the subpopulation among all bats is calculated using Eq. ‎(10). The combination of the sub workflows to initialize the main population is done regarding the probability of each solution based on the roulette wheel approach.

argmaxp∈P(f)=∑i=1nWaAip+RipWcCip+WrtRTip (9)

where p represents a bat 1 ≤ p ≤ P; Wx are the client preferences regarding QoS limitations that are adopted in this work, and x refers to the QoS limitations, which include availability weight (Wa), reliability weight (Wr), cost weight (Wc), and response time weight (Wrt).

Prop=fp∑iP⁡fi (10)

where fp refers to the fitness value of bat p obtained from Eq. ‎(9).

4.2 Elitist Strategy

In this work, the elitist strategy is inspired by [8], which contributes to enhancing the convergence speed rate of BA. The algorithm search pattern is the main factor of convergence speed, so the elitist strategy in this work is adapted and adjusted to accommodate the WSC problem. Accordingly, the best solution moves through future iterations.

In the elitist strategy, the iteration best solution (SIbest) can be defined as the best solution among all bats in each iteration (maximum value of iteration based fitness value f(t)). In contrast, the global best solution (SGbest) can be defined as the best solution among all bats in all iterations (maximum value of distance-based fitness value D(t)). The iteration best and global best solutions are obtained from the fitness values of the bats during a search for optimal solutions using 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. ‎(9).

The SIbest and SGbest values are compared with the fitness values of the following iterations. If the next fitness values are better than the current values, the SIbest and SGbest are 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)

The formulas mentioned above require modifying the bats’ basic formulas search, velocity, and frequency equations to attain a better tradeoff among searching mechanisms using Eqs.‎ (15)–(18) [8].

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={SGbesttifrand > rixnew+vitotherwise (18)

where i refer to ith bat at iteration t.

4.3 Neighborhood Search

An updated variant of the neighborhood search mechanism proposed in our previous works [12,13] is proposed. An adaptive neighborhood search mechanism has been proved to achieve a better tradeoff between exploration and exploitation of nature-inspired algorithms [12]. In addition, it is an effective tool to overcome the local optima [8]. Previously in [12,13], the neighborhood search was based on the neighborhood web services of the best web services selected so far. However, this process is time-consuming depending on the number of neighborhood web services. In this work, the neighborhood search is improved to be done using the neighborhood bats where:

First: Check the improvement status in the current iteration; if there is no improvement, then continue to the neighborhood search procedure; else, terminate the neighborhood search procedure.

Second: A Random Number (RN) of neighborhood bats is selected in a case where 1 ≤ RN ≤ P.

Third: For each neighborhood bat, a mutation is applied where a randomly selected task in the workflow will be mutated with a task value from the iteration best solution.

5  Experimental Setup and Results

The simulation results of the IBA are represented in this section. Since there are no standard datasets for WSC [18], in this work, the synthetic dataset is generated using the tool introduced in [29] for simulation in five datasets. All datasets are a large scale where the number of tasks (n) is 100, 200, 300, 400, and 500, and the number of web services in each dataset equals 2*n. The idea behind these large-scale datasets is the growing number of providers and the expansion in the demands for web services over the cloud. Therefore, the larger-scale datasets are necessary to test the algorithms’ performance [18] rather than small-scale datasets. The QoS constraints (C, A, RT, and R) values are generated arbitrarily from 1 to 1000 for each web service. All algorithms shown in this work are implemented using Java, and all experiments are conducted on a PC Intel(R) Core(TM) i7-7500U CPU @ 2.70 GHz and 8.0GB RAM of memory.

5.1 Experimental Setup

In this simulation, four bat-inspired algorithms are chosen for comparison purposes. These algorithms are the standard BA, Random Bat Algorithm (RBA) [18], Self-Adaptive Bat Algorithm (SABA) [18], and BA-WSC [14]. The control parameter of RBA, SABA, and BA-WSC are set as mentioned in their works, except for the population size (P) and maximum iterations (Z), where they are set to 100 and 500, respectively. The adaptive behavior of the IBA reduces the parameter setting where the neighborhood bats, sub workflows, and neighborhood bats are obtained automatically. For other parameters, the initial values are listed in Tab. 2.

5.2 Improvement Strategies Verification

The proposed algorithm is composed of three different improvement strategies (Initialization Cooperative (IC), Elitist Strategy (ES), and Neighborhood Search (NS)). This section will assess the effectiveness of these three improvements on the BA incrementally. To test the effectiveness of all improvement strategies, the three instances of the proposed algorithm were created and compared to BA. The three instances are IBA-IC (the proposed algorithm with the initialization cooperative method only), IBA-ES (the proposed algorithm with elitist strategy and initialization cooperative methods), and IBA (proposed algorithm with all improvement strategies). The experiments were done on all datasets with only one run and similar parameters mentioned above.

Fig. 3 illustrates the fitness value curve of the BA, IBA-IC, IBA-ES, and IBA on all datasets based on 500 maximum iterations. It is clearly noticed from the figure that the IC method increases the start search point and effects on enhancing the solution quality compared to the BA. These results support the abovementioned claim that the nature-inspired algorithms’ performance is significantly impacted by the population initialization [10,11]. However, the random searching behaviors may contribute to the searching results during the execution, so we can see from the result on dataset 400 × 800 that the IBA-IC suffers from local optima. As a result, the BA outperforms it.

Figure 3: Fitness value curve obtained using the three IBA instances compared to BA on 500 iterations

The elitist strategy was added to the IBA-IC and notated as IBA-ES. In the IBA-ES, the elitist strategy behavior is tested along with the initialization cooperative on the BA to see the improvement of ES. It can be seen from Fig. 3 that the ES improves the convergence speed and stability of the IBA-IC among the large-scale datasets. These results support the abovementioned claim that the algorithm search pattern is the main factor of convergence speed, so the elitist strategy in this work is adapted and adjusted to accommodate the WSC problem.

Finally, the neighborhood search was added to the IBA-IC and IBA-ES and notated as IBA. NS aims to achieve a better tradeoff between exploration and exploitation of BA. The results show that the IBA performance is enhanced compared to the IBA-ES performance, and this is because of the proposed algorithm’s best balancing of exploration and exploitation ability.

The results above prove the applicability of the three proposed enhancements to improve BA performance. The first enhancement aims to enhance the search starting points and convergence speed; the second enhancement was proposed. The exploration and exploitation were enriched using the third enhancement to improve the performance.

5.3 Convergence Speed of IBA Compared to Other Algorithms

To verify the stability of the IBA compared to other algorithms, the convergence speed of IBA was reached using 500 iterations in one run. Fig. 4 illustrates all algorithms’ convergence rates overall algorithms.

Figure 4: Fitness value curve obtained using the IBA, BA, RBA, BA-WSC, and SABA over all datasets

It is clearly seen that the IBA outperforms all competitors where it has a fast convergence rate. The figure also depicts that the IBA has the best initial value, which confirms the effectiveness of the IC method in improving the initialization process of the bats. Furthermore, the figure illustrates that the competitors suffer from local optima with a different level where their convergence rates have fluctuated. For example, the results on dataset 200 × 400 show that the RBA algorithm achieves better results than IBA; however, this achievement didn’t continue because it suffers from local optima after approximately iteration number 300, and IBA then overcomes it. The reasonable IBA convergence rate is because of the ES and NS mechanism’s collaboration, which helps IBA avoid the local optima and achieve better exploration and exploitation behavior.

5.4 Result Comparison of IBA Compared to Other Algorithms

In this subsection, the simulation results are discussed of the IBA, standard BA, and three bat-based algorithms of related works using the five large-scale datasets with 30 different runs and 500 maximum iterations. The results are evaluated the average fitness value, an average execution time, and the Standard Deviation (Std) of the fitness value. Tab. 3 reports the fitness values average and standard deviation by implementing the five algorithms to address the WSC problem overall datasets obtained from 30 independent runs. The best results are highlighted in bold. As shown in Tab. 3, The IBA outperforms BA, RBA, BA-WSC, and SABA in all datasets. Furthermore, we can observe that the proposed mechanism, especially the elitist strategy, effectively improves the convergence rate and the solution quality.

Figs. 5 and 6 illustrate the Boxplot relative to 30 different runs of the IBA, BA, RBA, BA-WSC, and SABA over all datasets. The Boxplots are utilized to analyze the optimizers’ variability to get the average fitness value and average execution time in MilliSeconds (MS) in all the runs. In Fig. 5, the Boxplots justify and confirm the better performance of IBA compared to the competitors in terms of the average fitness value. In Fig. 6, the Boxplots show the competitive performance of IBA compared to the competitors in terms of the average execution time.

Figure 5: Boxplots representation of the average fitness value of the IBA, BA, RBA, BA-WSC, and SABA over all datasets

Figure 6: Boxplots representation of the average execution time of the IBA, BA, RBA, BA-WSC, and SABA over all datasets

The abovementioned results depict, on average, that the IBA outperforms the standard BA and other competitors. Wilcoxon’s rank-sum statistical test is conducted to confirm the significance of IBA compared to the competitors in each independent run and evaluate the overall performance. Tabs. 4 and 5 show the Wilcoxon test results at a significance level of 0.05 in terms of average fitness value and execution time. In the table, “−”, “+”, “=” denotes that the competitors’ performance is worse, better than, or equal to the version of IBA, respectively.

Tab. 4 shows that the IBA provides the best results for all datasets, and the results also show that the IBA exhibits better stability and an increase in the scale of the datasets. Furthermore, Tab. 5 indicates that the IBA algorithm provides the best execution time for all the datasets. It gives the best execution time than BA-WSC and SABA on four datasets. The IBA has competitive results compared to BA.

6  Conclusion

In this work, three improvements are proposed to improve the BA performance for the web service composition problem. The proposed improvements efficiently deal with BA’s population initialization, convergence speed, exploration, and exploitation balancing issues. A cooperative and adaptive population initialization mechanism is developed to resolve the population initialization problem. An elitist strategy is utilized to address the BA convergence rate. Furthermore, a neighborhood search mechanism is designed to achieve a better tradeoff between exploration and exploitation searching mechanisms. The IBA performance is tested using five large-scale datasets compared to the standard BA and three bat-based algorithms of related works. The IBA achieves better quality solutions results in average fitness value, standard deviation fitness value, and average execution time.

Furthermore, the effect of the three proposed improvements was investigated, and their applicability was proved. It is observed from the simulation results that introduced enhancement obtains significant results compared to four bat-inspired algorithms. In the future, we are planning to continue the investigation of using different nature-inspired algorithms to solve the WSC problem and their hybridization.

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

Funding Statement: The author extend their appreciation to Deputyship for research & Innovation, Ministry of Education in Saudi Arabia for funding this research work through the Project Number (IF-PSAU-2022/01/19619).

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