叶恒舟, 郝 薇, 胡志丹
(桂林理工大学 广西嵌入式技术与智能系统重点实验室, 广西 桂林 541006)
Web服务的数量呈现出几何倍数的增长, 服务的质量(quality of service, QoS), 特别是时序约束, 显著影响着Web服务组合的效果。生产性能更好、成本更低，并在更高程度上实现客户目标的组合服务是十多年来研究的热点[1]。
QoS约束分解策略是求解时序约束Web服务组合问题的常用方法, 时序约束分解模型的性能决定着相应的服务组合方法的性能。然而, 现有的QoS约束分解模型在不同用户约束强度下, 并不总能表现良好[2-7]。Guidara等[4]针对时序约束建立了不丢失可靠组合方案的分解模型, 当用户的约束强度较强时, 该策略可以淘汰相当一部分的候选服务, 从而有效降低问题规模，但当用户约束强度较弱时, 通过该策略只能淘汰很少的候选服务, 效果很不明显。文献[5]提出的时序约束分解模型(TCD)将施加于全局的时序约束分解为针对各个活动或者任务的局部时序约束, 在保证全局时序约束、降低问题规模方面取得了一定的成果，但该模型在用户约束强度较强时, 可能丢失本就不多的可行组合方案, 导致找不到可行解。文献[6]提出用户约束强度感知的时序约束分解模型(CIA-TCD), 它在文献[5]TCD模型中引入了松弛因子, 并提出了一种基于模糊推理规则的自适应调节松弛因子的方法, 无论用户约束强度较弱还是较强, 都表现出了较好的性能，但模糊推理规则需要人为设定, 且仅考虑了活动个数、约束强度对松弛因子的影响。
近年来对神经网络(neural networks, NN)的研究取得了突破性的成果[8-10], 并被广泛应用于环境污染预测[11]、工业预测[12]、人体监测[13]、市场竞争[14]以及林业估算[15]等重要领域, 起到了关键性的作用。针对文献[6]提出的CIA-TCD模型的不足, 本文使用基于NN的松弛因子自适应调节方法替换基于模糊推理规则的自适应调节方法, 以期避免对人工经验的依赖, 并增加考虑候选服务个数及约束个数对约束因子的影响。
1.1 传播
前向传播算法将相邻两层的神经元节点通过权值连接起来, 前一层的神经元节点，作加权求和及偏移操作后，再作非线性变化得到的结果就是本层神经元节点。神经网络中每一层神经元都执行该操作, 向前传播, 最终可得到输出层的结果。图1表示了NN前向传播的原理，即如何由输入x1、x2、x3、x4获得输出y[16]。
图1 NN前向传播原理图
反向传播算法的学习过程由信号正向传播与误差反向传播两个过程组成。正向传播将输入信息经输入层传入到隐藏层, 经过逐层处理后传向输出层, 输出层对输出的结果与期望值进行比较, 如果两者误差达不到预期目标, 便开启反向传播过程, 计算每层目标函数对各神经元权值的偏导数, 即梯度, 作为修改权值的依据。神经网络中的信号在传递的过程中, 权值不断被修改, 并用一个损失函数权衡输出值和期望值的差值[17], 当结果与期望值的差值在允许范围之内时, 停止网络学习。
1.2 激活函数和损失函数的选择
在神经网络学习过程中, 使用激活函数处理每层数据的输入值, 使得数据每经过一层后都变得更加复杂, 最终结果也会更加精准。激活函数存在各种不同的类型。式(1)所示的Sigmoid函数与其反函数都是单调递增的, 经常作为神经网络中阈值函数[18]。
(1)
损失函数计算网络模型中真实值y与预测值a之间的差异度。损失函数的值越小, 则表示该模型的鲁棒性越好。常用的损失函数模型有: 均方差损失函数、交叉熵损失函数、指数损失函数、Hinge损失函数等，这些模型也可以搭配使用, 其中均方差损失函数常与Sigmoid激活函数一起搭配, 形成最小二乘法
(2)
其中:J为损失函数；
N为样本数；
yi、ai分别是第i个样本的标签值和预测值。
为有效解决时序约束的服务组合问题, 文献[5]提出了一种保障时序约束的时序约束分解(TCD)模型, 描述如下:
目标
(3)
约束条件
fk(tc1,tc2, …,tcn)≤τk,k=1, 2, …,r;
(4)
min(Ai.t)≤tci≤max(Ai.t)。
(5)
式(3)描述了TCD模型的优化目标,即，使经过约束分解后剩余的候选组合服务个数最大化。n为工作流中包含的活动个数,第i个活动记为Ai,sij为Ai的第j个候选服务,mi为Ai候选服务个数,sij.t表示sij所需的执行时间,tci为Ai应满足的时序约束, 即TCD模型的因变量, #B表示集合B中的元素个数。式(4)中,τk(k=1, 2, …,r)为用户针对整个工作流或某个局部工作流给定的时序约束。fk(tc1,tc2, …,tcn)描述为当Ai(i=1, 2, …,n)选择所需执行时间为tci的候选服务时, 完成τk针对的工作流所需要的执行时间, 其具体计算方法参考文献[5]。式(5)约定tci的取值范围，min(Ai.t)与max(Ai.t)分别表示Ai的候选服务中所需要的执行时间的最小值和最大值。
TCD模型在约束分解阶段保障了时序约束, 因而可以使用局部优选策略为每个活动在剩余的候选服务中选择合适的服务而不违背时序约束。但TCD模型在用户约束较强时, 容易导致找不到可行解, 原因在于在约束分解阶段可能已经淘汰了可行解。为此, 文献[6]在TCD的基础上, 提出了一种约束强度感知的时序约束分解模型(CIA-TCD), 其核心思想是在TCD的基础上引入松弛因子γk(γk≥0,k=1, 2, …,r), 将式(4)改写为
fk(tc1,tc2, …,tcn)≤(1+γk)τk。
(6)
引入γk后, 实质上放宽了约束分解时的约束条件, 从而可以降低丢失可行解的概率; 同时, CIA-TCD模型不再能保障时序约束, 在后续的优选阶段不再能使用局部优选策略, 而是需要全局优选策略, 因而经过约束分解后剩余的组合方案个数不宜过多, 以降低优选阶段的时间开销。
因此, 在确定γk值时, 需要兼顾以下两个指标:RS和RI。其中：RS表示经过时序约束分解后, 剩余组合方案存在可行解的概率，若用sum表示总测试次数,numavail表示在剩余组合方案存在可行解的次数, 则RS=numavail/sum;RI表示经过时序约束分解后, 由各个活动所保留的候选服务所确定的剩余组合方案个数, 即由式(3)所描述的优化目标。
实验测试发现,γk的合理取值与工作流的结构、工作流中包含的活动个数、每个活动的候选服务个数、时序约束个数、每个约束所针对的局部工作流中包含的活动个数、每个候选服务的执行时间等诸多因素相关, 亟需寻找确定γk的有效策略。文献[6]提出了一种基于模糊推理规则的松弛因子自适应调节方法, 通过将活动个数与约束强度模糊化, 结合实验测试效果, 设计了确定γk的推理规则。该策略考虑的因素较少, 较为依赖经验数据。为此, 本文提出一种基于神经网络的松弛因子自适应调节方法。
采用基于NN的松弛因子自适应调节方法替代基于模糊推理规则的松弛因子自适应调节方法是NN-CIA-TCD模型与CIA-TCD模型的主要区别。采用基于NN的松弛因子自适应调节方法, 先通过感知约束强度来控制可找到可行组合方案的概率和剩余组合方案的个数, 逆向求解 NN-CIA-TCD模型, 以获取包含特征及标签的训练数据集, 再建立神经网络模型, 将训练集输入到该模型中进行训练。考虑到Web服务组合时工作流、时序约束的个数与位置等是不确定的, 为了增强适应性, 在训练数据集时用于表示组合服务的工作流、时序约束个数、位置等是随机的, 这就导致在训练时可能出现分类不合理的标签, 需要剔除这些标签。图2为基于NN的松弛因子自适应调节方法的流程图。
图2 基于NN的松弛因子自适应调节方法流程图
3.1 建立样本库
在建立样本库时, 选择了4个影响松弛因子取值的因素: 活动个数、候选服务个数、约束强度和约束个数。根据这4个值, 随机生成一个时序约束组合服务问题, 代入由文献[6]采用的模糊推理规则确定的松弛因子, 求解相应的TCD模型。若求解结果不理想, 则适当调整松弛因子。通过反复实验, 最终确定出与这4个影响因素对应的松弛因子的值。
求解结果是否理想, 由RS和RI指标共同确定, 即RS应较大,RI应较小。本文采取的策略是, 若RS≥0.9, 则以恒定步长0.01尝试减小松弛因子, 直到不能调整, 即一旦调整,RS会小于0.9; 否则，尝试增大松弛因子, 直到RS≥0.9。
对于一次求解过程, 每个时序约束都对应一个松弛因子, 但考虑施加在局部约束的时序约束具有不确定性, 且容易受到其他约束的影响, 仅保留了全局时序约束对应的松弛因子。式(7)描述了松弛因子的波动范围, 可以用来对训练样本中的松弛因子进行分类
(7)
其中:λT表示分类后的松弛因子;λmax与λmin表示松弛因子的最大、最小值;NT表示的是合适的分类个数。将活动个数、候选服务个数、约束强度和约束个数4个变量和与之对应的λT做成一个样本, 活动个数、候选服务个数、约束强度和约束个数是特征值,λT作为标签。改变这4个变量的值, 重复上述工作, 即可形成样本集。
由于工作流、候选服务集都是随机的, 在产生样本时, 同一组特征值, 即活动个数、候选服务个数、约束强度与约束个数均相同时对应的标签(即松弛因子)可能是不一样的。在初始产生样本集时, 每一组特征值对应的样本记录都要达到一定的数量。这些记录中, 若某个标签出现的次数明显多于其他, 则选取该标签; 否则, 去掉最小和最大的标签后, 取其他标签的平均值。最终的样本集中, 每组特征值只对应一个标签。
3.2 NN分类训练
由于松弛因子的分类数较多, 需要大量的训练样本，为此将样本库拆分成若干互斥的子样本集, 对NN进行迭代更新训练, 以降低训练时对设备性能的要求。从各个子样本中随机选择少量样本形成测试样本集, 对NN的训练结果进行测试。测试时若发现训练结果不满意, 需要定位并剔除或修改异常样本, 以更新训练样本集。图3描述了NN分类训练流程。
图3 分类训练流程图
本实验运行在配置为Interl(R)Core(TM)i7-3630QM、2.40 GHz CPU、4 GB内存、64位Windows 7操作系统的PC机上, 编程语言为Java 1.8, MATLAB 2017b。实验中神经网络共分为3层, 每一层的节点数分别设置为50、100、50, 迭代次数为2 000次。
在仿真实验中, 通过改变约束强度和服务组合规模(表1), 固定约束个数, 从RS、RI两个性能指标分析对比约束强度、活动个数以及候选服务个数对TCD模型、CIA-TCD模型和NN-CIA-TCD模型的性能影响。工作流根据活动个数随机生成, 候选服务的执行时间由QWS数据集[19-20]中的响应时间来模拟。约束强度的变化区间为[-0.8, 0], 步长为0.1。
表1 服务组合规模的设定
4.1 约束强度对RS和RI影响(G1与G2)
G2规模较G1规模增加了每个活动的候选服务个数。图4给出了在G1、G2规模下, 分别采用TCD、CIA-TCD和NN-CIA-TCD三种模型, 所得到的RS的对比结果。分析可得: 候选服务个数的增加会提高对应模型找到可行组合方案的概率; 约束强度的值变大, 即约束强度变弱时, 3种模型相对应的可找到可行组合方案概率会显著提高, 但终会趋于平稳; 当约束强度较强时(-0.8～-0.5), 采用NN-CIA-TCD模型较CIA-TCD模型可找到可行解的概率更高, 表现更好, 在约束强度较弱时, NN-CIA-TCD模型也能够保持较高找到可行组合方案的概率；
但当约束强度值位于[-0.5, 0]时, 与CIA-TCD相比, NN-CIA-TCD获得的RS要低一些。这是因为松弛因子是由两个指标RS和RI共同确定的，而这两指标存在冲突。在确定样本时,RS是以0.9为分界点的, 最终获得的RS也在0.9附近波动，表明RS与预期一致。虽然NN-CIA-TCD较CIA-TCD在指标RS上要差一些，参照图5, 但在该区间RI较为稳定, 且明显低于CIA-TCD。可见在设置NN-CIA-TCD参数值时，倾向于获得更好的RI。若需要更好的RS, 可以在生成样本时, 提升RS的分界点。
图4 约束强度对RS的影响对比(G1与G2)
图5给出了在G1、G2规模下, 3种模型所得到的RI的对比结果。可以发现: 随着候选服务个数的增加, 采用不同模型时的剩余组合方案个数明显下降; NN-CIA-TCD模型在约束强度较强时能够提高剩余组合方案个数, 在约束强度较弱时, 能够控制剩余组合方案个数; 当约束强度增加时, TCD模型和CIA-TCD模型的剩余组合方案个数的指数值RI都呈现出缓慢上升的趋势, 只有NN-CIA-TCD模型的值始终趋于稳定。这说明无论约束强度如何, NN-CIA-TCD模型都能维持较为合适的剩余组合方案个数。
图5 约束强度对RI的影响对比
4.2 约束强度对RS和RI影响(G1与G3)
G3规模较G1规模增加了活动的个数。图6给出了在G1、G3规模下, 3种模型所得到的RS的对比结果。可以看出: 随着活动个数的增加, 模型对应的找到可行组合方案的概率会有小幅度的下降; 当约束强度较强时, TCD模型找到可行组合方案的概率较低, 采用CIA-TCD模型和NN-CIA-TCD模型可以有效提高找到可行组合方案的概率; 当约束强度较弱时, 3种模型都能有较高的找到可行组合方案的概率; 当约束强度和规模相同时, 对比CIA-TCD模型和NN-CIA-TCD模型的RS可以发现, 约束强度较强时(≤0.6), NN-CIA-TCD模型比CIA-TCD模型表现更好。与图4类似, 由图6可见，在约束强度位于[-0.5, 0]时, 与CIA-TCD相比, NN-CIA-TCD获得的RS也要低一些。
图6 约束强度对RS的影响对比
图7给出了在G1、G3规模下, 3种模型所得到的RI的对比结果。分析可得: 随着活动个数的增多, 模型对应的剩余组合方案个数会有大幅度的上升; 当约束强度增加, 规模相同时, TCD模型和CIA-TCD模型的RI都依然呈现缓慢上升的趋势, 而NN-CIA-TCD模型的剩余组合方案个数的RI值呈现出先上升后一直稳定的趋势。这说明对于不同约束强度, NN-CIA-TCD模型能够更快获得更合理的剩余组合方案个数。
图7 约束强度对RI的影响对比
在研究时序约束服务组合问题时, 时序约束分解策略受到广泛关注, 它需要在保障全局约束与有效降低解空间之间取得平衡, 以适合不同强度的用户约束。通过在现有的保障全局约束的分解模型中引入松弛因子, 可以较好地维持上述平衡。在分别建立包含特征值(活动个数、候选服务个数、约束强度和约束个数)与标签(松弛因子)的训练集、神经网络模型的基础上, 提出了一种基于神经网络的松弛因子自适应调节方法。仿真实验分析表明, 该方法优于现有方法。由于工作流、时序约束位置的不确定性, 以及松弛因子的分类个数较多, 如何在NN训练时避免或减少人工干预而保障较好的训练精度, 仍值得关注。
猜你喜欢 时序个数约束 顾及多种弛豫模型的GNSS坐标时序分析软件GTSA导航定位学报(2022年5期)2022-10-13清明小猕猴智力画刊(2022年3期)2022-03-28怎样数出小正方体的个数小学生学习指导(低年级)(2021年9期)2021-10-14你不能把整个春天都搬到冬天来意林·作文素材(2021年23期)2021-01-22怎样数出小木块的个数小学生学习指导(低年级)(2019年9期)2019-09-25最强大脑学生导报·东方少年(2019年27期)2019-01-14怎样数出小正方体的个数小学生学习指导(低年级)(2018年9期)2018-09-26基于FPGA 的时序信号光纤传输系统电子制作(2017年13期)2017-12-15马和骑师小学阅读指南·低年级版(2017年1期)2017-03-13适当放手能让孩子更好地自我约束人生十六七(2015年6期)2015-02-28