1 Introduction

I n response to the deteriorating economic situation, the fast changing market demands and the rapid rise of human costs, more and more small and medium manufacturing enterprises in China are becoming united to take risks and responsibilities together to overcome current challenges and achieve their common interests and goals. This unification means that the production resources and manufacturing capabilities of the enterprises are shared together. With the rapid development of Internet of Things (IoT), cloud computing, mobile computing, big data analytics [1,2,3,4,5,6,7,8,9, 10] and industrial techniques [11, 12], cloud manufacturing mode (CMM) [13,14,15,16,17,18], as a new manufacturing model making the full use of this sharing, has taken up an increasing important stage. In CMM, three types of roles, including service providers, service platforms and service users, are generally included. Service providers and service users publicize and use services through the platform respectively, which generally includes three key steps [19]: (1) service providers supply the manufacturing resources and capabilities to the platform as encapsulated manufacturing services, such as material resources, equipment resources, human resources, analysis capabilities, production capabilities, and so on; (2) service users release the production demands to the platform, which in general include functional and nonfunctional requirements, the Quality of Service (QoS) indices are always used as nonfunctional indicators; and (3) the platform then analyzes the supplies and demands and makes reasonable divisions of them into small ones. Next, the platform chooses the optimal set of manufacturing services to match the different small demands and to meet the user’s original demand finally. Obviously, to select the optimal manufacturing service composition becomes a very difficult problem when the homogeneous manufacturing services with very different QoS indices increase dramatically. The problem is known as a manufacturing service composition (MSC) problem [20].

Since MSC problem is NP hard [21], solving large scale MSC problems using traditional methods may be highly unsatisfactory. Since heuristic algorithms and intelligent algorithms are effective and efficient approaches for solving NP hard problems [22,23,24,25,26], lots of these kind of algorithms are introduced to deal with MSC problem, such as Genetic Algorithms (GAs) [27,28,29], Differential Evolution (DE) [30, 31], Particle Swarm Optimization (PSO) [32, 33] and so on. In these studies, MSC in different kinds of service-oriented enterprise systems is discussed. However, the scale of the MSC problem, such as the number of sub-tasks and service providers, considered is still small, which shows the limitation of these studies. In the age of the Internet, the demand for intelligent manufacturing is increasingly diversified and personalized, and the manufacturing tasks are divided into a large number of sub-tasks. At the same time, the globalization of manufacturing makes the number of service providers increasing dramatically. Therefore, it is necessary to investigate the MSC problems with large scale, which is one of the main purposes of this work.

Bat Algorithm (BA) proposed by Yang et al. in 2010 [34,35,36] is an optimization algorithm based on the simplified behavior and acoustics of echolocation of bats. The algorithm attracts the attention of many scholars, because of its fast convergence, less control parameters, and easier implementation. They appear to have high performance in numeric optimization. However, there are still some defects in the solution search equation of the BA, which may lead to inferior exploration and premature convergence in the exploitation process.

To improve the search abilities of BA and investigate its performance on MSC problem, a new algorithm called Self-Adaptive based Bat Algorithm (SABA) is proposed by introducing the self-adaptive learning framework into BA with multi-behaviors and dual resetting mechanisms. We perform a comprehensive comparative study of the proposed algorithm with different parameter and strategy settings. The statistical analyses of the experimental results show that the proposed algorithm achieves a better performance compared with DE, PSO and Global and local real-coded genetic algorithms based on parent-centric crossover operators (GL25) [37].

The remainder of the paper is organized as follows. Section 2 discusses the related works. Section 3 presents the MSC problem and generalizes its corresponding optimization model. Section 4 presents the details of the proposed algorithm. Section 5 presents and analyzes the experimental results to investigate the effect of different strategies and to validate our proposed approach. Finally, Section 6 is dedicated to the conclusion.

2 Related works

2.1 Manufacturing service composition problem

MSC problem is the core issue of CMM. In essence, MSC problem is another kind of service composition problem, which is similar as the web service composition problem [20]. The important difference between the web service composition problem and the MSC problem is in the participating roles. The service users and service providers are mainly the enterprises and manufactures, including not only online users, but also the combination of online and offline users in most cases in CMM, which makes the evaluation factor and evaluation mode of the MSC problem different from the web service composition problem. MSC problem has become a hot topic recently. The related research is mainly focused on formulating the model of MSC problem and solving it with a designed algorithm. In [21], considering both software and hardware cloud services in manufacturing systems, the MSC problem is modeled as a multi-objective optimization problem for the first time, which is NP hard. Then, a novel parallel intelligent algorithm is proposed to tackle the problem. Full connection topology based on coarse-grained parallelization and message passing Interface (MPI) collective communication was also adopted in the algorithm for improving the searching efficiency further. In [38], Xiang et al. established MSC model based on QoS and energy-consumption. They use group leader algorithm (GLA) to solve this problem with introducing variation strategies and a one-way and single-point crossover operator. Since the transportation from one resource to another will inevitably increase the cost and processing time when taking into account the resources of the service chain, Lartigau et al. [39] set up MSC model by adding a geo-perspective consideration when evaluating composition. Consequently, they proposed an adapted artificial bee Colony (ABC) algorithm based on enhanced initialization to deal with this MSC problem. Weining Liu et al. [40] extended the MSC model from single-manufacturing task to multi-manufacturing tasks. That is, the platform should choose optimal cloud services composition for many users’ QoS requirements on multi-functionality manufacturing tasks simultaneously. They implemented a hybrid-operator based matrix coded genetic algorithm (HO-MCGA) to tackle this problem and obtain a well performance.

The above studies addressed the different models of MSC problems. It should be noted that the scale of MSC problem in these studies is still relatively small. As a result the approaches cannot meet the demand of the current intelligent manufacturing with increasingly diversity and personality. Therefore it is necessary to investigate MSC problems with large-scale in which the number of service providers are very large and the task is divided into a large amount of sub-tasks at the same time.

2.2 Bat algorithm

BA is a new paradigm proposed by Yang et al. in 2010 [34], which imitates the echolocation behavior of bats during predation. The concept of bat algorithm is simple and easy to implement, it has gained a greater attention in numerical optimization. Pei et al. [41] integrated the BA with Differential Evolution (DE) into a new hybrid algorithm called BA-DE for solving the constrained optimization problems. Comparisons show that BA-DE outperforms most advanced methods in terms of the solution quality. Khooban et al. [42] proposed an intelligent strategy based on a combination of the bat algorithmand the Fuzzy Logic (FL) which is used to optimally tune parameters of Proportional-Integral (PI) controllers in the Automatic Generation Control (AGC). Crossover and mutation operators are introduced to the algorithm to increase the bat population diversity and an adaptive parameter updating strategy is used. Yang [43] extended the basic BA to solve multi-objective optimization problems and it has achieved efficient results in multi-objective optimization. The above works show that BA is a simple but efficient optimization algorithm compared to many other search heuristics. BA and its variants appear to have high performance in numeric optimization. However, there are still some defects in the solution search equation of the BA, which may lead to inferior exploration and premature convergence in the exploitation process.

In this paper, we are proposing three different novel behaviors in our Self-Adaptive based Bat Algorithm to improve the exploration and exploitation abilities of the algorithm for various MSC problems. Although the statistical based self-adaptive learning framework can greatly improve the performance of the intelligent algorithm, using the framework alone is still unable to avoid the premature convergence due to the loss of the population diversity during iterations of the algorithm. Therefore, we are also proposing the dual resetting mechanisms to avoid premature convergence, which is demonstrated to be very effective.

3 MSC problem formulation

Let T = {T 1, T 2, ⋯T i ,  ⋯ , T D } be a complex manufacturing task where D represents the number of sub-tasks of a task. Each sub-task T i consists of C i candidate services \( {S}_i^j \), where i represents the number of the corresponding sub-tasks, j represents the number of candidate services and j = 1 , 2 ,  ⋯  , C i . Each candidate service is evaluated using a QoS indicator set. By comprehensively considering the existing research results [21, 39, 40, 44, 45], the main QoS indices used in MSC problem are as follows:

  1. 1)

    Time t: it refers to the time consumption during the manufacturing. t includes the execution time of the service itself, the transmission time required for the remote service and the time consumed in the process of system interaction.

  2. 2)

    Cost c: c refers to the cost that a service user has to pay for using the capability or resource of the service. To achieve the optimal solution, c should be minimum and is calculated from the maximum price that the service demander is willing to invest independently of the currency.

  3. 3)

    Energy e: according to product overall lifecycle, energy consumption of a single service includes the service preparation stage, the service composition stage, the logistic transportation stage and service configuration, and the service waste disposal stage, the service using stage and the recycled energy after the cancellation of the service [44].

  4. 4)

    Reliability r: it assesses the ability of the service to run normally and continuously. Some of the conventional production index can be used to describe the reliability, such as the average no-failure rate and the average failure rate under a given time and condition. Obviously, service users prefer to choose the service with high reliability.

  5. 5)

    Maintainability m: it refers to the ability that the resource service can cope with unexpected accidents. The maintainability is the proportion of the number of the successfully processed unexpected accidents to the total number of the unexpected accidents.

  6. 6)

    Trust-QoS u:it refers to hold trusting entity ability in a given situation at a time slot that gives it confidence to carry a transaction out with the trusted entity. Trust-QoS is achieved by trust-QoS relationship [45].

  7. 7)

    Reputation v: it refers to the service credibility, which used to measure the ability of the service to achieve its functions in the specified conditions. The evaluation of this attribute is derived from the feedback of the subjective evaluation of the users. Because this value is changed dynamically with the actual situation of the service, it is often evaluated based on the dynamic calculation method to quantify the real time reputation.

Fig. 1 depicts the main flow of the MSC carried out on the platform. It can be seen from Fig. 1 that the goal of the composition of cloud manufacturing services is to select a best path that satisfies the task demands of the service users. Theoretically, there are \( {\prod}_{i=1}^D{C}_i \) service composition paths totally, where D and C i are the number of sub-tasks and the number of candidate services respectively. When D and C i increase, the scale the problem will rapidly increase and thus the problem is NP hard.

Fig. 1
figure 1

The main flow of MSC

Full size image

A service composition path can be expressed as x = {x 1, x 2,  ⋯ , x i ,  ⋯ , x D }, where, x i represents the selected candidate service to execute the ith sub-task, and 1 ≤ x i  ≤ C i . The cloud manufacturing service composition path in the actual scene is a directed graph showing the hybridized path structure which contains a variety of sub-structures, such as sequence, parallel, selective and circular sub-structures. Generally, the parallel, selective and circular structure can be converted into sequence structure when evaluate the path with QoS indices according to several reduction principles [33]. Thus, the MSC problem in this paper is modeled based on the sequence structure. In this structure, the QoS parameter values of each service S i is \( q\left({S}_i^j\right)=\left\{{q}_1,{q}_2,\cdots, {q}_m\right\} \), m = 7, namely \( q\left({S}_i^j\right)=\left\{t,c,e,r,m,u,v\right\} \).

The QoS indices of the whole service composition path can be expressed as Q = {Q 1,  ⋯ , Q m } = {T, C, E, R, M, U, V}, in which each index is evaluated by the specific rules according to the characteristics of the QoS index of the manufacturing services itself. The calculation methods of T , C , E , R , M , U , V are shown in Table 1 with the computing rules including SUM, PRODUCT and AVERAGE.

Table 1 QoS calculation method in MSC
Full size table

The objective of finding the optimal path is to minimize T , C , E while maximizing R , M , U , V, which is consistent with the above description of each QoS index. It is a constrained multi-objective optimization problem. In this paper, the problem is transformed into a constrained single objective optimization problem with the commonly used weighted sum method in order to facilitate the calculation. Thus, the objective function of MSC problem is as follows, which is also the fitness function used in the proposed algorithm:

$$ f\left(\mathrm{x}\right)={w}_1T\left(\mathrm{x}\right)+{w}_2C\left(\mathrm{x}\right)+{w}_3E\left(\mathrm{x}\right)-{w}_4R\left(\mathrm{x}\right)-{w}_5M\left(\mathrm{x}\right)-{w}_6U\left(\mathrm{x}\right)-{w}_7V\left(\mathrm{x}\right) $$
(1)
$$ \min f\left(\mathrm{x}\right) $$
(2)
$$ {\displaystyle \begin{array}{l}s.t.\\ {}\left\{\begin{array}{c}\hfill q\left({S}_i^j\right)\mathrm{satisfies}\kern0.17em \mathrm{each}\;\mathrm{QoS}\;\mathrm{index}\kern0.17em \mathrm{demands}\kern0.17em \mathrm{in}\;\mathrm{MSC}\hfill \\ {}\hfill 1\le j\le {C}_i\hfill \\ {}\hfill 1\le i\le D\hfill \\ {}\hfill {\sum}_{i=1}^D{w}_i=1\hfill \end{array}\right.\end{array}} $$
(3)

where {w 1, w 2, … , w 7} are the corresponding weights for each QoS index and each of them is set to the 1/7 in this paper.

4 The proposed algorithm

The proposed algorithm is detailed in subsections 4.2–4.7 as follows:

4.1 The original bat algorithm

The bats use ultrasound to detect space and foods. In the process of predation, bats can find food by adjusting flight route based on the current environmental information. In BA, the bats in the feasible region update flight speeds and adjust positions according to their own status. Each bat uses the change of the acoustic pulse frequency f i  to detect the gap between its own position and the position of the food, and then uses it to adjust the speed and direction. The new position of ith bat \( {x}_i^t \) and velocity \( {v}_i^t \) at time step t are updated by

$$ {f}_i={f}_{min}+\left({f}_{max}-{f}_{min}\right)\beta $$
(4)
$$ {v}_i^t={v}_i^{t-1}+\left({x}_i^t-{x}_{\ast}\right){f}_i $$
(5)
$$ {x}_i^t={x}_i^{t-1}+{v}_i^t $$
(6)

where β ∈ [0, 1] is a random vector from a uniform distribution, and x ∗ is the current global best location (solution) in the population. The product\( \left({x}_i^t-{x}_{\ast}\right){f}_i \) is the velocity increment used to adjust the velocity change to make an exploration over the searching space. Initially, each bat is randomly assigned a frequency which is drawn uniformly from [f min , f max ]. The values of f min and f max are predefined depending on the domain size of the problem of interest.

The steps of the basic algorithm are as follows:

  • Step 1: Initialize the bat position x i (i = 1, 2,  ⋯ , N) and velocity v i , define pulse frequency f i at x i , and initialize pulse rates r i and the loudness A i .

  • Step 2: Select individual i, adjust the frequency and update velocity to generate new solutions;

  • Step 3: If rand ≥ r i , select a solution among the best solutions, and generate a local solution around the selected best solution.

  • Step 4: Generate a new solution by flying randomly.

  • Step 5: Evaluate the solutions.

  • Step 6: If (rand < A i  & f(x i ) < f(x ∗)), accept the new solutions, and increase r i and reduce A i .

  • Step 7: Rank the bats and find the current best x ∗.

  • Step 8: If the algorithm satisfies the stopping criteria, output the best individual, otherwise go to Step 2.

4.2 Self-adaptive bat algorithm

Based on the basic BA, a Self-Adaptive Bat Algorithm (SABA) is proposed to solve the MSC problem. Three novel flight behaviors are introduced below to update the position of the bat, a Local and a Global resetting mechanisms are adopted to prevent the premature convergence of the algorithm, which greatly improves the exploration and exploitation ability of the algorithm on MSC problem. The mapping between the model of BA and the MSC problem is shown in the Table 2.

Table 2 The mapping between the model of BA and the MSC problem
Full size table

Therefore, searching for an optimal service composition path to solve the MSC problem is equivalent to the process of searching for the best food source in the feasible search space in BA.

4.3 Overall algorithm procedure

The main steps of SABA are described as follows:

  • Step 1: Initialization: Initialize the population and the parameters in the algorithm and evaluate the fitness value of each bat in the population.

  • Step 2: Behavior selecting: For each bat i, generate a new position new_x i from x i according to the behavior selected by roulette wheel selection.

  • Step 3: Adaptive learning: If the new position new_x i is better than the original x i , then replace x i with new_x i , update the behavior selected probability by equation (13) and (14), then set NET i to 0, otherwise set NET i to NET i  + 1.

  • Step 4: Local resetting: If the NET i reaches the predefined threshold LIMIT, reset all the behaviors selected probabilities of bat i to 1/M.

  • Step 5: Gbest bat updating: If the generated new bat position new_x i is better than that of Gbest bat, then replace the Gbest bat with the new one and set the NET value NET gbest of Gbest bat to 0; otherwise, set NET gbest to NET gbest  + 1.

  • Step 6:Global resetting: If the NET gbest reaches the LIMIT_GBEST, the whole algorithm is reset with Gbest bat and FEs preserved.

  • Step 7:Termination: If the termination condition is satisfied, then output the current optimal solution, otherwise go to step 2.

Fig. 2 gives the framework of SABA and the details of the steps are given in the following section.

Fig. 2
figure 2

The framework of SABA with Local and Global resetting

Full size image

4.4 Initialization

Given that the population size is N, the foraging space of bats is D dimensional which is the same as the problem dimension. The initial population {x 1, x 2,… , x N } is generated randomly, where x i are the positions of the bats. The dth dimension of position x i is generated by

$$ {x}_i^d=\left[{lb}^d+{\left({ub}^d-{lb}^d\right)}^{\ast}\mathit{\operatorname{rand}}\left(0,1\right)\right] $$
(7)

where lb d and ub d are the lower and upper bounds of the value of dth dimension respectively. rand(0, 1) is a function which generates a random value between 0 and 1. [] represents a rounding operation. It can be seen that \( {x}_i^d \) is a uniformly distributed random value in the range of [lb d, ub d].

The fitness values f(x i ) are calculated by (1). The current best fitness value and the corresponding position are marked as f best and x best respectively, and the related bat is called Gbest bat in this paper.

4.5 Behavior selection

BA is easy to suffer from premature convergence since all the flying directions of bats are concentrated to the current best location x best . To alleviate the premature convergence and enhance the exploration capability of the algorithm, multi-behaviors are designed for each bat in SABA.

The new position new_x i of bat i is generated based on the different flight behavior B i (i = 1, 2, 3), which is chosen by the roulette wheel selection strategy according to the behavior selected probabilities of each bat. The behaviors are detailed as follows.

In Behavior 1 (B1), the new_x i is generated by

$$ new\_{x}_i={x}_i+\left[{F}_1\left({x}_{r1}-{x}_i\right)\right]+\left[{F}_2\left({x}_{gbest}-{x}_i\right)\right] $$
(8)

where x r1 is a position randomly sampled from current bat population, x r1 − x i is the difference vector between x r1 and the current bat x i , which makes a wider range of exploration; x gbest  − x i refers to another difference vector between the optimal bat location in the population and the current bat x i , which is used to maintain the specific search direction towards optimal region. F 1 ∈ [−1, 1] and F 2 ∈ [0, 2] are random values drawn from a uniform distribution. [] is rounding symbol. It can be observed that two difference vectors are added to the base vector to perform perturbation so as to ensure the diversity of the population. The sum of two vectors replaces the speed vector of the original BA and can be adjusted in a certain range by two mutation factors F 1 and F 2 to ensure the speed of convergence and avoid falling into local optima.

In Behavior 2 (B2), the dth dimension of new_x i is generated by

$$ new\_{x}_i^d=\left[{x}_{best}^d+F\times N\left(0,\left({ub}^d-{lb}^d\right)\times \mathit{\operatorname{rand}}\left(0,1\right)\right)\right] $$
(9)

where F is the random value of [−1, 1] satisfied the uniform distribution. [] is rounding operator. N(0, (ub d − lb d)∗ rand(0, 1)) is a value drawn from the normal distribution that mean is 0 and deviation is (ub d − lb d)∗ rand(0, 1). \( {x}_{best}^d \) is the dth dimension of the optimal position in the current population. It is implied from (9) that new solutions can keep certain changes in the neighborhood of optimal solution. It can not only ensure optimal direction of rapid convergence, but also avoid premature convergence.

In Behavior 3 (B3), the new_x i is generated by

$$ new\_{x}_i^d=\left[{x}_i^d+{v}_i^d\right]\mathrm{if}\kern0.5em {r}_i^d\kern0.5em <\kern0.5em {A}_i^d $$
(10)

where \( {v}_i^d \) is the dth dimension of the speed of bat i in the current generation. \( {A}_i^d \) is the loudness varies from a large value to a minimum constant value along with the iterations, \( A={A}_{min}+\left(1-\frac{Current Iteration}{\mathit{\operatorname{Max}}\ Iteration}\right)\times \left({A}_{max}-{A}_{min}\right) \), which is used to control the degree of flight direction and position. \( {r}_i^d \) is a random value between 0 and 1. If \( {r}_i^d<{A}_i^d \), then the dth dimension should carry on the change as shown in (10), otherwise it will keep the original value. The B3 is a modified version of the flying behavior of the original BA.

For example, consider a task which has 3 sub-tasks (D = 3) and each sub-task has 10 candidate services, assume that N = 5, then the randomly generated positions and there corresponding fitness values are shown in Table 3.

Table 3 Example of initialization
Full size table

In the initialization, each bat position represents a path of service composition. For example, the position of 1st bat [1, 1, 2] represents a service composition path: \( {S}_1^1\to {S}_2^1\to {S}_3^2 \) and the 4th bat [2, 5, 7] represents a service composition path:\( {S}_1^2\to {S}_2^5\to {S}_3^7 \). The velocity of all the bats is [0,0,0] initially. Obviously, the 4th bat has the optimal fitness value, so f best and x best are memorized to 0.2117 and [3, 3, 5] respectively.

4.6 Adaptive learning

The boundary control operation shown below should be performed on the new position generated by the above behaviors before evaluating.

$$ \left\{\begin{array}{c}{x}_i^d= Lb\ \mathrm{if}\ {x}_i^d< Lb\\ {}{x}_i^d= Ub\ \mathrm{if}\ {x}_i^d> Ub\end{array}\right. $$
(11)

Then, the fitness value of the new position of each bat f(new_x i ) is calculated according to (1). For each bat, including Gbest bat, if the new fitness value f(new_x i ) is not better than the original fitness value f(x i ), then the Not Evolve Times (NET) value NET i of bat i is added 1, NET i  ← NET i  + 1. On the contrary, the following update operations are performed.

  1. 1.

    Update the bat. The bat i will updated to the new position new_x i with the corresponding fitness value at same time.

$$ \left\{\begin{array}{c}{x}_i\leftarrow new\_{x}_i\\ {}f\left({x}_i\right)\leftarrow f\left( new\_{x}_i\right)\end{array}\right. $$
(12)
  1. 2.

    Update Behavior Selected Probability (BSP) for bat i as follows. Note that this operation is not carried out for Gbest bat, because Gbest bat is memorized to guide the evolution only.

$$ {BSP}_i^m\leftarrow {BSP}_i^m+1/M $$
(13)

where m ∈ {1, 2,  … , M} is the number of selected behaviors and M is 3 in this paper. Then normalization should be carried out to ensure the selected probability \( {BSP}_i^m\in \left[0,1\right] \) and the sum of probabilities \( {\sum}_{m=1}^M{BSP}_i^m=1 \).

$$ { BS P}_i^m\leftarrow \frac{BS{P}_i^m}{\sum_{m=1}^M{ BS P}_i^m} $$
(14)
  1. 3.

    The NET value of ith bat is set to 0, NET(x i ) = 0.

The behavior selected probabilities vector of each bat can be calculated and updated by the above operation. Each bat will choose the appropriate behavior by roulette wheel selection based on the behavior selected probabilities. As the behavior selected probability will be updated based on the development of the bat in the iteration, the behavior beneficial to the fitness value of the current bat is able to get more opportunities to be chosen. It is noted that, with the continuous adaptive learning, the selected probability of certain behavior may be far greater than the other behaviors, which leads to the behavior be the main behavior of the bat while others be ignored in the next iterations. As a result, the algorithm tends to fall into local optima or stop convergence when the fixed behavior is selected in successive iterations. In order to avoid this situation, the Local and the Global Resetting mechanisms, which are described in the following section, are put forward to ensure the algorithm evolving continuously.

4.7 Dual resetting mechanisms

The Local and the Global resetting mechanisms are simple but effective for avoiding the algorithm falling into local optima. As seen from the algorithm flow, the objective of Local resetting and Global resetting are different. The former is for each bat, it performs as follows: if the NET value of the bat exceeds the preset threshold, then reset all the behaviors selected probabilities of this bat to 1/M. The latter is for Gbest bat only, it performs as follows: if the NET value of Gbest bat exceeds the preset threshold, then reset the algorithm itself with Gbest bat and the number of Fitness Evaluations (FEs) preserved. Resetting algorithm means that all the parameters are reinitialized and the algorithm is restarted. It is implied that, when the behavior cannot continuously optimize the fitness value for the individual bat, Local resetting will be carried out to make the subsequent behavior with randomization, so as to provide a possibility for the current individual to escape from local optimum. Global resetting is focused on the overall behavior of the bat population in the algorithm, which helps to avoid stopping convergence because of the lack of the diversity of the whole population. In general, the Local and the Global resetting mechanisms are self-recovery mechanisms when the algorithm is prematurely converged.

5 Experiments and analysis

In most research works on MSC problem [21, 33], because of the lack of public data sets, the synthetic datasets are always used for simulation. These data sets are generated with a hypothesis, namely, the number of sub-tasks in the manufacturing process is relatively small. However, with the increasing of the degree of production refinement, and the expansion of the demands for personalized customization manufacturing based on the Internet, both the number of manufacturing sub-tasks, and the number of service candidates, are growing dramatically. Therefore, it is necessary to test the performance of the algorithm on larger scale data sets. In this paper, the data set is constructed from small scale to large scale, which is used to test the algorithm in a variety of conditions. The values of QoS properties of each service are generated randomly from (0,1). The number of sub-tasks D and service candidates C varies from small to large, which consists of two cases: (1) D fixed to 100, C increased from 500 to 5000; (2) C fixed to 500, D increased from 100 to 1000.

5.1 Results analysis and comparison with other similar algorithms

In order to verify the effectiveness of the proposed algorithm, SABA and SABA without Local resetting (SABA\LR) were compared with other commonly used algorithms including DE, PSO and GL25, which are available as open source. The settings of MSC problem are as follows: (1) D was set to 100, C varied from 500 to 5000 and (2) D increased from 100 to 1000, C was set to 500. For each algorithm, 30 independent runs were conducted with MaxFEs = 120000 as the termination criterion and the population size N = 50. The other parameter settings are descripted in Table 4.

Table 4 The parameter settings of SABA, DE, PSO and GL25
Full size table

The individuals in DE, PSO and GL25 were the discretization form by rounding operator because the MSC problem is a discrete optimization problem. The mean and standard deviation results of these algorithms are shown in Tables 5 and 6. Tables 7 and 8 are Wilcoxon’s rank sum test at a significance level of 0.05, in which “+”, “−” and “≈” denote that the performance of corresponding algorithm is better than, worse than, and similar to that of SABA, respectively. It can be seen that SABA and SABA\LR provide the best results for all the problems. Even though the stability of SABA and SABA\LR becomes gradually worse along with the increase of the problem dimension, the performance of SABA\LR in terms of solution quality is rather competitive. This may be due to the great exploration and exploitation ability of multi-behaviors based on the self-adaptive learning framework and the resetting mechanisms especially Global resetting.

Table 5 The mean and standard deviation of fitness values of SABA, DE, PSO, GL25, SABA\LR, SABA\LR, SABA\GR, SABA\R, SABA\SAL and RBA on MSC problem with D fixed to 100, C varying from 500 to 5000
Full size table
Table 6 The mean and standard deviation of fitness values of SABA, DE, PSO, GL25, SABA\LR, SABA\LR, SABA\GR, SABA\R, SABA\SAL and RBA on MSC problem with C fixed to 500, D varying from 100 to 1000
Full size table
Table 7 Wilcoxon’s rank sum test results of SABA, DE, PSO, GL25 and SABA\LR on MSC problem with D fixed to 100, C varying from 500 to 5000
Full size table
Table 8 Wilcoxon’s rank sum test results of SABA, DE, PSO, GL25 and SABA\LR on MSC problem with C fixed to 500, D varying from 100 to 1000
Full size table

Furthermore, the convergence maps of SABA, SABA\LR, DE, PSO and GL25 on MSC problem with different conditions in Fig. 3 show that the SABA and SABA\LR always converge faster than other algorithms. It can be observed that DE, PSO and GL25 suffer from local optima while SABA and SABA\LR have better global search ability. The reason for the results is that SABA and SABA\LR are able to select most appropriate behavior at different stages for different conditions by self-adaptive learning framework and keeping diversity of the population by resetting mechanism. Therefore, the proposed algorithms not only have good convergence efficiency, but also maintain well search ability when the other algorithms are converging slowly or even prematurely.

Fig. 3
figure 3

The convergence characteristics of SABA, DE, PSO and GL25 on MSC problem where FEs varies from 50 to 120,000

Full size image

5.2 Analysis of dual resetting

The experiment was designed to investigate the effect of the resetting mechanisms on the performance of the algorithm. SABA without Local resetting (SABA\LR), SABA without Global resetting (SABA\GR), SABA without resetting including both Local and Global resetting (SABA\R) were compared with SABA on MSC problem. The parameter settings of SABA, SABA\LR, SABA\GR and SABA\R are shown in Table 9.

Table 9 The parameter settings of SABA, SABA\LR, SABA\GR and SABA\R
Full size table

Table 5 reports the mean and standard deviation of fitness values by applying the four algorithms to optimize MSC problem, in which D is fixed to 100, C varies from 500 to 5000. Table 6 shows the mean and standard deviation of fitness values of SABA, SABA\LR, SABA\GR and SABA\R on MSC problem with C fixed to 500, D varying from 100 to 1000. The best results are typed in bold. The data are the statistical results obtained from 30 independent runs. As shown in Tables 5 and 6, SABA and SABA\LR outperform the SABA\GR and SABA\R in all cases. For cases, D = 100 and C = 3500, D = 700 and C = 500, D = 800 and C = 500, D = 900 and C = 500, D = 1000 and C = 500, SABA\LR has a better performance than SABA. While for other cases, the solution quality of SABA is higher than that of SABA\LR. The fact that SABA\R works better than SABA\GR demonstrates that the use of the Local resetting mechanism alone has no positive effect on the performance of the algorithm. From the above results we can observe that the resetting mechanism especially the Global resetting mechanism is really effective for the algorithm to improve the solution quality.

5.3 Analysis of self-adaptive learning framework

This experiment was designed to study the effects of self-adaptive learning framework on algorithm performance when running SABA on MSC problem. SABA without Self-Adaptive Learning (SABA\SAL), Random Bat Algorithm (RBA), are compared with SABA on MSC problem. In SABA\SAL, only the B3 was used for updating the position and velocity of the bat. In RBA, three behaviors were selected randomly instead of self-adaptive learning, that is, the probabilities of the behaviors were not considered in the process of the algorithm. The parameter settings of SABA are the same as in 5.1, and the other parameter settings of SABA\SAL and RBA are the same as in SABA.

Tables 5 and 6 presents the mean and standard deviation results of these algorithms with 30 independent runs. It can be seen that SABA performs best out of the three algorithms. Comparing with SABA\SAL, RBA obtains better results on all conditions. It is because the multi-behaviors can help the algorithm having a better ability of exploration than the single behavior. From the comparison results of the three algorithms, we can investigate that SABA can not only maintain the global search ability, but also have the ability of adopting different behaviors in different stages of the algorithm based on self-adaptive learning, which makes the algorithm perform best.

Furthermore, Fig. 4 illustrates the average selected probability of each behavior of all bats in the process of SABA for four MSC problem conditions. Fig. 4a represents the average selected probabilities of three behaviors in the whole population under FEs increasing from 50 to 120,000, where the number of tasks D = 100 and the number of candidate services C = 500. As can be seen from the figure, at the beginning, the selected probability of each behavior is 1/3 because of the equal selection probability of three behaviors in the algorithm initialization. Throughout the iterative process, the selected probability of B1 is significantly higher than the other two behaviors, which implies B1 plays a dominant role in the solution process of the algorithm on this problem. Although the selected probability of B1 is relatively high in overall trend, there is a certain degree of fluctuation in the whole iterative process. The result is consistent with the self-adaptive learning framework in which different behaviors in different iterative stages have different effects of the algorithm to solve the different problems. Similarly, in the case of the D=200, D=500 and D=1000, B1 shows its significant effect for solving this problem than the other two behaviors. The effect of the resetting mechanisms cannot be clearly demonstrated in the figures since the figures only show the average results.

Fig. 4
figure 4

The average behavior selected probabilities of all bats of SABA running 30 times independently, where FEs varies from 50 to 120,000

Full size image

Therefore, Fig. 5 illustrates the selected probability of each behavior of a bat of the median run of SABA for four MSC problem conditions. As can be seen from the Fig. 5a, the selected probability of each behavior is the same and equal to 1/3. Different from the previous analysis of the average probability, the three behaviors have a sharp increase or decrease since the behavior is always changing for the individual. If the B2 generates a better solution in one generation, the selected probability of B2 behavior is increased in the next generation, while the selected probabilities of the others are fall. It can be found that when the FEs equals to 40,000, the selected probability point of three kinds of behaviors will coincide again, which may be due to the resetting mechanisms of the bat (Local resetting) or the algorithm (Global resetting). Similar results can be observed in other graphs. The red dot in the figure indicates the actual choice of the behavior in the algorithm. As can be seen in Fig. 5, the behavior with the largest selected probability is always being chosen. The other behaviors with low selected probabilities also have the chance to be selected because of the randomness of roulette wheel selection. For example, B1 has a largest selected probability when FEs = 90,000 in Fig. 5a, but in fact B3 is selected. This shows that the behavior of each bat is not entirely determined by the selected probability and the choice of the behavior has some randomness on the basis of probability, which brings a perturbation to some extent.

Fig. 5
figure 5

The behavior selected probability and the real selected behavior of a specific bat of the median run of SABA, where FEs varies from 50 to 120,000

Full size image

5.4 Discussion

The experiments show that SABA performs better in terms of solution quality and convergence speed than the other algorithms on MSC problems, especially when the problem scale becomes larger. The main reason is that SABA has some good characteristics compared with other algorithms. Firstly, SABA has a multi-behavior selection framework based on self-adaptive learning. In this framework, three behaviors have different properties and search abilities. For example, in B1, inspired by DE algorithm, two difference vectors, which express the promoting and stochastic direction respectively, are added to the current individual. This leads to the current individual moving to the promoting area with certain randomness. B1 is demonstrated to be helpful to provide a good balance of global and local search capability for the algorithm, as shown in 5.4. B2 is inspired from EDA [47] and ES [48] algorithms. It uses the Gauss distribution in the solution space of the problem to carry out the sampling and the updating operations, which enables good exploitation. As for B3, it is similar to that in the original bat algorithm. The main difference is that the updating dimensions in B3 are selected according to the parameter A which gradually decreases as the number of iterations increases. Self-adaptive framework helps the algorithm to select the most appropriate behavior in different stages according to different problems, thus enhances the dynamics and universality of the algorithm. Furthermore, SABA has dual resetting mechanisms, namely, Local resetting and Global resetting. Local resetting can make the individual behavior not tend to be single, while Global resetting can help escape from local optima. Both of them are able to enhance the diversity of the population. It is worth noting that Global resetting is based on the reservation of the global best solution to avoid the full blindness of the subsequent iteration process and to ensure that the promising area in the search space will not be discarded. Experiments in section 5.2 show that this mechanism can significantly improve the performance of the algorithm.

6 Conclusion

With the rapid growth of manufacturing services in CMM, it has become an important issue to obtain the optimal manufacturing service composition with a large number of service providers and subtasks. We have proposed a self-adaptive based bat algorithm (SABA) to tackle the MSC problem. In SABA, the self-adaptive learning framework with three different novel behaviors is designed to make a tradeoff between the global exploration and the local exploitation of the algorithm. Additionally, the Local and the Global resetting mechanisms are introduced into the algorithm to avoid suffering from premature convergence. The proposed algorithm has advantages in terms of the solution quality and efficiency compared with other algorithms especially for large-scale testing instances. Therefore, it is a competitive solution for MSC problem.

In the future work, we will obtain more practical data from the industrial field for experiments, and further verify the value of this method in real world. In addition, we will also perform further research on multiple behaviors, including how to design evolutionary behaviors, combine behaviors, and choose the quantity of behaviors.