研究背景

在工业互联网和服务计算领域，单个服务的功能有限。用户通常需要组合多个服务（形成 Mashup 或服务组合）来完成复杂业务需求。核心问题：给定成千上万的服务，如何推荐一组能协作良好的服务组合？

这个问题拆成三个子问题：

  1. 服务之间的协作关系如何度量？
  2. 历史上成功的服务组合有什么模式？
  3. 如何在协作度和 QoS 之间权衡？

参考文献

  1. Compatibility-Aware Web API Recommendation for Mashup Creation via Textual Description Mining

    • Qi L, Song H, Zhang X, et al.
    • ACM Transactions on Multimedia Computing Communications and Applications, 2021
    • 核心思路：通过 API 文本描述挖掘兼容性关系

  2. Manufacturing service recommendation method toward industrial internet platform considering the cooperative relationship among enterprises

    • Wang, Lei, et al.
    • Expert Systems with Applications, 192 (2022): 116391
    • 核心思路：考虑企业间协作关系的制造服务推荐方法

核心思路：构建服务协作关系图

二部图表示

服务协作可以建模为一个二部图：

    Task 层       ┌──────┐   ┌──────┐   ┌──────┐
  (Mashup/任务)    │ T1   │   │ T2   │   │ T3   │
                   └──┬─┬─┘   └──┬───┘   └──┬─┬─┘
                      │ │        │          │ │
              ┌───────┘ │   ┌────┘    ┌─────┘ └───────┐
              │         │   │         │               │
    Service层 │     ┌───┴───┴───┐ ┌───┴───────┐ ┌─────┴────┐
              │     │   S1      │ │   S2      │ │   S3     │
              │     └───────────┘ └───────────┘ └──────────┘

关系：T1 调用了 S1 和 S2 → S1 和 S2 在 T1 中有协作关系

服务相似度矩阵计算

从二部图出发，可以将服务间的协作关系量化为相似度矩阵：

相似度 SR(Si, Sj) 的核心公式：

SR(Si, Sj) = 与 Si 和 Sj 都协作过的 Task 数量 / 与 Si 或 Sj 任一协作过的 Task 数量

（本质是 Jaccard 相似度在二部图上的应用）

不频繁项（协作次数少的服务）之间的相似度也可以通过这个矩阵计算——不需要显式的共现关系。

频繁共现模式挖掘：FP-growth

为什么需要频繁模式

单看两个服务之间的关系还不够。实际场景中，一组服务可能经常一起出现——这种 n 元共现关系包含了更丰富的协作信息。

FP-growth 原理

与 Apriori 算法相比，FP-growth 避免了反复扫描数据集的问题：

Apriori:
  每次找 k+1 频繁项集都需要重新扫描一次数据库
  计算量大，不适合大规模服务数据

FP-growth:
  1. 扫描一次数据库，统计每个服务出现的频率
  2. 构建 FP-Tree（频繁模式树）
  3. 从 FP-Tree 递归挖掘频繁模式
  不需要反复扫描数据库

应用到服务推荐：将每个历史 Mashup 看作一条交易记录（其调用的服务集合 = itemset），用 FP-growth 挖掘频繁共现的服务集合。

服务组合相似度评分方案

针对两个服务组合 A 和 B 的相似度评分，用频繁项和相似度矩阵结合：

场景频繁项判断相似度处理评分规则
A 和 B 的服务历史上都协作过全都是频繁项-直接 +1
部分历史协作部分是频繁项-频繁项 +1，不频繁项取最大相似度
协作过的部分是频繁项局部频繁不频繁项取相似度同上的加权
协作过的都不是频繁项都不是频繁项全依赖相似度矩阵取相似度的最大值（<1）
没有历史协作部分频繁项频繁项贡献 +1混合评分
完全没有历史数据没有频繁项全靠矩阵相似度作为唯一指标

最终评分公式：

score(A, B) = [ Σ(频繁项权重=1) + Σ(不频繁项与频繁项的最大相似度) ]
              / (|A| + |B|)

这个公式保证了：
  - 频繁共现的服务组合得高分
  - 历史数据少的冷门服务不会完全被忽略
  - 归一化到 [0, 1] 区间

结合多目标进化算法 (MOEA)

为什么需要多目标优化

推荐服务组合时有两个目标经常冲突：

  • 内联协作度（相似度）：服务之间配合好，指标越高越好
  • QoS（质量指标）：响应时间、吞吐量、可靠性、价格

高协作度的组合可能 QoS 不高（历史上协作好的服务可能是慢服务），而 QoS 最高的组合可能协作度低（两个高性能服务从没配合过）。

Pareto 前沿

    QoS ↑
        │     ★ 帕累托前沿的解
      ★ │        （无法在不降低协作度的情况下提高 QoS）
        │   ★
        │       ·  ·  ·
    ·   │     ·    ·    被支配的解
        │   ·   ·
        └─────────────────→ 协作度 →

多目标优化的输出不是一个"最优解"，而是一组帕累托最优解
——由用户根据实际情况选择

算法流程

1. 初始化种群（随机生成服务组合）
2. 对每个个体计算两个目标：
   - 内联协作度（基于上述相似度评分方案）
   - QoS（响应时间、可用性等加权综合）
3. 基于 Pareto 支配关系进行选择
4. 交叉 + 变异（服务组合的交叉：交换子集）
5. 迭代至收敛
6. 输出帕累托前沿——用户选择最适合自己场景的组合

学术论文中的 MOEA 方法扩展

近年来关于 MOEA 的改进方向主要集中在：

NSGA-II（非支配排序遗传算法）

核心操作：
  1. 非支配排序：将所有个体按 Pareto 支配关系分层
  2. 拥挤度距离：同一层内，个体离邻居越远越好（保持多样性）
  3. 合并父代和子代（2N 个体）→ 选前 N 个

MOEA/D（基于分解的多目标进化算法）

核心思想：将多目标优化分解为多个单目标子问题
  - 每个子问题是一组权重的加权和
  - 相邻子问题共享信息
  - 适合于3个以上目标的场景

未来方向

  • 冷启动问题：新服务没有历史数据，如何合理估计协作度？可以借助服务描述文本（如文献1）做语义相似度
  • 动态更新：服务池经常增减，频繁项集需要增量更新而非全部重算
  • 用户偏好建模：不同用户对 QoS vs 协作度的偏好不同，引入交互式进化算法（IGA）让用户直接参与选择过程

总结

  • 服务组合推荐的核心挑战是冷门服务和协作关系发现
  • FP-growth 挖掘频繁共现模式，二部图迭代相似度矩阵覆盖非频繁项
  • 两者的结合评分方案能处理从”有丰富历史”到”完全没有历史”的不同情况
  • MOEA 在协作度和 QoS 两个冲突目标之间找到帕累托最优解集
  • 一个实际可用的服务推荐系统还需要解决：冷启动、动态更新、用户偏好建模