求解云计算任务调度的粒子群优化算法研究

目前，云环境下任务调度问题是一个研究热点，而粒子群算法(Particle Swarm Optimization, PSO)是解决任务调度问题的重要智能算法。针对相关性粒子群算法(Correlation Particle Swarm Optimization, CPSO)和新的基于自适应惯性权重粒子群算法(New Adaptive Inertia Weight Based Particle Swarm Optimization, NewPSO)在解决该问题时易陷入局部最优解和寻优能力差的不足，本文以任务执行时间和代价为目标，将随机因子与惯性权重相融合，提出增强型粒子群算法(Enhanced Particle Swarm Optimization, EPSO)。仿真结果表明，在相同条件下，与PSO算法、CPSO算法和NewPSO算法相比较，EPSO算法能更有效的减少执行时间，降低代价消耗(包括任务执行时间，时间花费以及虚拟机花费)，得到更优的调度方案。

近年来，云计算以其独特的方式成为互联网发展的热门话题。云计算主要是利用虚拟化技术，将庞大的计算处理任务通过网络分成多个较小的子任务， 再交给由多部服务器组成的庞大系统， 经过计算后， 将处理结果返回给用户[1] [2]。

在云计算中，任务调度策略直接影响到用户的任务执行效率以及云环境下资源的使用效率。在解决任务调度问题的研究领域里，群体智能优化算法越来越得到研究者的广泛关注，逐渐成为解决调度问题的新工具。1995 年，Kennedy 等提出PSO 算法[3]。该算法的基本思想是粒子在寻优过程中，不仅考虑自身的局部认识，而且还要考虑种群的全局认识，即每个粒子是在充分利用这两个认知信息的基础上决定下一次的进化方向。由于PSO 算法有参数少、易实现、收敛速度快等特性，已被广泛应用于各个领域。

文献[4]提出改进的粒子群算法优化神经网络及应用，通过采用动态惯性权重，提高粒子的多样性， 一定程度上避免陷入局部最优。文献[5]提出一种基于种群多样性的粒子群优化算法设计及应用，通过种群多样性设计自适应惯性权重策略，实现粒子全局优化能力与局部开发能力的平衡，从而避免陷入局部最优解。文献[6]在传统惯性权重的基础上提出了新的基于自适应惯性权重的粒子群算法(New Adaptive Inertia Weight Based Particle Swarm Optimization，NewPSO)，可以进一步调整粒子速度以平衡粒子全局与局部搜索，使算法避免了陷入局部最优。文献[7]提出基于动态加速因子的粒子群优化算法研究，通过引入动态的加速因子，提高全局搜索能力，改善粒子群算法的收敛速度及精度。文献[8]提出优化粒子群的云计算任务调度算法，解决了粒子群算法在寻优过程中没有考虑随机因子作用而造成全局优化能力不足的缺陷。

上述方法只考虑惯性权重或者只考虑随机因子，并没有有效避免陷入局部最优解，提高全局优化能力。因此本文将自适应惯性权重与随机因子相融合，并将改进后的粒子群算法运用到云计算任务调度问题中，得到时间与代价均优的调度策略。