基于机器学习的服务组合技术研究进展

张 晔，鲍 亮

(1.中国电子科技集团公司第三十研究所，四川 成都 610041；2.西安电子科技大学 计算机科学与技术学院，陕西 西安 710071)

互联网的应用开发中已经出现了大量的Web服务，每个服务提供特定的功能。单独的个体服务已经无法满足日益复杂的用户需求，越来越多的实际项目需要将Web服务组合进行集成，以便提供更优的功能。服务组合技术可将现有的多个服务以特定的方式组合成一个高质量、高性能的逻辑整体，来满足用户的功能需求。服务组合技术在原有服务的基础上生成新的增值服务，使得系统功能可以灵活地扩展。不同服务提供商提供的功能相似的服务一般具有不同的服务质量(Quality of Service，QoS)，包括价格、吞吐量、传输延迟、错误率等。服务组合需要生成既满足相应QoS约束，又能实现用户需求功能的最优或者接近最优的组合服务[1]。

计算机技术与人工智能的飞速发展间接性带动了服务组合领域的进步。研究人员将人工智能领域的知识与传统服务组合技术结合起来，将智能化的思想引入服务组合中，推动服务组合的发展。机器学习使得服务组合算法拥有了一定的自主学习能力，从而使其能够更好地适应愈加复杂的环境。

互联网的高速发展使得服务的数量规模日益增大，服务组合的方法也需要与时俱进来适应不断变化的复杂环境。本文将对服务组合问题进行系统性的介绍：首先，介绍服务组合的分类、服务组合问题所面临的挑战以及最新的人工智能在服务组合上的应用；然后，对服务组合的问题进行总结；最后，对今后的发展方向进行展望。

1 服务组合问题的分类

服务组合问题是服务计算领域中的经典问题，其经过数十年的发展，已产生了多种分支。根据不同的划分标准，可将现有的服务组合问题划分为不同种类。本章节简要介绍了3种常见的划分标准：(1)是否已知业务的工作流；(2)优化目标的种类；(3)多目标优化方式。

1.1 是否已知组合服务的工作流

组合服务的工作流是指多个子功能按照它们之间的数据流构成的工作流程，此工作流程满足用户提供的输入输出需求。目前已有多种方法可用于生成组合服务的抽象工作流，例如路径查找策略[2]。已知用户所需组合服务的工作流，目的是在子功能对应的候选服务集内挑选出具体服务以优化其组合目标的问题，被称为半自动服务组合问题[3]。目前，针对半自动服务组合问题已有大量研究[4-6]。然而，在实践中通常难以提供这样的工作流程，这也限制了半自动服务组合方法的适用性。服务组合问题的另一分支，即全自动服务组合问题[3]，逐渐受到了关注。全自动服务组合问题根据用户提供的输入输出参数挑选具体服务进行连接，并在此过程中同时进行目标的优化[7-9]。

1.2 优化目标的种类

服务组合问题具有不同的应用背景，例如云上服务组合、物联网中的服务组合等，因此也具有不同的优化目标。本文将优化目标分为两类：(1)基于QoS的服务组合问题。QoS是对服务非功能质量的定性或定量通用评价标准，包括服务响应时间、成本、可用性、成功执行率、吞吐率等。基于QoS的服务组合问题旨在得出一个整体QoS较好的服务组合方案[10]；(2)基于其它优化目标的服务组合问题。除了QoS之外，基于不同的应用背景，还需考虑额外的优化目标，例如组合服务的子服务数量[11]、组合服务的网络QoS[12]、服务运行资源[13]等。

1.3 目标优化方式

服务组合问题往往需要同时优化多个目标。基于不同的考量，不同研究使用了不同方式进行目标优化：(1)多目标优化[14]。最直观的方式是将服务组合问题直接建模为多目标优化问题，并利用多目标优化算法寻找帕累托最优解集；(2)转化为单目标进行优化[15]。多目标算法的求解难度往往较大，因此有许多研究为每个优化目标赋予不同权重，并将多个目标根据权重加权形成一个单一指标，从而将多目标优化问题简化为单目标优化问题。但是，这种做法在简化问题求解难度的同时，也带来了局限性。在实际应用中，使用该方法无法给出相应权重。

2 服务组合问题面临的挑战

随着人工智能、互联网等领域的飞速发展，“服务组合智能化”成为了研究人员新的目标方向。服务组合虽然在过去的数十年间取得了一定的成果，但受制于传统思想方法的局限性，有关服务组合的理论体系、工程方法、应用技术等方面还不够成熟，服务组合智能化道路仍有较多的问题需要解决，其中的主要问题为：

(1)动态的Web环境。服务是应用于网络层面的，而网络是不稳定的，因此网络的波动会导致QoS产生一定的变化，有些服务会因为环境的变化而失效，同时又会有新的服务出现。因此，需使服务组合算法具有动态性和可扩展性，以便适应复杂的环境；

(2)大规模的服务组合问题。随着互联网行业的飞速发展，服务的数目也在迅速增多，从过去的数十个扩增到如今的数万规模。从海量的候选服务中挑选出满足用户需求的组合服务，不仅需要提高算法的准确性，更要降低计算时间，减少服务成本；

(3)QoS约束。服务组合问题不仅要求构建出功能满足用户需求的增值服务，还需要满足用户的QoS需求，例如用户若对服务的实时性需求较高，则其可能会要求整体响应时间小于某一阈值；

(4)QoS依赖。在许多情况下，服务的 QoS 与其他服务相关。当可以从多个系统调用服务时，选择来自同一个系统的服务进行调用，能够在一定程度上降低工作成本。当调用了某一个系统的服务时，再次调用其系统的其它服务则会降低操作难度；

(5)QoS的数目。现有的研究考虑QoS较少，大多数的研究仅挑选少数QoS进行实验比较，目前缺少考虑了大量QoS的实验；

(6)现实物理环境。服务组合除了要考虑动态的虚拟环境，某些情况下也受到现实物理环境的限制。在物联网中，实际的物理环境、物理地址也会影响到服务的QoS。在处理这种服务组合问题时，将现实环境的影响因素结合起来也是一个难点。

3 机器学习在服务组合问题中的应用

伴随着网络技术的飞速发展，Web服务组合的环境也越来越复杂。人工智能的飞速发展使得智能化的思想被越来越多地应用于服务组合，机器学习与服务组合的结合已成为该领域的发展潮流。机器学习就是让计算机拥有像人类一样的学习能力，能够从过往的经验中总结规律形成某种认知，从而对未来的新事物进行判断。计算机通过机器学习算法对大量原始数据训练总结出模型，用模型来对新的情景进行判断处理。强化学习是机器学习的一个分支，不需要预先的指导，能够在无标记的数据中展现有效的学习能力，通过接收环境状态对动作的反馈从而获得学习信息，更加接近于人的学习行为。对比某些传统的算法，强化学习可以实现无模型的、端对端的、状态到动作的高维映射关系的自学习，它的自学习能力可以泛化到各种各样的情况中。深度学习是用于建立、模拟人脑进行分析学习的神经网络，并模仿人脑的机制来解释数据的一种机器学习技术，对比与传统方法，其具有效率高、可塑性强、普适性好的特点。将强化学习、深度学习等机器学习算法与服务组合结合起来，已经成为了当下研究的主流方向。

根据机器学习算法在服务组合问题中起到的作用，可以将其划分为两类：(1)求解组合方案的算法。这些算法中，机器学习是算法的主体部分，为用户提供最终的组合方案；(2)起到辅助增强作用的算法。这些算法中，机器学习是服务组合算法的子步骤，为主体算法提供前置条件或辅助增强主体算法。

3.1 求解组合方案的算法

强化学习算法是最常被用于解决服务组合问题的机器学习算法。该算法中，代理通过不断地与环境交互，试图找到累计回报最大的策略，进而得出最优组合方案。近年来，基于强化学习的服务组合方向不断有新的研究出现，是一个重要的研究方向。

文献[16]为提升强化学习算法的效率，并使其适用于大规模服务环境，提出了一种在动态和大规模环境中自适应服务组合的方法。该方法采用基于平铺卷积滤波器的Double Q-Learning网络，逐步建立了大规模服务环境的准确抽象。文献[17]将离散哈密顿力学、分布式多智能体控制、最优控制理论和博弈论结合起来，提出了一种多主体强化学习算法。文献[18]设计了基于马尔可夫决策过程的Web服务组合优化模型(Web Service Composition Markov Decision Processes，WSC-MDP)，提出了多目标智能体强化学习的分布式Q-learning算法。文献[19]提出了一种多代理的分布式Q-learning算法，将服务组合任务分解为多个子任务，使每个代理专注于自己的子任务，以加快收敛速度，此外该算法还引入了经验分享策略以提高效率，从而增加对不断变化环境的适应能力。文献[20]记录了服务每一次实际运行的QoS，利用历史QoS模拟动态环境，针对QoS的不确定性提出了一种具有自适应性的Q-Learning算法，满足了用户的QoS约束。文献[21]提出了一种利用长短期记忆网络(Long Short-Term Memory，LSTM)改进Deep Q-Learning的服务组合优化方法。相对于传统方法，该方法在大规模服务环境下计算速度更快，服务组合成功率更高，具有更强的处理能力和处理效率。文献[22]将循环神经网络(Recurrent Neural Network，RNN)与强化学习结合起来，提出了基于LSTM的自适应深度Q-Learning框架，用深度学习模拟服务组合状态问题，以形成拟合的Q值曲面，用作在线启发式函数以启发后续的强化学习。文献[23]也将深度学习与强化学习相结合，用深度强化学习来解决大规模服务组合问题。文献[24]将服务组合问题建模为部分可观察的马尔可夫决策过程，提出了一状态一网络(One State One Network，OSON-WSC)框架，通过启发式方式将状态分为隐藏状态和完全可观测状态，为两种状态分别训练不同的策略。为了能够在用户无需太多手动说明的情况下组合个性化服务，文献[25]使用排名学习算法RankBoost，根据用户的历史数据自动学习用户偏好并确定偏好的优先级。随后，该研究使用多目标强化学习(Multi-Objective Reinforcement Learning，MORL)算法在用户偏好之间进行权衡，并推荐一组服务以实现最高目标。文献[1]将天际线技术与强化学习相结合，通过从候选服务中提前选用高质量的服务，减少了搜索空间，降低了时间复杂度，并使用Q-Learning来进行服务选择。这种方法提高了搜索效率，使得服务组合在面对大规模问题时有了更好的解决效果。

求解组合方案的机器学习算法的相关应用如表1所示。

表1 求解组合方案的算法总结

由表1可以看出，近年来，强化学习是机器学习算法中最常被用于服务组合问题的算法。无模型的强化学习算法中，代理与环境不断交互得到立即回报并发生状态的转移。通过这种交互信息，代理能够捕捉到环境的变化，并通过调整模型参数自动适应环境的动态性。因此，强化学习适用于解决服务组合问题所面临的服务及QoS不稳定的问题。

3.2 起到辅助增强作用的算法

除了直接将机器学习算法用于求解组合方案外，研究人员还将机器学习算法与其他算法结合起来。在这种联合算法中，机器学习算法不直接承担求解组合方案的功能，而是作为一个辅助增强环节，或是作为主算法的预处理步骤，来帮助减小主算法的求解难度，提升求解效果。

聚类算法是服务组合中常用的算法，主要用于对服务进行聚簇，从而在服务组合算法开始前过滤出无需考虑的服务，减小搜索空间，降低求解难度，提高求解速度；该算法还可根据服务的功能属性对服务进行聚簇，形成候选服务集，进而构建出组合服务的工作流等。文献[26]使用基于信任的k均值聚类算法(k-means)集群化搜索空间，并使用蜜蜂交配优化算法实现全局优化，不仅改善了算法的响应时间，还能够选择出更多受信任的服务。文献[27]使用基于概念的相似度对服务进行聚类，随后根据每个聚类簇的输入输出参数，构建抽象服务网络；然后，针对用户请求从后往前查询合适的路径，并在寻找的过程中，进一步过滤候选服务集；最终，得出候选服务集及工作流。文献[28]用聚类的方法来考虑全局QoS约束，通过k-means聚类的方法将各个候选服务分组到各个集群当中，不同集群代表不同QoS级别。该研究提出了一种基于所得群集特征的效用函数公式来消除不满足用户需求的候选服务方法，通过减少候选服务的数量来缩短组合服务的合成时间。文献[29]提出了一种集群指导遗传算法(Genetic Algorithm，GA)的算法，解决了数据密集型服务组合问题。该方法根据Web服务的成对距离，采用k-means聚类将其分组到集群中获得初始群落，减少了局部最优的影响；然后，对每个集群计算平均适应度值，根据平均适应度值对集群重新排序，进而迭代后代，生成更优服务集[30]。文献[4]借鉴了聚类的思路，使用孪生支撑向量机(Twin Support Vector Machine，TWSVM)来划分候选服务，用大脑风暴优化作为搜索方案，并采用自适应对偶策略来生成高质量的组合服务。

由于服务组合是一种长期的经济策略，而服务QoS又具有不稳定性，因此很多研究试图预测出服务的未来QoS变化趋势，从而构建出长期有效的服务组合方案。文献[31]提出了一种基于深度学习的服务组合(Deep Learning Service Composition，DLSC)框架，应用LSTM网络来预测未来一段时间内的服务QoS，并使用粒子群优化算法组成最佳的组合服务，以便最大程度地降低消费者成本。文献[32]同样使用LSTM网络预测服务未来的QoS，并使用预测的QoS值和用户对QoS的可接受及偏好范围，在长期服务组合中准确推荐服务和替换服务，增强了任何现有的组合和替换技术。文献[33]在马尔可夫决策的基础上新定义了动态Web服务组合模型，并使用LSTM通过过去的数据预测出未来的QoS，继而采用Q学习进行服务选择。

除了直接使用强化学习进行服务组合外，强化学习也常用于作为元启发式方法的增强步骤。文献[34]认为GA的性能很大程度上取决于初始种群，因此研究人员利用Q-Learning算法生成初始种群以提升GA的效率。

本文将起到辅助增强作用的机器学习算法的应用进行了总结。由表 2可以看出，机器学习中聚类和序列预测算法是最常被用于解决服务组合问题的方法。

表2 起到辅助增强作用的算法总结

4 结束语

本文首先介绍了服务组合问题的几种分类标准和目前服务组合问题主要面临的挑战，随后总结了机器学习算法在服务组合问题中的两种应用方向。由上述介绍可以看出，机器学习算法在服务组合领域中具有良好的应用前景，同时也面临着一些问题：(1)缺乏高质量的数据集。许多研究在解决环境的动态性问题时，由于缺乏真实的历史记录数据，只能人工假设数据的分布，进而模拟环境的变化。但这种操作缺乏真实性，且收集数据集也增加了工作量；(2)对动态环境的自适应性不强。现有基于强化学习的服务组合算法中，许多算法通过实际执行服务获取立即回报，从而调整参数。但该操作会降低算法的实时性和实用性；(3)算法运行效率较低。在现有基于强化学习的服务组合算法中，许多算法无法学习组合的经验，对于新的组合需求，总需要重新进行训练，与传统方法相比，效率并没有显著提高。

基于以上问题，机器学习算法在服务组合领域上的发展方向主要为：(1)收集数据，在服务组合领域内形成公认的有效数据集；(2)利用服务的历史QoS信息构造长期可用的服务组合，或改进强化学习模型，使其通过与模拟环境进行离线训练，学习针对部分执行完毕的服务组合做下一步行动；(3)设计强化学习中代理的状态表示，使状态中包含尽量多的服务组合全局信息，从而使强化学习学到服务组合问题的通用策略。

机器学习算法在服务组合领域中仍然具有较大的发展空间与潜力，在服务组合领域中也将出现更多实用性与创新性并存的研究。