基于自适应t分布的改进粒子群实时任务调度算法

柳子来 王健敏

（1.昆明理工大学信息工程与自动化学院 云南省人工智能重点实验室；2.云南省农村科技服务中心）

近年来，随着社会智能化程度的提高和人工智能技术的发展， 信息物理融合系统（Cyber-Physical System，CPS）［1］这种分布式智能系统受到了广泛关注。CPS以信息处理为核心，能够实现通信、计算与控制的高度融合［2］，满足人类越来越复杂的智能化需求。

CPS相较于传统的分布式系统具有资源异构性强［3］、感知实时性高和网络动态拓扑的特点，这使得传统任务调度算法无法满足CPS中实时任务调度与分配的需求。随着CPS应用环境的扩展，如何高效地完成调度任务，同时满足用户多种服务质量（Quality of Services，QoS）需求，成为了目前CPS中亟待解决的问题。近年来，许多启发式算法都被用来解决此类任务调度问题。 文献［4］使用粒子群算法来处理CPS的资源调度问题， 通过在粒子更新中使用自适应的莱维飞行策略来进一步更新位置，提高全局搜索能力，达到优化的目的。 文献［5］通过结合果蝇算法与遗传算法的优点，提出了一种融合调度算法，该算法针对果蝇种群采用正交数组和量化技术进行初始化，对探索步长进行动态调整，并使用遗传算法对个体进行了选择处理，改进后的算法具有更高的效率和资源利用率。 文献［6］提出了一种基于改进粒子群优化算法的任务调度算法，通过考察任务调度中的平均调度长度与成功执行的比率来生成最优解。 但是上述调度算法普遍存在用户QoS研究单一、各性能指标考虑不足的问题，而优化算法也存在优化性能不足的问题，没有达到同时提高收敛速度与避免局部最优的目的。

为此，笔者提出一种基于自适应t分布的改进粒子群实时任务调度算法。 以经典粒子群算法为基础，在粒子位置更新时引入了自适应t分布的变异策略，借此来提高收敛速度并避免算法陷入局部最优。 同时在充分考虑任务调度多QoS需求的条件下，以任务完成时间、任务总成本和服务质量为衡量标准来设置适应度函数，在优化任务完成时间的前提下， 尽可能地控制任务总成本、降低资源消耗、减少资源传输成本，同时提高资源的服务质量，使得算法在处理任务调度问题时表现出更好的性能。

1 基本概念

1.1 CPS中的实时任务调度问题

CPS中的实时任务调度问题本质上是多目标优化组合问题，基本思想是将完整的任务调度问题分解为较小的子任务， 建立任务与资源的映射，通过在计算资源上的并行处理，最终完成调度任务。 所以，调度问题的关键是在不同的需求之间进行资源共享来减少任务的完成时间，使能耗和成本最低，同时兼顾被分配的计算资源的服务能力，实现整个系统的负载均衡。

CPS实时任务调度问题可以通过构建有向无环图（Directed Acyclic Graph，DAG）任务调度模型 表 示［7］，如 图1 所 示。 一 般 表 示 为DAG=（T，E），其中T=｛t1，t2，t3，…，tm｝是执行任务节点的集合，m是需要执行的任务总数；E=｛eij｜eij=＜ti，tj＞，eij∈T×T｝是DAG任务调度模型中的有向边，有向边连接的两个节点具有依赖关系。 如果eij∈E，则表示任务ti与tj之间存在依赖关系，tj必须在ti之前完成。在CPS中，DAG中的边就代表一个通信开销。

图1 有向无环图任务调度模型

为了方便任务调度研究，通常会理想化地假设节点间的通信是畅通的，在研究过程中会重点考虑时间、成本和服务质量这3个因素。

1.2 粒子群算法

粒子群算法［8］是一种受到自然界动物行为启发而产生的智能优化算法。 粒子群算法在处理实时任务调度问题时，可以把每一个粒子看成是调度过程中一个合理的调度方案，通过在寻优过程中对每一个粒子的适应度值进行计算与评价，并根据结果来进行速度与位置更新，以获取粒子种群和个体的最优位置，最终逼近任务调度的最优调度方案。根据CPS任务调度的实际需要，用粒子群算法处理任务调度问题时，需要将粒子位置和速度进行实例化定义， 假设粒子在一个K维任务空间搜索最优解，则任务调度的可行解可以用粒子的位置和速度来表示，即Xi=（xi1，xi2，xi3，…，xiK），Vi，j=（v1，1，v1，2，v1，3，…，vi，j）。

通过适应度函数来选取每次迭代过程中的个体最优位置pi，j和群体最优位置gj， 粒子速度与位置的更新公式如下：

其中，k为当前迭代次数；ω为惯性权重因子，不同的ω值在粒子群进化过程中有不同的作用；r1与r2为区间［0，1］上的随机数；c1与c2为学习因子，具体数值需根据任务实际情况选取，其值代表粒子对自身和群体的学习能力的强弱，决定了调度任务解的好坏。 粒子的速度与位置需控制在一个合理的范围内以保证算法的严谨性。

2 基于自适应t分布的改进粒子群实时任务调度算法

粒子群算法在处理实时任务调度问题时具有效率高、收敛速度快、效果较好的优点。 但是因为大部分种群会在迭代过程中集中在最优解的附近，导致种群的多样性降低，容易陷入局部最优， 使得算法在处理多QoS需求的任务调度问题时得不到最优解。 为此，笔者通过在粒子群算法中引入自适应t分布的变异策略来进行粒子群位置的更新，同时采用改进算法的适应度函数与目标函数来满足任务调度的多QoS需求。

2.1 目标函数与适应度函数

CPS实时任务调度的最主要目标是在尽可能短的时间内完成任务与资源的关系映射。 基本的任务调度算法中，只将任务完成时间作为任务调度的唯一需求。 笔者在适应度函数的选取上运用了多QoS需求的思想，将任务完成时间、任务总成本和服务质量三者作为任务评价标准。

任务完成时间Time是任务在整个CPS资源调度中花费的时间，其计算式如下：

任务总成本Cost包括任务执行成本和任务传输成本，CPS中的任务要尽可能消耗最低的成本来保证任务的完成，具体计算式如下：

服务质量Serve是用来衡量计算资源服务能力的标准， 好的服务质量对应着好的用户满意度，具体计算式如下：

为了实现对任务完成时间、任务总成本和服务质量的统一权衡，在目标函数中引入了加权模型：

其中，α、β、γ 分别表示任务完成时间、任务总成本和服务质量的加权系数。 考虑算法在迭代过程中，前期以任务完成时间为主要目标，而随着迭代的进行，任务总成本和服务质量成为了更重要的目标， 所以针对算法各阶段的不同目标，对加权系数进行进一步的调整与改进，具体如下：

其中，Dmax表示最大迭代次数，Dnow表示当前迭代次数。 选取式（6）作为本文算法的适应度函数，通过该函数来计算粒子每一次位置更新后的适应度值，以此作为标准来进行粒子群个体最优与全局最优的更新，迭代完成后，获得的最优群体即为最优解。

2.2 自适应t分布变异策略

t分布是统计学与概率论中的一类重要分布类型，目前广泛应用于诸多领域。 t分布的曲线形态与参数自由度有关：自由度nt越大，曲线形态表现越高耸，曲线接近于标准正态分布曲线；当自由度nt无限大时，t分布为高斯分布，即t（nt→∞）→N（0，1）；自由度nt越小，曲线形态表现越低平；当自由度nt=1时，t分布为柯西分布，即t（nt=1）→C（0，1）。

为了在粒子群算法中引入自适应t分布的变异策略，笔者先设置自适应因子η，然后在算法中粒子位置更新时进行t分布的变异操作，利用自适应因子η来控制变异程度， 最终通过这种自适应变异策略来达到优化效果。

自适应因子η的计算式为：

其中，D为算法迭代次数；pk为限制因子，用于控制迭代开始阶段的变异幅度， 避免幅度过大，造成结果的不可控；在迭代过程中η的值在1到0之间非线性减小，在迭代初期，自适应因子η发挥作用最大，随着迭代的进行，自适应因子η的作用逐渐减小。

对粒子群中粒子个体Xi，j=（x1，1，x1，2，x1，3，…，xi，j）采用自适应t分布的变异策略，具体如下：

其中，t（D）是以算法迭代次数D为参数自由度的t分布。式（10）是在当前粒子个体位置的基础上增加了自适应t分布的变异干扰项η·t（D）。迭代初期D值较小， 此时的变异干扰项可视为柯西变异，使得算法保持了粒子群种群的多样性，具有良好的全局探索能力，此时变异干扰项发挥的作用最大，有助于算法跳出局部最优；当算法进入运行后期，变异干扰项变为高斯分布变异，提高了搜索精度，加快了收敛速度，此时算法拥有较强的局部探索能力，同时变异干扰项的作用逐渐减小，当达到最大迭代次数时，变异干扰项的作用最小。

2.3 算法流程

基于自适应t分布的改进粒子群实时任务调度算法的基本执行步骤如下：

a. 初始化粒子群调度算法的各项基本参数；

b. 将式（6）中加权模型的目标函数作为适应度函数；

c. 根据适应度函数对初始粒子进行适应度评价，找出群体当前的pi，j与gj；

d. 随机设定粒子的初始速度，初始位置则设为当前的个体最优，根据式（1）、（2）更新粒子速度与位置；

e. 根据式（10）对粒子位置进行自适应t分布变异；

f. 计算粒子进行自适应t分布变异后的适应值，根据适应值的好坏更新粒子群的个体最优与群体最优；

g. 判断算法是否达到最大迭代次数，若没达到则跳转至步骤d，若达到则输出CPS调度结果。

3 实验结果及分析

3.1 实验仿真环境及参数设置

使用云计算仿真平台CloudSim作为调度实验的仿真器，通过在Datacenter Broker类中添加调度算法来完成实验仿真。 为了避免仿真平台在处理自定义任务时产生差异性， 实验利用CloudSim自带的PlanLab工作流来进行任务调度。 PlanLab工作流中共有9个调度任务，本实验随机选取其中6个。 仿真实验采用树状网络拓扑结构，与实际云计算虚拟机资源拓扑结构保持一致。

3.2 性能分析

3.2.1 收敛性能及任务完成性能

分别采用PSO、Cauchy-PSO［9］和t-PSO这3种算法进行收敛性能与任务完成性能的对比实验，以此对算法的性能作出判断，并根据结果来衡量算法的优化程度，结果如图2所示。 可以看出，随着迭代次数的增加，t-PSO的收敛速度与收敛时间都优于PSO、Cauchy-PSO算法。 而在任务完成性能上，t-PSO更是表现出极大的优势， 具有更短的任务完成时间。 可见，在粒子群算法中加入自适应t分布变异策略，可使改进后的算法表现出更好的收敛性，具有更短的任务完成时间，能有效解决PSO算法易陷入局部最优的问题。

图2 收敛性能及任务完成性能仿真实验结果

3.2.2 调度性能

图3分别比较了3种算法的执行成本、总成本和服务质量。 总成本与服务质量是衡量本文算法调度性能的两个重要因素。 通过图3可知，在处理不同的CPS实时任务调度问题时，t-PSO算法更能满足用户的多QoS需求， 在各个方面的寻优性能均优于PSO、Cauchy-PSO算法。

传统的粒子群算法因为只关注任务完成时间一个标准，导致在其他方面表现良好的部分粒子丢失， 因此在进行多目标优化性能时表现不好。 柯西变异粒子群算法因为柯西分布的局限性，导致算法不稳定，在个别任务上出现了负优化的情况。 而本文算法在目标函数中加入了任务完成时间、 任务总成本和服务质量这3个衡量标准，同时引入了自适应t分布的变异策略，解决了粒子群算法存在的收敛过慢和容易陷入局部最优的问题， 使得本文算法在处理CPS任务调度时具有更好的整体性能。

4 结束语

笔者对CPS实时任务调度问题进行了研究，提出了一种改进的任务调度算法。 针对传统粒子群算法存在容易陷入局部最优的问题，通过引入自适应t分布的变异策略对算法做了改进；CPS实时任务调度中通常只以单一的任务完成时间为标准， 笔者将改进后的粒子群算法作为调度策略，然后从任务完成时间、任务总成本和服务质量3个因素出发去完成任务调度。 实验结果表明：本文算法在处理CPS任务调度问题时具有良好的效果，在任务完成时间、任务总成本和服务质量3个方面都有所优化，满足了CPS任务调度的多QoS需求。 另外，针对算法中出现的传输成本优化问题，今后将作进一步的研究与改进。