Page 68 - 《软件学报》2021年第11期

3394 Journal of Software 软件学报 Vol.32, No.11, November 2021

由以上最优化模型可知,该模型的目标为最大化函数A(Φ)的值,便可获得最大化的用户群体满意度.其中,决
策变量为 s ij 和 x j ,约束条件如公式(5)所示.
⎧ 0≤ s ≤ ij x j
⎪
⎨ 1 ∑ ≤≤ m s = 1 (5)
ij
j
⎪ x j ⎢ / nk⎥ ⎣ ⎩ ⎦ ≤ ∑ ≤≤ n s ij x j ⎡ ≤ / nk⎤ ⎢ ⎥
1 i
1) 1≤i≤n,1≤j≤m,0≤s ij ≤x j ,即当且仅当在线服务 s j 包含在 Top-k 在线服务集合中,服务 s j 能够代表用
户 u i .
2) 对于所有用户, ∑ s = 1,即每个用户只能被一个在线服务代表.
j
1≤≤ m ij
3) x j ⎢ / nk⎥ ⎣ ⎦ ≤ ∑ ≤≤ n s ij x j ⎡ ≤ / nk⎤ ⎢ ⎥ ,即每个在线服务或者最多代表⎡n/k⎤个用户,或者不代表任何用户.
1 i
Monroe 针对该规则提出了一个转移算法 [12] ,其思想是:首先,将每个用户 u i 分配给使该用户满意度最大的
在线服务 s j ;然后,通过转移用户来平衡分配,在转移过程中,最小化用户群体满意度的减少量.然而,当 k>2 时,转
移过程就变得非常复杂.根据该转移算法,例 1 中能满足用户群体满意度最大的 k 分配如下所示:
Φ(u 1 )=Φ(u 3 )=Φ(u 4 )=s 1 ,Φ(u 2 )=Φ(u 5 )=Φ(u 6 )=s 3 .
利用公式(2)计算用户对在线服务的满意度分数;进一步,利用公式(3)计算用户群体满意度为:A(Φ)=3+2+3+
3+2+3=16.因此,根据问题示例得到 Top-k 在线服务评价的结果为{s 1 ,s 3 },s 1 和 s 3 能使全体用户满意度最大.

3.3 Monroe贪心算法
在 Monroe 规则下寻找最优 Top-k 在线服务是一个 NP-hard 问题 [13,24] .问题的解空间随着用户和在线服务
的数量以及最终选择的服务数量 k 值的增大呈指数增长.利用传统的穷举法或用户转换策略寻找最优的 Top-k
在线服务集合,需要计算每种可能的服务集合对应不同用户组的满意度,计算量非常庞大,且需要较大的存储空
间 [12] .
当用户数量和在线服务数量较小时,利用整数规划和固定参数法求解 Monroe 问题并取得了较好效果 [24] .
但是,当用户数量 n 和在线服务数量 m 较大时,利用上述方法寻找最优解仍是一个 NP 完全问题,用户群体不能
在多项式时间内找到满足用户群体满意度最大化的在线服务集合 W.虽然用上述方法寻找 Monroe 最优解在问
题规模较大时计算非常困难,但贪心算法为缓解该计算难问题提供了可能.
因此,我们利用文献[13]的贪心算法(Monroe greedy algorithm,简称 MGA)来解决基于 Monroe 的 Top-k 在线
服务评价的计算难问题.MGA 算法从用户或在线服务未被分配的初始状态出发,进行 k 次迭代,每次迭代选择能
够保持局部用户满意度最优或较优的在线服务,逐步逼近给定的目标,在更短的时间内获得满足用户群体满意
度最大化的 Top-k 在线服务最优解(或较优解).
MGA 算法建立了一个迭代解决方案,在每次迭代过程中选择某个未被分配过的在线服务 s j ,将最佳匹配服
务 s j 的 n/k 个用户分配给服务 s j ,即把这 n/k 个用户分配给服务 s j 得到的满意度最大.执行 k 次迭代,并将返回的
结果作为 Top-k 在线服务评价结果.
←
算法 1 给出了 MGA 算法的主要步骤.其中,Φ 表示已经分配过的用户,Φ ← 表示已经分配过的在线服务,符
号“\”表示每次循环需要排除“\”后已被分配过的用户或在线服务.第 7 步对用户进行排序的规则为:若在线服务
s j 在用户 u i 偏好序中的位置小于或等于其在用户 u′ 中的位置,即 pos i ()s ≤ pos′ i ()s ,则认为用户 u i 优于 u′ ,以此
i
i
j
j
规则对用户进行排序.
算法 1. MGA 算法.
输入:用户群体偏好集合 P,k 值大小.
输出:Top-k 在线服务评价集合 W,即评价结果.
1. W=[⋅];
2. FOR l=1 to k DO
3. score=[⋅];