基于最近探索的启发式服务组合方法

摘要

本发明公开了一种基于最近探索的启发式服务组合方法，包括如下步骤：1、将服务组合问题建模为一个六元组马尔可夫决策过程；2、应用基于Q‑learning的启发式学习方法求解六元组马尔可夫决策过程，得到最优策略；3、将最优策略映射为web服务组合的工作流。该方法充分利用学习过程中的学习经验来提高学习速度，学习效率更高。

说明书

技术领域

本发明涉及一种利用计算机对Web服务组合的方法，属于人工智能领域。

背景技术

Web服务作为面向服务的架构(Service-Oriented Architecture，SOA)的一种实现方式，它继承了SOA的特征如自包含，自描述等特性，通过互联网可以被应用调用。如图1所示，一个Web服务的实现过程：服务提供者把服务描述信息发送到服务注册中心进行注册，使潜在用户可以发现这些服务；服务请求者查找Web服务，通过UDDI把服务描述和绑定信息写入注册表；根据业务需求，服务请求者，通过网络到UDDI查找Web服务，根据查找的绑定信息定位服务提供者；服务请求者，通过绑定信息取得服务的WSDL描述，绑定、调用服务。然而，单个的服务是无法满足用户的需求，这时就需要将多个服务集成组合起来共同完成用户需求，服务组合技术由此而生。服务组合作为一种新的软件复用技术，通过将互联网上的可调用的服务进行组合，充分利用了已有的软件资源，提高软件的开发效率，同时降低了软件开发成本。

近年来，关于Web服务组合方法的研究引起了学术界和工业界的广泛关注。研究人员和工业机构从各自的角度出发，提出了大量的Web服务组合技术。其中基于强化学习的服务组合技术是重要的组成部分，顺序性的强化学习问题可以被建模成一个马尔可夫决策过程(Markov Decision Process，MDP)，继而通过求解该MDP模型来求得最优策略。下面给出基于马尔可夫决策过程的服务组合模型的形式化定义：

一个基于马尔可夫决策过程的服务组合可以被定义为一个六元组，如下式：

MDP-WSC＝<S；s₀；s_r；A(·)；P；R>

其中S代表从初始状态迁移到终止状态的过程中所能经历的所有状态的集合，该状态集合包含初始状态和终止状态；s₀是初始状态，表示任何动作还没有发生时的状态，也即工作流的初始，s₀∈S；s_r是终止状态，也即工作流的终态，当系统到达终态时，表明一个完整的服务执行路径已经形成，可以构建一个完整的组合服务，s_r∈S；A(·)代表系统在状态s∈S下可以采取的动作的集合，由于每一个动作和具体的Web服务存在着映射关系，A(s)也即为系统在状态s下可执行的Web服务的集合；P是状态转移函数，P(s′|s；a)表示在状态s下执行服务a∈A(s)转移到后继状态s′的概率；R是回报函数，当一个服务a∈A(s)被调用后，环境从当前状态s转移到后继状态s′，同时得到一个立即回报值r＝R(s′|s；a)。

针对基于MDP模型的服务组合问题，一种有效的求解方式是利Q-learning来学习最优策略。下面是Q-learning的更新公式：

Q(s，a)←(1-σ)*Q(s，a)+σ*(r+γ*maxQ(s′，a′))

Q学习的目标是学习在动态环境下如何根据外部评价信号，如回报值，来选择较优动作或者最优动作，本质是一个动态决策的学习过程。当Agent对环境的知识一点也不了解时，它必须通过反复试验的方法来学习，算法的效率不高。

发明内容

发明目的：为了加快Agent的学习速度，提高学习效率，减少不必要的探索，本发明提出一种基于最近探索的启发式服务组合方法，该方法充分利用学习过程中的学习经验来提高学习速度，学习效率更高。

技术方案：本发明采用如下技术方案：

一种基于最近探索的启发式服务组合方法，包括如下步骤：

(1)将服务组合问题建模为一个六元组马尔可夫决策过程；

(2)应用基于Q-learning的启发式学习方法求解六元组马尔可夫决策过程，得到最优策略；

(3)将最优策略映射为web服务组合的工作流。

具体地，步骤(1)中将服务组合问题建模为如下六元组马尔可夫决策过程：

MDP-WSC＝<S；s₀；s_r；A(·)；P；R>

其中S代表从初始状态迁移到终止状态的过程中所能经历的所有状态的集合；s₀是初始状态，表示任何动作还没有发生时的状态，s₀∈S；s_r是终止状态，当系统到达终态时，表明一个完整的服务执行路径已经形成，可以构建一个完整的组合服务，s_r∈S；A(·)代表系统在状态s∈S下可以采取的动作的集合；P是状态转移函数；R是奖励函数。

具体地，步骤(2)应用基于Q-learning的启发式学习方法求解六元组马尔可夫决策过程，得到最优策略，包括如下步骤：

(21)初始化Q-learning中学习率σ，折扣率γ，当前状态s＝0，当前时间步长t＝0；随机选择一个服务a作为当前动作；

(22)当前时间步长t不为0时，以概率e应用启发式策略选择新的服务a，以概率1-e随机选择新的服务a；

(23)执行服务a，记录在状态s下执行当前服务a的回报值r、执行次数c、探索补贴bonus；

(24)按照下式更新Q值：

Q(s，a)←(1-σ)*Q(s，a)+σ*(r+bonus+γ*maxQ(s′，a′))，

其中Q(s，a)表示在状态动作对<s，a>下的Q值，σ为学习率，r为回报值，γ为折扣率，bonus为探索补贴，s′为执行服务a后从当前状态s转移到的后继状态，a′为在状态s′下选择的服务，Q(s′，a′)表示在状态动作对<s′，a′>下的Q值；

(25)更新当前状态：s＝s′，t＝t+1；当s为终止状态sr且满足收敛条件时，强化学习结束，得到最优策略；否则转步骤(22)。

具体地，所述步骤(23)中探索补贴bonus的计算方法为：

其中μ＞0，是探索补贴系数；t为执行服务a时的当前时间步，t′为动作状态对<s，a>上次被访问的时间步。

具体地，所述步骤(22)中启发式策略选择新的服务a包括如下步骤：

在(0，1)区间随机产生一个随机数υ，如果υ＞ε，随机选择一个新的服务a；如果υ≤ε，选择使探索策略函数值最大的服务作为新的服务a；所述探索策略函数Π*(s)如下式：

其中p，q为用来平衡表达式的大小的系数，其中EX(s′，a′)为记录在状态动作对<s′，a′>下回报值的矩阵。

优选地，步骤(25)中收敛条件为：从初始状态到终止状态累计Q值的变化小于门限值Q_th：|∑Q-∑Q′|＜Q_th，其中∑Q为本次学习过程中从初始状态到终止状态累计Q值，∑Q′为上次学习过程中从初始状态到终止状态累计Q值。

有益效果：与现有技术相比，本发明公开的基于最近探索的启发式服务组合方法具有以下优点：

1、强化学习又称为增强学习、加强学习、再励学习或激励学习，是一种从环境状态到行为映射的学习，目的是使动作从环境中获得的累积回报值最大。传统的强化学习框架如图2所示。强化学习通过多次试验，重新取样特定状态动作对的效用值来学习最优(或近优)策略。初始时，大部分的状态空间和动作空间都是未知的，为了检验可选动作的有效性，动作需要根据某种探索规则被选择，因而可能会导致有大量的状态动作对需要被探索，这是非常耗时的。本发明在探索的过程中利用一些知识对于采取的行动(服务)给予相应的补贴，对于最近未被访问的行动(服务)给予较多的补贴，让Agent通过该行动(服务)学习到一些额外知识或者经验，加快学习速度，更快学习到最优策略。

2、本发明公开的方法中探索策略函数值随着服务执行次数c的增大而减小，其含义为当一个动作(服务)被访问很多次了，那么它被再次访问的概率就变小了，如此减少盲目的探索，从而加快学习速度。

附图说明

图1是Web服务实现过程；

图2是传统强化学习框架；

图3是启发式探索的强化学习框架；

图4是本发明公开的基于最近探索的启发式服务组合方法流程图。

具体实施方式

下面结合附图和具体实施方式，进一步阐明本发明。

一种基于最近探索的启发式服务组合方法，包括如下步骤：

步骤1、将服务组合问题建模为一个六元组马尔可夫决策过程：

MDP-WSC＝<S；s₀；s_r；A(·)；P；R>

其中S代表从初始状态迁移到终止状态的过程中所能经历的所有状态的集合；s₀是初始状态，表示任何动作还没有发生时的状态，s₀∈S；s_r是终止状态，当系统到达终态时，表明一个完整的服务执行路径已经形成，可以构建一个完整的组合服务，s_r∈S；A(·)代表系统在状态s∈S下可以采取的动作的集合；P是状态转移函数；R是奖励函数。

步骤2、应用基于Q-learning的启发式学习方法求解六元组马尔可夫决策过程，得到最优策略，如图4所示，包括如下步骤：

(21)初始化Q-learning中学习率σ，折扣率γ，当前状态s＝0，当前时间步长t＝0；随机选择一个服务a作为当前动作；

(22)当前时间步长t不为0时，以概率e应用启发式策略选择新的服务a，以概率1-e随机选择新的服务a；

(23)执行服务a，记录在状态s下执行当前服务a的回报值r、执行次数c、探索补贴bonus；执行次数c记录在矩阵CountAction中；

(24)按照下式更新Q值：

Q(s，a)←(1-σ)*Q(s，a)+σ*(r+bonus+γ*maxQ(s′，a′))，

其中Q(s，a)表示在状态动作对<s，a>下的Q值，σ为学习率，r为回报值，γ为折扣率，bonus为探索补贴，s′为执行服务a后从当前状态s转移到的后继状态，a′为在状态s′下选择的服务，Q(s′，a′)表示在状态动作对＜s′，a′＞下的Q值；

探索补贴bonus的计算方法为：

其中μ＞0，是探索补贴系数；t为执行服务a时的当前时间步，t′为动作状态对<s，a>上次被访问的时间步。

(25)更新当前状态：s＝s′，t＝t+1；当s为终止状态sr且满足收敛条件时，强化学习结束，得到最优策略；否则转步骤(22)；

启发式策略选择新的服务a包括如下步骤：在(0，1)区间随机产生一个随机数υ，如果υ＞ε，随机选择一个新的服务a；如果υ≤ε，选择使探索策略函数值最大的服务作为新的服务a；所述探索策略函数Π*(s)如下式：

其中p，q为用来平衡表达式的大小的系数，其中EX(s′，a′)为记录在状态动作对<s′，a′>下回报值的矩阵；

收敛条件为：从初始状态到终止状态累计Q值的变化小于门限值Q_th：|∑Q-∑Q′|＜Q_th，其中∑Q为本次学习过程中从初始状态到终止状态累计Q值，∑Q′为上次学习过程中从初始状态到终止状态累计Q值。

(3)将最优策略映射为web服务组合的工作流。