基于改进人工蜂群算法的云制造服务组合优化方法

胡强，田雨晴，綦浩泉，吴鹏，刘庆雪

（1.青岛科技大学信息科学技术学院，山东 青岛 266061；
2.昆明学院机电工程学院，云南 昆明 650214）

作为一种典型的“互联网+”制造实现模式，云制造通过共享或协同分布式制造资源与能力，快速实现各类产品的定制[1]。企业将自身的制造资源或业务功能进行服务化封装，发布在各类云平台，用户可以按照需求租用云制造服务，弥补自身制造能力的不足，从而便捷地构建和部署新的制造业务。

对于一些复杂的制造需求，云制造服务平台需要将一组相关的制造服务进行组合，以云制造服务流程的形式实现响应。云平台中存在许多功能相似的云制造服务，在建立服务组合流程时，每个业务节点都可能存在多个可供选择的服务，不同的业务节点中的云制造服务之间通过组合，可以产生大量的云制造流程实例[2]。因此，如何从大量的服务组合中求解最优组合流程实例成为云制造领域所面临的一个难题[3]。

群智能算法是服务组合流程优化的主流解决方法，如遗传算法（GA,genetic algorithm）[4]、粒子群优化（PSO,particle swarm optimization）算法[5-6]、人工蜂群（ABC,artificial bee colony）算法[7-8]等。为了提高搜索能力和优化质量，研究者在上述算法的基础上提出了一系列的改进方法，这些方法在组合优化求解过程中已取得不错效果。然而，已有研究在构建组合优化求解模型时，主要关注服务自身质量属性，缺乏考虑服务之间的协同质量，此外，在组合流程的寻优质量、效率及稳定性等方面也存在进一步提升的空间。

为此，本文提出一种基于改进人工蜂群算法的云制造服务组合优化方法，主要贡献如下。

1) 挖掘云制造服务组合场景下的服务协同要素，建立了3 种服务协同质量度量方法，用于评价云制造服务之间的组合关联强度。

2) 构建了融合云制造服务自身质量与协同质量的组合优化决策模型，提升了云制造服务组合优化的合理性。

3) 设计了一种具有多搜索策略岛屿模型的人工蜂群算法，并将其用于云制造服务组合优化模型的求解。实验证明所提算法有效提升了组合流程的寻优质量、效率和稳定性。

服务成本、可靠性、可用性、响应时间等属性是研究者在构建服务组合优化模型时常考虑的基本要素。例如，考虑到不稳定的QoS 可能会影响服务组合的可靠性，Xie 等[4]通过计算历史QoS 的偏差值来确定QoS 的稳定性，综合考虑QoS 稳定性和协作能力来提高服务组合的有效性。Thangaraj 等[9]通过可用性、响应时间、吞吐量和服务之间的互操作性建立组合优化模型评估服务组合的质量，为用户提供了具有最大吞吐量和互操作性的高可靠性服务组合。

Wang[10]在研究云制造服务组合异常重构时，在传统服务质量基础上，将加工质量和服务占用时间等因素作为约束构建优化模型，提出基于强化Harris-Hawks 优化器服务组合重构算法，提高了重构的效率和精确度。任磊等[11]提出了服务合作强度，将其划分为交易合作关系强度、共同社区强度、物理距离关系强度、资源相关关系强度、社会相似关系强度五类，以传统服务质量和合作强度的加权最大化为目标构建了服务组合优化模型，提高了流程优化质量。在上述成果的基础上，本文将进一步挖掘云制造服务组合流程中涉及的协同要素，建立更加科学合理的优化决策模型。

在组合优化模型求解方面，为了解决现有群智能算法在组合优化求解中质量不高、难以兼顾局部与全局最优等问题，研究者从不同角度改进各类算法。例如，Tarawneh 等[12]构建一种蜘蛛猴优化算法，通过使用负载均衡器来分配工作负载，最大限度地减少服务组合的响应时间，很好地平衡虚拟机资源、处理机位置等信息来为用户推荐最合适的Web 服务。Jin[13]提出一种基于均匀变异和改进鲸鱼算法的eagle 搜索策略，利用均匀变异进行全局搜索来保持种群的多样性，基于改进鲸鱼优化算法进行局部搜索，平衡算法的全局和局部搜索能力，提高组合最优解的求解质量。Wu等[14]将花卉授粉算法与快速非支配排序及种群选择策略相结合，提出一种混合花卉授粉算法，在执行过程引入差分进化策略和随机干扰策略，提高了服务组合算法的优化能力。

在众多的群智能算法中，人工蜂群算法因参数少、收敛快、计算简便等特点在各类优化问题中备受青睐。为提高人工蜂群算法的性能，Zhou 等[15]通过构造精英群体，在雇佣蜂和观察蜂阶段分别改进解搜索方法，并基于精英群体改进邻域搜索算子，更好地实现探索和开发能力之间的平衡。Arunachalam 等[16]提出了一种基于综合概率多搜索解决方案的人工蜂群优化方法，能够有效地确定工作流图的源顶点和汇顶点之间存在的最佳路径，利用接受规则和多搜索概率参数来解决服务组合的全局优化。Ye 等[17]提出了一种基于随机邻域结构的高效搜索人工蜂群算法，为每个解设计独立且大小随机的邻域结构，并在随机邻域结构上改进搜索策略，采用深度优先搜索方法来增强观察蜂的探索能力，使该算法具有更优的性能。

云平台中存在许多相似的云制造服务，对于服务组合流程，流程中每个节点都存在一组满足需求的候选服务，形成候选响应服务集合。从每个候选响应服务集合中选择一个服务，即可组合成为用户所需的云制造服务流程实例。如图1 所示，若流程模型包含4 个服务节点，每个节点对应的候选响应服务集合中的服务数目分别为w、x、y和z个，则可形成wxyz种服务组合。

图1 流程实例优化示意

随着流程中服务节点数量的增多，可满足用户需求的云制造服务组合流程数量将呈指数级增加，这些服务组合流程的质量各异，因此，如何从候选响应服务集合中构建高质量的服务组合流程是云制造流程响应所面临的一个重要问题。

2.1 组合优化决策要素

在构建服务组合流程时，流程的服务质量包含两类，一类是组成服务本身所固有的质量属性，质量属性在大量服务计算相关研究文献中均有介绍，不再详述。本文选取制造周期（MT）、价格（SC）、信誉（SP）、可靠性（SR）参与流程优化。另一类是服务节点之间的协同质量，在构建服务组合流程时，服务之间的历史合作关系、当前的政策以及迁移代价都会对相邻服务节点选择产生影响，从而影响最终服务组合流程的质量。

本文将服务节点之间的协同质量归结为迁移代价（MC）、合作强度（CI）、合作意向（CP）这三类。由于存在量纲与数值上的差异，所有决策要素的质量求解均采用最大最小归一化后的属性值。

1) 迁移代价。不同领域的云制造服务迁移代价度量要素不同，通常情况下，迁移代价主要包含迁移时间、迁移成本和迁移损耗。令mt、mc 和ml分别表示归一化后的迁移时间、迁移成本和迁移损耗，迁移代价计算方法为。

2) 合作强度。存在合作关系的服务形成了事实上的交互协作，具有服务组合质量上的潜在优势，再次合作的可能性会更大，因此合作强度是服务关联质量属性的重要评估要素。合作强度通常采用合作频次比来计算，但此类方法忽视了时间对合作强度的影响。同样的合作频次比，近期合作次数多的2 个服务的合作强度应该更大，基于上述考虑，本文构建了式(2)所示的合作强度计算方法。

其中，tc 和tk 分别为当前时间段和tk 时间段，Ctk(si,sj)为tk 时间段服务si与sj的合作次数，e-(tc-tk)为时间修正因子，通过tk 与tc 的差值大小来调节不同时间段中的合作次数在合作强度中的贡献大小。

3) 合作意向。合作意向由历史合作满意度和政策扶持度共同决定。历史合作满意度高的服务之间通常具备更优的服务组合质量，同时，受国家政策扶持力度大的服务通常具备服务质量上的优势。历史合作满意度hc 和政策扶持度ps 均采用等级分制进行评价。

历史合作满意度hc 的评分规则借鉴文献[18]中的量化规则，将对关联服务的满意度划分为5 个等级，各级赋分为{(非常不满意：1 分)，(不满意：3 分)，(基本满意：5 分)，(满意：7 分)，(非常满意：9 分)}。政策扶持度ps 由政策发布单位等级评分和政策类型评分共同决定。依据政策发布单位级别，赋分为{(国家级：4 分)，(省级：3 分)，(市级：2分)，(地区级：1 分)}；
依据政策类型，赋分为{(规划级：3 分)，(条例级：2 分)，(通知级：1 分)}。令hc 和ps 为归一化后的历史合作满意度和政策扶持度，则合作意向为

2.2 组合优化决策模型

为了便于构建云制造服务组合优化决策模型，首先给出云制造服务组合模型的形式化定义。

定义1云制造服务组合模型

云制造服务组合模型定义为二元组csp，csp 及其组成元素规约形式如下

其中，sn 表示流程业务节点，符号→表示顺序关系。csp 表示由sn 节点按照顺序结构组成的业务逻辑序列。sn 节点分为流程起始节点sb、流程终止节点se、服务节点s和子流程结构块sp 这4 种类型。其中，s用于描述云制造服务，sp 用于描述流程需求中存在的选择、并发或循环结构的子流程。

sp 定义为路由节点rn 与服务节点序列sl 的集合，其中sl 为顺序执行的服务节点序列；
rn 中的节点成对匹配出现，路由节点对{as,aj}、{os,oj}和{ls,le}分别用于构建并发结构、选择结构和循环结构。图2 为一个云制造服务组合模型示例，由3 个云制造服务s1，s2和s3以及子流程结构块sp1组成。sp1是通过路由节点as1和aj1构建的并发流程结构，对应3 个分支流程sl1、sl2和sl3，每个分支均为顺序结构的云制造服务节点序列。

图2 云制造服务组合模型示例

假设服务组合模型csp 中包含起始节点sb、终止节点se、n个服务节点(s1,s2,…,sn)、m个子流程结构块(sp1,sp2,…,spm)。子流程结构块spi所包含的服务数量为ui，其组成服务表示为{spi_s1,spi_s2,…,spi_sui}。为了便于计算流程的服务质量，将sb 和se 分别编号为s0和sn+1。

服务组合的4 种流程结构如图3 所示，循环结构可以看作重复执行的顺序结构，因此多数文献中将循环结构的服务质量求解等价于顺序结构，本文也采取类似处理方式。表1 提供了由n个服务节点组成的4 种流程结构的服务质量计算方法，按照表中提供的求解规则，服务组合模型csp 对应的流程质量模型如式(4)～式(8)所示。

图3 服务组合流程结构

表1 不同流程结构的服务质量计算方法

包含n个服务节点的csp 对应的迁移代价MC、合作强度CI、合作意向CP 的计算方法如式(9)～式(11)所示。

其中，MC(si,si+1)、CI(si,si+1)和CP(si,si+1)分别为服务节点si与si+1之间的迁移代价、合作强度和合作意向，特别地，s0与s1、sn与sn+1之间的上述质量属性值均设置为0。

服务节点si和si+1之间加入子流程结构块，将改变MC(si,si+1)、CI(si,si+1)和CP(si,si+1)的值。将m个子流程结构块融入流程节点s0,s1,s2,…,sn,sn+1，存在如图4 所示的3 种融入模式。

图4 子流程结构块的融入模式

加入并行子流程结构块后的服务组合之间的协同质量属性MC、CI 和CP 计算式如式(12)～式(14)所示。其中，每个计算式的第一行对应在起始节点s0与第一个节点之间加入并行子流程结构块sp1，此时服务协同质量变为sp1中所有服务节点与s1之间的协同服务质量之和。计算式的第二行表示在节点si与si+1之间加入了并行子流程结构块spk，服务协同质量变为si与spk以及si+1与spk中所有服务节点的协同质量值之和。计算式的第三行表示在最后一个节点sn与终止节点sn+1之间加入并行子流程结构块sm，服务协同质量变为sn与sm中所有服务节点的协同质量值之和。

加入选择子流程结构块后的流程服务之间的协同质量属性MC、CI 和CP 计算式如式(15)～式(17)所示，计算式中每一行的含义与式(14)～式(16)相同，但由于是选择结构的子流程结构块，在进行协同质量处理时不再是汇总求和，而是根据质量属性的不同，分别取最大值或最小值。

基于融入子流程结构块后的MC、CI 和CP 计算方法，cps 对应的服务协同质量的QoS 值的计算式为

式(19)为本文基于服务属性（制造周期MT、价格SC、信誉SP、可靠性SR）和服务协同属性（迁移代价MC、合作强度CI、合作意向CP）建立起的服务组合流程的质量优化决策模型。

文献[11]指出，复杂制造业务过程中广泛存在着资源运输、信息传递和知识共享问题，服务之间也存在社会协作关系，因此，将本文构建的包含迁移代价、合作强度、合作意向3 个要素的协同质量融入组合优化模型中，使优化模型更合理，最终求得的最优流程实例将优于不考虑这些要素的传统组合优化模型。

3.1 标准ABC 算法

设D为问题的维数，SN 为蜜源总量（解空间数量），xi=(xi,1,xi,2,…,xi,D)为一个蜜源（解向量），其中，xi,d为xi的第d维值。xi,d∈(Ld,Hd)，Hd和Ld分别为xi,d的上限和下限，算法迭代次数为CSN，蜜源耗尽上限limit 为SNDc(c为0～1 的参数)。

1) 初始化阶段。利用式(20)生成初始蜜源。

每个初始蜜源的蜜源量fiti为

其中，fi为所需解决问题的优化函数。

2) 雇佣蜂阶段。利用式(22)更新蜜源，计算蜜源量，用贪婪算法保留较好的蜜源，丢弃较差的蜜源。

其中，xk=(xk,1,xk,2,…,xk,D)为xi的邻域蜜源，vi,d为蜜源更新后的第d维值，φi,d为值域在[–SF,SF]的均匀分布函数，用于控制xi,d的更新步长，其中SF 为尺度因子，在标准ABC 算法中SF 设置为1。

3) 观察蜂阶段。利用式(23)计算蜜源概率。

其中，NP 为雇佣蜂的总量。根据Pi选择蜜源对其进行局部搜索，用贪婪算法保留最优解，局部搜索无法提高适应度，计数器trial 加1。

侦查蜂阶段。检查计数器trial 最大的值，若超过蜜源耗尽上限limit，则用式(20)重新生成新蜜源。

在ABC 算法的3 个阶段中，雇佣蜂随机搜索蜜源并把信息分享给观察蜂，观察蜂对依据Pi选择的蜜源进一步搜索，如果蜜源质量得不到提高，雇佣蜂或观察蜂转化为侦查蜂进行新蜜源的开采。在这3 个阶段中，每种蜜蜂都有其各自的功能，雇佣蜂用来开发新蜜源，观察蜂用来对优秀蜜源进行进一步探索，侦查蜂用来摆脱局部最优。

3.2 融合多搜索策略岛屿模型的ABC 算法

标准ABC 算法优化求解时，往往存在收敛过早、陷入局部最优等问题。引入岛屿模型，通过多岛屿演化的方式可增加解的多样性，是解决上述问题的一种有效方法。然而，现有基于岛屿模型的ABC 算法通常在每个岛屿（子种群）中采用相同的搜索方式，独立寻优的能力有待提高。

为增加种群多样性和丰富岛屿演化模式，提升ABC 算法的寻优能力，本文设计了一种融合精英种群与最优解指导的搜索策略，并结合其他已有的三类搜索策略，构建了一种融合多搜索策略岛屿模型的ABC 算法（MSSIABC）。在MSSIABC 的岛屿演化中，为每个岛屿随机选用以下搜索策略。

1) 标准人工蜂群搜索策略。在雇佣蜂阶段和观察蜂阶段采用相同的搜索方式，如式(24)所示，该策略虽然局部搜索能力较弱，但其较强的全局搜索能力能提供多样化的蜜源。

2) 基于精英种群的搜索策略[15]。选取前10%的最优的蜜源作为精英种群，在每次迭代时都计算本次迭代中最优的蜜源，采用更高密度的搜索方式进行寻优，增强局部搜索能力。

其中，φ为0～1 的随机数；
MR 为修正率，用于控制扰动频率，本文取值为0.5。

3) 融合精英种群与最优解指导的搜索策略。雇佣蜂阶段沿用标准ABC 算法搜索式。在观察蜂阶段，搜索式采用式(25)和式(26)，分别采用精英种群和当前全局最优解指导蜜源开发，在每迭代m次后选取前n个优秀蜜源对指导方向进行调整。该策略可有效提升局部搜索能力。

4) 自适应的搜索策略[18]。根据蜜源更新情况，动态改变寻优方向以提高更新成功率、加快算法的收敛速度，在雇佣蜂的搜索阶段，当邻域xk的适应度高于当前蜜源的适应度时，搜索式为

其中，φ为0.95～1.5 的随机数，步长stepe1为

若低于当前蜜源的适应度，搜索式为

其中，ψ为1.2～1.6 的随机数，φ为0.5～1.5 的随机数，步长stepe2为

在观察蜂阶段，邻域适应度高于当前蜜源的适应度时，搜索式为

其中，φ为–0.45～0.45 的随机数，步长stepf1为

邻域适应度低于当前蜜源适应度时，搜索式为

其中，φ为–0.45～0.45 的随机数，步长stepf2为

基于MSSIABC 的云制造服务组合流程优化求解算法如算法1 所示。

算法1基于MSSIABC 的云制造服务组合流程优化求解算法

输入组合模型 csp，候选响应服务集合CandiServ，最大迭代次数max_iter,岛屿数量ln,迁移频率Fm，迁移比例Rm

输出流程响应集合RespServ，流程服务质量QoS(csp)

步骤1)～步骤4)根据组合模型csp 和候选响应服务集合Candiserv 完成解空间的初始化，构建流程服务质量的适应度函数，然后将解空间划分为ln个岛屿，并为每个岛屿随机分配搜索策略。随后，在算法达到最大迭代次数前，针对每个岛屿循环执行以下处理。

步骤8)～步骤11)执行所在岛屿分配的雇佣蜂阶段搜索策略，产生新的解并根据贪婪算法选择适应度最优的解。步骤12)～步骤19)根据式(25)计算出的Pi选择观察蜂阶段需要进一步开发的解xi，通过岛屿所对应的搜索方式产生新的解向量，根据贪婪算法选择适应度更优的解，当解空间的适应度不再提高时，令trial+1，直至trial 达到更新失败阈值上限limi（t本文取值为20）。步骤20)～步骤28)，当trail 达到limit 时，进入侦查蜂阶段开发新解。每迭代Fm 次，将岛屿中适应度最差的Rm 个解向量转移到相邻岛屿，直到达到max_iter。

当迭代次数到max_iter 时，步骤30)～步骤32)将岛屿中的最优解xbest及其适应度作为最终的返回结果CSS 和QoS(csp)。

为验证本文方法在服务组合中的寻优质量、效率和稳定性，构建如图5 所示的服务组合模型。为测试在不同规模数据的算法性能，数据集1～数据集4 中每个节点的候选响应服务集合中服务数量分别设置为50、100、300 和600。实验选取近3 年发表论文中的8 种算法进行对比，包含4 种ABC 改进算法和4 种非ABC 类型的群智能算法。取50 次运行结果的平均值确定最终结果，将组合流程中节点属性设置为相同的权值。

图5 服务组合模型

在对比不同算法优化得到的流程服务质量时，100次迭代内，每10次迭代监测一次流程服务质量；
100～500 次迭代过程中，每100 次迭代监测一次流程服务质量。

图6～图9 为4 个数据集下MSSIABC 与4 种ABC 改进算法MGABC[15]（multi-elite guidance artificial bee colony）、MABCM[19]（multi-subpopulations artificial bee colony with memory）、SFABC[20]（self-learning artificial bee colony）、IABC[21]（island artificial bee colony）的迭代次数–服务质量的对比。从 4 个折线图中可以看出，本文MSSIABC 算法在500 次迭代过程中，在4 个数据集的56 个监测点中，仅有3 个监测点（图6 迭代次数为30 次时，图7 迭代次数为20 次时，图9迭代次数为300 次时）的服务质量与MABCM 重合，其他53 个监测点均高于其他算法优化得到的服务质量，因此，MSSIABC 算法在模型寻优质量上得到明显提升。

图6 MSSIABC 与ABC 改进算法在数据集1 中流程优化质量对比

图7 MSSIABC 与ABC 改进算法在数据集2 中流程优化质量对比

图8 MSSIABC 与ABC 改进算法在数据集3 中流程优化质量对比

图9 MSSIABC 与ABC 改进算法在数据集4 中流程优化质量对比

此外，从图6～图9 可以看出，相比其他ABC改进算法，MSSIABC 算法能够在较少迭代轮次内获得较高的适应度值，收敛速度较快，效率较高。图10～图13 为MSSIABC 与非ABC 类群智能算法SCRIHHO[10]（service composition reconfiguration based on harris hawks optimizer ）、IGSA[11]（improved gravitational search algorithm ）、GA-HH[22]（genetic algorithm based hyper-heuristic）、A-NSGA-III[23]（adaptive non-dominated sorting genetic algorithm Ⅲ）的迭代次数–服务质量的对比。在4 个数据集的56 个监测点中，本文MSSIABC 算法均高于其他类型算法获得的流程服务质量。相比ABC 类算法，非ABC 类算法的求解得到的流程服务质量与MSSIABC 算法的求解得到的流程服务质量差距较大，这说明MSSIABC 算法的寻优能力显著高于实验中非ABC 类群智能算法。

图11 MSSIABC 与其他类型群智能算法在数据集2 中流程优化质量对比

图12 MSSIABC与其他类型群智能算法在数据集3 中流程优化质量对比

图13 MSSIABC与其他类型群智能算法在数据集4 中流程优化质量对比

除了拥有较好的寻优能力之外，MSSIABC 算法表现出优秀的稳定性。表2～表5 给出了迭代次数为20 时，各算法在多轮次运行时求得服务流程值的最差值、最优值、平均值和标准差。选择第20次迭代时的数据做稳定性对比是因为在4 个数据集中，迭代轮次为20 时，流程服务质量对应的折线形态变化均最显著。

表2 数据集1 中各算法稳定性对比

表3 数据集2 中各算法稳定性对比

表4 数据集3 中各算法稳定性对比

表5 数据集4 中各算法稳定性对比

从表2～表5 中的数据可以看出，与其他8 种算法相比，MSSIABC 在4 个数据集上的最优值均最高，这说明了MSSIABC 的寻优能力优于所有对比算法。从标准差反映的优化稳定性角度来看，MSSIABC 在4 个数据集中的标准差均小于ABC 类对比算法，这说明MSSIABC 提高了ABC 算法的优化稳定性。

与4 种非ABC 类的群智能算法相比，MSSIABC仅在数据集3 中的标准差略高于GA-HH 算法，在其他对比数据集中MSSIABC 均取得了较低的标准差，这也进一步证明了MSSIABC 算法的优化稳定性。

本文提出一种基于改进人工蜂群算法的云制造服务组合优化方法。从迁移代价、合作强度与合作意向3 个方面建立服务协同质量度量方法，构建了融合服务质量与协同质量的服务组合优化决策模型，提升了组合优化的合理性。设计了具有多搜索策略岛屿模型的人工蜂群算法，实验表明，该算法的组合流程的寻优质量、效率和稳定性均优于对比方法，能有效提升云制造服务组合的优化效果。

后续研究工作将进一步完善组合优化模型中服务协同质量的度量方法，探讨岛屿个数与搜索策略之间的关系，以进一步提升云制造服务组合的优化质量、效率和稳定性。