目前对制造服务建模方法的研究主要集中在对属性和功能的描述上，制造服务属性包含基本属性、使用属性、状态属性和动态属性[6-7]。随着研究的深入，制造服务的功能也被纳入到建模的考虑范围内，服务模型既封装功能属性又封装非功能属性[8]。基于构建的制造服务模型，围绕制造服务组合优选方法的研究大多采用传统智能优化算法，比如遗传算法(Genetic Algorithm, GA)、粒子群优化(Particle Swarm Optimization, PSO)算法、蚁群算法等。也有很多****综合考虑云制造服务种类多数量大的特点，对传统的优化算法进行改进[9-10]或尝试一些新的搜索组合方法[11-12]，这些方法都对服务的建模和优选匹配做出了改进和完善。
从属性和功能方面对制造服务建模有效描述了制造资源的数据信息，然而制造服务往往比其他领域的服务更加复杂，仅仅包含服务属性和功能的建模方法显得不够细致和全面。为完善服务模型创建的准确性和全面性，本文将多层次划分理论引入制造服务的描述和建模过程，多层次划分理论是根据对象所包含的属性功能多少或粗细粒度进行分类的方法[13]。根据多层次划分理论，本文将制造服务划分为资源服务、功能服务和流程服务，从多层次的角度描述和构建制造服务模型。针对多层次服务模型的组合优选问题，本文提出一种基于小生境的改进引力搜索算法(Niching behavior based Gravitational Search Algorithm，NGSA)，将小生境技术引入传统引力搜索算法(Gravitational Search Algorithm, GSA)，克服了GSA探索能力弱的缺点。算例验证表明，在制造服务解空间不规律和数量多的情况下，该算法相比传统的智能优化算法具有更高的收敛性和准确性。
1 多层次制造服务及组合优选评估建模 1.1 制造服务多层次特点 云制造过程的服务种类多、异构性强，同时不同用户提出的制造任务差异也很大。举例说明，如图 1所示，机床用户提出的制造任务是机床整体任务，机床生产厂商提出的制造任务可能是机床箱体任务，而变速箱厂商提出的制造任务是箱体里传动齿轮的齿轮工序任务。对于机床整体任务，服务平台应匹配设计、工艺、制造、维修整个流程服务；对于机床箱体任务，平台应匹配机加、装配等制造功能服务；而对于齿轮工序任务来说，平台只需匹配满足磨削加工的设备、软件和操作质检人员等制造资源服务。由图中的例子可以看出，不同层次制造任务的组合优选过程需匹配对应层次的制造服务。
 |
| 图 1 制造任务和服务多层次特点 Fig. 1 Multi-level characteristic of manufacturing tasks and services |
| 图选项 |
从制造任务角度分析，提出制造任务的用户可能是终端消费者也可能是生产制造环节的中间生产企业，中间生产企业相对其上游企业而言又变成了用户。从制造服务角度分析，通常一个产品的制造周期包含设计、工艺、制造、维护等环节，其中制造环节又可细分为机加、下料、热处理、铸造、装配等工艺环节，而机加工艺环节可再细分为车、铣、磨、钳等工序环节。由此可见，不同类型用户提出的制造任务和不同粒度的制造服务都具有多层次的特点。本文引入多层次划分方法对制造服务进行描述和建模，根据制造服务所包含的资源和功能粒度，将服务细分为资源服务、功能服务和流程服务3个层次，从而更准确地描述服务和匹配不同类型用户的任务需求。经过多层次划分后，制造服务的建模和组合优选过程如图 2所示。
 |
| 图 2 多层次服务建模和组合优选过程 Fig. 2 Multi-level service modeling and optimal-selection process |
| 图选项 |
从图 2可以看出，用户在应用层输入制造任务，云服务平台按照一定的智能组合优选算法在不同层次服务间迭代搜索并组合服务，然后将最优的服务集合输出给用户，最优服务集合往往是多个层次服务的合集。
1.2 多层次制造服务建模 基于多层次制造服务划分方法，本文分别对各层制造服务进行描述和建模，然后从服务质量评估的角度，构建多层次制造服务组合优选的质量评估模型。
定义1 ??资源服务是指由完成单元功能的制造资源所发布成的服务，比如一台加工中心、一名操作人员等。资源服务RS满足：
 | (1) |
式中:rsh、rss和rsp分别表示硬件资源服务、软件资源服务和人力资源服务。
定义2??功能服务是指由具有关联关系的多个资源服务封装发布成的服务。比如车铣加工服务是由加工中心、编程软件和设备操作员封装而成，各资源服务之间具有约束关联关系。功能服务FS满足：
 | (2) |
式中:Rij表示资源服务间的关联关系；n为功能服务包含资源服务的数量。
定义3 ??流程服务是由多个功能服务按照一定的执行顺序连接后封装发布成的服务。流程服务往往能完成一个相对完整的制造流程，比如质量处理流程、外协流程等。流程服务PS是由功能服务和执行顺序所形成的一个有向无环图，如图 3所示。
 |
| 图 3 流程服务有向无环图 Fig. 3 Directed acyclic graph of process services |
| 图选项 |
图 3中，圆圈VFS为流程服务顶点，该顶点是一个功能服务，带箭头的线EFS是流程服务顶点间的方向矢量，表示功能服务间执行的顺序。流程服务可转换为功能服务和资源服务的组合，满足：
 | (3) |
式中: m′和l′分别为流程服务包含功能服务的数量和功能服务包含资源服务的数量，0 < m′≤m, 0 < l′≤l。
1.3 制造服务组合优选评估建模 假定用户输入的制造任务集为T={T1, T2, …, TN}，其中Ti(1≤i≤N)为制造任务集T中第i个子任务，平台里的制造服务集为S={S1, S2，…, SM}。制造服务的组合优选问题就是从服务集S中搜索匹配出能完成任务T的最佳服务组合，保证该组合的质量评估结果最优。
根据多层次服务划分理论，制造服务集可表示为S={RS, FS, PS}，则制造服务集S中所包含的各层服务可表示为
 | (4) |
式中: l、m和n分别为制造服务集S所包含的资源服务、功能服务和流程服务的数量; M为服务的总数量。
从服务质量评估的角度构建多层服务的评估模型，本文考虑的评估指标包含3个：服务执行时间ST、服务花费成本SC和服务用户评价SE。服务执行时间ST是指优选服务完成制造任务所使用的时间总和，包括服务执行的时间和服务之间转换的时间；服务花费成本SC是指优选服务完成制造任务所消耗的成本总和；服务用户评价SE是指优选服务在完成制造任务后用户对该服务的综合评价。3个评估指标的质量评估函数如表 1所示，r为服务转换时间与执行时间的比值。
表 1 多层次服务的质量评估函数 Table 1 QoS functions for multi-level services
| 评估指标 | 质量评估函数 |
| ST |  |
| SC |  |
| SE |  |
表选项
各层服务考虑执行时间、花费成本和用户评价指标后的质量评估函数分别为
 | (5) |
制造服务集S是多层服务的合集，S的总适应度值表示为各层服务质量评估函数的加权求和，即
 | (6) |
式中：α、β和γ为各层服务的权重因子，本文考虑多层次制造服务可相互转换特点，权重因子的取值采用各层服务的数量占比进行计算。根据多层服务模型定义将各层服务都转换为资源服务，权重因子的计算公式为
 | (7) |
其中:l′i为第i个功能服务所包含资源服务的数量；l″ij为第ij个流程服务所包含的资源服务的数量。
2 多层次制造服务组合优选方法 多层次制造服务的组合优选是一个复杂的多目标优化问题，由于制造服务往往是不连续的，服务组合的帕累托最优解一般很难在较短的时间内获得。与传统优化算法相比较，GSA在收敛速度和收敛精度上都体现出明显优势，但它的不足是容易早熟和收敛停滞[14]。为克服GSA易陷入局部最优的缺点，本文将小生境的拥挤度算子和适应值共享技术引入，提出一种基于小生境的NGSA。
具体来说，NGSA从3个方面对GSA进行改进：种群初始化采用轮盘赌选择法进行筛选、组合优选过程引入拥挤度因子和适应值共享策略、多层服务模型之间增加层间映射迁移机制。
2.1 种群初始化 初始化过程包括种群编码和适应度值计算。为提高多层次制造服务描述的简便性，本文选用实数编码，编码维度代表任务维度，编码值代表匹配的服务值。
为尽量选择较优的个体，在种群初始化过程增加轮盘赌选择法，根据式(6)计算个体的适应度值，再根据式(8)计算个体被选中的概率，按照计算概率来选择个体。
 | (8) |
式中:Fitness(Si)为个体Si的适应度值;
2.2 拥挤度因子和适应度值共享 一方面，GSA主要考虑粒子的质量和粒子之间的距离，GSA中吸引概率AP主要考虑质量因子MF，质量因子的计算公式为
 | (9) |
然而在多层次制造服务的组合优选问题上，服务分布的稀疏度也是影响选择的重要因素。本文引入小生境技术里的拥挤度因子CF，拥挤度因子CF的计算方法是找出距离粒子i最近的2个粒子i-1和i+1，计算前后2个粒子目标函数的差，即为粒子i的拥挤度值，如式(10)所示，第一个和最后一个粒子的拥挤度因子为无穷大。
 | (10) |
式中：fji+1和fji-1分别表示距离粒子i最近的两个粒子i+1和i-1的目标函数值，两者差的绝对值表示粒子i所处前后空间拥挤度值的大小，j表示粒子的维度，对j维度求和获得粒子i在目标函数f下的拥挤度值。
算法的总吸引概率算子是综合考虑质量因子MF和拥挤度因子CF，即
 | (11) |
式中:r1和r2分别为2个因子的权重。r1越大，表示对质量的依赖性越强；r2越大，表示对拥挤度的依赖性越强。为维持GSA对质量的依赖度，本文以质量依赖为主，拥挤度依赖为辅，因此取r1=0.6, r2=0.4。
另一方面，为改善GSA在多层次服务组合优选中易陷入局部最优的问题，本文引入小生境的适应值共享技术，当搜索陷入局部最优时，将种群划分为两部分，其中一部分继续沿着局部进行优化搜索，另一部分则通过定义适应值共享函数，通过改变共享区域内粒子的适应度值，促使粒子逸出，从而跳出局部最优。
引入适应值共享函数，采用海明距离对粒子间的相似度进行度量，将每次迭代结果中的适应度峰值数据视为资源，该资源由峰值周围的粒子所共享。设定u次迭代结果集里的峰值集合为Sbest={Sbest1, Sbest2, …, Sbestw}，共享区的半径为R，则Si到Sbestj(1≤j≤w)的距离用hdi表示，满足：hdi=|Si-Sbestj|，其中1≤i≤n, 1≤j≤w，若hdi < R，说明该粒子处在共享区内，其适应度值为
 | (12) |
式中：Fitness(Si)new为粒子Si调整后的适应度值；A为调整系数，调整系数根据种群数量多少和稀疏度确定；Ki(di)为距离系数。假设Sbestj共享区内共有x个粒子，则Ki(di)等于该粒子到峰值的距离与共享区内所有粒子到峰值距离和的比值，计算式为
 | (13) |
可以看出, 粒子Si距离峰值Sbestj越近，种群越拥挤(m越大)，则Ki(di)越小，调整后的适应度值Fitness(Si)new就会增大越多，因此越容易跳出局部最优区间，逸出到新的搜索范围。
2.3 层间映射迁移 根据本文对制造服务多层次的划分理论，组合优选的结果往往是多层服务的合集。多层次服务的搜索组合流程如图 4所示，不同层次服务内部并发执行搜索。设定服务组合的适应度阈值Eo，服务层次内部迭代得到的最优适应度值与Eo比较，若大于Eo，则输出最优服务组合；反之若小于Eo，说明该服务层次内部匹配度不能满足临界值需求，此时进行不同层次服务间的映射迁移，通过改变寻优的服务层次来提高匹配度值，最终输出多个层次服务的最优组合集。
 |
| 图 4 NGSA层间迁移流程图 Fig. 4 Flowchart of interlayer migration of NGSA |
| 图选项 |
NGSA主要初始化的参数是种群个数、引力常数、适应值共享半径、适应度调整系数、层间映射迁移阈值和各层服务评估模型权重值，算法的终止条件是迭代搜索服务组合的适应度值大于等于适应度阈值Eo。算法的流程如下：
1) 初始参数，随机生成各层服务种群，对个体进行实数编码。
2) 调用式(6)计算个体的适应度值，采用轮盘赌选择法从种群中选取N个体组成初始种群集。
3) 循环N个服务个体，计算总吸引概率算子AP=0.6MF+0.4CF，根据总吸引概率算子计算个体之间的引力值、加速度和位置。
4) 每次迭代后，对N个体的适应度值进行大小排序，取适应度值前P个体视为资源，计算其他个体与P个资源之间的海明距离并与共享半径R比较，若小于R，计算距离系数Ki(di)并则根据式(12)修改该个体适应度值，反之不变。
5) 各层服务迭代结束后，最优解适应度值与阈值Eo比较，若小于Eo，则转步骤6)；若大于Eo，则转步骤7)。
6) 层间服务迁移，并转步骤2)。
7) 输出最优服务组合。
3 算例验证 本文选用串并混合连接的有向无环图任务流程为验证场景，任务集分别包含10个任务和30个任务，任务的候选服务集分包含100服务和500服务2种情况考虑，多层服务的初始值随机产生，数据的范围区间选为[1，1 000]。本文验证过程所选取的各层服务转换完的数量相同，因此各层服务质量模型的权重取相同值，即α=β=γ=1/3。算法采用MATLAB R2017a编程，在2.60 GHz处理器的64位Windows 7操作系统下进行。
选择传统智能优化算法中的GA和PSO作为比较算法。对于优化算法中关键参数的取值，相关****进行了大量实验研究并给出了参数取值的最优建议[15-16]。本文基于参数的建议值，并结合所研究的多层次制造服务组合优选场景特点，来确定本算例验证的参数取值。GA考虑交叉算子和变异算子，算子概率值分别取0.8和0.2；PSO采用全局极值法，惯性权重和速度取值范围分别设定为[0.5, 0.9]和[-5, 5]，个体速度和全局速度的加速系数都设为1.6；NGSA中，引力常数G0设为100，适应值共享半径R选为10，适应度调整系数A设为8，层间映射迁移阈值Eo设为50。各算法经过100次迭代后，适应度值和迭代时间被记录下来。
从图 5的仿真对比结果可以看出，NGSA的收敛速度和平均适应度值都优于GA和PSO。理论上分析，GA主要通过交叉算子和变异算子来保持种群的多样性，而在制造服务数量多且不规律的情况下，GA易将种群限制在相对较小的搜索范围内，不易得到全局最优解。PSO在连续性的优化问题中表现出较好的性能，但在制造服务组合优选场景中，服务模型本身是离散描述的且异构性强，PSO的收敛速度会明显变慢。NGSA将小生境技术引入GSA，有效平衡了开发能力和探索能力，在搜索陷入局部最优时能快速跳出局部范围，在更全局的范围内获得最优解。
 |
| 图 5 三种智能算法的迭代趋势 Fig. 5 Iteration trend of three intelligent algorithms |
| 图选项 |
从表 2的搜索时间角度看，当输入制造任务数量较少的情况下，NGSA的平均迭代时间高于GA，低于PSO；而当输入任务逐渐增多时，NGSA的平均迭代时间明显低于GA和PSO。理论上分析，在制造任务少的情况下，任务和服务的组合优选空间集也较小，GA和PSO都可以进行快速迭代；而在组合优选空间集变大的情况下，NGSA更能快速在不同小生境间迁移进化找到最优解，且迭代时间明显少于GA和PSO。制造服务候选集越大，输入的制造任务越多，NGSA的优势就体现得越明显。
表 2 三种智能算法的时间性能 Table 2 Time performance of three intelligent algorithms
| 任务集/服务集 | 算法 | 最优适应度 | 最差适应度 | 平均适应度 | 平均迭代时间/ms |
| 10任务/100服务 | NGSA | 100.002 | 75.037 5 | 96.181 | 31.48 |
| GA | 99.994 2 | 17.604 3 | 82.171 1 | 23.12 | |
| PSO | 100.002 | 65.250 3 | 93.289 5 | 45.24 | |
| 10任务/500服务 | NGSA | 100.003 | 78.217 2 | 96.056 7 | 43.97 |
| GA | 101.146 | 17.988 72 | 82.016 4 | 37.6 | |
| PSO | 100.004 | 68.762 | 94.063 9 | 51.7 | |
| 30任务/100服务 | NGSA | 199.985 | 167.485 | 190.416 | 75.6 |
| GA | 199.981 | 59.179 | 168.23 | 78.08 | |
| PSO | 200.001 | 140.691 | 187.58 | 109.03 | |
| 30任务/500服务 | NGSA | 200 | 146.342 | 193.048 | 99.4 |
| GA | 203.228 | 19.734 3 | 165.127 | 114.88 | |
| PSO | 200.002 | 143.183 | 186.944 | 158.12 |
表选项
4 结论 1) 本文在详细阐述制造任务和制造服务多层次特点的基础上，从多层次的角度对制造服务进行描述和建模，分别给出资源服务、功能服务和流程服务3个不同层次服务的模型。然后从服务组合优选角度，选取服务执行时间、服务花费成本和服务用户评价3个质量评估指标，构建多层次服务组合优选的评估模型。
2) 基于多层次制造服务模型和组合优选评估模型，本文提出一种基于小生境的NGSA。该算法引入小生境的拥挤度因子和适应值共享技术，一方面把拥挤度因子纳入到吸引力概率因子统一考虑，另一方面通过调整小生境内共享个体的适应度值，使组合优选过程能及时跳出局部搜索范围，进入到全局搜索从而得到最优解，有效提升了算法的收敛性和准确性。通过与传统GA、PSO进行仿真对比，结果表明NGSA在收敛速度、收敛时间上都具有明显的优势，从而验证了NGSA在解决制造服务组合优选问题上的合理性和有效性。
参考文献
| [1] | 李伯虎, 张霖, 王时龙, 等. 云制造-面向服务的网络化制造新模式[J]. 计算机集成制造系统, 2010, 16(1): 1-7. LI B H, ZHANG L, WANG S L, et al. Cloud manufacturing:A new service-oriented networked manufacturing model[J]. Computer Integrated Manufacturing Systems, 2010, 16(1): 1-7. (in Chinese) |
| [2] | 张霖, 罗永亮, 范文慧, 等. 云制造及相关先进制造模式分析[J]. 计算机集成制造系统, 2011, 17(3): 458-468. ZHANG L, LUO Y L, FAN W H, et al. Analysis of cloud manufacturing and related advanced manufacturing models[J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 458-468. (in Chinese) |
| [3] | 陶飞, 张霖, 郭华, 等. 云制造特征及云服务组合关键问题研究[J]. 计算机集成制造系统, 2011, 17(3): 477-485. TAO F, ZHANG L, GUO H, et al. Typical characteristics of cloud manufacturing and several key issues of cloud service composition[J]. Computer Integrated Manufacturing Systems, 2011, 17(3): 477-485. (in Chinese) |
| [4] | 李伯虎, 张霖, 任磊, 等. 云制造典型特征、关键技术与应用[J]. 计算机集成制造系统, 2012, 18(7): 1345-1355. LI B H, ZHANG L, REN L, et al. Typical characteristics, technologies and applications of cloud manufacturing[J]. Computer Integrated Manufacturing Systems, 2012, 18(7): 1345-1355. (in Chinese) |
| [5] | LIANG G, JING X Q. Optimization technology in cloud manufacturing[J]. The International Journal of Advanced Manufacturing Technology, 2018, 97(1-4): 1181-1193. DOI:10.1007/s00170-018-1991-0 |
| [6] | XU W J, YU J J, ZHOU Z D, et al. Dynamic modeling of manufacturing equipment capability using condition information in cloud manufacturing[J]. Journal of Manufacturing Science and Engineering, 2015, 137(4): 040907. DOI:10.1115/1.4030079 |
| [7] | HUANG B Q, CHENG H L, TAO F. A chaos control optimal algorithm for QoS-based service composition selection in cloud manufacturing system[J]. Enterprise Information Systems, 2014, 8(4): 445-463. DOI:10.1080/17517575.2013.792396 |
| [8] | LIU N, LI X P.A resource virtualization mechanism for cloud manufacturing systems[C]//4th International Working Conference on Enterprise Interoperability.Berlin: Springer, 2012, 122(2): 46-59. |
| [9] | WANG L, GUO S S, LI X X, et al. Distributed manufacturing resource selection strategy in cloud manufacturing[J]. International Journal of Advanced Manufacturing Technology, 2018, 94(9-12): 3375-3388. DOI:10.1007/s00170-016-9866-8 |
| [10] | 王尔申, 庞涛, 曲萍萍, 等. 基于混沌的改进粒子群优化粒子滤波算法[J]. 北京航空航天大学学报, 2016, 42(5): 885-890. WANG E S, PANG T, QU P P, et al. Improved particle filter algorithm based on chaos particle swarm optimization[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(5): 885-890. (in Chinese) |
| [11] | QI J, XU B, XUE Y, et al. Knowledge based differential evolution for cloud computing service composition[J]. Journal of Ambient Intelligent and Humanized Computing, 2017, 9(3): 565-574. |
| [12] | LI C Y, GUAN J H, LIU T T, et al. An autonomy-oritented method for service composition and optimal selection in cloud manufacturing[J]. International Journal of Advanced Manufacturing Technology, 2018, 96(5): 2583-2604. |
| [13] | YAN X, LAU R Y, SONG D, et al. Toward a semantic granularity model for domain-specific information retrieval[J]. ACM Transactions on Information Systems, 2011, 29(3): 15. |
| [14] | RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA:A gravitational search algorithm[J]. Information Sciences, 2009, 179(13): 2232-2248. DOI:10.1016/j.ins.2009.03.004 |
| [15] | 胡洁. 智能优化算法理论及应用[M]. 2版. 广州: 世界图书出版公司, 2015: 95-97. HU J. Theory and application of intelligent optimization algorithms[M]. 2nd ed. Guangzhou: World Publishing Corporation, 2015: 95-97. (in Chinese) |
| [16] | HORN J, GOLDBERG D E.A timing analysis of convergence to fitness sharing equilibrium[C]//5th International Conference on Parallel Problem Solving from Nature.Berlin: Springer, 1998, 1498: 23-33. |
