基于改进鲸鱼优化算法的资源调度策略＊

余隆勇

(浙江理工大学计算机科学与技术学院，浙江 杭州 330018)

0 引言

群智能算法[1]自提出以来被广泛应用于解决各种生活和科学研究问题，如资源调度、路径规划、最优策略等。它通过模拟种群中动物习性，通过单个个体的行为与群体的合作和组织，表现出群体智能行为的特征，使用随机搜索方式来获取算法最优解。但随着随着信息化的深入发展，越来越多的应用和任务部署在云端从而导致了传统群智能算法不能有效快速地解决资源分配问题。因此许多学者通过将群智能算法进行改进并运用到资源调度中，如Wu Daqin[2]针对目前粒子群算法性能低效，提出一种通过引入迭代选择算子的改进粒子群算法并进行实验，结果表明改进后的算法可以提高优化能力，尽可能避免陷入局部最优，具有较好的收敛效果。孟凡超[3]等人针对云数据中心虚拟机分配存在的不均衡问题，参考用户对虚拟机资源需求，避免在同一台虚拟机上部署，提出了一种蚁群优化算法的资源调度策略，并通过实验证明该算法能够快速完成虚拟机的放置并让数据中心的虚拟机具有较低的负载不均衡度，提高资源利用率。李勋章[4]等人针对遗传算法在资源调度中存在收敛速度过快以及陷入局部最优解等问题，利用多优选保留技术选取适应度值较大的个体放入种群，通过与普通个体进行杂交从而使种群往更优的方向不断进化，以此保证种群多样性以及避免陷入局部最优解的作用。程曦[5]针对云计算资源调度优化问题，提出改进布谷鸟的随机搜索策略和丢弃概率策略，来提高算法的局部搜索能力和收敛速度，并在解决云资源调度的多目标问题针对减少延迟，提高资源利用率和服务质量取得很好的效果。

针对传统鲸鱼算法[6]在资源调度上存在的问题，提出一种改进的鲸鱼优化算法，该算法通过对传统鲸鱼算法的三个阶段进行优化，首先通过非线性变量结构的包围阶段和基于平均最优解(Average Optimal Solution)的螺旋位置变化，提高了算法的局部优化能力和收敛速度；提出自适应加权[7]搜索捕食策略来提高算法全局最优解的速度和精度。

1 鲸鱼优化算法

鲸鱼优化算法（Whale Optimization Algorithm,WOA）作为一种群智能算法，主要模拟座头鲸的捕食行为，并将捕食行为分为了包围猎物、螺旋气泡捕食以及搜索猎物三个阶段。

1.1 包围猎物阶段

鲸鱼在收缩包围阶段是通过向当前适应度最优的个体进行靠拢来更新位置。其余鲸鱼个体也通过这种方式来实现对猎物的包围。包围阶段位置更新公式如下：

1.2 螺旋气泡捕食阶段

螺旋气泡捕食作为鲸鱼猎食行为中进行局部搜索的另一个阶段，它通过一个螺旋式游动来对食物进行抓捕。螺旋捕食的更新公式如下：

其中，b 用来定义螺旋形状，通常取值为常数1；l是[-1,1]之间均匀分布的随机数。包围阶段和螺旋气泡捕食阶段同作为鲸鱼算法的局部搜索阶段，在标准的鲸鱼算法中采用相同的概率P 来决定采用哪种策略进行位置的更新。具体更新公式如下：

1.3 搜索猎物阶段

搜索捕食是鲸鱼算法在避免陷入局部最优、求得最优解的一个阶段。在寻找最优的行为中，它主要通过随机搜索来进行鲸鱼猎食的位置更新。具体模型如下：

2 改进鲸鱼优化算法

2.1 基于自适应权重的搜索捕食

传统的WOA 算法通过A的取值来控制当前鲸鱼个体是否进入搜索捕食阶段，因此当A越大时可以使鲸鱼个体保持更佳的探索能力。或者A较小时采用包围策略时能够实现较高精度的求解，拥有更好的局部寻优能力。因此本文针对上述情况提出了一种基于自适应权重的方式来控制鲸鱼对策略的选取，对式⑺具体的改进如下：

其中，EMBED Equation.DSMT4是改进自适应搜索捕食中的控制系数，它根据当前迭代次数t以及改进后的正弦公式来进行下一次迭代的位置更新。

2.2 非线性变化的包围策略

在收缩和环绕阶段，通过计算每头鲸的适应度值获得当前最优解，并根据当前最优解迭代和逼近剩余的个体鲸，具体的位置更新公式如式⑴、式⑵。由式⑶中的a可以得知，鲸鱼算法在进行包围行为的过程中是一种线性变化的策略，线性变化结构在算法的迭代过程容器造成趋近于局部最优解、收敛速度过快等情况。因此本文针对包围阶段提出一种非线性变化包围策略来控制算法的收敛速度。具体更新公式为：

其中，更新后的a公式是一个余弦函数，它可以通过控制算法在迭代的前中后期实现非线性的变化。r1、r2是0 至1 的随机控制系数、Tmax是最大迭代次数。在更新后的公式中，鲸鱼收敛速度随着迭代次数的增加是越来越快的，但是在后期会减缓来保证算法的收敛能力从而更好的求最优解、减少收敛时间。

2.3 基于AOS的螺旋位置变更

鲸鱼的捕食路径是一种螺旋状，鲸鱼个体可能会向最优个体靠拢来进行位置的更新，这种单一的更新方式很容易导致陷入局部最优解问题，当其余鲸鱼个体也向当次迭代最优解靠拢时，就容易导致所有个体产生局部最优解。在该阶段本文通过借鉴灰狼算法[9]思想，提出基于AOS（Average Optimal Solution）的螺旋位置变更策略。具体的公式为：

其中，ω1、ω2、ω3为[0,1]的随机数且总和为为当前种群中最优的三个鲸鱼个体。通过不同的变更系数ω与其对应的最优个体向量的成积和来进行鲸鱼个体的螺旋位置更新。该算法采用三个最优个体的组合作为更新策略，保证了求解过程中收敛速度不会过快，增加了鲸鱼种群的多样性，避免了基于单个最优个体的位置更新陷入局部最优解的问题。改进位置公式如下：

2.4 WOA-3改进算法具体流程设计

改进后的WOA-3 算法在搜索捕食阶段中，将每一个鲸鱼个体当作一个具体的解，根据每一次迭代的结果对鲸鱼个体进行评估，在达到最大迭代次数时将在当前最大迭代次数中的最优鲸鱼个体视为算法的全局最优解。具体步骤如下。

⑴初始化鲸鱼种群：种群规模大小n,为每个鲸鱼个体随机生成初始位置，螺旋位置更新系数ω1、ω2、ω3，最大迭代次数Tmax，参数a、A、C、r1、r2、P等。

⑶进入迭代，更新参数参数a、A、C、r1、r2、P。根据当前迭代结果计算每个鲸鱼的适应度值并进行排序，得出当前迭代中前三个最优解以及

⑷当P>0.5 且A>1 时，选择公式⑽，采用随机一个用来进行鲸鱼的位置更新；当P ≤0.5且A>1时，算法通过公式⒂进行鲸鱼个体的位置更新。

⑸当P >0.5 通过公式⒃确定鲸鱼个体的位置更新。

⑹根据2-5 过程更新当前迭代的种群适应度值并重新排序，更新当前解以及

⑺如果当前个体的最新解优于上次迭代的值，则进行更新。

⑻如果当前迭代次数达到最大值Tmax，输出当前鲸鱼最优解；未达到最大迭代次数，跳回步骤⑵。

3 仿真实验与结果

3.1 改进鲸鱼优化算法性能实验

为了验证本文提出的改进鲸鱼优化算法[10]性能，我们将选取WOA、POS、GSA 和本文改进的WOA-3对四个测试函数在Matlab 进行实验，具体函数如表1所示。得到对应的最优解、平均解和标准差，如表2所示。

表1 测试函数

表2 测试函数结果

由表2可知，标准WOA算法在四个函数测试的最优解、平均值以及标准差在大多数情况下都是优于PSO 和GWO 算法的，但是改进的WOA-3算法在这些结果中相比于WOA 算法，除了在f4 函数的结果存在略微偏差，其余函数的计算精度均有着明显的提高。为了能够表明改进算法的作用，本次实验还将各算法在这四个测试函数中的收敛情况进行对比，结果显示，WOA 算法比PSO 和GWO 算法有更好的收敛性，改进的WOA-3 算法比WOA 算法有更好的收敛速度和求解精度，具体如图1～图4所示。

图1 F1函数

图2 F2函数

图3 F3函数

图4 F4函数

3.2 资源调度仿真实验验证

3.2.1 实验环境

为了验证改进的WOA-3 算法在资源调度中的性能，本文通过CloudSim[8]平台模拟在Kubernetes 集群上进行资源调度的实验。集群主要包括一个主节点Master 和四个Node 节点，并使用十个Pod 任务进行测试。Master 节点用于实现资源调度、监控等功能，而Node 节点则是真正用来处理Pod 任务请求的工作节点。具体配置如表3和表4所示。

表3 实验配置信息

表4 Pod请求资源量

3.2.2 实验结果与分析

在本文中，为了验证WOA-3 算法在资源调度上的性能将其与WOA、PSO 以及Kubernetes 的默认调度算法在资源调度性能进行对比。相比于Kubernetes的默认性能评价因子CPU 和内存，在实际的应用场景中任务的调度还需要考虑到对网络宽带的访问和磁盘的读写需求，所以在本次实验中额外添加了磁盘和网络两个性能指标。从图5～图8 可以看出，相比于PSO和默认资源调度算法相比，WOA 算法得到了改进，但改进后的WOA-3 算法可以使资源负载更加均衡，资源利用率高于WOA 算法。由此说明，改进的WOA-3算法在进行资源调度时能够让各节点的利用率更好，使负载更加均衡。

图5 Node1节点

图6 Node2节点

图7 Node3节点

图8 Node4节点

4 结束语

针对鲸鱼算法在资源调度中容易出现收敛速度慢，陷入局部最优解等问题，提出一种改进的WOA-3算法。WOA-3 算法主要是针对鲸鱼猎食三个阶段分别进行改进，通过改进非线性变化结构的包围策略以及基于AOS 策略改变螺旋更变位置，来加快鲸鱼算法的局部收敛速度；同时，通过提出自适应加权捕食策略来提高鲸鱼算法的全局寻优能力和收敛能力。在算法性能仿真实验中验证了算法的收敛性和优化能力，改进的WOA-3 算法相比于传统的WOA、PSO 和GWO 算法，都有更好的收敛性，能够在更少的迭代中趋近于最优值；同时也在资源调度的仿真实验中验证了WOA 算法相比于Kubernetes 默认的调度算法和PSO 算法有一定的提升，而改进WOA-3 算法相比于传统WOA 算法能够使资源的调度更加均衡，资源利用率更高。