Emerging cloud manufacturing paradigm aims towards providing highly integrated solutions via enabling cooperation between distributed manufacturing resources and capabilities. Implementation of this groundbreaking idea, however, is facing serious challenges spring ing from the currently centralized industrial structures. In order to help it make its way out, researchers have to address a number of pi votal issues in this regard. Service composition and optimal selection (SCOS), which tackles the problem of optimally selecting and combining available resources into a composite service is one of them. To deal with this NP -hard problem, we developed a novel hybrid algorithm based on the recently - introduced grey wolf optimizer (GWO) in which evolutionary operators are also embedded into the hunting mechanism of the basi c algorithm. This approach not only makes it possible to adapt an algorithm with continuous structure such a s GWO to solve a combinatorial problem such as SCOS, but also empowers it with providing higher exploration through crossover and mutation operators. Experiments c onducted clearly proves the superior performance of the proposed algorithm over existing disc rete variations of GWO and genetic algorithm, especially in large -scale SCOS problems. © 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY -NC-ND license ( http://creativecommons.org/licenses/by -nc-nd/3.0/ ) Peer-review under responsibility of the Scientific Committee of NAMRI/SME . Keywords: service composition, cloud manufacturing (CMfg), QoS (quality of service), grey wolf optimizer (GWO) 1. Introduction Today’s rapidly changing and highly customized market is metamorphosing the traditional product -oriented manufacturing into a service -oriented structure. The service - oriented manufacturing makes it possible for customers to involve in the whole product life cycle and in the manufa cturers’ side, empowers them by providing more effective collaboration both within their facilities and across different partners. Cloud manufacturing (CMfg) has been proposed as the panacea to implement this groundbreaking idea in recent years. Nonetheles s, to fully achieve this goal, there remains significant issues with regard to enabling technologies [3-7], trust evaluation [8], task and resource description [9,10], sch eduling [11-13] and service composition , among which the last one, is the key to offering composite services through the above -mentioned collaboration among partners. This has to be done by selecting the optimal resource for each sub -task out of the existing candidates at the resources pool and composing them to achieve the highest qua lity of service (QoS). The focus of this research is to solve this problem through implementing a hybridized variation of recently developed grey wolf optimizer (GWO) in which crossover and mutation operators are also embedded in the structure of the basic algorithm in an attempt to achieve better exploration power. There has been a growing interest in service composition and optimal selection (SCOS) problem in the context of CMfg , targeting different aspects of it including, among other things, developing and applying more advanced 2 Author name / Procedia Manufacturing 00 (201 9) 000–000 algorithms, consideration of transportation in the modeling, trust evaluation and correlation awareness . In terms of implemented algorithms, the list covers a wide spectrum of metaheuristics from various variations of improved an d/or hybridized GA (genetic algorithm) [14] and PSO (particle swarm optimization) [15] to AC (ant colony) [16] and IWO (invasive weed optimization) [17]. Grey wolf optimizer (GWO) is a recently introduced swarm intelligence algorithm mimicking the social hierarchy found in the wolf packs and their haunting behavior. The algorithm gained acknowledgment from researchers in various fields and has been applied to solve different problems such as parametric optimization of abrasive water - jet machining processes [18], optimization of production time in the multi -pass milling process [19], optimal control of thermal systems [20], economic load dispatch problem of electric power systems [21] , feature selection [22] and parameter selection in surface waves [23]. Generally, this algorithm has proved to produce competitive or superior results compared to other well -established algorithms such as PSO and DE (diff erential evolution), especially in terms of exploitation. However, this exploitative mechanism, which can be tracked down to its searching mechanism (called as “hunting”), makes the GWO algorithm prone to stagnation in local solutions. To overcome this pre mature convergence and achieve a better balance between exploration and exploitation, we propose incorporating mutation and crossover operators into the GWO, which eventually combines the merits of GWA and GA both. The remain der of this paper is organized as follows. First, the SCOS problem is briefly explained in Section 2. The GWO algorithm is presented in Section 3 and then the hybridized GWO -GA algorithm along with its embedded operators to solve the SCOS problem are discu ssed in Section 4. Simulation experiments and results analysis are provided in Section 5. Finally, Section 6 concludes the paper. Figure 1: SCOS in CMfg Platform [1,2] Author name / Procedia Manuf acturing 00 (201 9) 000–000 3 2. Description of SCOS problem As one can see from Figure 1, the process of matching demands and resources should be studied from the very beginning after tasks’ submission. Generally speaking, this process can be broken down into three steps a s depicted in Figure 2. (1) Task decomposition: First of all, the submitted task which can be considered as a complex manufacturing project, should be decomposed into n subtasks denoted by 12, ,...,n ST ST ST according to certain logic rules. (2) Se rvice discovery: Then, for subtask iST and based on functional requirements, a number of services will be retrieved by matching algorithms. These algorithms are mostly based on semantics similarity between subtasks and resources’ descriptions. After this process, each subtask can be associated with a number of candidate manufacturing services ( 12, ,...,m MS MS MS ). (3) Service composition and optimal selection: Finally, it becomes the time for service composition and optimal se lection which can be defined as selecting one candidate service from each corresponding candidate set to compose the service while ensuring the overall QoS is optimal . Both aggregation models and normalization formulas are given in Bouzary and Chen [24] in a detailed manner . The mathematical model of the SCOS problem is given as follows: ( ) ( )kk Max Qos Max w Norm Q  (1) .st 0 ()kk agg Q Q if kQ is a positive attribute (2) 0 ()kk agg Q Q if kQ is a negative attribute (3) 11r k kw  (4) Where kw is the weight of the k th attribute, ()k Norm Q is the normalized value for the k th QoS attribute, r is the number of attributes, 0kQ is the lower bound value of QoS for the k th attribute and [0,1]kw . 3. Grey wolf optimizer Grey wolf optimizer (GWO) is a recently -developed swarm intelligence algorithm which was introduced by Mirjalai, et al in 2014 [2 5]. Since then, it has gained acknowledgment and has been repeatedly implemented to solve various optimization problems. It mimics the leadership hierarchy and hunting mechanis m of grey wolf packs in nature. The behavior of wolves is simulated through three main steps including hunting (searching for prey), encircling prey, and attacking prey. The pack is divided into four categories. The fittest solution is considered as the al pha (  ). Second best and third best solutions are categorized as beta (  ) and delta wolves (  ), respectively. The rest of the population are assumed to be omega (  ). Search for prey is led only by  ,  and wolves and  wolves have to follow these three [2 5]. The mathematical interpretation of encircling prey, hunting and attacking prey as the three pillars of GWO algorithm follows immediately. 3.1.1. Encircling prey Grey wolves tend to encircle prey before the hunt. This behaviour can be mathematically simulated through equations ( 5-8). . ( ) ( )p D C X t X t (5) ( 1) ( ) .p X t X t A D   (6) 12.A a r a (7) 22.Cr (8) where t represents the current iteration, pX indicates the position of the prey, and X represents the po sition vector of a wolf. A and C are coefficient vectors which make it possible for wolves to reach different locations around the prey. Essentially, D equals to the distance of wolf from the prey. Components of a linearly decrease from 2 to 0 over the course of iterations and r 1, r2 are random vectors in [0,1] [25]. 3.1.2. Hunting Despite the fact that hunting is usually guided by the alpha, beta and delta, in an abstract search space, the location of the optimum (prey) is unknown. In order to mathematic ally simulate the hunt ing process, it is assumed that  ,  and  have better knowledge regarding the possible location of prey. Therefore, position of three best individuals found so far are saved and position of every other wolf will be updated according to these three solutions. This can be achieved using formulas 9-11 [25]. 1 1 1. , . , . D C X X D C X X D C X X           (9) 1 1 2 2 3 3 . , . , . X X A D X X A D X X A D           (10) 1 2 3( 1)3X X XXt (11) Through equations (12 -14) below , alpha, beta, and delta estimate the position of the prey, and other wolves update their positions randomly about the prey [25]. 3.1.3. Attacking prey and searching for prey The process of approaching the prey is simulated through decreasing value of a . In this way, while random values of A change between -1 and 1, the next position of a wolf can be somewhere between its current position and the position of the prey. On the other hand, any random value of 1A or 1 A , leads to an opposite behaviour called “searching for prey” which provides better global search and helps to avoid getting stuck in local optimal solutions. Through the above -mentioned operators, GWO guides its search agents to gradually update their position s based on the position of best three agents and eventually obtain a near - optimal solution. A more detailed explanation on this algorithm can be found in [25]. 4 Author name / Procedia Manufacturing 00 (201 9) 000–000 4. Hybrid GWO -GA algorithm As mentioned before, the standard GWO is designed to solve optimization problems with continuous solution space, since the updated position of wolves could take any possible value within the solution space. However, the SCOS problem is a typical combinatorial problem. Therefore, a discrete hybrid variation o f grey wolf optimizer equipped with evolutionary operators, has been developed to pave the way for making use of this powerful algorithm in the context of SCOS problem, and any other combinatorial problem in general. 4.1. Representation of SCOS problem The solu tion for the SCOS problem is a composition of cloud manufacturing candidates for a task. In this case, a wolf’s position vector represents a feasible composition. For instance, a solution for a composition involving 5 subtasks and each subtask having 10 av ailable candidate services, can be represented in the form of a string as shown below. 2 10 3 7 1 4.2. Embedded evolutionary operators Solving a combinatorial optimization problem is very different from solving a problem with a continuous solution space. In a continuous search space, the search agents of GWO are able to update their position vectors according to the hunting process mimick ed by equations (12 -14). In a discrete space, however, the position of wolves cannot be updated likewise, since the position vectors can only take on discrete values. As a result, there have been some attempts to adapt the algorithm to solve problems with discrete solution spaces. For instance, Emary et al. [22] have developed a binary variation of GWO algorithm through employing a sigmoid function to solve the feature selection problem. However, in case of SCOS problem, we did not find the same approach effective enough , which urged us to develop another GWO -based approach by adding evolutionary operators into the structure of the standard algorithm. This approach can, to a great extent, improve the balance between exploration and exploitation, yet preserving the advantages of both GWO and GA algorithms. All the considered modifications intended to adapt GWO to the SCOS problem, as well as the added crossover and mutation operators are presented as follows. 4.2.1. Range checking Updating the position of wol ves during the hunting process using equations ( 9-11), does not guarantee that the value of every direction does not exceed the bounds of the problem. As a result, after attaining the discrete values of each direction through rounding toward zero the updat ed values of positions obtained from equation ( 9-11), an additional step is needed to be considered to return back the exceeding values into the boundaries of the problem. In the case of SCOS problem, upper bound denoted by ub , equal s to the number of available candidates for each subtask, and lower bound, denoted by lb , is equal to 1. Equation ( 12) is applied to achieve this goal. .( ) . .iiX X u l ub u lb l    (12) Where i u X ub and i l X lb . 4.2.2. Selection operator Roulette wheel selection is a widely -used selection operator applied in several proposed genetic algorithms solving the service composition problem [26]. The basic idea behind t his operator is this fact that the better the fitness of an individual, the larger the probability of its survival and mating. The same selection operator is applied here to select the parents that will go through the crossover and mutation operators. To select an individual for crossover and mutation processes out of a population with size n (size of wolf pack in our case) we use the following steps: Step 1. Generate a random real number (r) ∈ [0, 1]. Step 2. If r ≤ 1p , select the first wolf in the population w 1, otherwise; select the ith wolf iw (i=1,2,…, n) such that 1ip < r ≤ ip , where ip is the cumulative probability for each wolf iw in the current population (pack) which will be calculated according to equation ( 13). 1 1 1 12i n j j i ii n j jfp f fp p if i n f           (13) Where if is the fitness of individual i in the population [27]. 4.2.3. Crossover operator Every selected pair of parents will go through the crossover operator and a pai r of new individuals (children) will be produced by combining their genes. Here, we have employed a two -point crossover operator similar to some other research works on service composition [28]. During this operator, two crossover points are randomly chosen in the two parents. Then, the subsequent genes, between these two cutting points of each parent are exchanged from a chro mosome to another one (see Figure 2 (a)). Figure 2: Evolutionary operators in genetic phase. a) two -point crossover, b) swap mutation 4.2.4. Mutation operator Mutation operator is intended to provide exploration and to avoid local optimum stagnation through maintaining the Author name / Procedia Manuf acturing 00 (201 9) 000–000 5 diversity of population which will be achieved by making a small and slow genetic frequency change in the generated chromosomes. Swap mutation is used here in which two genes in the chromosome of an individual wil l be randomly selected and then their values will be interchanged (see Figure 2(b)). Now that crossover and mutation operators are applied, an overlapping population will emerge, where parents and offspring are merged, and t he best individuals from this union will form the next iteration’s population. In fact, this merged population will be sorted in descending order and the first best n individuals (equal to the size of the wolf pack) will be selecte d and replaced as the initial population for the next iteration. The whole process from the initialization up until this point, will be repeated until a stopping criteria is met. Exceeding a specific CPU time, reaching a predefined number of iterations, a certain number of iterations without any improvement in the fitness of the fittest solution and converging to a specific fitness value are among the most popular termination criteria for metaheuristic algorithms. In this study, we have used the maximum num ber of iterations as the stopping criterion for our proposed algorithm. A summary of the embedded procedures of the proposed hybrid GWO algorithm is organized step by step in Algorithm 1. Algorithm1: Hybrid GWO algorithm for SCOS problem (1) Initialize ( t = 0) step1: Randomly generate an initial population ( 1,2,..., )iX i n , where n denotes the size of the wolf pack (2) Repeat (t = 1 to maxiter ) Step2: Initialize vectors ,,a A C according to Equations ( 7-8) Step3: Calculate the fitness values of each wolf Step4: Record the position of first three best wolves as X , X and X , respectively and update accordingly Step5: Update the position of wolves through hunting process using Equations ( 9-11) Step6: Discretize the elements of position vectors obtained in step5 ( ( 1)Xt ) using the floor function Step7: Perform range checking for values obtained in Step6 and map out of bound values (if any) into the allowed space according to Equation ( 12) Step8: Select cPn number of parents for crossover operation and mPn number of parents for mutati on operator according to Equation ( 13), where cP and mP are probability of crossover and mutation, respectively Step9: Perform the two -point crossover on the selected parents Step10: Perform the swap muta tion operator on the selected individuals for mutation Step11: Merge the populations created in Steps 9 and 10 with the original population obtained after Step7 Step12: Sort the Step11’s population in descending order and only keep the first fittest n individuals. Step13: Replace this new population as the initial population for the next iteration Step14: Memorize the best solution achieved so far. Assign 1tt . Step15: If stop criterion is not reached, go to Step2. Step1 6: Output the best solution (3) Output 5. Experiments and results In this section, we investigate the performance and efficiency of the proposed hybrid GWO algorithm for SCOS problem, and its potential for solving other combinatorial problems as well. To this end, this section conducts performance comparison with two oth er metaheuristics under the following testing scenarios as well as different user QoS p