一种支持高效服务选择的混合增强ABC算法

张宏国，陈 阳，马 超，方 舟，黄 海

(1.哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080；2.哈尔滨理工大学 软件与微电子学院，哈尔滨 150080；3.黑龙江省网络空间研究中心，哈尔滨 150001)

0 引 言

面向服务计算[1](service oriented computing, SOC)是一种实现复杂软件服务系统的流行范式。在SOC范式中，复杂软件服务系统的业务功能被封装到可互操作的软件服务中，并通过标准的发布，发现与聚合过程直接重用于新的复杂软件服务系统[2]。作为SOC范式的关键方法，服务聚合是对互联网上可用的软件服务进行动态选择与编排，以按需提供组合软件服务[3]。这种组合软件服务能够满足单个软件服务无法满足的大规模的、个性化的用户要求，从而为用户提供更高的服务价值。

目前，互联网上存在大量功能方面相似但是非功能方面不同的软件服务，如何快速发现和组合这些软件服务成为现如今研究的热点。为了解决这一问题，基于群体智能的启发式算法被广泛应用于服务选择过程。以遗传算法[4]、粒子群算法[5]、蚁群算法[6]和人工蜂群算法[7]为代表。其中，人工蜂群[8](artificial bee colony, ABC)算法凭易于理解、应用方便等特点，以及在解决连续数值优化问题时展现的突出性能而受到越来越多的关注。文[9]利用Sigmoid函数将任意实数映射到(0,1)之间，再以一定概率变换为0或1，将经典的ABC算法应用到二进制离散优化问题中，提出了离散型ABC算法。文[10]则利用一系列逻辑运算，改进了离散型ABC算法，将其扩展到一般n值离散化问题。但它们与经典的解决连续域问题的ABC算法一样，均不适用与解决服务选择问题。服务选择问题虽然属于离散域问题，但是离散域的空间巨大，并且多维空间中每一维的元素又是多维的离散值，这无疑增加了问题解决的难度。

目前，已有学者在应用ABC算法解决服务选择问题方面做了一些研究，并取得一定的研究成果。文[11]为了有效解决服务选择问题，引入了一个数学模型，并采用带有混沌因子的禁忌策略增强了ABC算法。文[12]介绍了最优连续性概念的定义，并提出了基于阈值的算法(TBA)和基于距离的算法(DBA)。文[13]提出了对ABC算法的一种增强，它使用动态选择和替换邻居。这种选择和替换过程的目的是平衡算法的探索和开发机制。

然而，由于当前互联网上可用的软件服务数量呈现爆炸性增加的趋势，导致ABC算法需要搜索的空间越来越大。与此同时，用户的需求呈现出个性化、动态化的趋势，对ABC算法的性能提出了更高的要求。为此，本文提出了一种混合增强ABC算法-HEABC。HEABC算法将K-means算法、KNN算法与ABC算法融合，保证ABC算法在离散解空间更新解时，保持连续性。进一步地，算法通过增加蜜蜂群体之间信息共享这一能力，增强了蜜蜂群体的探索和开发能力。最后，通过数值仿真实验，验证了HEABC算法的性能。

1 服务选择问题描述

目前，在企业开发复杂软件服务系统的实践中，普遍利用互联网基础设施来集成异构平台上的不同软件服务，以实现高效满足用户需求这一目标。面向服务的架构[14](service-oriented architecture, SOA)提供了可用于从功能性方面满足用户需求的标准解决方案，利用它可以将异构平台上的软件服务统一封装成Web服务。Web服务[15]具有可互操作的、松散耦合的、定义良好的和即时集成等特征。

用户的功能性需求可以采用不同结构的工作流模式表示。针对不同的功能性需求，有4种典型的模式，如图1所示。在顺序模式中，用户需求按顺序被满足；在并行模式中，某些用户需求同时被满足；在条件模式中，某些用户需求以特定概率P被满足；在循环模式中，某些用户需求可能需要被满足多次。一般的说，用户的功能性需求由上述4种模式中的一种或几种聚合而成，图2给出了一个包含10个抽象软件服务AS的复杂工作流实例。

图1 工作流模式Fig.1 Workflow patterns

图2 复杂工作流实例Fig.2 An example of complex workflow

服务选择问题的表示有n个抽象软件服务，每个抽象软件服务都有来自不同服务提供者的m个具体软件服务，这些具体软件服务在功能上相似，均可以满足对应的抽象软件服务的任务需求，因此，可能解的个数等于n×m，如图3所示。

图3 服务选择问题表示Fig.3 service selection problem representation

如上所述，用户的功能性需求可以通过综合利用四种典型的工作流模式，聚合n个抽象软件服务来表示，接着针对n个抽象软件服务，依次从对应的候选集(由m个功能相似的具体软件服务构成)中随机选择一个来实现抽象的软件服务，即可完成服务聚合过程。

但是抽象软件服务的候选集中不同的具体软件服务可能具有不同的非功能性特征，通过随机选择方法构成的解决方案可能无法满足用户的非功能性需求，为此，需要具体刻画软件服务的非功能性特征。传统的服务质量[16](quality of service, QoS)语义不足以完全的描述软件服务的非功能性需求。为了解决这一问题，本文引入服务契约[17]这一概念，利用契约条款来更加充分的刻画软件服务的非功能性需求。

如图4所示，组合软件服务(composite software service)由一系列原子软件服务(atomic software service)按照一定结构模式聚合而成，它们均具有自己的服务契约(service contract)。服务契约由一系列契约条款(contractual terms)组合构成。这些契约条款从服务质量QoS、法律领域(legal aspects)、知识产权(intellectual property)和业务领域(business aspects)等4个方面描述软件服务的非功能特性。例如，当我们从非功能性方面刻画一个软件服务时，不仅可以从响应时间、吞吐量、可靠性等服务质量QoS的角度对其进行描述，还可以从业务领域的角度描述软件服务的使用价格，从法律领域的角度描述软件服务的数据安全等级要求。

图4 服务契约概念模型Fig.4 Concept model of service contract

综上所述，为了满足用户在服务契约条款方面的要求，我们从功能性和非功能性方面刻画了用户需求和软件服务，那么服务选择问题就可以定义为针对能够体现用户需求的抽象软件服务流程，从n×m大小的离散解空间中，选择最优化的解方案。

2 ABC算法

ABC算法[18]由Karaboga等提出，其是模拟蜜蜂觅食行为的群体智能算法。算法包含3个不同阶段的搜索过程：在阶段1——雇佣阶段中，雇佣蜂探索解空间，寻找更好的解；在阶段2——跟随阶段中，跟随蜂等待雇佣蜂探索的解，根据解的质量来选择跟随的对象。在前两个阶段中，蜜蜂仅记录每次迭代中当前的最优解。在阶段3——侦查阶段中，如果搜寻次数超出预先设计的阈值后，当前解的质量仍未改善，就会派遣侦察蜂来随机的寻找新的解。

在搜索开始阶段，雇佣蜂在食物源周围根据式(1)搜索产生新食物源，即

vij=xij+r(xij-xkj)

(1)

其中：xij为当前的可行解，j∈{1,2,3,…,D}为随机选择的需要修改的维度，D为解的维度；xkj为随机选择的相邻解，i,k∈{1,2,3,…,S}，S为雇佣蜂的数量，i≠k；r为[-1,1]的随机数。

随后雇佣蜂计算搜索出食物源的质量，当所有跟随蜂完成式(1)的运算后，会飞回到信息交流区共享当前的食物源信息，跟随蜂根据式(2)选择跟随雇佣蜂进行进一步的寻优。文[19]在经典ABC算法的基础上提出了一种优化的计算食物源选择被选择概念的方法，即

(2)

其中：fi为雇佣蜂搜寻出食物源的适应度值；fbest为当前种群中适应度的最佳值。

随后跟随蜂采用与雇佣蜂相同的搜索方式进行邻域搜索，寻找出新的可行解，并计算其适应度值，然后记录当前找到的最优解。雇佣蜂和跟随蜂进行比较，保留两个可行解中较好的一个。侦察蜂监视雇佣蜂和跟随蜂的搜索过程，如果迭代的次数超出了预先设定的阈值，所得到的当前可行解的质量不再有改善，这一可行解将会被放弃，然后雇佣蜂转换成侦察蜂，随机初始化一个新的解。

在本研究中，我们将K-means算法和KNN算法融合到ABC算法中，在保证更新解的连续性的情况下，通过赋予蜜蜂共享信息的能力，在蜜蜂之间建立信息共享机制，增加蜂群的探索能力。

3 HEABC算法

对于ABC算法来说，初始种群的优劣直接影响算法本身的收敛速度。对于先验知识匮乏的契约感知服务选择问题，初始解分布应尽可能均匀[20]。为此，在进行HEABC算法的种群初始化时，本文利用K-means算法对D个候选软件服务集进行聚类分析，令K=SN，SN是雇佣峰、跟随蜂的个数，也是初始解的个数，然后从K个类别的子集中依次选取候选食物源作为初始解，以此来保证初始解分布的均匀性。

ABC算法最初是针对连续域问题而设计的，然而契约感知服务选择是离散域中的优化问题。因此，在利用ABC算法求解这一问题时，必须对其进行离散化处理，即HEABC算法是离散型的ABC算法。本文在利用HEABC算法求解契约感知服务选择问题时，蜂群从第一个抽象软件服务开始并跳转直到它们到达最后一个抽象软件服务。在每次跳转时，蜂群将一个具体的软件服务添加到解决方案路径中。在后续迭代中，蜂群会尝试提高解决方案质量并记录解决方案未被改善的次数，如果没有改进的次数超过了设定的阈值，就利用侦查蜂拓展新的解，选择和替换过程如图5所示。

图5 选择和替换过程示意图Fig.5 The schematic diagram of selection and replacement process

Pr=Ord(CSi,j,h)/H*Coe

(3)

因为在更新参数维度时，采用随机选取的方式会缺乏导向性。所以为了提高HEABC算法的开发能力，本文增加了种群个体之间进行信息共享的能力，通过计算当前解和从种群中随机抽取的另一个解间的欧式距离来表征二者之间的差异度。

全局差异度，即两个解在D维空间上的总体差异度，其计算为

(4)

局部差异度，即两个解在D维空间中的某一维上的差异度，其计算为

(5)

为了更好的平衡算法的开发能力和探索能力，本文根据全局差异度的大小制定更新维度的选取策略。

策略1.当GD≥Th时，对D个LDj进行降序排列，从前一半中随机选择一维更新；

策略2.当GD

在设计契约感知服务选择问题的优化目标时，我们一方面要考虑法律领域、知识产权和业务领域维度的参数对优化目标的限制，另一方面也要将服务质量QoS维度的参数兼容进来，下面给出了一个常见的契约感知服务选择问题的优化目标。

F=(w1g1(RT)+w2g2(T)+w3g3(R))⊕

IsSat(DS)

(6)

其中：RT为响应时间；T为吞吐量；R为可靠性；函数g为对应质量参数的归一化和计算函数，其根据质量参数的正负向，以及抽象软件服务的逻辑结构不同而不同；权重w可以采用层析分析法，在与抽样的用户进行充分沟通后，进行确定；DS为数据安全要求，即某一个具体软件服务被聚合时，对方案中其他软件服务在数据安全等级是哪个的要求；函数IsSat(DS)的作用是判断此方面的约束是否被满足，如未被满足，则函数取值为0。

K-means算法和KNN算法的融入，保证了HEABC算法在雇佣蜂阶段和跟随蜂阶段更新解时，始终保证连续性；而种群间信息共享能力的增加，增强了蜜蜂种群对接的探索和开发能力。HEABC算法伪代码如下：

输入：n个抽象软件服务集AS=[AS1,AS2,…,ASn]，以及每个抽象软件服务ASn下所包含的m个对候选服务集CS=[CS1,CS2,…,CSm]。

输出：最优解

初始化：种群数SN，雇佣蜂eb，跟随蜂ob，侦查蜂sb，最大寻优次数Limits，算法运行次数Z

Begin

初始化蜂群中所有蜜蜂的参数

Limit=0

eb=ob=SN/2

sb=SN

均匀地初始化eb

计算适应度值

foriter=0→Z-1

fori=1→eb

利用策略1或者2产生一个新的解

利用式(3)保证新解的连续性

使用式(6)计算新解x’i的适应度值

ifF(X’i)

then

Xi=X’i

else

++Limit[i]

end

使用式(2)计算prob[Xi]

end

forj=1→ob

根据prob[]选择一个解

利用策略1或者2产生一个新的解

利用式(3)保证新解的连续性

使用式(6)计算新解X’i的适应度值

ifF(X’i)

Then

Xi=X’i

else

++Limit[i]

end

end

fori=1→sb

ifLimit[i]==Limits

then

随机初始化一个新的sbi

Limit[i]=0

end

end

保留最优解

end

返回最优解

End

复杂性分析：算法涉及以下运算：初始化，雇佣蜂与跟随蜂寻优，候选服务集聚类，类别判断，重新生成候选集，新旧解距离计算，适应度计算，侦查蜂初始化。初始化成本为O(SN×N)，其中SN是种群大小，N是抽象软件服务数。雇佣蜂与跟随蜂搜索成本复杂度为O(Z×SN×N×D)，其中Z是迭代次数，D是维度。候选服务集聚类的复杂度为N×O(K)，其中K为聚类的类别数，且K=SN。类别的判断消耗成本为N×O(SN)。重新生成候选集消耗的成本为N×O(SN×H)，H为生成相识度最高候选软件服务的个数。适合度计算时间复杂度为O(Z×SN×N×D)。在最坏情况下，每次寻优时均达到Limits时，每次均会派遣侦查蜂，派遣侦查蜂的时间复杂度为O(Z×SN)。由上述可得，HEABC算法的时间复杂度为O(SN×N)+O(Z×SN×N)+N×O(K) +N×O(SN×H)+O(Z×SN×N×D)+O(Z×SN)。

4 仿真实验

实验环境是在一台装有英特尔i5处理器和Windows 10操作系统的个人电脑上进行的。我们设计了仿真实验以验证算法的有效性，并与文[12]中的TBA算法和文[13]中的EABC算法进行对比。程序是使用JAVA语言实现的，代码是在文[12]的基础上做的优化。在初始化解时，首先进行了特征聚类，保证算法执行过程中得到的解均在离散空间内。在执行选择和替换操作时，对候选服务集提前分类，将候选解分为不同类别的簇，使用KNN算法从对应的簇中对解进行随机替换，保证解的相似性。

4.1 参数设置

我们在不同的两类数据集做了仿真。第一种类型的数据集有100个web服务，它们具有不同数量的任务，分别是10、20、30、40、50、60、70、80、90和100。第二种数据集有10个任务，每个任务对应不同数量的候选服务集，分别是100、200、300、400、500、600、700、800、900和1000。每种类型有60个数据集。这些数据集是人工生成的，我们将QoS属性的值定义在[0,1000]范围内。

算法所使用的控制参数如表1所示，分别为初始化蜂群数SN、算法的执行次数Z、最大寻优次数Limits、调和系数参数Coe和相识度最高的候选服务集个数参数H。

对于每个数据集，实验共重复30次，以检测算法对可能影响算法行为的随机因素的鲁棒性。算法的评价指标为最佳解的平均质量和平均执行时间。

表1 实验参数设置Tab.1 Experimental parameter settings

4.2 实验结果

在第一类数据集上进行算法验证，可知该算法对于不同数量的Web服务性能进行实验，可得到的最优解对比图如图6所示，在Web服务数量较少时(0～100之间)，TBA、EABC和HEABC算法在求解质量上一致，并无太大的浮动。但是在Web服务数量超过100时，TBA的求解质量呈下降趋势，而EABC和HEABC算法波动不大，但在相同条件下，HEABC算法求解质量略高于EABC算法。执行时间对比图如图7所示，TBA算法在求解的执行时间呈上升趋势，EABC和HEABC算法在执行时间上保持一致，整体呈下降趋势。

图6 算法对不同数量的Web服务的性能Fig.6 Algorithms’ performance for different numbers of web services

图7 算法对不同数量的Web服务性能Fig.7 Algorithms’ performance for different numbers of web services

在第二类数据集中对算法验证，可知该算法对于不同数量的任务性能进行实验，可得到的最优解对比图如图8所示，在保持整体的Web服务数相等时，随着任务数的增多TBA求解质量呈下降趋势。HEABC和EABC算法相较于稳定，且HEABC算法求解质量略高于EABC算法。执行时间的对比图如图9所示，在保持整体的Web服务数相等时，随着任务数的增多3种算法最终的执行时间趋近于一致。

图8 算法对不同数量的任务性能Fig.8 Algorithms’ performance for different numbers of tasks

图9 算法对不同数量的任务性能Fig.9 Algorithms’ performance for different numbers of tasks

总的来说，对于不同的数据集，HEABC算法虽然在寻优的步骤上增加了聚类操作，但由于是并行操作，并未增加过多的时间成本，所以对于求得的最终解，执行时间与EABC相差无几。而在解质量上，HEABC算法略优于EABC和TBA算法，这是因为通过聚类以及对相似服务的选择，增加了蜜蜂群体间信息共享的能力，从而在寻优时能保留更好的解。

5 结 论

为了高效地完成服务选择和匹配，本文改进了传统的人工蜂群算法，对算法蜜源初始化以及蜂群寻优两个方面做了改进。首先通过K-means算法对候选蜜源进行特征聚类，将蜜源分为不同类别的簇，每一部分对应着当前类别下的相似解，代表着同一类原子服务。然后通过KNN算法对每次寻优得到最新解进行类别判断，找到与之对应的簇，再次更新解的参数时，只在其对应类别阈值范围内浮动，从而保证了所有解都在离散空间内。最终的仿真实验表明，本文所提的算法在求解质量和求解时间上均有所提高，应用前景十分广阔。