基于改进磷虾群算法的服务组合优化

廖水聪，孙 鹏，刘星辰，钟 贇

（1.空军工程大学信息与导航学院，西安 710077；2.93182部队，沈阳 110015；3.空军工程大学装备管理与无人机工程学院，西安 710051）

（∗通信作者电子邮箱lsc520802kgd@163.com）

0 引言

随着面向服务的架构（Service Oriented Architecture，SOA）技术的逐步应用，大量资源被虚拟化为服务。然而随着用户需求的日益复杂，单个服务难以满足用户实际需求，将性能单一的单个服务通过服务组合［1］的方式统一起来，构建复合服务以满足用户复杂需求，已成为当前研究的主流。随着服务数量的不断增加，实际中存在大量功能相同但非功能属性不同的服务，导致同一服务组合逻辑下存在大量满足要求的复合服务。为了评价复合服务的优劣，学者们引入了服务质量（Quality of Service，QoS）指标来衡量服务的非功能属性［2］，期望在满足用户功能需求的基础上，找到总体QoS 最佳的服务。这类问题称为服务组合优化问题。

随着抽象服务和候选服务数量的增多，可能的组合方案数呈爆炸性增长，服务组合优化问题已成为非确定性多项式（Non-deterministic Polynomial，NP）难问题，此时如果通过遍历的方式寻找最佳复合服务，时间代价将变得难以接受。智能优化算法因其可以在较短时间内找到全局最优或者近似全局最优解的特性，常被用于求解服务组合优化问题。学者们使用遗传算法［3-4］、蚁群算法［5-6］、粒子群优化（Particle Swarm Optimization，PSO）算法［7］、烟花算法［8］、人工蜂群（Artificial Bee Colony，ABC）算法［9-10］等各类智能优化算法来求解服务组合优化问题。然而此类算法由于自身寻优机理的原因，一方面存在易早熟，陷入局部最优解的问题；另一方面时间开销上仍有待优化。

Gandomi 等［11］在南极磷虾群生存运动行为的基础上，于2012 年提出了一种磷虾群（Krill Herd，KH）算法。KH 算法认为磷虾个体的运动位置受诱导活动、觅食活动和扩散活动影响，基于三种运动设计了全局搜索和局部搜索两种策略，两种策略并行工作，显著提升了算法寻优的效率。同时，该算法借鉴了遗传的思想，在磷虾运动位置更新后进行交叉操作，提高了算法跳出了局部最优解的能力。Gandomi 将KH 算法和其他智能优化算法进行对比，验证了KH 算法较好的寻优性能。目前KH 算法主要用于函数优化领域［12-15］，较少用于组合优化领域，仅有部分学者用于数据聚类［16］等方面，取得了一定的效果，但暂无人用于求解服务组合优化问题。考虑到KH 算法较好的寻优性能，本文将KH算法引入到服务组合优化领域。

尽管KH 算法能在迭代初期很快地找到优秀的可行解，但随着迭代次数的增加，诱导和觅食运动对磷虾个体吸引力趋同，算法局部搜索能力下降，也存在容易陷入局部最优解的问题。针对上述问题，学者们对KH 算法做了不同程度的改进：文献［12］中提出一种基于动态压力控制算子的KH 算法，用多个优秀个体代替传统最优个体来计算诱导运动，从而加速新磷虾个体的产生，提高了磷虾个体的局部探索能力；文献［13］中利用模拟退火算法和贪婪策略对KH 算法进行改进，模拟退火增加了种群的多样性，贪婪策略小概率接受模拟退火中适应度低的解，避免算法早熟收敛，增强了算法跳出局部最优解的能力；文献［14］中从改进扩散活动的角度出发，用和声搜索代替物理扩散过程，在大多数情况下取得了优于基本KH算法和其他优化算法的性能；文献［15］中提出了一种基于对立学习的自由搜索KH 算法，每个磷虾个体可以根据自己的感知和活动范围进行搜索，这种自由搜索策略使磷虾个体能有效跳出局部最优，提高了磷虾种群的多样性和探索能力。这些针对磷虾算法的不同改进均旨在提高算法搜索能力，以期找到质量更高的最优解，同时尽可能降低算法所需的时间开销，取得了一定的效果。

本文提出一种加入自适应交叉算子和随机扰动算子的KH（KH with adaptive crossover and random perturbation operator，PRKH）算法，在增加种群多样性的同时，一定程度上提高了算法的搜索能力。实验结果表明，本文提出的PRKH 算法在寻找最优复合服务方面优于基本KH 算法、PSO算法、ABC 算法和花朵授粉算法（Flower Pollination Algorithm，FPA）。

1 服务组合优化问题描述

服务组合优化的基本模型可以分为三层：任务层、抽象服务层和候选服务集。如图1 所示，服务组合优化过程可以描述为从任务层中选择任务T2，然后确定该任务对应的服务工作流程，即抽象服务层中的S1至Sn。最后对每一个抽象服务，从候选服务集中选择对应的具体服务si，j，在满足用户QoS 约束的基础上寻找QoS最优的复合服务。

图1 服务组合优化示意图Fig.1 Schematic diagram of service composition optimization

1.1 相关定义

定义1任务集合为S=[S1，S2，…，Sn]，n为抽象服务的数量。

定义2候选服务集中的具体服务定义为si，j，其中i≤n，j≤m，m是候选服务集中具体服务的数量。

定义3服务质量是一个4 元组Q=(t，c，ava，rel)，t是服务响应时间，c是服务调用一次的成本，ava是服务可用性，rel是服务可靠性。

定义4W=[ω1，ω2，ω3，ω4]是Q中各属性对应的权重，并满足。

定义5服务质量评价函数F=WT*Q。

1.2 QoS计算方法

通常认为QoS 由一些非功能属性组成，主要包括服务响应时间、服务执行费用、服务可靠性、服务可用性等属性［2］。复合服务QoS 可以由单个服务QoS 来表示，根据组合结构的不同，在顺序、并行、选择、循环结构下均有对应的计算公式。组合结构和计算公式如图2和表1所示。

图2 服务组合结构Fig.2 Service composition structures

表1 不同结构下复合服务QoS计算公式Tab.1 Calculation formulas of composite service QoS under different structures

表1 中，tj、cj、aj、rj分别表示第j个服务的响应时间、服务费用、可用性和可靠性；n为服务的个数，k为循环结构中具体服务的执行次数。

对于成本型属性，优化目标是越小越好；对于效益型属性，优化目标是越大越好。在计算复合服务QoS之前，有必要对QoS 值进行归一化处理，使得归一化后的服务的各个QoS属性值变换到［0，1］域，且实际意义上各QoS属性值均为越低越好，便于后期算法处理。归一化公式如下，其中：f为QoS属性值，maxf为磷虾群中最大适应度值，minf表示磷虾群中最小适应度值。

2 基于改进磷虾群算法的服务组合优化

2.1 标准KH算法

KH算法其运动方式可以归纳为诱导运动、觅食运动和随机扩散。定义磷虾个体的速度更新公式如下：

其中：Xi为第i只磷虾的位置；Ni、Fi、Di分别代表诱导运动、觅食运动和随机扩散。Ni的构造公式如下：

其中：Nmax表示最大诱导速度；αi代表诱导方向；ωn代表诱导权重；为上一次运动的诱导活动方向。诱导方向定义如下：

觅食运动主要由食物位置和先前关于食物位置的经验共同决定。觅食运动公式构造如下：

其中：Vfood是觅食速度；Bi是觅食方向；觅食惯性权重是上一次运动的觅食活动方向。觅食方向由食物对磷虾个体的吸引力和最佳磷虾个体对磷虾的吸引力共同组成，具体计算公式如下：

扩散运动可以理解为一种磷虾群体随机性勘探外界的行为，当群体逐渐聚集，整体趋于最优时，这种运动会越来越弱，具体构造公式如下：

其中：δ为随机单位方向矢量，范围是［-1，1］。

在磷虾个体速度更新公式的基础上，定义位置更新公式如下：

其中：Δt是位置更新步长，Ct是取值范围在［0，2］的步长限制因子，NV是变量的总数，UBj和LBj分别是第j个变量的上限和下限。

为提升算法的性能，Gandomi 在文献［11］中使用交叉算子对算法进行改进，取得了较好的效果。交叉算子公式如下：

其中：Xi，m表示第i只磷虾交叉前的位置；Xr，m表示与第r只磷虾进行了交叉后的磷虾位置，r是1 到N的随机数；Ri，m为第i只磷虾的一个随机数，用来判定是否需要交叉；Cr为第r只磷虾对应的交叉概率。

2.2 算法改进策略

2.2.1 自适应交叉算子

Gandomi 在文献［11］中已通过实验证明加入交叉算子能有效提高磷虾算法的性能。然而，不同大小的交叉概率会明显影响算法收敛情况和寻找最优解的能力：较大的交叉概率会帮助算法产生更高比例的新磷虾位置，在前期快速接近全局最优解，提高算法收敛速度，但较大的交叉概率在后期可能会导致磷虾种群难以稳定，算法难以收敛。因此确定一个合适的交叉概率对提升算法性能非常关键。

本文借鉴自适应的思想，采用文献［17］提出的自适应交叉算子，使交叉概率能随适应度自动改变，随迭代次数呈现出一种前高后低的态势。适应度值低于种群平均值的个体，保持较大的交叉概率，从而更快地产生新的磷虾位置，加速寻找全局最优解。个体适应度值高于种群平均值的个体，交叉概率降低但仍保留一定的交叉概率，使优良个体仍处在一种会变化的状态，避免算法陷入局部最优。自适应交叉算子公式如下：

其中：fmax为最优磷虾的适应度值，favg是磷虾群的平均适应度值，f ′为待交叉磷虾的适应度值中较大值；pc1是最大交叉概率，pc2是最小交叉概率，pc1=0.9，pc2=0.6；pc为待交叉概率，对应式（10）中的Cr。

2.2.2 随机扰动算子

迭代后期磷虾群在食物中心附近聚集，此时诱导运动和觅食运动对磷虾位置更新的吸引力趋同，容易陷入局部最优解。为了使算法快速收敛和提高算法跳出局部最优解的能力，考虑在每轮迭代的最后加入随机扰动。

如果采用传统的扰动思想，应该在磷虾位置更新时，加入一个随机偏移量以提高算法跳出局部最优解的能力，但如果这个随机偏移量过大，导致产生的新的磷虾位置跳出边界范围，将对寻找最优解没有帮助。因此一方面需要进行边界检查，另一方面需要对这个随机偏移量的范围进行限制。本文考虑在每轮迭代中诱导运动、觅食运动和随机扩散运动产生的实际偏移量的基础上，通过乘以一个在(0.75，1.25)内波动的随机扰动系数将随机偏移量限制在(-0.25，0.25)倍实际偏移量的范围内。同时，这个随机偏移量应该在迭代前期相对较大，以提高算法在前期的全局搜索能力，在迭代后期相对较小直至归零，在给算法提供一定局部搜索能力的基础上，加快算法收敛。因此本文考虑将随机扰动系数设置为一个随迭代次数逐渐降低，并最终收敛于1的一个动态系数。

在此分析的基础上，本文提出一种随机扰动算子，定义随机扰动更新公式如下：

其中：pr是随机扰动系数。通过式（12）和式（13），给KH 算法的位置更新过程添加了一个扰动系数随迭代次数降低，系数在(0.75，1.25)内波动最终收敛于1的随机扰动。

2.3 算法流程

PRKH算法步骤如下：

步骤1 种群初始化和参数设置；

步骤2 随机生成所有磷虾的位置集合X、计算适应度值并记录最佳磷虾的位置和适应度值f；

步骤3 进入迭代，计算虚拟食物中心的位置Xfood和敏感邻域半径ds，j，并不断更新食物中心位置；

步骤4 按式（3）～（7）计算诱导运动、觅食运动和扩散运动带来的位置偏移量；

步骤5 按式（11）计算自适应交叉概率pc，按式（12）和（13）执行随机扰动算子，更新磷虾位置和适应度值；

步骤6 如果满足终止条件（迭代次数），输出最佳磷虾适应度值和所在位置，否则返回步骤3。

图3 PRKH算法流程Fig.3 PRKH algorithm flowchart

3 仿真分析

3.1 实验数据和实验环境

为验证本文提出的PRKH 算法解决基于QoS 的服务组合优化问题的有效性，本文从最优解质量、最优解稳定性、时间开销三个维度对KH 算法、加入随机扰动的KH（KH with Random disturbance，RKH）算法、加入自适应交叉算子的KH（KH with adaptive crossover operator，PKH）算法和PRKH 算法进行比较，同时也将PRKH 算法和粒子群优化（PSO）算法、人工蜂群（ABC）算法、花朵授粉算法（FPA）进行比较以验证优于其他基本算法的性能。实验环境为：Windows 7（64位）操作系统，CUP 为Inter Xeon E5 2620-v3 2.40 GHz，内存为32 GB，Matlab 2020a。

本实验以指挥信息系统服务组合为例，由于当前还没有标准数据集供实验调用，各候选服务集中的具体服务的QoS参数均在规定的范围内随机生成。设定抽象服务数量为20个，每个抽象服务对应的候选服务集中候选服务数为100 个。为保证实验公平有效，所有算法均采用此随机数据集进行测试。为降低偶然性，每组实验重复100次并取平均值。

3.2 实验参数

考虑到作战时对可靠性和可用性要求较高，给予这两个指标相对较高的权重，设定属性权重W=［0.15，0.15，0.35，0.35］，其他各算法参数设置如表2所示。

表2 各算法参数设置Tab.2 Parameter setting of each algorithm

3.3 仿真结果分析

实验使用定义5 中的服务质量评价函数作为算法中的适应度值计算公式。QoS 数据按式（1）归一化处理后，适应度值越小代表最优解的质量越高。

3.3.1 PRKH算法与KH、RKH、PKH算法对比

1）最优解质量。如图4所示，从100轮结果中随机选取了第6 轮迭代的结果。可以看出，在本次迭代中，本文提出的PRKH 算法寻得了比其他三种算法质量更高的最优解，同时PRKH 算法以更快的速度接近了全局最优解。在算法后期，其他算法已经陷入局部最优解时，PRKH 算法仍有一定的跳出局部最优解的能力，能不断提高局部最优解的质量。

图4 第6轮迭代结果Fig.4 Results of the sixth iteration

为了防止实验的偶然性，将100 轮迭代寻找到的最优解适应度值进行平均，同时将100 轮迭代中的最优解作为算法最终寻找到的最优解，实验结果如图5 所示。可以看出，PRKH 算法100 轮迭代中寻找到的最优解适应度值的平均值和最佳值相较RKH、PKH、KH 算法均更好，验证了自适应交叉算子和随机扰动算子在提升最优解质量上的有效性。同时可以看出，自适应交叉算子对KH 算法性能的提升相比随机扰动算子更大。

图5 PRKH、RKH、PKH和KH算法最佳适应度值对比Fig.5 Best fitness comparison of PRKH，RKH，PKH and KH

2）最优解稳定性。如图6所示，将100轮迭代的最佳适应度值数据以箱线图的形式表示，可以看出PRKH算法和RKH、PKH、KH算法寻优结果数据离散程度差异不大。具体标准差数据如表3 所示，可以看出PRKH 算法寻子在提升KH 算法最优解稳定性上有一定效果，但效果不大。观察箱线图中数据平均值也可看出PRKH 算法寻找到的最优解质量更高，验证上述结论。

图6 PRKH、RKH、PKH和KH算法最佳适应度数据箱线图Fig.6 Best fitness data box plot of PRKH，RKH，PKH and KH algorithms

表3 PRKH、RKH、PKH和KH算法最佳适应度值标准差Tab.3 Standard deviations of best fitness values of PRKH，RKH，PKH and KH

3）时间开销。取100 轮迭代的平均时间开销进行对比，如图7 所示，PRKH 算法的时间开销略大于其他3 种算法，每轮迭代时间数据离散程度相差不大。PRKH 算法中的自适应交叉算子比原有交叉算子更复杂，添加的随机扰动算子也增加了算法的复杂性，因此一定程度上提升了PRKH 算法的时间开销。但两种改进算子并未改变算法复杂度，图中也可看出4 种算法的时间开销仍保持在同一个量级内，因此在对时间要求不高的实际问题中，PRKH算法仍有较大价值。

图7 PRKH、RKH、PKH和KH算法时间开销箱线图Fig.7 Time cost box plot of PRKH，RKH，PKH and KH algorithms

综上，自适应交叉算子和随机扰动算子有效地提高了KH算法寻找到的最优解的质量，标准差方面PRKH 算法也较RKH、PKH、KH 算法有了一定的提升。尽管在时间开销方面PRKH 算法略大于其他三种算法，但当用户追求高QoS 而对时间容忍度较高时，PRKH算法仍是较优的选择。

3.3.2 改进KH算法与PSO、ABC、FPA对比

1）最优解质量。如图8 所示，PRKH 算法100 轮迭代中寻找到的最优解适应度值的平均值和最佳值相较PSO、ABC、FPA 均更好。其中PRKH 算法寻优性能明显高于PSO 和ABC算法，略高于FPA。

图8 PRKH、PSO、ABC和FPA最佳适应度对比Fig.8 Best fitness comparison of PRKH，PSO，ABC and FPA

2）最优解稳定性。图9 和表4 可以看出PRKH 算法寻优结果数据离散程度略大于PSO、ABC、FPA，标准差数据显示四者仍在同一量级。经分析，可能是因为PRKH 算法中磷虾个体同时受到诱导运动、觅食运动和扩散运动三种因素影响，复杂性更高，带来了相较其他智能优化算法更高的不稳定性。

图9 PRKH、PSO、ABC和FPA最佳适应度数据箱线图Fig.9 Best fitness data box plot of PRKH，PSO，ABC and FPA

表4 PRKH、PSO、ABC和FPA最佳适应度值标准差Tab.4 Standard deviation of best fitness values of PRKH，PSO，ABC and FPA

3）时间开销。由图10 可以看出，PRKH 算法的时间开销明显小于PSO 算法和FPA，略低于ABC 算法。迭代时间数据的离散程度也小于PSO和FPA，具有稳定性。

图10 PRKH、PSO、ABC和FPA的时间开销对比Fig.10 Time cost comparison of PRKH，PSO，ABC and FPA

综上，与PSO、ABC 和FPA 相比，PRKH 算法寻找到最优解的质量较PSO 和ABC 算法有明显提升，且时间开销上量级相当；PRKH 算法较FPA 性能上略有提升，但时间开销比FPA小得多。尽管PRKH 算法在标准差上略逊于其他三种算法，但从满足用户对QoS 高质量需求角度，PRKH 仍是综合最优的选择。

4 结语

本文研究了磷虾群（KH）算法在服务组合优化问题中的应用，通过在标准KH 算法的基础上加入自适应交叉算子和随机扰动算子，提出了一种PRKH 算法。实验结果表明该算法相较其他智能优化算法，能迅速找到更优的复合服务。下一步我们将考虑服务组合优化问题中服务间的约束关系和动态环境下服务性能变化的问题，同时分析制约KH 算法性能的原因，以期进一步提高算法性能。