一种Web服务组合方法

摘要

本发明公开了一种Web服务组合方法，针对传统服务组合方法存在的耗时长、灵活性差等问题，将多Agent（智能体）技术、博弈论和强化学方法引入服务组合过程，将服务组合过程转化为一个马尔可夫博弈过程（Markov Games,or Stochastic Games）。在此基础上进一步融入Q-learning方法和团队马尔可夫博弈理论，使其能够适用于多Agent协同学环境，通过迭代求解的方式求得最终的服务组合结果。本发明方法能够有效提高求解速度，确保各个智能体在高效协作的同时，能够自主地适应环境并进行动态的服务组合，有效提高了服务组合的灵活性和自适应性。

主权项

一种Web服务组合方法，其特征在于，该方法包括以下步骤：1)将服务组合建模为马尔可夫博弈，并初始化系统参数和变量：所述建模的具体过程为：把投放的全部智能体定义为局中人集合，将Web服务的前置和后置条件作为马尔可夫博弈过程的状态空间，把可执行的Web服务定义成动作空间，动作表示为如何将一个状态转换为另一个状态，将得益值定义为实际Web服务质量参数的函数；由此得到一个七元组r＝<G,S,S₀,S_τ,A,T,R>，G是智能体集合，其中S是状态集，A是联合行为空间，A＝A₁×...×A_i×...×A_n，其中A_i是第i个智能体的可用行为集，n是智能体的总个数，T是状态转移概率函数，T:S×A×S→[0,1]，R是所有智能体共有的得益函数，R:S×A→ω，S₀是开始状态，S_τ是终止状态；所述初始化系统参数和变量的具体内容为：初始化折扣因子γ，0<γ<1；初始化学习率α，0<α<1；初始化瞬时得益矩阵和长期得益矩阵；初始化迭代次数m为1；2)将开始状态S₀作为系统当前状态；3)根据玻尔兹曼探索策略来计算系统当前状态s下各个联合行为的被调用概率，得到联合行为的概率分布，然后选择当前状态s下被调用概率值最大的联合行为a^max，作为当前联合行为，系统开始调用、执行所述当前联合行为，系统当前状态s∈S；4)细化得益函数，更新瞬时得益矩阵：首先根据实际Web服务质量参数，按照下式计算系统当前状态s下各智能体采取对应行为时每个智能体的得益值：$R\left(s\right)={\mathrm{\Sigma w}}_i\times \frac{{\mathrm{Att}}_i^s-{\mathrm{Att}}_i^{\min }}{{\mathrm{Att}}_i^{\max }-{\mathrm{Att}}_i^{\min }},$其中w_i是服务质量中第i个属性指标的权重，是第i个属性指标的最大值，是第i个属性指标的最小值，是当前网络下由执行动作反馈的真实观察值；将当前联合行为下所有智能体的得益值求和，即为当前联合行为下的得益值用计算得到的当前联合行为下的得益值更新瞬时得益矩阵；5)采用Q学习方法，更新长期得益矩阵：根据下式计算在系统当前状态s下各智能体采取对应行为时系统所得到的长期得益值l_i1i2...in^m(s)：l_i1i2...in^m(s)＝(1‑α)·l_i1i2...in^m‑1(s)+α·(r_i1i2...in(s)+γ·l_i1i2...in^m‑1(s′))m为迭代次数，s′是s的下一后继状态；用计算得到的所有联合行为下的长期得益值更新长期得益矩阵；6)待系统执行完毕当前联合行为，并收到反馈后，进入下一后继状态，当所述后继状态为终止状态S_τ时，进入步骤7)，否则返回步骤3)；7)判断系统的学习过程是否收敛：观察长期得益矩阵，如果更新得到的长期得益矩阵与上一次迭代过程结束后得到的长期得益矩阵相比，其中所有数据变动幅度均小于ε收敛判断阈值，则认为系统的学习过程已经收敛，并进入步骤8)，否则令m＝m+1后返回步骤2)；8)根据学习结果，生成工作流：从开始状态S₀开始，按照贪心原则，选取一条从开始状态S₀到终止状态S_τ的完整路径，将路径中出现的所有联合行为按其出现的先后顺序排列，然后按照步骤1)所构建七元组中规定的映射关系，将这些联合行为里的各个子行为，替换为七元组里的web服务，生成完整的工作流。