基于离散群搜索和QoS感知的第三方IT服务选择方法

摘要

本发明涉及一种基于离散群搜索和QoS感知的第三方IT服务选择方法，包括以下步骤：生成初始种群作为当前种群，初始种群的每个个体对应一个第三方IT服务组合实例；建立cost函数，对当前种群中的每个实例进行评估；根据评估结果将当前种群中的个体划分为捕食者、追随者和巡视者；建立min‑cost函数，捕食者、追随者和巡视者分别基于min‑cost函数执行迭代操作，生成新种群；以cost函数对新种群中的每个实例进行评估，获得cost函数值最小的实例，判断迭代是否结束，若是，则获得最优解，若否则重复执行迭代步骤。与现有技术相比，本发明具有有效提高第三方IT服务组合的寻优效率、可快速获得最优一站式第三方IT服务等优点。

说明书

技术领域

本发明涉及一种服务选择技术，尤其是涉及一种基于离散群搜索和QoS感知的第三方IT服务选择方法。

背景技术

自工信部出台《信息化和工业化深度融合专项行动计划(2014-2019年)》以来，各个重点行业对信息化的关注度不断提高，数据中心IT基础设施已成为各项信息化应用的支撑核心。由于IT基础设施的复杂性、品牌多样性导致用户对数据中心IT基础设施服务需求快速增长。相较于原厂商，第三方IT服务商具有多品牌服务能力，能够根据客户需求提供一体化综合服务解决方案。客户对第三方IT服务的需求日益增加，随之出现了众多具有不同服务质量(QoS)的第三方IT服务商。在第三方IT服务的研究中，服务选择的任务是：在客户提出的QoS限定条件下，从侯选的第三方IT服务商中选择合适的服务商，为客户提供符合其QoS限定条件的高效优质的一站式第三方IT服务。这是一个极具现实意义的研究课题。QoS属性用于描述第三方IT服务非功能性的特性，例如服务的成本、响应时间、可用性等，对于客户合理评估服务的质量至关重要。基于QoS属性的质量评判分别有成本标准和收益标准两类原则。成本标准相关的QoS属性的值与对应的服务质量成反比，即服务质量随属性值降低而升高。收益标准相关的QoS属性的值与对应的服务质量成正比，即服务质量随属性值升高而升高。在评估第三方IT服务商的服务质量时，两类标准的QoS属性需要统一考虑。在满足客户提出的QoS限定条件下，综合考虑两类标准的QoS属性，如何提高精确寻觅到最优一站式第三方IT服务的效率，成为一项富有挑战性的工作。

目前基于QoS的服务选择方法主要有基于QoS语义的方法和基于QoS属性值进行计算的方法。客户为了获取优质服务，往往会为第三方IT服务的QoS属性设置期许的限制条件。由于基于QoS属性值的计算方法较易满足客户对一站式第三方IT服务的全局限制条件，因此应用此类方法进行服务选择的技术方案较多。综观以往的研究成果，基于QoS属性值的计算方法主要有穷尽计算方法和遗传算法等。基于穷尽计算方法的寻优方案的计算量较大，可扩展性差。相较于穷尽法，基于遗传算法的寻优方案在计算量的减少方面有优势，例如2014年李倩、窦润亮等提出一种基于多种群遗传算法的面向QoS属性的服务选择方法，2016年MB Karimi等提出一种基于数据挖掘技术和遗传算法的QoS感知的全局服务寻优方法。但基于遗传算法的寻优方案收敛的效率均有待提高。

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种基于离散群搜索和QoS感知的第三方IT服务选择方法。

本发明的目的可以通过以下技术方案来实现：

一种基于离散群搜索和QoS感知的第三方IT服务选择方法，包括以下步骤：

1)生成初始种群作为当前种群，所述初始种群的每个个体对应一个第三方IT服务组合实例；

2)建立cost函数，以所述cost函数对当前种群中的每个实例进行评估；

3)根据评估结果将所述当前种群中的个体划分为捕食者、追随者和巡视者；

4)建立min-cost函数，所述捕食者、追随者和巡视者分别基于所述min-cost函数执行迭代操作，生成新种群；

5)以所述cost函数对所述新种群中的每个实例进行评估，获得cost函数值最小的实例，判断迭代是否结束，若是，则执行步骤7)，若否，则执行步骤6；

6)将步骤4)获得的新种群作为当前种群，返回步骤3)；

7)以cost函数值最小的实例作为最优解。

所述cost函数为：

其中，F为某一实例X_j的cost函数，为X_j的第i个全局QoS属性，为对应的QoS属性限制，为权重，k为全局QoS属性的数量，为效用函数。

所述效用函数的表达式为：

所述步骤3)具体为：

将当前种群中cost函数值最小的实例设定为捕食者，将除捕食者外的实例按比例划分为追随者和巡视者，所述追随者分布于捕食者周围，所述巡视者随机分而于捕食者和追随者周围。

所述比例为8：2。

所述步骤4)中，min-cost函数定义为：设在n维空间上，一个实数坐标P的四周有2ⁿ个整数坐标，存在g个由正整数组成的坐标，取该g个坐标对应的实例的cost函数最小值，表达式为：

F_min-cost(P)＝min(F(X₁),F(X₂),...,F(X_g))

其中，X₁、X₂、…、X_g为g个坐标对应的实例。

所述步骤4)中，捕食者的迭代操作为：

捕食者应用min-cost函数从当前位置分别选取n维空间上正前方、左方、右方三个方向的随机位置作为候选位置，应用cost函数评估所述候选位置对应的三个实例，选取cost函数值最小的实例作为最终候选位置，若该最终候选位置对应实例的cost函数值小于捕食者的cost函数值，则捕食者迁移至最终候选位置，否则捕食者停留在原位置。

所述捕食者应用min-cost函数从当前位置分别选取n维空间上正前方、左方、右方三个方向的随机位置作为候选位置时，所选取的候选位置满足以下条件：

其中，为捕食者在第h次迭代时的位置，X_sub-z为捕食者在第h次迭代后所选取的正前方候选位置，X_sub-r为捕食者在第h次迭代后所选取的右方候选位置，X_sub-l为捕食者在第h次迭代后所选取的左方候选位置，r₁∈R¹为一个满足均值为0及方差为1条件的正态分布随机数，r₂∈R^n-1是在(0,1)范围内的随机数序列，θ_max为设定的最大转角，l_max为个体最大搜索长度，φ^h为第h次迭代时的搜索角度，表示笛卡尔坐标变换函数。

所述步骤4)中，追随者的迭代操作为：

追随者以随机步长向捕食者位置靠近，满足如迭代更新公式：

其中，为捕食者在第h次迭代时的位置，为某一追随者在第h和h+1次迭代时的位置，r₃∈Rⁿ为一个在0到1之间分布均匀的随机数序列，符号表示各分量对应相乘。

所述巡视者的迭代操作为：

巡视者从当前位置以随机步长朝随机方向迁移到新位置，满足如下迭代更新公式：

l_i＝a·r₁l_max

其中，为捕食者在第h次迭代时的位置，为某一巡视者在第h和h+1次迭代时的位置，r₁∈R¹为一个满足均值为0及方差为1条件的正态分布随机数，l_max为个体最大搜索长度，φ^h+1为第h+1次迭代时的搜索角度，表示笛卡尔坐标变换函数。

与现有技术相比，本发明具有以下有益效果：

(1)基于改进的离散群搜索服务模型ID-GSS(improved discrete group searchservice)的计算方法，有效提高了第三方IT服务组合的寻优效率，为用户快速寻觅到满足多QoS属性限制的最优一站式第三方IT服务。

(2)本发明定义了min-cost函数，改进的离散群搜索服务模型ID-GSS基于min-cost函数创建，有效辅助捕食者、追随者、巡视者在每次迭代中快速寻觅到各自的近似最优解，提高寻优效率。

(3)本发明追随者和巡视者的寻优迭代过程中采用随机步长，搜寻方向是随机生成的，避免陷入局部最优化，有效提高了寻优精度。

附图说明

图1为本发明的流程示意图；

图2为一个二维空间初始种群分布的例子；

图3为了n＝10时ID-GSS模型和D-GSS模型的收敛性能比较示意图。

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。本实施例以本发明技术方案为前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。

本发明提供一种基于离散群搜索和QoS感知的第三方IT服务选择方法，该方法是基于改进的离散群搜索服务模型ID-GSS(improved discrete group search service)的计算方法，以提高第三方IT服务组合的寻优效率，为用户快速寻觅到满足多QoS属性限制的最优一站式第三方IT服务。离散群搜索服务模型D-GSS(discrete group search service)是基于捕食者-追随者-巡视者模型创建的，该模型模拟了狮子群体搜索及捕猎行为，在收敛性能方面优于遗传算法。而本发明的改进的离散群搜索服务模型ID-GSS是基于min-cost函数创建的，min-cost函数可辅助捕食者、追随者、巡视者在每次迭代中快速寻觅到各自的近似最优解。由于min-cost函数的引入，ID-GSS模型在收敛效率方面优于D-GSS模型。在该发明中，整个实现过程都是由计算机自动完成的，用户只要输入关于第三方IT服务组合所有全局QoS属性的限制值，就可让计算机自动分析，最终获得最优一站式第三方IT服务。

如图1所示，本发明方法的具体技术方案如下：

步骤1，建立效用函数、cost函数、min-cost函数。

效用函数制定了成本标准或收益标准QoS属性一致性的方法，并将第三方IT服务的全局QoS属性与相应限制要求相结合考虑。

定义1效用函数：设第三方IT服务组合实例X_j拥有k个全局QoS属性，其中某个属性标记为qⁱ(1≤i≤k)，服务需求方对于该属性的限制为Qⁱ，表示实例X_j的第i个属性，表示对应的属性限制Qⁱ，而表示具有两个参数和的效用函数，具体如公式(1)所示：

cost函数的创建可用于评估第三方IT服务组合实例的质量，若cost函数值越小，则实例提供一站式第三方IT服务的质量越高。

定义2cost函数：设服务组合实例X_j的全局QoS属性表示为对应的QoS属性限制对应于实例X_j的属性qⁱ的权重标记为表示效用函数，则F(X_j)表示cost函数，为三个参数X_j、q_c、Q_c的关系，具体如公式(2)所示：

其中，

基于cost函数创建min-cost函数，以辅助捕食者、追随者、巡视者在每次迭代中快速寻觅到各自的近似最优解。

定义3min-cost函数：设在n维空间上，一个实数坐标P的四周有2ⁿ个整数坐标d₁,d₂,...,d_k(k＝2ⁿ)，其中存在g(1≤g≤n)个由正整数组成的坐标(注：坐标含0表示某类服务的原子服务不存在)，评估g个相应第三方IT服务组合实例的cost函数值，取其中的最小值，具体如公式(5)：

F_min-cost(P)＝min(F(X₁),F(X₂),...,F(X_g))(5)

其中，X₁、X₂、…、X_g∈Rⁿ，为g个坐标对应的实例。

步骤2，建立n维寻优空间。设第三方IT服务组合共有N类服务，每类服务有N_i(1≤i≤n)个候选的由第三方IT服务商提供的原子服务，每个原子服务有k个QoS属性，在此基础上可建立相应的n维空间。如此将多QoS属性限制下第三方IT服务组合实例中寻优问题转化为在多维搜索空间中寻找最优值的问题。第三方IT服务组合的N类服务与寻优空间的n维相对应，即寻优空间中的每维代表第三方IT服务组合中的一类原子服务。

寻优空间中每维上的坐标点和一类第三方IT服务中的候选原子服务一一对应。第i类服务有N_i个候选原子服务，第i维的坐标轴有相应的N_i个坐标点。每维坐标轴上的坐标点均衡分布，相邻坐标点的间距均为1。

设表示第i维第j个坐标点对应的原子服务，则原子服务相对应的cost函数值将处于升序状态，即：

步骤3，设定初始参数。

设种群第i位个体X_i的第h次迭代对应的实例所处位置的坐标标记为代表n维坐标组组中第y个坐标点代表第y类第三方IT服务中对应该实例的某个原子服务。个体X_i在第h+1次迭代时变迁到新的实例，该实例所处位置的坐标标记为该位置相应的坐标组为

本方法必须设置个体捕食的最大距离，即捕食者、追随者、巡视者在每轮迭代中迁移的最大距离必须事先限制好，以避免轻易步出事先设定的区域。个体迁移的最大距离设为l_max，其为各维第三方IT原子服务数集成而得，如公式(7)所示。

步骤4，选择一些第三方IT服务组合实例组成种群，这些实例的各全局QoS属性的效用函数值均小于等于1。计算种群个体对应实例的cost函数值，依据实例的cost函数值将为种群个体分别设定捕食者、追随者、巡视者的角色。

在n维寻优空间I中，第i位个体X_i用以下公式(8)表示。

其中第i位个体X_i在第k次迭代时于搜索空间所处的位置对应一个服务组合的实例。

种群中的个体在各自原先的位置上依据捕食者、追随者、巡视者的角色分别进行角度搜索，由此决定了下一次迭代中的迁移方向，可迁移到服务质量更高的新服务组合实例的位置。原先位置个体的顶角为即的位置相对于n-1多维方向的角度第i位个体X_i的搜索角度是n维向量是通过公式(9)-(11)将经过笛卡尔坐标变换而计算得到。

在种群对应的实例中寻找cost函数值最小者，设定该实例对应捕食者的角色，种群中除捕食者以外的实例中选择80％对应追随者的角色，分布在捕食者周围。最后剩余的实例对应巡视者的角色，随机分散在捕食者和追随者四周。

步骤5，种群个体分别从捕食者、追随者、巡视者的角度经过多次迭代不断迁移到新位置，这些位置在n维上的整数坐标与min-cost函数有关，每个位置均对应一个第三方IT服务组合的实例。捕食者、追随者、巡视者在迭代中的情况如步骤6、步骤7、步骤8所述。

步骤6，捕食者从当前位置分别查看n维空间上正前方、左方、右方三个方向的随机位置，每个位置均是捕食者在下轮迭代中变迁的候选位置。捕食者应用min-cost函数从当前位置分别选取n维空间上正前方、左方、右方三个方向的随机位置作为候选位置，应用cost函数评估所述候选位置对应的三个实例，选取cost函数值最小的实例作为最终候选位置，若该最终候选位置对应实例的cost函数值小于捕食者的cost函数值，则捕食者迁移至最终候选位置，否则捕食者停留在原位置。

捕食者应用min-cost函数从当前位置分别选取n维空间上正前方、左方、右方三个方向的随机位置作为候选位置时，所选取的候选位置满足以下条件：

其中，为捕食者在第h次迭代时的位置，X_sub-z为捕食者在第h次迭代后所选取的正前方候选位置，X_sub-r为捕食者在第h次迭代后所选取的右方候选位置，X_sub-l为捕食者在第h次迭代后所选取的左方候选位置，r₁∈R¹为一个满足均值为0及方差为1条件的正态分布随机数，r₂∈R^n-1是在(0,1)范围内的随机数序列，θ_max为设定的最大转角，l_max为个体最大搜索长度，φ^h为第h次迭代时的搜索角度，表示笛卡尔坐标变换函数。

捕食者需要更新其搜索角度，在第h+1次迭代中新的搜索角度如公式(15)所示。

φ^h+1＝φ^h+r₂α_max(15)

若捕食者在第h次迭代后又经过a次迭代后未找到更好实例，则捕食者的搜索角度重新回归到零度角，如公式(16)所示。

φ^h+a＝φ^h(16)

步骤7，追随者聚集在捕食者的周围。追随者会确定一个随机步长，然后以随机步长向捕食者位置靠近，每个追随者在下轮迭代中变迁的新位置为捕食者周围某个实例对应的位置。追随者的迭代操作为：

追随者以随机步长向捕食者位置靠近，满足如迭代更新公式：

其中，为捕食者在第h次迭代时的位置，为某一追随者在第h和h+1次迭代时的位置，r₃∈Rⁿ为一个在0到1之间分布均匀的随机数序列，符号表示各分量对应相乘。

步骤8，为避免局部最优化，巡视者将设定一个随机步长，搜寻的方向是随机生成的。巡视者将从当前位置以相应步长朝随机方向迁移到新位置。新位置将对应某个可能更接近最优实例min-cost函数值的任意实例。巡视者分散在捕食者和追随者周围游荡，具体行为如下：

1)应用公式(15)生成随意搜索角度。

2)应用公式(18)设定基于Gauss分布的随意步长。

l_i＝a·r₁l_max(18)

3)以所设角度及步长向新实例坐标位置变迁，满足如下迭代更新公式：

其中，为捕食者在第h次迭代时的位置，为某一巡视者在第h和h+1次迭代时的位置，r₁∈R¹为一个满足均值为0及方差为1条件的正态分布随机数，φ^h+1为第h+1次迭代时的搜索角度，表示笛卡尔坐标变换函数。

步骤9，若最优实例未寻觅到，选择cost函数值最小的实例对应捕食者的角色，剩余的实例按照8：2比例分别设为追随者和巡视者的角色。重复步骤6-步骤8。

步骤10，多次迭代后，收敛至第三方IT服务组合的最优实例为止。本方法在所有多QoS属性限制下的待选第三方IT服务组合实例中选择cost函数值最小的实例作为最优解，求得最优解的公式(20)如下所示：

其中X_j∈Rⁿ。

由图3的收敛性能比较示意图可知，本发明的ID-GSS计算方法的收敛速度优于D-GSS。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。