一种面向Web服务组合的优化方法

摘要

本发明公开了一种面向Web服务组合的优化方法，该方法采用捕食搜索策略平衡粒子群算法的局部搜索和全局搜索，捕食搜索在较差的区域进行全局搜索，以找到较好的区域，然后在较好的区域进行集中的局域搜索，使解得到迅速改善；利用Web服务的特点对Web服务进行分类，将具有相同的输入和输出的服务分在同一个类中，从而减少组合数，使得完全枚举所有组合方案成为可能。在粒子群算法中采用余切初始化和余切扰乱替换随机初始化和随机扰乱，对Web服务组合方案的初始化和更新做了改进，大大提高了最终组合方案的多样性。本发明在满足用户服务需求的前提下，保证Web服务组合的QoS服务质量达到最优，进一步提高了Web服务组合的效率以及Web服务组合的多样性。

权利要求

1.一种面向Web服务组合的优化方法，其特征在于，包括如下步骤：

步骤1，利用捕食搜索策略在所有的Web服务中求得一条可行服务链，该可行服务链满足用户Web服务组合的要求；

步骤2，可行服务链的长度为m，搜索可行服务链上每个Web服务对应的候选服务，即将与可行服务链上各Web服务具有相同输入集合和输出集合的Web服务放入同一个服务类中，得到m个候选服务类；

步骤3，在候选服务类中，使用具有混沌性质的余切序列依次从各候选服务类中选择一个候选服务，形成一个Web服务组合，该Web服务组合映射为一个粒子，重复上述过程n次，得到n个粒子；对每个粒子的速度和位置进行初始化；

步骤4，利用适应度函数评价n个Web服务组合，将适应度函数值最大的Web服务组合作为最优Web服务组合，并判断对应的适应度函数值是否达到理论最优，如果是，则将该最优Web服务组合作为局部最优Web服务组合，否则，执行步骤5；当找到最终的局部最优Web服务组合或更新次数达到上限，则停止，并输出停止时的局部最优Web服务组合；

步骤5，利用混沌扰乱更新n个Web服务组合，使得这n个Web服务组合向本身历史最优Web服务组合和当前局部最优Web服务组合学习，更新完成后，返回执行步骤4；

步骤6，重复步骤1-步骤5，直至找到全局最优Web服务组合或捕食搜索次数达到上限；

搜索结束后，对全局最优Web服务组合进行逻辑结构优化，得到优化后的全局最优Web服务组合；

所述对全局最优Web服务组合进行逻辑结构优化，得到优化后的全局最优Web服务组合的具体过程为：步骤61、根据全局最优Web服务组合的长度m，随机生成一个整数x，0≤x≤m-1；

步骤62、取全局最优Web服务组合中下标为x的候选服务Sx，根据候选服务Sx的输入集合和输出集合，利用步骤1-步骤5进行求解，是否有与候选服务Sx等效的服务链；

步骤63、若有等效的服务链，则将等效的服务链替换候选服务Sx，并判断替换后的全局最优Web服务组合的适应度函数值是否优于替换前，若是则替换，否则不替换；

步骤64、重复步骤61-步骤63，生成不同的随机数，且替换次数小于等于 得到优化后的全局最优Web服务组合。

2.根据权利要求1所述面向Web服务组合的优化方法，其特征在于，所述步骤1的具体过程为：步骤11，设置searchSet集合为空，搜索所有的Web服务，将满足用户Web服务组合要求的Web服务加入服务链，同时将该Web服务的输入集合存放于searchSet集合中；

步骤12，在将满足用户Web服务组合要求的Web服务加入服务链之前，判断searchSet集合中是否已有该Web服务的输入集合，若没有，则将该Web服务加入服务链，否则，不加入；

步骤13，当前搜索结束后，若没有得到可行服务链，则将searchSet集合清空，在没有被搜索过的Web服务中重复步骤11-步骤12，直到找到一条可行服务链或到达最大搜索次数，停止搜索。

3.根据权利要求1所述面向Web服务组合的优化方法，其特征在于，所述步骤3的具体过程为：步骤31，可行服务链的长度为m，j＝0,…,m-1，第j个Web服务有kj个候选服务；

步骤32，确定kj的数量级 根据与第j个Web服务对应的余切序列值 截取余切序列值小数点后φj位作为整数值ui,j， i＝0,…,n-1，n为粒子总数；

步骤33，将ui,j对kj取余，产生混沌值ξi,j，混沌值与第j个Web服务对应的候选服务类中的一个候选服务对应，将所对应的候选服务在粒子中位置设为1，其他设为0，粒子的位置Xi初始化完成；同时，粒子的速度Vi及粒子本身历史最佳位置Pi的初始化均等于Xi。

4.根据权利要求1所述面向Web服务组合的优化方法，其特征在于，步骤4所述适应度函数值的计算公式为：其中，j＝0,…,m-1，tj、cj、rj、aj分别表示当前计算的Web服务组合中第j个候选服务的响应时间、执行成本、可靠性、可用性，α+β+γ+η＝1，α、β、γ、η分别表示各个属性权重，T_Max、C_Max分别表示所有候选服务中响应时间最大的值、执行成本最大的值，F表示当前计算的Web服务组合的适应度函数值。

说明书

一种面向Web服务组合的优化方法

技术领域

[0001] 本发明涉及一种面向Web服务组合的优化方法，属于信息集成和软件工程应用技术领域。

背景技术

[0002] 目前用户的需求越来越多，也越来越复杂，原来单个Web服务所能解决的问题越来越少，复杂性的增加使得服务组合越来越重要，因为Web服务组合起来能解决更多的问题，而且在软件工程的概念上提高了聚合程度，降低了耦合程度，在组合的基础上维护起来更加方便，增加新的功能和减少原来的功能更加容易，只要单独的Web服务模块经过严格的测试，各个方面的参数都满足要求，我们就可以放心的来使用，并且在发现错误后可以很快的定位，最终的服务是经过测试好的单独服务组合起来的，并且单个服务模块是正确的。这就使得Web服务组合的应用越来越广泛。

[0003] 随着Web服务组合应用的广泛，随之出现的问题也越来越多，较为突出的有语义Web服务组合问题，即单个Web服务信息交互，消息理解一致性等，这是由于广泛存在的服务异构问题造成的，这样的问题降低了服务发现，匹配和选取的准确率以及服务之间互操作的能力，影响组合服务的有效性和正确性，成为动态组合发展的瓶颈之一。

[0004] Web服务的不确定性问题也比较突出，不确定性问题包括Web服务是否可用是不确定的，Web服务的服务质量(Quality of Service，QoS)是动态变化的，是不可控的，是不同的，当然用户对Web服务质量QoS的要求是不同的，对于不同Web服务应用领域，Web服务的组合模式和关联关系是不同的。不确定性问题给Web组合带来的问题是多种多样的，它影响着系统的有效设计、开发、可靠性、可用性以及质量问题。

[0005] Web服务目前已经在很多领域得到了应用。服务质量QoS问题对于Web服务的成功应用非常关键，如何提供具有QoS保证的Web服务是目前Web服务研究和应用的一个热点问题。从Web服务组合的角度看，如何从大量的Web服务中选择合适的Web服务并进行优化组合，以使得Web组合服务的QoS满足需求，是Web服务组合研究中的一个重要问题。

[0006] 在Web服务组合中，一个Web服务组合中各个服务的选配问题，这是复杂的组合优化问题，即在大量的Web服务集合中搜索满足一定的服务质量且符合用户的需求的组合。求解该问题不但耗时，而且很难找到最佳Web服务组合方案，求解的结果直接影响Web服务组合的质量和成本。针对这一问题，采用智能优化算法求解Web服务组合优化问题是目前的主流思路。这样在一定程度上对Web服务组合进行了优化，但仍然存在以下不足：

[0007] 1)由于随着Web服务的数量增大，其计算量成指数增长，所以求解优化问题的效率低下；

[0008] 2)在搜索最优解过程中，随机搜索策略不能保证最终解的多样性，需要新的搜索策略；

[0009] 3)求解Web服务组合优化问题时，不但需要考虑Web服务的选取，还需要考虑Web服务之间的逻辑关系问题。

发明内容

[0010] 本发明所要解决的技术问题是：提供一种面向Web服务组合的优化方法，面向Web服务组合的环境，实现在控制满足用户服务需求的前提下，保证Web服务组合的QoS服务质量达到最优，并且进一步提高了Web服务组合的效率，提高了Web服务组合的多样性。

[0011] 本发明为解决上述技术问题采用以下技术方案：

[0012] 一种面向Web服务组合的优化方法，包括如下步骤：

[0013] 步骤1，利用捕食搜索策略在所有的Web服务中求得一条可行服务链，该可行服务链满足用户Web服务组合的要求；

[0014] 步骤2，可行服务链的长度为m，搜索可行服务链上每个Web服务对应的候选服务，即将与可行服务链上各Web服务具有相同输入集合和输出集合的Web服务放入同一个服务类中，得到m个候选服务类；

[0015] 步骤3，在候选服务类中，使用具有混沌性质的余切序列依次从各候选服务类中选择一个候选服务，形成一个Web服务组合，该Web服务组合映射为一个粒子，重复上述过程n次，得到n个粒子；对每个粒子的速度和位置进行初始化；

[0016] 步骤4，利用适应度函数评价n个Web服务组合，将适应度函数值最大的Web服务组合作为最优Web服务组合，并判断对应的适应度函数值是否达到理论最优，如果是，则将该最优Web服务组合作为局部最优Web服务组合，否则，执行步骤5；当找到最终的局部最优Web服务组合或更新次数达到上限，则停止，并输出停止时的局部最优Web服务组合；

[0017] 步骤5，利用混沌扰乱更新n个Web服务组合，使得这n个Web服务组合向本身历史最优Web服务组合和当前局部最优Web服务组合学习，更新完成后，返回执行步骤4；

[0018] 步骤6，重复步骤1-步骤5，直至找到全局最优Web服务组合或捕食搜索次数达到上限；搜索结束后，对全局最优Web服务组合进行逻辑结构优化，得到优化后的全局最优Web服务组合；

[0019] 所述对全局最优Web服务组合进行逻辑结构优化，得到优化后的全局最优Web服务组合的具体过程为：

[0020] 步骤61、根据全局最优Web服务组合的长度m，随机生成一个整数x，0≤x≤m-1；

[0021] 步骤62、取全局最优Web服务组合中下标为x的候选服务Sx，根据候选服务Sx的输入集合和输出集合，利用步骤1-步骤5进行求解，是否有与候选服务Sx等效的服务链；

[0022] 步骤63、若有等效的服务链，则将等效的服务链替换候选服务Sx，并判断替换后的全局最优Web服务组合的适应度函数值是否优于替换前，若是则替换，否则不替换；

[0023] 步骤64、重复步骤61-步骤63，生成不同的随机数，且替换次数小于等于 得到优化后的全局最优Web服务组合。

[0024] 作为本发明的一种优选方案，所述步骤1的具体过程为：

[0025] 步骤11，设置searchSet集合为空，搜索所有的Web服务，将满足用户Web服务组合要求的Web服务加入服务链，同时将该Web服务的输入集合存放于searchSet集合中；

[0026] 步骤12，在将满足用户Web服务组合要求的Web服务加入服务链之前，判断searchSet集合中是否已有该Web服务的输入集合，若没有，则将该Web服务加入服务链，否则，不加入；

[0027] 步骤13，当前搜索结束后，若没有得到可行服务链，则将searchSet集合清空，在没有被搜索过的Web服务中重复步骤11-步骤12，直到找到一条可行服务链或到达最大搜索次数，停止搜索。

[0028] 作为本发明的一种优选方案，所述步骤3的具体过程为：

[0029] 步骤31，可行服务链的长度为m，j＝0,…,m-1，第j个Web服务有kj个候选服务；

[0030] 步骤32，确定kj的数量级 根据与第j个Web服务对应的余切序列值截取余切序列值小数点后φj位作为整数值ui,j， i＝0,…,n-1，n为粒子
总数；

[0031] 步骤33，将ui,j对kj取余，产生混沌值ξi,j，混沌值与第j个Web服务对应的候选服务类中的一个候选服务对应，将所对应的候选服务在粒子中位置设为1，其他设为0，粒子的位置Xi初始化完成；同时，粒子的速度Vi及粒子本身历史最佳位置Pi的初始化均等于Xi。

[0032] 作为本发明的一种优选方案，步骤4所述适应度函数值的计算公式为：

[0033]

[0034] 其中，j＝0,…,m-1，tj、cj、rj、aj分别表示当前计算的Web服务组合中第j个候选服务的响应时间、执行成本、可靠性、可用性，α+β+γ+η＝1，α、β、γ、η分别表示各个属性权重，T_Max、C_Max分别表示所有候选服务中响应时间最大的值、执行成本最大的值，F表示当前计算的Web服务组合的适应度函数值。

[0035] 本发明采用以上技术方案与现有技术相比，具有以下技术效果：

[0036] 1、Web服务组合优化问题是复杂的NP-Hard问题，时间复杂度为多项式时间的问题，随着问题规模的扩大，会导致组合爆炸，完全遍历所有的组合方案是不现实的。本发明利用Web服务的特点对Web服务进行分类，将具有相同的输入和输出的服务分在同一个类中，从而减少组合降低，使得完全枚举所有组合方案成为可能。

[0037] 2、本发明引入具有混沌性质的余切序列方法，在粒子群初始化阶段，使用余切序列初始化粒子的位置，利用余切序列的遍历性、规律性、伪随机性的特点，弥补了PSO算法的随机搜索策略，使得算法整体搜索效率提高；在混沌扰乱阶段，使用一套全新的扰乱规则，对粒子的速度和位置进行充分的扰乱，使得算法具有良好的全局搜索能力。

[0038] 3、本发明采用捕食搜索策略，平衡了局域搜索和全局搜索，使得改进后的算法具有良好的搜索能力和适应性，有效的解决了粒子的早熟问题，并且在最后进行逻辑优化，保证了最终Web服务组合方案的多样性。

附图说明

[0039] 图1是Web服务组合方案寻优模拟图。

[0040] 图2是陷入局部最优示意图。

[0041] 图3是扰乱产品组合方案示意图。

[0042] 图4是Web服务组合逻辑结构图。

[0043] 图5是服务链和候选服务。

[0044] 图6是服务链替换服务图，图6(b)的服务链可以替换图6(a)服务链中的服务S2。

[0045] 图7是本发明一种面向Web服务组合的优化方法的流程图。

具体实施方式

[0046] 下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

[0047] 本发明是在Web服务组合的环境下，实现在控制满足用户服务需求的前提下，保证Web服务组合的QoS服务质量达到最优，并且进一步提高了Web服务组合的效率，以及提高了Web服务组合的多样性。采用智能优化算法求解Web服务组合优化问题是目前的主流思路。粒子群优化算法(Particle Swarm Optimization，PSO)，是一个以群为基础的随机搜索算法，通过群体智慧搜索出最优的位置，因其参数少，具有收敛速度快，建模简单，且易于实现等优点。对PSO算法的改进方案主要有两种思路：一种是对粒子群算法本身进行性能优化，如动态调整搜索步长、优化粒子更新策略等，另一种是将粒子群算法和其他智能优化算法(如遗传算法、蚁群算法、模拟退火算法等)进行融合以改进性能表现。本发明针对Web服务组合优化问题，对PSO算法进行改进，通过引入捕食搜索策略来调节全局搜索和局部搜索，以及在粒子群的初始化和更新中引入混沌理论，提出了一种面向Web服务的优化方法。

[0048] 如图1所示，在X0,X1,…,Xi,…,Xn-1中，每一个向量均表示一种Web服务组合方案，将所有Web服务组合方案进行比较，选出全局最优的Web服务组合方案。假设Web服务组合方案Xi距离最优Web服务组合方案最近，所以设Xi为当前全局最优Web服务组合方案，并且设该全局最优Web服务组合方案为Xg。每个Web服务组合方案在寻优过程中，均会保留自己历史最优Web服务组合方案即Xip。通过不断更新，使得当前Web服务组合方案向历史最优Web服务组合方案和全局最优Web服务组合方案学习，更新公式如式(1)和式(2)所示。

[0049] Vi(t+1)＝w·Vi(t)+c1·r1·(Xip-Xi)+c2·r2·(Xg-Xi)   (1)

[0050] Xi(t+1)＝Xi+Vi(t+1)   (2)

[0051] 上述寻优模型考虑的是只有一个全局最优Web服务组合方案的情况，通常情况下的优化问题均为多峰值的优化问题，即有多个极值和多个最优值。所以传统的组合优化算法在求解多峰值的优化问题时，由于收敛速度快，在计算过程中容易陷入局部最优，导致群体早熟。陷入局部最优情况如图2所示，图中有两个全局最优Web服务组合方案，两个局部最优Web服务组合方案。当前Web服务组合方案Xi距离局部最优Web服务组合方案A最近，然后所有的Web服务组合方案均向Xi靠近，陷入了局部最优Web服务组合方案。即更新前Web服务组合方案的状态，所有Web服务组合方案向局部最优Web服务组合方案A靠近。

[0052] 本发明采用余切扰乱，对Web服务组合方案的更新做了改进，即余切扰乱使得Web服务组合方案在寻优过程中充分扰乱Web服务组合方案的位置和动向，从而极大的降低了陷入局部最优值的概率；如图3所示，是Web服务组合方案更新后的状态，更新后充分扰乱了Web服务组合方案的位置和动向，破坏了Web服务组合方案陷入局部最优。对于为多峰值的优化问题，本发明可以搜索到尽可能多的全局最优Web服务组合方案，保证了组合方案的多样性。

[0053] 为了方便理解本发明的技术方案，下面定义一些概念：

[0054] 定义1混沌搜索方法是由确定方程得到具有伪随机性、遍历性和规律性等特点的随机运动状态点。

[0055] 本发明中采用的是具有混沌性质的余切公式作为混沌搜索方法，其公式如式(3)所示：

[0056] an+1＝cot(an)   (3)

[0057] 式(3)中的an是余切序列的一次取值，当给余切序列一个初值时，需要满足a0∈(0,π)，将初值通过余切序列公式迭代，可以产生一个伪随机序列。“余切公式”是蝴蝶效应的一个典型例子。例如，取三个余切初值分别为1、1.0001、1.00001，使用余切公式分别将初值迭代，三个数列每一项都是前一项的余切，当计算到第10项后，三个数列开始形成巨大的分歧。这就是混沌的数列，经过足够多项后，得到的数字是随机的、混沌的、遍历的。

[0058] 定义2服务类(Wj)Wj是具有相同服务功能的集合，具有相同的输入集合和输出结合的服务归类为同一个服务类，表示为W＝{W0,W1,…,Wm-1}，其中Wj表示第j类服务。

[0059] 定义3候选服务 是构成服务组合的基本逻辑单元，第j个服务类的候选服务为 其服务类Wj对应的输入集合为 输
出集合为

[0060] 每一个候选服务包含一个QoS向量 该向量包含4个参数：

[0061] ①服务执行时间(Response Time，t)：服务的执行时间t等于请求发送的时间点到结果被收到的时间点之间这段时间。

[0062] ②执行成本(Execution Cost，c)：服务的执行费用c是指作为服务使用者请求执行该服务要付出的费用。

[0063] ③可靠性(Reliability，r)：服务的可靠性r是一个请求在最大期望时间内被正确响应的概率，其表达式为：

[0064] r＝Ns/Nt   (4)

[0065] 式中Ns表示服务在观察时间内被成功调用的次数，Nt表示在观察时间内调用服务的总次数。

[0066] ④可用性(Availability，a)：服务的可用性是服务可使用的概率，其计算公式为：

[0067] a＝Tλ/λ   (5)

[0068] 式中λ是根据服务的类型设置的常量，Tλ是服务在时间λ内可用的时间。

[0069] 定义4服务组合(Wc)根据定义2和3可定义，服务组合是由来自不同服务类的候选服务组成，描述为Wc＝{0,1,…,0,…,1}；其中，

[0070] 定义5服务链(Sc)将服务组合中值为1服务选出，并根据其输入输出逻辑，按照逻辑顺序组合成顺序有向图，即为服务链，如图4所示。

[0071] 本发明面向的Web服务组合的优化模型如下：

[0072] (1)假设服务共有m个服务类，即W＝{W0,W1,…,Wm-1}；

[0073] (2)每个服务类中有若干个候选服务组成，即 其中kj表示第j个服务类中共有kj个候选服务；

[0074] (3)每个服务均有描述其质量的属性参数；

[0075] (4)假设有服务链Sc＝s0→s1→...→sj→...→sm-1(sj属于服务类wj)；

[0076] (5)服务组合尽可能的提高服务质量。

[0077]

[0078] 其中α、β、γ和η，分别表示各个QoS属性权重，R、T、C和A分别表示服务链的各个QoS属性的积或和，其中R和A分别为可靠性和可用性，多个服务组合起来的总的可靠性为各个服务的可靠性的乘积，同理可得可用性；而T和C分别表示执行时间和执行成本，多个服务的执行总时间为多个服务的时间之和，同理可得执行总成本。sj表示服务链上的某一服务，getInput()和getOutput()函数是获取对应服务的输入集合和输出集合。

[0079] 根据以上定义，本发明分为三个步骤：首先，全局搜索一条可行的服务链，并找到服务链上的各个服务的候选服务；其次，通过余切序列混沌初始化粒子；最后，计算各个粒子的适应度函数值，评价各个粒子的优劣，选择最优的粒子作为被学习的对象，以及更新其它粒子。

[0080] 首先，采用捕食搜索策略在全局求得一条可行的服务链，所有的Web服务数据存放在txt文件中，每一行对应一个Web服务，一行由四个部分组成，部分与部分之间均空格分开。例如：天气服务USWeather City,Date WeatherInfo500,10.1,97,73；第一个部分表示服务的名字；第二部分表示服务的输入集合，若有多个服务参数则以逗号分开；第三部分表示输出集合，同样以逗号分开；第四部分表示QoS属性值，依次为响应时间、执行成本、可用性和可靠性。

[0081] 在搜索服务链的过程中，为了保证服务链中没无效的服务(即对最终输出结果没有影响的服务)，增加了一个搜索集合，下面伪代码中用变量searchSet表示。在一次搜索过程中将服务链上Web服务的输入集合存放于该变量中，在Web服务加入到服务链上之前，需要判断searchSet中是否已有该Web服务输入集合，若不存在，且满足要求，则该Web服务可加入服务链中，否则，不可以；当该次搜索结束后，没有搜索到可行服务链，则将搜索集合清空，在没有被搜索过的Web服务中搜索，直到找到一条可行的服务链，或者经过最大搜索次数，停止搜索。

[0082] 定义6混沌初始化即通过余切序列产生的为随机序列值作为粒子位置的初始值。

[0083] 经过捕食搜索在全局已经搜索得到一条可行的服务链，在混沌初始化前，首先对混沌初始化中所需的参数进行说明：

[0084] (1)根据捕食搜索策略搜索一条全局可行的服务链，假设服务链是由m个服务组成的。

[0085] (2)根据服务链上的服务，找到服务链的候选服务，服务链上每一个服务均对应一类候选服务，令每一种类分别为Wj＝{wj,0,wj,1,…}(j＝0,1,…,m-1)，服务链和与之对应的候选服务如图5所示。

[0086] (3)将具有相同功能的Web服务分为一类(本发明将具有相同的输入集合和输出集合归为同一类)；通过分类，使组合数降低，这样完全枚举所有组合方案成为可能。

[0087] (4)假设每一候选服务项目的个数为kj(j＝0,1,…,m-1)，所以

[0088] (5)根据(1)和(2)两点假设得粒子的位置Xi＝(W0,W1,…,Wm-1)，粒子的维数为[0089] Web服务组合优化问题具有不确定性，这里的不确定性主要是指评估组合方案优劣的最优适度函数值提前是不知道的，所以只能尽可能的找到更优解；以及不同服务链上的不同服务对应的候选服务数量也是不确定的，对应不同的服务链，初始化所需的余切序列会有所不同，所以本文提出一种动态的余切序列方法来初始化粒子。

[0090] 采用余切序列，本发明设计一种动态的混沌序列，主要步骤如下：

[0091] (1)假设服务链上的Web服务种类为m，每种服务对应的候选服务的个数为kj；

[0092] (2)m个0～π之间的随机double类型的数值，作为序列的初始值

[0093] (3)代公式an+1＝cot(an)依次计算出后面的余切序列值；

[0094] (4)类服务的候选服务的数量级来决定截取余切序列小数点后几位；例如第j类服务类有60个则取小数点后两位，使用截取的数对60求余，生成0～59之间的数，与该类的某一个候选服务对应。

[0095] 定义7适应度函数值即适应度函数的值，该值是量化指标，用来评价Web服务组合方案的优劣程度。

[0096] 本发明服务组合包含4个QoS参数，即可靠性、响应时间、执行成本和可用性。其中可靠性和可用性是一个概率，其值在0-1之间，所以需要规一化的参数为响应时间和执行成本，本文采用的策略为：选择所有候选服务中响应时间最大的值和执行成本最大的值，假设为R_Max和C_Max，则归一化公式为：

[0097]

[0098] 其中α+β+γ+η＝1，分别表示各个QoS属性权重。

[0099] 本发明是基于Web Service场景，若将本发明的方法应用于其他有序组合优化场景中，将适应度函数修改为具体场景的评价粒子优劣的指标即可。

[0100] 定义8混沌扰乱即Web服务组合方案在更新过程中引入余切扰乱方法，充分扰乱Web服务组合方案，尽可能遍历搜索空间。

[0101] 设式(1)中的Xip-Xi＝Vip和Xg-Xi＝Vig，则速度更新公式如式(8)所示：

[0102] Vi(t+1)＝w·Vi(t)+c1·r1·Vip+c2·r2·Vig   (8)

[0103] 其中，Vip＝(vi,0p,vi,1p,…,vi,hp,…)，Vig＝(vi,0g,vi,1g,…,vi,hg,…)，且vi,jp和vi,jg对应的规则如式(9)和式(10)所示。

[0104]

[0105]

[0106] 式(9)和式(10)中的random(1)表示随机产生一个0或1的随机数，即当前Web服务p组合方案Xi的第j维变量值等于该方案的历史最佳Web服务组合方案Xi的第j维变量值，则vi,jp的值为0或1的随机数，否则为0。

[0107] 定义9逻辑优化即基于求得的最终服务链，考虑是否可以使用服务链替换最终服务链上的某一服务，如果替换后的新的服务链的服务质量更高，则替换，否则，不替换。

[0108] 通过本发明的方法求得全局最优服务链，为了进一步提高组合方案的多样性，本文将得到的最优服务链进行逻辑结构优化。考虑到一个服务可以由一条服务链替代，所以可能存在以下这种情况：假设算法求得的最优服务链如图6的(a)所示，其中，服务S2可以由服务S4和S5组成的服务链替代，如图6的(b)所示。所有通过这种逻辑优化可以搜索到更多符合要求的服务链，可以进一步提高组合方案的多样性。

[0109] 本发明以Web服务组合为例，其服务质量确定问题中的质量包括服务执行的时间、执行成本、可靠性和可用性。本发明的Web服务组合方案生产流程图如图7所示。其具体操作步骤如下：

[0110] 步骤1：首先引入捕食搜索策略，采用捕食搜索策略在全局求得一个可行的服务链，即搜索一条满足用户Web服务组合要求的服务链。其具体描述如下：

[0111] ①在一次搜索过程中将服务链上Web服务的输入集合存放于searchSet集合变量中；

[0112] ②在Web服务加入到服务链上之前，需要判断searchSet集合中是否已有该Web服务输入集合，若不存在，且满足要求，则该Web服务可加入服务链中，否则，不可以；

[0113] ③当该次搜索结束后，没有搜索到可行服务链，则将搜索集合清空，在没有被搜索过的Web服务中搜索，直到找到一条可行的服务链，或者经过最大搜索次数，停止搜索。

[0114] 步骤2：假设该服务链的长度为m，搜索步骤1中的可行服务链上的每个服务对应的候选服务，即将具有相同的输入集合和输出集合的Web服务放入同一个服务类中，从而使组合数降低，提高搜索效率，根据服务链长度可得m个候选服务类，即W＝{W0,W1,…,Wm-1}。

[0115] 步骤3：然后在粒子群初始化中，引入混沌搜索方法替代随机初始化，在候选服务中使用混沌序列依次从各个候选服务中取一个候选服务，形成一个可行的服务链，每个服务链对应一个粒子，多次执行初始化操作生成多个粒子；服务链上的每个服务有kj个候选服务，这里假设是给第i个粒子进行初始化。其具体步骤如下：

[0116] ①首先确定kj的数量级 根据与服务对应的余切序列值 截取小数点后φj位作为整数值u0,j，其范围为 (不包括 )；

[0117] ②然后将u0,j对kj取余，产生0～kj(不包括kj)之间的混沌值，这里将该混沌值设为ξ0,j，该值与该服务对应的候选服务中的某一个服务对应，则所对应的候选服务在粒子位置中设为1，其他的设为0。同样，服务链上的所有服务均执行该操作后，则第i个粒子的位置Xi初始化完成。

[0118] 假设共有n个粒子，则需要上述过程共n次，可以得到一个n×m的余切序列矩阵C，如式(11)所示，通过余切序列矩阵通过截取并取余数操作得到与粒子一一对应的矩阵。其具体步骤如下：

[0119] ①迭代n次，即生成一个n×m的余切序列矩阵，如式(11)所示：

[0120]

[0121] ②将余切序列矩阵根据对应候选服务数量的数量级φj确定截取小数点后几位数，并将截取后的值对kj取余，得到混沌矩阵Φ，如式(12)所示。

[0122]

[0123] 初始化中，粒子的速度Vi以及粒子本身历史最佳位置Pi的初始化均等于Xi，如式(13)所示。

[0124] Xi＝Vi＝Pi(i＝0,1,…,n-1)   (13)

[0125] 步骤4：根据具有个性化的适应度函数来评价这n个Web服务组合方案，找到这n个Web服务组合方案中的最优的Web服务组合方案，并判断对应的适应度函数值是否达到理论最优。如果是，则该Web服务组合方案即为全局最优Web服务组合方案；否则，执行步骤5。当找到最终的最优Web服务组合方案或者迭代次数达到上限，则停止，输出停止时的最优的Web服务组合方案，即为全局最优Web服务组合方案。其具体描述如下：

[0126] ①遍历n个Web服务组合方案，分别计算出各个Web服务组合方案的适应度函数值，存放于数组F[n]中。

[0127] ②遍历数组F[n]，将最大值赋值给全局最优适度值F_Best，最大值对应的下标赋值给index。

[0128] ③判断F[index]是否达到理论最优值F_Theory(该值表示在相应的目标成本下，Web服务组合的服务质量可达到的理论最优适度值)，如果达到理论最优，则Xindex＝(W0(index),W1(index),…,Wm-1(index))为最佳Web服务组合方案。否则，Count++(Count值表示迭代了多少次，初值为0)，并且判断Count是否达到最大迭代次数Iteration，如果是，输出Xindex，结束搜索；否则执行步骤5。

[0129] 步骤5：用混沌扰乱规则更新n个Web服务组合方案，使得这n个Web服务组合方案向本身历史最优Web服务组合方案和全局最优Web服务组合方案学习。更新完成后，返回执行步骤4。其具体步骤如下：

[0130] ①更新Web服务组合方案的动向，其对应的更新规则如式(14)所示。

[0131]

[0132] 式(14)中表示当且仅当vi,h(t)＝＝vi,hp＝＝vhg时，vi,h更新后保持不变，否则令vi,h(t+1)＝-1。

[0133] ②更新Web服务组合方案，其对应的更新规则如式(15)所示。

[0134]

[0135] 式(15)中，C(xi,h)是余切扰乱函数，当更新后的速度vi,h(t+1)＝＝0或者vi,h(t+1)＝＝-1(当vi,h(t)≠vi,hp≠vhg)，即当更新后某一维上的速度为0或者速度为-1且vi,h(t),vi,hp,vhg三个速度值都不同，则会触发调用该函数，充分扰乱粒子的位置。其中xi,h中的i表示第i个粒子，h表示的是粒子位置的第h维对应的值。

[0136] 下面举个例子来说明余切扰乱函数的具体操作步骤，假设更新前vi,h(t+1)＝＝0，则触发余切扰乱函数，所以需要对位置xi,h进行余切扰乱：

[0137] 首先，根据粒子变量的h可以计算出xi,h属于哪一类候选服务，通过下面的规则为：这就表示xi,h是属于第e类候选服务中对应的变量。找到位置xi,h对应
的余切序列值 通过余切公式an+1＝cot(an)迭代一次得到新的余切序列值 该值对应服务链上的第e+1个的候选服务类，即

[0138] 然后，将更新后的余切序列值 通过 截取得到ui,e(1)，与ke取余得到更新后的混沌值ξi,e(1)。

[0139] 最后，确定xi,h是属于第e类候选服务中的哪一维，通过 来确定，所以xi,h对应第e类候选服务下标为p的那个服务，即we,p；而更新后的混沌值ξi,e(1)对应着第e类候选服务下标为ξi,e(1)的那个服务。如果更新后混沌值ξi,e(1)和当前下标p相同时，且xi,h＝＝0，则余切扰乱规则就是将xi,h直接赋值为1，为了保证每个类别中只选择一个服务，所以(1)
再将第e类中其他变量全设为0；同样的，当满足条件p！＝ξi,e &&xi,h＝＝0&&xi,z＝＝1时，直接将xi,h赋值为1，且令xi,z＝0(其中 )。当满足条件p＝＝ξi,e(1)&&xi,h＝＝1时，将xi,h赋值为0，并且重新通过更新后的余切序列值 初始化一个位置，令xi,d＝1，其中 同样的，当满足条件p！＝ξi,e(1)&&xi,h＝＝1时，直接将xi,h赋值为0，且
令xi,z＝1。其扰乱规则公式如式(16)所示。

[0140]

[0141] 步骤6：通过粒子群的求得基于当前服务链的全局最优解，或者达到最大迭代次数，则通过捕食搜索策略在全局重新求得一个不同的可行的服务链，在这服务链的基础上再次执行粒子群求解，直到找到全局最优解，或者达到最大捕食搜索次数后，结束搜索，当前最优解，对应的服务链为当前最优服务链。

[0142] 步骤7：考虑到一个服务可以由一条服务链替代，即一条服务链替换当前搜索到的最优服务链中的一个服务，对步骤6中求得的当前最优服务链进行逻辑优化，搜索到更多符合要求的服务链，进一步提高组合方案的多样性。其具体步骤如下：

[0143] ①步骤6中求得当前最优服务链后，根据服务链的长度，假设为m,随机产生一个0～m-1的整数，假设为x。

[0144] ②取最优服务链上的下标为x的服务Sx，根据服务Sx的输入集合和输出集合，使用本发明方法进行求解，是否有与服务Sx等效的服务链。

[0145] ③若有等效服务链，则判断替换后的服务链的服务质量是否优于替换前的，若服务质量大于等于替换前的，则替换，否则不替换。

[0146] ④多次替换，为了提高算法效率，生成不同的随机数，且执行替换的次数小于等于[0147] 以上实施例仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明保护范围之内。