QoS感知物流Web服务组合的改进遗传算法

沈记全,罗常委,侯占伟,刘志中

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

1 相关研究

在经济全球化浪潮中,第四方物流的发展在推动经济贸易增长方面有着不可替代的作用,是新的国民经济增长点,为加速发展物流行业开创了新的道路[1].然而由于Web服务运行环境的开放性,用户反馈需求的随意性,还有Web服务数据真实性等各种不稳定的因素,导致了互联网上功能性相同、非功能性不同的物流Web服务数量日益增加[2].如何从数量众多的物流Web服务中挑选一组资源服务,并且构建出具有最优QoS的Web服务组合是服务应用领域亟待解决的重点问题.

文献[3]针对Petri网理论,提出了Web服务组合的Petri网自动生成方法,从Web服务执行的角度,给出了Petri网的服务组合定义,并进一步讨论了原子服务的Petri网的PNML+OWL描述方法.文献[4]提出了一种基于动态Web服务选择的离散粒子群算法,为了避免粒子群陷入局部最优,设计了粒子无希望与重希望准则来保证粒子群的多样性.文献[5]提出了一种免疫遗传算法,基于生物免疫机制中的抗原识别、抗原记忆和抗体的抑制、促进原理,应用于货郎担(TSP)优化问题的求解,该算法具有较好的全局搜索能力.文献[6]基于参数自适应思想,提出了全局自适应优化蚁群算法GAO,改进了状态转移概率和蚁群信息素更新规则,该方法具有很好的全局收敛能力.文献[7]针对Web服务的动态性、不稳定性以及多种QoS属性约束的问题,提出一种多信息素动态更新的蚁群算法MPDACO.

上文中所建立的数学模型容易忽略物流Web服务QoS属性内在的信誉度和可靠性.而且以粒子群算法(PSO)、遗传算法(GA)、蚁群算法(ACO)为代表的群体智能进化算法存在一定的缺陷:求解结果不稳定,容易陷入局部最优等.

针对物流服务的不确定性,利用数学特征对QoS信息建模,引入了服务可靠性、可用性和信誉度对组合服务进行综合评价.同时为了提高遗传算法的搜索效率,进一步优化了遗传算法的不足之处.最后通过对比实验证明了该方法的可行性和有效性.

2 物流Web服务组合问题

通过复合多种物流Web服务的手段,也就是按照一定的业务逻辑构造多个Web服务以及Web服务之间的集成模式,即是物流Web服务组合.

图1 物流Web服务组合Fig.1 Logistics Web service composition

Web组合服务的原子结构包括顺序结构(sequence)、选择结构(choice)、循环结构(loop)和并行结构(parallel)[8].这些组合模型可以通过采取文献[9]中的技术转化成顺序原子结构.服务流程已经确定的Web服务组合如图1.设一个Web组合服务有n个物流服务类,每个服务类有m个候选Web服务,每个候选Web服务有r个QoS属性.这种物流Web服务组合为:CSS={S1,S2,…,Sn},S1,S2,…,Sn是组成物流Web服务组合流程的服务节点.Web服务类CSj={CSj1,CSj2,…,CSjm}包含m个拥有一样的功能但QoS不同的候选物流服务类.每个候选Web服务的QoS属性值可用向量表示为:qk(CSji)={q1(CSji),q2(CSji),…,qr(CSji)}.

当处理物流Web服务组合流程时,可以根据以下两种方法判定Web服务组合程序是否具备可行性:

1)在一个物流Web服务组合程序中,物流Web服务的运能可否能够达到用户运能的最低标准,只有在所有物流Web服务的运能都可以满足用户要求时,该物流Web服务组合程序才是有效的.

2)对于一个完整的物流Web服务组合程序,要求其中所有Web服务的终止时间都要在紧接其后的Web服务的开始时间之前,还需要按照调度Web服务的时间约束条件设置相应的缓冲间隔.

3 数学模型

物流Web服务作为一种复杂的Web服务具有多种QoS属性指标[10],所有物流Web服务的QoS属性大体上可以分成两类,一类是考虑QoS属性最大化的积极属性,比如Web服务的可靠性、信誉度、可用性等;另一类是考虑QoS属性最小化的消极属性,比如Web服务的成本、响应时间等.为了能够客观准确地判断物流Web服务的QoS优劣,需要将不同数值类型、不同取值区间的QoS属性值归一化处理,转化为相同的取值类型和范围.

(1)

在满足用户QoS需求的前提下,物流Web服务的全局服务质量属性应当符合下列约束条件:

(2)

(3)

根据定性概念的数字特征,可以精确地判断出QoS属性的不确定程度,从而为获得可靠的物流Web服务组合提供了保障.对于客户而言,保留QoS较优且波动性小的物流Web服务比不稳定的物流Web服务更为重要.

满足全局QoS约束的最优物流Web服务组合的目标函数为:

(4)

4 改进的遗传优化算法

遗传算法GA是由美国Holland教授于1975年提出的一种基于随机搜索的智能优化算法,其宗旨是将问题的隐含解表示为个体,并利用适应度函数计算个体的评价值.

4.1 遗传编码与初始种群

为了让GA找到物流Web服务组合的有效解,首先需要对染色体进行编码.染色体由一些候选物流Web服务构成,其中的一个基因代表一个候选Web服务,包含了r条QoS属性及其数值.为了简化染色体的编码方式,文中利用双层位置编码模式,使得染色体上不同的基因都有对应的Web服务,QoS属性由相应的基因决定.

目前许多的启发式进化算法都采用简单的均匀取种法或者随机取种法来构造初始种群,这两种方法的随机性比较强,可能会引起种群适应度普遍偏低,很难提高算法的收敛能力[11].

对于确定的物流Web服务组合流程,候选Web服务CSji的QoS适应度函数如下:

(5)

CSji被选中的概率为:

(6)

4.2 交叉操作

大多数遗传算法的交叉操作往往只要求随机选择两条染色体作为交叉算子,容易导致算法搜索结果不稳定.本文在交叉算子的基础上引入协作学习的概念,加快了算法的搜索效率.对于所有的物流Web服务组合方案,其中的每个具体服务都是基因片段.将这些候选服务路径分成相等的子路径,再使它们分别与剩余的服务路径间进行模仿选择,交叉的节点个数为C.自适应交叉概率如下:

(7)

4.3 变异操作

(8)

自适应变异概率如下:

(9)

4.4 遗传算法步骤

基于QoS感知的物流Web服务组合与优化算法中,其基本理念是:根据用户对服务质量的约束及偏爱,挑选出满足用户需要的候选物流Web服务,提高Web服务组合的搜索效率.再通过使用改进后的遗传优化算法,得到具有最优QoS的物流Web服务组合方案.详细步骤如下:

Step1.初始化候选物流Web服务集合与服务质量属性,根据公式(2)、公式(3)初步选择候选物流Web服务,设定最大进化代数Nmax,确定种群规模.

Step2.对物流Web服务进行编码,按照公式(5)计算物流Web服务适应度,

Step3.根据适应度大小选择物流Web服务,产生初始种群NGA.

Step4.根据选择概率公式可以计算出所有候选物流Web服务的选择概率,根据轮盘赌方法可以得到物流Web服务组合.

Step5.根据交叉概率Pc计算Web服务的交叉概率,判断是否需要进行交叉操作.

Step6.按照变异概率Pm计算Web服务的变异概率,然后根据公式(8)进行领域搜索,产生新的Web服务组合.

Step7.判断算法是否达到终止进化次数Nmax,如果达到就执行下一步,否则跳回Step 4.

Step8.终止算法,得到最优物流Web服务组合方案.

5 实验与分析

5.1 仿真实验

在仿真实验中,物流Web服务组合算法采用的运行工具为VC++语言,算法的运行环境为个人电脑,详细配置为:Windows 7 SP1,RAM为2.00GB,CPU为Intel(R)Core(TM)2 E7500.

根据物流Web服务的特征,实验中的任务个数固定为9,候选物流Web服务的QoS属性随机生成.QoS属性指标分别为:运行时间(time)、成本费用(cost)、可靠性(reliability)、可用性(availability)和信誉度(reputation)五种QoS维度.它们各自的取值范围分别为:(1h≤t≤30h)、(1$≤c≤100$)、(0.75≤rel≤1)、(0.75≤a≤1)、(0.5≤rep≤1).相应的服务质量属性偏爱设置为{0.15,0.2,0.2,0.15,0.3}.

实验分为两个方面:1)当物流候选Web服务数量固定时,比较不同算法的服务组合评价值;2)随着候选Web服务数量的增加,不同算法运行时间的变化趋势.

5.2 结果分析

图2是算法在相同的实验环境下搜索到的物流Web服务组合评价值以及相应的迭代次数,其中候选Web服务数量

图2 组合Web服务评价值的比较Fig.2 Comparison of composite Web service evaluation values

设为m=50.两种算法在相同的迭代次数下搜索到的组合服务评价值有着很明显的差距,改进后的遗传算法(EGA)的收敛速度与搜索解的性能明显强于GA.

图3记录了候选物流Web服务数量增加时,两种不同的算法最终收敛时的运行时间,其中算法的最大迭代次数设定成Nmax=50.显然,随着物流服务数量的增加,两种算法搜索性能的差距变得越来越大.

图3 算法运行时间(s)的变化趋势Fig.3 Trend of algorithm running time

从上述的仿真数据可以看出,改进后的遗传优化算法更加适合用于求解物流Web服务组合与优化问题.

6 结束语

Web服务以其特有的性质引起了商业界、学术界的广泛关注,而基于QoS的服务组合技术更是占据了重要地位.目前遗传算法在服务组合领域还不是十分成熟,文中提出了一种基于QoS感知的物流Web服务组合优化方法,计算机仿真实验证明了该算法具有较高的收敛能力和搜索性能.下一步工作将研究如何将遗传优化算法应用到实际的面向服务系统开发中,并针对QoS动态性、Web服务负载等方面进行更深入的研究.