Web服务是一种基于Web环境的自包含、自描述、模块化且具有良好互操作能力的分布式软件结构,可以通过网络发布、定位和调用^[1].近年来,大量与Web服务相关的技术成果不断问世,如网格计算、服务计算、SOA、网构软件^[2]等,这些成果一方面推动了Web服务的研究进程,一方面使得具有类似功能的服务数量呈爆炸式增长.如何获取满足用户请求的候选服务,成为Web服务发现的研究内容.

现有服务发现的过程以语义本体技术为基础,利用匹配程度表示服务请求与服务库中服务之间的紧密程度.在服务匹配过程中,由于服务与请求间存在多种匹配方案,如何在有限时间内找到匹配精度较高的方案,是提高服务发现质量的主要手段.但是,当前服务匹配存在的主要问题包括:

(1)服务匹配概念的狭窄性.现有服务匹配假设单个服务满足服务请求,即,原子服务匹配过程.随着业务认知深度的加强,单一Web服务很难满足人们日益复杂的软件业务表达的需求,需拓展服务匹配的概念,实现一个请求由多个服务协同完成,即,复合服务匹配过程;

(2)现有服务匹配求解算法的时间复杂度较高.目前,匹配算法多是基于经典的优化策略,如整数规划算法^[3]、贪心算法^[4]或二分图算法^[5]等,这些算法在低维度的服务匹配问题下能够获得最优的结果;但是随着复合服务匹配概念的引入,匹配问题规模的扩大导致匹配结果呈爆炸型增长,现有匹配算法为获得最优的结果必须消耗大量时间,表现出较差的在线响应能力和匹配问题的适应能力,处理效率难以被用户接受;

(3)在其他技术领域中,智能优化算法是处理复杂问题的主要技术手段,但是由于匹配方案的直观表示是一组满足约束的续偶对,而智能优化算法通常处理的求解方案是简单的序列形式,两者在表示上呈现出的差异,导致现有智能优化算法难以直接求解服务匹配问题.

基于服务匹配存在的问题,本文首先通过形式化手段对原子服务匹配进行命题,并以此为基础扩展服务匹配的概念,给出复合服务匹配命题以及服务匹配问题的数学表示,该数学表示可作为求解匹配问题的目标函数及约束条件;其次,设计匹配方案的表示方法,将具有续偶形态的匹配方案等价转换为智能优化算法所能够处理的一般序列形式;最后,采用协同演化的思路,利用PSO(PSO particle swarmoptimization)以及SA(SAsimulation annealing)变异策略的互补特性,设计能够在有限迭代次数内获得较优服务匹配方案的PSO-SA协同演化算法.

本文第1节介绍相关工作.第2节介绍服务匹配命题并抽象匹配问题的数学表达.第3节设计匹配方案的表示方法.第4节介绍PSO-SA算法.第5节通过实验选择合理参数配置,对比分析现有算法及PSO-SA的收敛精度、收敛情况以及在线响应时间.最后,总结并介绍今后研究方向.

1 相关工作分析

服务匹配是实现高质量服务发现的重要步骤,目前,国内外服务匹配方面的研究主要分为以下两类:服务匹配的语义相似度模型及服务匹配的求解算法等.

·通过语义关系对服务匹配过程进行建模.

Paolucci等人^[6]提出了一种基于语义匹配的Web服务发现方法,通过语义描述Web服务的输入/输出参数,实现完全匹配、插入匹配、失败匹配和包含匹配这4种主要关系.较传统的基于关键字匹配的UDDI(universaldescription discovery and integration)^[7]方法,Paolucci等人的方法能够以更加柔性的匹配过程发现更多满足用户请求的可用Web服务,但由于语义关系的复杂性,在实际中具有匹配不精细等问题.邝砾等人^[1]针对语义本体相似度计算速度慢及服务发现问题单一性等问题,提出了基于倒排索引优化的语义服务发现机制,该机制对服务库中的候选服务参数进行标注建树,从而快速、准确、高效地发现目标服务.邱田等人^[8]将Web服务匹配过程看作是描述服务不同属性间的细粒度匹配过程.欧伟杰等人^[9]在前人方法的基础上,引入概念松弛方法,重新定义概念间的泛化和特化关系,降低服务查询过程中的匹配参数数量,提高服务查询效率.

·针对服务匹配求解提出了不同的解决方案.

Zeng等人^[3]从QoS(quality of service)角度重新对服务的输入/输出参数进行定义,提出了局部优化和全局优化算法.裘江南等人^[4]在输入/输出本体的语义相似度矩阵上,利用贪心算法,选取匹配关系矩阵中每一行的最大匹配组成匹配方案,实现快速匹配,但其结果并不是最优的.邓水光等人^[5]提出了基于二分图匹配的语义Web服务发现方法,该方法不受限于具体的Web服务模型和表达语言,通过对二分图最优匹配进行扩展,将求解服务匹配问题转换成扩展二分图的最佳匹配.张佩云等人^[10]采用遗传算法的方法将服务发现应用于已有任务流程不同阶段的服务选择上,其本质是一种与供应链问题类似的粗粒度匹配.

现有研究成果表明,采用语义来描述Web服务已成为解决服务匹配问题的主要手段.但现有匹配算法均是针对单一服务发现而设计的,难以利用现有服务库中的服务形成具有协同关系的复合服务来满足日益复杂的用户需求,存在匹配概念狭窄的问题.同时,二分图和整数规划方法均是一种全局搜索策略,当匹配问题规模n上升时,获取最优匹配方案的计算复杂度为O(n³),运行效率较低,匹配速度严重影响服务发现的在线响应能力.优化算法是解决复杂问题的主要手段,但是由于匹配方案的自然表示较难被智能优化算法所处理,制约了优化算法在服务匹配方面的应用.

2 服务匹配问题 2.1 　原子服务匹配

原子服务匹配的目标是发现能够满足用户请求的单个服务,目前,大量的研究均是基于原子服务匹配展开的.本节在给出必要定义的基础上,对原子服务匹配方案进行命题.

定义1(Web服务). 一个Web服务w由一个二元组组成.w:=<n^s,F>,其中,n^s表示该服务的名称及服务的功能概述;F表示该服务所实现的所有操作集合,f_i为F的元素,表示具体的服务操作.

定义2(服务操作). 一个服务操作f由一个三元组组成.f:=<f^s,I,O>,其中,f ^s表示操作名称及操作功能概述, I={i₁,i₂,…,i_n}描述f的输入本体参数集合,O={o₁,o₂,…,o_m}描述f的输出本体参数集合.

定义3(用户请求). 用户请求R由一个三元组组成.R:=<r^s,I ^r,O^r>.其中,r^s用于标识本次请求,${I^r} = \{ i_1^r,i_2^r,...,i_k^r\} $描述R所能提供的输入本体参数集合,${O^r} = \{ o_1^r,o_2^r,...,o_l^r\} $描述R所期望得到的输出本体参数集合.

命题1(原子服务匹配方案). 对于服务请求R和∀w,如果∃f∈w.F,使得建立在I到I^r的关系I_f和O^r到O上的关系O_f满足需求(1)和需求(2),则称<I_f,O_f>为满足R的原子服务匹配方案.需求(1)和需求(2)为

(1)$\forall {i_i},{i_j} \in I,{i_i} \ne {i_j}{\kern 1pt} ,\exists i_k^r,i_l^r \in {I_r},{\kern 1pt} {\kern 1pt} {\kern 1pt} i_k^r \ne i_l^r,{\text{ s}}{\text{.t}}{\text{. }}{I_f}({i_i}) = i_k^r,{I_f}({i_j}) = i_l^r;$

(2)$\forall o_i^r,o_j^r \in {O^r},o_i^r \ne o_j^r{\kern 1pt} ,\exists {o_k},{o_l} \in O,{o_k} \ne {o_l},{\text{ s}}{\text{.t}}{\text{. }}{O_f}(o_i^r) = {o_k},{O_f}(o_j^r) = {o_l}.$

命题1表明,原子服务匹配方案由建立在f.I到R.I ^r上的本体参数映射关系I_f和从R.O ^r到f.O上的本体参数映射关系O_f组成.在服务匹配过程中,存在多个满足命题1的匹配方案.如果采用本体相似度e来表示不同本体参数间匹配程度,则可获得表示匹配方案的整体匹配程度z.原子服务匹配问题的目标是从所有满足命题1匹配方案中,寻找能够最大化z的匹配方案作为最优匹配结果.

2.2 复合服务匹配

随着技术的发展,服务库中必然存在大量可用服务,现有原子服务匹配过程难以充分利用多个服务协同实现日益复杂的用户需求.为提高服务的利用率以及实现对复杂用户请求的匹配,本节在原子服务匹配定义的基础上,引入复合服务匹配的概念,对复合服务匹配方案进行命题.

定义4(复合服务). 复合服务cw由一个二元组组成,cw:=<n^cw,F^c>,其中,n^cw为标识该复合服务的字符串. ${F^c} = \{ f_1^c,f_2^c,...,f_n^c\} $为该cw所容纳的所有操作.对于F^c中任意操作$f_i^c$,存在服务库中某一服务w,使得$f_1^c \in w.F.$

命题2(复合服务匹配方案). 对于服务请求R和∀cw,如果$\exists {F^x} \subseteq {2^{{F^c}}}$,使得建立在F^x.I^c到R.I ^r的关系I_fc和建立在R.O^r到F^x.O^c的关系O_fc为本体参数映射关系,则称<I_fc,O_fc>为满足R的复合服务匹配方案.

在命题2中,I ^c和O^c分别是cw.F^c中输入和输出本体参数的并集,如公式(1)和公式(2)所示.

${I^c} = \{ f_i^c.I|f_i^c \in {F^c},i \in 1,2,..,n'\} = \bigcup\limits_{i = 1}^{n'} {{F^c}.f_i^c.I} $

(1)

${O^c} = \{ f_j^c.O|f_j^c \in {F^c},j \in 1,2,..,m'\} = \bigcup\limits_{j = 1}^{m'} {{F^c}.f_j^c.O}$

(2)

命题2表明:复合服务匹配并不要求在服务库中存在单个满足请求的服务,而是认为现有服务库中大量的遗留服务,可组合成一个逻辑上的复合服务cw来协同实现复杂的服务请求任务.复合服务的引入,能够在现有服务的基础上最大化地满足复杂请求的多参数需求,增加匹配成功的概率;但与原子服务匹配的方案数量相比,复合服务匹配方案数量将存在更多满足命题2的匹配方案.如何在众多匹配方案中高效地获取能够最大化匹配程度z的匹配方案,是求解复合服务匹配的关键.

在某些实际服务发现过程中,存在R'⊂R.O^r依赖于I'⊂R.I^r的情况,即,用户提供的请求本体集合的子集R'部分依赖于用户所需的本体参数集合的子集I'.这类情况的处理方法是:首先将具有依赖关系的子集R'和I'从R.O^r和R.I^r中取出,采取命题1的原子服务匹配过程获取所需的服务;对于集合中非依赖关系的本体{R.O^r-R'}和{R.I^r-I'},仍然采取命题2,通过复合服务匹配过程获取所需的服务.最终结果为原子服务匹配和复合服务匹配的并集.

2.3 服务匹配问题的数学表达

在命题2的基础上,将复合服务匹配问题转化为优化问题,获得问题的适应度函数以及约束条件.如果令I^*={e_ij}_n'xn表示I^c与I^r中输入本体参数的语义相似度矩阵,O={p_ij}_mxm'表示O^r与O^c的输出本体参数的语义相似度矩阵,则满足命题2的服务匹配问题可表达为公式(4)约束下,最大化公式(3)所示的目标函数.

$\max z = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^{n'} {{\alpha _{ij}}{\varepsilon _{ij}}} } + \sum\limits_{i = 1}^{m'} {\sum\limits_{j = 1}^m {{\beta _{ij}}{\pi _{ij}}} } $

(3)

${\text{s}}{\text{.t}}{\text{. }}\left\{ {\begin{array}{*{20}{l}} {\sum\limits_{i = 1}^n {{\alpha _{ij}}} = 1,{\text{ }}j = \{ j|j \in {Z^ + },j \in [1,n']\} } \\ \begin{gathered} \sum\limits_{j = 1}^{n'} {{\alpha _{ij}}} = 1,{\text{ }}i = \{ i|i \in {Z^ + },i \in [1,n]\} \hfill \\ \sum\limits_{i = 1}^{m'} {{\beta _{ij}}} = 1,{\text{ }}j = \{ j|j \in {Z^ + },j \in [1,m]\} \hfill \\ \sum\limits_{j = 1}^m {{\beta _{ij}}} = 1,{\text{ }}i = \{ i|i \in {Z^ + },i \in [1,\;m']\} \hfill \\ \end{gathered} \\ {\sum\limits_{i = 1}^{n'} {\sum\limits_{j = 1}^n {{\alpha _{ij}}} + \sum\limits_{i = 1}^{m'} {\sum\limits_{j = 1}^m {{\beta _{ij}}} } = n'\; + m'} } \\ {{\alpha _{ij}},{\beta _{ij}} \in \{ 0,1\} } \end{array}} \right.{\kern 1pt} {\kern 1pt} $

(4)

公式(3)和公式(4)表明:求解服务匹配旨在输入和输出相似度矩阵中找到满足命题2的映射关系I_fc和O_fc,且能够最大化目标函数z的匹配方案.由公式(3)及公式(4),I_fc和O_fc均可表示为在I^*和O^*上寻找从原象集(F^x.I^c,R.O^r)到目标象集(R.I^r,F^x.O^c)的映射关系,且在目标函数的表示上及对应参数的约束上具有等价的特性.因此,为避免后续内容描述的冗余,后续章节以I_fc为例,对于O_fc的求解过程可对照I_fc的求解过程.

3 服务匹配方案的转换方法

由命题2,匹配方案I_fc可理解为使矩阵{a_ij}中某一行某一列为1的所有下标(i,j)的序偶集合.每个序偶的第1个元素来源于匹配关系原象集元素下标,第2个元素来源于匹配关系的目标象集的元素下标.虽然序偶表示方法直观地体现了匹配过程,但其形式过于复杂,若要应用优化算法进行求解,必须进行转化.因此,通过3种等价转换——方阵转化、排列转化和顺序转换,将I_fc从序偶形式转换成智能算法所能处理的简单序列形式I_fcr.转换过程如图 1所示.

3.1 方阵转换

在矩阵$I_{n' \times n}^*$中,可能存在用户给定参数冗余的情况,即,n≥n'.为便于匹配算法处理,在$I_{n' \times n}^*$矩阵中添加|n-n'|行以ε=0为元素的行向量,使矩阵$I_{n' \times n}^*转换为方阵$I_{n \times n}^*$.定理1保证了方阵转换的等价性.

定理1. 在服务匹配问题中,$I_{n \times n}^*$为$I_{n' \times n}^*$经过方阵转换的语义相似度矩阵,如果令z'和z分别为$I_{n \times n}^*$和$I_{n' \times n}^*$上的适应度,则该转换过程不改变匹配方案的适应度,即z'=z.

证明:在方阵$I_{n \times n}^*$上的适应度函数z'如公式(5)所示.

$z' = \sum\limits_{i = 1}^n {\sum\limits_j^n {{\alpha _{ij}}{\varepsilon _{ij}}} } = \sum\limits_{i = 1}^{n'} {\sum\limits_j^{n'} {{\alpha _{ij}}{\varepsilon _{ij}}} } + \sum\limits_{i = n' + 1}^{n'} {\sum\limits_j^n {{\alpha _{ij}}{\varepsilon _{ij}}} } $

(5)

根据转换过程,$\sum\limits_{i = n' + 1}^{n'} {\sum\limits_j^n {{\alpha _{ij}}{\varepsilon _{ij}}} } = 0$,即$z' = \sum\limits_{i = 1}^{n'} {\sum\limits_j^{n'} {{\alpha _{ij}}{\varepsilon _{ij}}} } = z$.证毕. □

3.2 排列转换

根据公式(3)和公式(4),I_fc'中每一个e_ij,都存在唯一的序偶(i,j)与之对应,如果将该等价变化过程定义为R_A,则由I_fc生成序偶集I_fcs={(i,j)}的过程如公式(6)所示.

${I_{fc'}}\overset {{R_1}} \longleftrightarrow {I_{fcs}}:{\varepsilon _{ij}} = {R_A}((i,j))$

(6)

R_A过程是将I_fcs中各序偶第1项按照自然数大小进行排序.排序后,所有序偶的后项构成全排列I_fca,该全排列即为匹配方案I_fcs的等价转换.该转换过程的等价性由定理2保证.

定理2. ∀(i,j)∈I_fcs,使得R_A:(i,j)↔j,则R_A(I_fc',I_fca)为原有匹配方案的等价转换.

证明:易证|I_fca|=|I_fc|,显然,R_A为(i,j)↔j是一种等价转换.证毕. □

3.3 顺序转换

虽然I_fca已经具备了一般优化算法所能处理的序列结构,但根据约束,序列中某一个数字仅允许出现1次.该约束导致优化算法必须消耗额外的资源确保I_fca的有效性.在维度较高的问题上,该约束将制约算法的求解效率.因此还需进一步对I_fca转换,使得匹配方案的每一维取值独立于其他维度的取值.基于此,本文利用顺序表示方法,将各维度具有约束关系的I_fca等价转化为各维度间无约束的I_fcr.

顺序表示过程是将I_fca中所有元素依次构成一个顺序表,从I_fca的最左端开始,依次从顺序表中选取元素.选取后,从顺序表中移除该元素,并将记录该元素在顺序表中的下标.当I_fca中所有元素处理完成后,由下标组成的序列I_fcr为原排列I_fca的顺序转换.转换后,I_fcr在第i维上的取值范围为[1,n-i],独立于其他维度的取值.容易证明,从I_fcr到I_fca的转换也是等价转换.

在匹配问题的求解算法中,将利用I_fcr进行演化.每一代演化结束后,采取顺序转换、排列转换和方阵转换的逆过程,将I_fcr转换为I_fc.使用公式(3)计算匹配方案I_fc的匹配精度.

4 求解服务匹配问题的协同演化算法 4.1 算法设计思路

根据NFL(no free lunch)^[11]理论,不存在适用于所有问题的优化算法;但对于一些特定的优化问题,则可通过协同演化进行优化算法设计,提高优化算法获取最优解的期望.从结构上看,协同演化算法分为串行协同^{[12, 13, 14]}和并行协同^{[15, 16, 17]}.其中,串行协同是指在每一代中顺序执行多个演化策略;并行协同通过策略选择概率,在多个策略中依历史信息,选择适用于当前演化过程的演化策略.与串行协同相比,并行协同对不同优化问题的适应性更强、时间复杂度更低.

本文基于PSO(particle swarm optimization)和SA(simulated annealing)演化策略设计适用于服务匹配问题的并行协同演化算法(PSO-SA).PSO易于实现,且具有更快的收敛速度,但容易陷入到局部最优解,表现为极强的趋同性和较低的种群多样性.SA采取概率的方式保留一些具有潜在寻优能力的候选解,提高了种群的多样性,但其收敛速度较慢.SA与PSO的演化特征具有互补性,结合PSO和SA进行算法设计,能够提高收敛速度并实现深度和广度的优化过程.

4.2 PSO-SA协同演化算法实现

PSO-SA的基本流程如图 2所示.

(1) 初始化种群及参数

设n为问题规模,S为种群规模,演化策略的选择概率m⁽¹⁾=(m⁽¹⁾(PSO),m⁽¹⁾(SA),SA初始温度t⁽¹⁾,SA的温度调节因子a,PSO中调和因子l₁和l₂,扰动因子r₁和r₂,迭代次数G,锦标赛轮数等于种群大小S,适应度函数为z.

在第1代,种群X⁽¹⁾中每一个个体可表示为一个三元组向量$({(I_{fcr}^i)^{(1)}},\xi ,v_i^{(1)}),\forall i \in \{ 1,2,...,S\} $.每个向量都是n-1维,如公式(7)所示.

$\left\{ {\begin{array}{*{20}{l}} {{{(I_{fcr}^i)}^{(1)}} = ({{(I_{fcr}^i)}^{(1)}}(1),{{(I_{fcr}^i)}^{(1)}}(2),...,{{(I_{fcr}^i)}^{(1)}}(n - 1))} \\ {\xi = (\xi (1),\xi (2),...,\xi (n - 1))\;\;\;\;\;\;\;\;{\kern 1pt} } \\ {v_i^{(1)} = \;(v_i^{(1)}(1),v_i^{(1)}(2),...,v_i^{(1)}(n - 1))\;\;\;\;{\kern 1pt} } \end{array}} \right.,i \in \{ i|i \in {Z^ + },i \in [1,S]\} $

(7)

其中,${(I_{fcr}^i)^{(1)}}$是决策变量,即匹配方案,随机显示为长度为n-1的自然序列;ζ为匹配方案的约束变量,控制匹配方案各维度的取值范围,ζ(d)=n-d,d∈{1,2,…,n-1};$v_i^{(1)}$为辅助变量,表示匹配方案不同维的速度,初值为[v_min,v_max]内的随机数.

在第k代开始时,PSO-SA根据策略选择概率μ^(k)选择本代的演化策略.

(2) PSO演化策略

PSO-SA所使用的PSO演化策略与标准PSO策略类似,均采用群体的最优位置和个体的历史最优位置来调控粒子当前速度.不同之处在于,PSO-SA综合考虑调和因子l₁和l₂对惯性因子的影响,通过公式(8)计算w.

$\left\{ {\begin{array}{*{20}{l}} {\phi = {\lambda _1} + {\lambda _2},{\lambda _1},{\lambda _2} \geqslant 2} \\ {\omega = 2/|2 - \phi - \sqrt {\phi (\phi - 4)} |} \end{array}} \right.$

(8)

对于决策变量${(I_{fcr}^i)^{(k)}},$采用inter-weight的方法,将ω不仅作用于前一时刻的速度,也作用于本代寻优过程中趋向个体的历史最优位置p_i和群体的历史最优位置g_i.同时,根据匹配问题的离散特征,对演化后的${(I_{fcr}^i)^{(k)}}$进行离散化操作.综合上述考虑,按照公式(9)产生k+1代候选解X'^(k+1).

$\left\{ {\begin{array}{*{20}{l}} {{{({{v'}_i})}^{(k + 1)}} = \omega (v_i^{(k + 1)} + {\lambda _1}{r_1}(p_i^k - {{(I_{fcr}^i)}^{(k)}}) + {\lambda _2}{r_2}(g_i^k - {{(I_{fcr}^i)}^{(k)}}))} \\ {{{(I_{fcr}^i)'}^{(k + 1)}} = \left\lceil {{{(I_{fcr}^i)}^{(k)}} + {{({{v'}_i})}^{(k + 1)}}} \right\rceil } \end{array}} \right.$

(9)

(3) SA演化策略

SA演化策略随机选择决策变量${(I_{fcr}^i)^{(k)}}$的某一维d,以离散高斯分布DN_d(-x(d),x(d))在约束范围内获取该维度的变异步长,按照公式(10)产生子代的候选解X'^(k+1).

$\left\{ {\begin{array}{*{20}{l}} {{{(I_{fcr}^i)'}^{(k + 1)}}(d) = {{(I_{fcr}^i)}^{(k)}}(d) + D{N_d}( - \xi (d),\xi (d))} \\ {{{({{v'}_i})}^{(k + 1)}} = v_i^{(k)}} \end{array}} \right.$

(10)

按照公式(11)确定候选子代的决策变量,其中,$I_{fcr}^{(k + 1)} \in {X^{(k + 1)}},{(I_{fcr}^*)^{(k + 1)}} \in {X'^{(k + 1)}}.$

$\left\{ {\begin{array}{*{20}{l}} {I_{fcr}^{(k + 1)} \leftarrow {{(I_{fcr}^*)}^{(k + 1)}},{\text{ }}z({{(I_{fcr}^*)}^{(k + 1)}}) \geqslant z(I_{fcr}^{(k + 1)})} \\ {I_{fcr}^{(k + 1)}\xleftarrow{P}{{(I_{fcr}^*)}^{(k + 1)}},{\text{ }}z({{(I_{fcr}^*)}^{(k + 1)}}) < z(I_{fcr}^{(k + 1)})} \end{array}} \right.$

(11)

在公式(11)中,概率P的计算方法如公式(12)所示.

$P(I_{fcr}^{(k)},{(I_{fcr}^*)^{(k)}},t(k)) = \min \left\{ {1,\exp \left( { - \frac{{z({{(I_{fcr}^*)}^{(k)}}) - z(I_{fcr}^{(k)})}}{{{t^{(k)}}}}} \right)} \right\}$

(12)

公式(12)表明:在适应度差距较小且温度较高时,系统更容易接受适应度较差的个体作为子代;而随着代数的增加,温度逐渐降低,系统接受较差个体的概率变小.

(4) 按约束调整解

经过PSO或SA演化后,会出现决策变量不满足约束x的情况,采用公式(13)调整不满足约束的维度d.

$I_{fcr}^i(d) = \left\{ {\begin{array}{*{20}{l}} {[I_{fcr}^i(d) - 1]\bmod (\xi (d) - 1) + 1,{\text{ }}I_{fcr}^i(d) > \xi (d)} \\ {[I_{fcr}^i(d) - {\xi _i}(d)]\bmod (1 - \xi (d)) + \xi (d),{\text{ }}I_{fcr}^i(d) < 1} \\ {I_{fcr}^i(d),{\text{ }}I_{fcr}^i(d) \in [1,\xi (d)]} \end{array}} \right.$

(13)

(5) 更新p_i和g_i

在第k代演化结束后,若采用PSO演化策略,则需根据候选子代X'^(k+1)和父代X^(k)的适应度,更新公式(9)中个体的历史最优位置p_i及种群历史最优位置g_i,如公式(14)和公式(15)所示.

$p_i^{(k + 1)} = \left\{ {\begin{array}{*{20}{l}} {p_i^{(k)},{\text{ }}z(I{{_{fcr}^i}^{(k)}}) \leqslant z(p_i^{(k)})} \\ {{{(I_{fcr}^i)}^{(k)}},{\text{ }}z({{(I_{fcr}^i)}^{(k)}}) > z(p_i^{(k)})} \\ {{{(I_{fcr}^i)}^{(k)}} \in {{X'}^{(k + 1)}} \wedge i \in \{ i|i \in {Z^ + },i \in [1,S]\} } \end{array}} \right.$

(14)

$g_i^{(k + 1)} = \mathop {\max }\limits_{p_i^{(k)}} (z(p_i^{(k)})),i = 1,...,{P_s}$

(15)

(6) 更新退火温度

在第k代演化结束后,若采用SA演化策略,则需计算k+1代的退火温度,如公式(16)所示.

t(k+1)=at(k)

(16)

其中,a为温度调节因子,控制相邻代数间温度下降的差异.

(7) 选择子代

在第k代演化结束后,从|X^(k)∪X'^(k+1)|个个体中,采用锦标赛方法,选择S个个体构成最终子代X^(k+1).具体操作过程:对于∀x∈X^(k)∪X'^(k+1),初始化其得分s_x=0,随机选择另一个个体y∈X^(k)∪X'^(k+1),比较个体的适应度,即,比较z(x.I_fcr)和z(y.I_fcr).如果z(x.I_fcr)≥z(y.I_fcr),则s_x=s_x+1.上述比较过程执行S次,最终,根据个体评分s_x的排序,选择序列中前S个个体构成子代X^(k+1).

(8) 更新策略的选择概率

第k代演化结束后,根据X^(k+1)中每个子代个体及其对应父代个体X^(k),对m^(k)进行如下更新.

针对X^(k+1)中个体的决策变量$I_{fcr}^{(k + 1)}$,如果是来自于父代的演化,说明第k代使用的演化策略为当前的优势策略.为促使演化过程尽快收敛,应提高该演化策略h的选择概率m^(k)(h),同时降低其他变异策略l的选择概率m^(k)(l),并确保m^(k)(h)+m^(k)(l)=1,如公式(17)所示.

$\left\{ {\begin{array}{*{20}{l}} {{\mu ^{(k + 1)}}(h) = {\mu ^{(k)}}(h) + \gamma (1 - {\mu ^{(k)}}(h))} \\ {{\mu ^{(k + 1)}}(l) = {\mu ^{(k)}}(l) - \gamma {\mu ^{(k)}}(l)} \end{array}} \right.$

(17)

同理,若演化策略h为劣势策略,则使用公式(18)调整策略选择概率.

$\left\{ {\begin{array}{*{20}{l}} {{\mu ^{(k + 1)}}(l) = {\mu ^{(k)}}(l) + \gamma (1 - {\mu ^{(k)}}(l))} \\ {{\mu ^{(k + 1)}}(h) = {\mu ^{(k)}}(h) - \gamma {\mu ^{(k)}}(h)} \end{array}} \right.$

(18)

在公式(17)和公式(18)中,g控制概率调整的步长.

4.3 算法的时间复杂度分析

对于优化算法,时间复杂度与问题规模n有密切关系.如果设z(n)表示计算适应度的多项式函数,S为种群规模,G为算法固定迭代次数,则PSO-SA的时间复杂度分析如下.

算法每执行一次PSO演化过程的时间复杂度见表 1,算法每执行一次SA演化过程的时间复杂度见表 2.

算法每执行一次子代过程和策略选择概率更新过程的时间复杂度见表 3.

如果设PSO-SA执行PSO过程G₁次,执行SA算法G₂次,满足G=G₁+G₂,则PSO-SA算法的时间复杂度为

O(2G1Sn+2G2S+GS+GSz(n)+GSlog(Sz(n))).

由于G>G₁,G>G₂且z(n)~n,化简后的时间复杂度为

O(3GSn+3GS+GSlogS+GSlogn).

如果PSO-SA采取固定迭代次数G以及种群大小S,则算法的时间复杂度可进一步化简为

O(3GSn+GSlogn)~O(n+logn).

在设定较低的迭代次数G以及种群大小S时,与传统二分图算法的时间复杂度O(n³)相比,PSO-SA的时间复杂度O(n+logn)随n上升的速度要远低于O(n³).

5 实验分析 5.1 数据准备

实验在Intel Core Duo 2.66GHz处理器和2G内存的主机上运行,通过Python,OWL-SAPI实现PSO-SA及其他对比算法.采用OWL-S TC(OWL-S serviceretrieval test collection)^[18] V4.0中来自5个领域中600个OWL-S服务进行服务匹配实验.采用已提出的语义相似度计算方法^[19],生成问题维度分别从10~60的6个匹配矩阵作为后续实验的数据集.

由于实际服务发现过程要求服务匹配能够在有限时间内及时返回相对较优的匹配方案,因此采取限定迭代次数作为终止条件来测试不同算法在数据集上的执行效果.

5.2 基本参数配置

根据第4.3节,算法的迭代次数G和种群规模S皆能影响算法效率.根据服务发现过程对服务匹配的效率要求,在后续实验中,对各种对比算法均设定同样较小的种群规模和较低的迭代次数,分析各算法在有限迭代次数内的寻优情况.实验基本参数的配置情况见表 4.

5.3 实验内容

在实验中,横向对比算法包括Greedy为贪心算法^[4]、GA为遗传算法、PSO为粒子群算法、SA为模拟退火算法.纵向对比组为串行协同和并行协同,串行协同包括PSOWSA^[12],PSOWGSA^[13]和HPSOSA^[14],PSOWSA在每一代中顺序执行PSO和SA,PSOWGSA只对种群中全局最优位置执行SA变异,HPSOSA仅在PSO多次变异但最优值保持不变时,采取SA策略尝试跳出局部最优.并行协同的成果较少,主要以PSO-SP^[17]为代表,它采取PSO和SP(single point)进行协同演化.

5.4 实验结果分析 5.4.1 主要参数取值

(1) γ取值分析

根据公式(17)和公式(18),当γ>0.5时,即使种群中仅有0.5S个个体的变异来自父代,也会产生μ^(k+1)(h)→0和μ^(k+1)(l)→1的效果,即,在第k+1代,PSO-SA必然演化策略l.因此,理论上,选取较大的γ会导致策略选择概率变化过于敏感,造成算法的过分拟合.故为进一步确定γ的取值,分析γ=0.1,0.2,0.3,0.4,0.5时,PSO-SA获得匹配结果适应度的统计量,以10维和60维实验结果为例进行说明,见表 5和表 6.表中数值为独立实验50次所得最优匹配精度的平均值、标准差和中位数.

根据实验结果,当γ=0.2时,各项统计量结果较优.后续实验中,γ=0.2.

(2) μ⁽¹⁾的取值分析

在不同问题维度的数据集上,μ⁽¹⁾(PSO)=0.1,0.2,…,0.9时,PSO-SA的最优匹配方案的适应度增长趋势相同.在同一维度中,采取不同μ⁽¹⁾(PSO)的初值所获得标准偏差的平均值为0.105,最终匹配方案的适应度间的差异较小.由上述实验结果,PSO-SA优化效果不依赖于μ⁽¹⁾(PSO)的取值.在后续仿真实验中,μ⁽¹⁾(PSO)=μ⁽¹⁾(SA)=0.5.

5.4.2 各算法求解精度对比实验

在问题规模为d=10,30,60的数据集上,分别运行横向对比组、纵向对比组以及PSO-SA算法50轮,计算各轮在100代时所获得的匹配方案的统计量:最大值Max、最小值Min、平均值Avg、标准差Std和中位数Med.横向对比组的统计量见表 7,纵向的统计量见表 8和表 9.

·横向对比组分析

当d=10时,PSO-SA的平均值上低于PSO和GA结果0.06和0.01.当d>10时,PSO-SA在除标准差外的各统计量上均优于组内其他算法.虽然GA在所有维度的问题中均具有较低的方差,但其所得到的平均匹配值劣于PSO-SA,说明GA在寻优过程中出现了早熟的情况.

·串行协同演化对比组分析

当d=10时,PSO-SA运行50轮所获得的中位数略劣于HPSOSA.在其他维度的各项统计量上,PSO-SA均优于PSOWSA,PSOWGSA和HPSOSA.

·并行协同演化对比组分析

从各维度的统计结果上看:虽然PSO-SP采取与PSO-SA类似的演化策略概率选择方式,但是由于使用不同演化策略,在服务匹配问题上,PSO-SP的寻优效果劣于PSO-SA.

综合上述实验结果,在d=10时,虽然PSO-SA可获得相对较优的匹配方案,但PSO通常具有更好的寻优精度.在d>10时,其他算法均无法获得比PSO-SA更优的匹配方案.随着用户需求的日益复杂以及服务库中候选服务数量的上升,具有高维特征的复合服务匹配问题将远多于低维特征的原子服务匹配问题.然而,一旦出现了低维度的匹配问题,也可以直接采用本文所提出的匹配方案转换方法,并直接使用PSO算法进行优化.

5.4.3 各算法实际收敛过程对比实验

在问题规模为d=10,30,60的数据集上,分别运行横向对比组、纵向对比组和PSO-SA,记录各算法每一代的最优匹配方案的适应度z,分析算法的实际收敛情况.横向对比组中各算法的收敛情况如图 3~图 5所示,纵向对比组中各算法的收敛情况如图 6~图 8所示.在各幅收敛图中,横坐标表示算法迭代代数,纵坐标表示算法获得匹配方案的适应度z.

·横向对比组分析

在d=10时,PSO-SA的收敛情况与GA接近,但最终收敛情况劣于PSO.SA算法出现了严重的退化现象.随着问题维度的上升,PSO-SA和GA均表现出稳定进化的特征,但GA出现了早熟现象,这一过程也解释了在表 7中GA的标准差较低的原因.单纯采用PSO和SA对服务匹配问题进行优化时,匹配方案的适应度随迭代过程而发生波动和退化现象,导致算法无法收敛.

·纵向对比组分析

在d=10时,PSO-SP,PSO-SA与HPSOSA的收敛情况类似.虽然PSOWSA也表现出稳定的进化特征,但容易陷入局部最优解,表现为趋同特征.PSOWGSA算法则整体出现波动较大及退化现象.随着问题维度的上升,PSO-SP,PSO-SA及PSOWSA均表现出稳定进化特征,但PSOWGSA和HPSOSA出现了严重的波动情况,导致算法无法收敛.

综合上述分析,PSO-SA能够在有限迭代次数内克服经典优化算法和现有协同演化算法在处理匹配问题时出现的早熟(GA,PSOWGSA)、难以收敛(PSO,PSOWGSA,HPSOSA)以及退化(SA,PSOWGSA)等问题,实现稳定进化的收敛过程,对不同维度匹配问题具有较好的适应性.与PSO-SP相比,PSO-SA更适合处理服务发现的匹配问题.

5.4.4 各算法在线响应时间的对比实验

分别运行PSO-SA以及纵向对比组中各种算法50轮,计算每轮算法运行100代所消耗时间的平均值,判断各算法的在线响应时间,如图 9所示,横坐标为问题维度,纵坐标为各算法的在线响应时间.

在同一维度中,各算法消耗时间的关系:PSOWSA>PSOWGSA>HPSOSA>PSO-SA>PSO-SP.其中,PSOWSA所消耗时间近似是PSO-SA消耗时间的2倍.原因为:PSOWSA的每一次迭代相当于先后执行了PSO操作和SA操作,即,等价于PSO-SA执行了两代演化操作.HPSOSA与PSOWGSA在演化过程中仅针对最优个体执行SA策略,但其仍然是一种串行演化过程,相当于在执行了PSO操作的基础上,有选择地执行SA操作,导致算法的在线响应时间微高于PSO-SP和PSO-SA.PSO-SP采用的单点操作无需进行概率选择过程,其在线响应时间较PSO-SA略低.各算法的在线响应时间均随着维度的上升呈现线性提高,实际相应时间满足第4.3节的分析结果.

综合上述分析,并行协同演化算法的在线响应时间要低于串行协同演化算法.PSO-SP虽然具有最低的响应时间,但综合第5.4.2节和第5.4.3节的实验结果,PSO-SP的寻优精度和收敛效果均劣于PSO-SA;且PSO-SA的在线响应时间在不同维度匹配问题上仅比PSO-SP高0.05s,在用户可接受范围内,满足服务发现对匹配算法高效的响应需求.

6 结束语

服务发现技术能够在海量服务中快速获取满足用户需求的候选服务,而匹配结果是决定服务发现质量的关键.针对服务匹配过程中存在的匹配概念狭窄、匹配方案的自然表示难以被优化算法处理及匹配算法的时间复杂度较高等问题,提出了适用于求解服务匹配问题的协同演化算法PSO-SA.实验结果表明:PSO-SA在处理不同维度的匹配问题时,能够在有限的迭代次数内获得比其他算法更高适应度的匹配方案,体现出较高的问题适应性以及高效的响应能力.

在后续的研究过程中,尝试引入其他演化策略,如人工蜂群算法,与现有PSO-SA结合,吸收各算法的演化优势,形成多策略协同演化过程.同时,服务匹配仅作为PSO-SA的一方面应用,对于其他组合优化问题,还需设计基于问题启发的解的转换方法及适应度计算方法,并进一步验证PSO-SA的适应性.