任务调度算法中新的自适应惯性权重计算方法

A Novel Computation Method for Adaptive Inertia Weight of Task Scheduling Algorithm

粒子群算法(particle swarm optimization,PSO)是解决云计算环境中工作流系统的任务调度优化问题的主流智能算法.然而基于传统自适应惯性权重的粒子群任务调度算法易陷入局部最优,导致调度方案的执行时间与费用较高.因此,通过改进单个粒子的成功值计算方法,提出了一种新的自适应惯性权重计算方法 NAIWPSO(new adaptive inertia weight based particle swarm optimization).该方法通过比较每个粒子的适应度与全局最优值,可以更加精确描述粒子状态,进而提高了权重的自适应性.在新惯性权重基础上,提出了一种解决云工作流系统中任务调度优化问题的改进粒子群算法.新权重可以更准确的调整粒子速度,使算法更好地平衡粒子全局与局部搜索,避免陷入局部最优,获得执行费用更优的调度方案.实验表明,与5种已有惯性权重算法比较,新算法收敛稳定、适应度最低、执行费用平均减少18%.

Particle swarm optimization （PSO） is a primary intelligence algorithm to solve task scheduling problem for workflow systems in cloud computing. The inertia weight is one of the most important parameters to achieve a balance between the global and local search in PSO algorithm. However, traditional adaptive inertia weight-based PSO task scheduling algorithms usually get local optimal and cause longer execution time and higher cost for scheduling plan. The traditional adaptive inertia weight does not comprehensively represent the information of particle position, and then cannot make a suitable balance between global and local search. Hence, a novel computation method for adaptive inertia weight is proposed to improve the computation method of success value of each particle. This method shows the position state of each particle more accurately and then improves the adaptability of inertia weight by comparing the fitness of each particle with the global best particle. Then a new inertia weight-based PSO algorithm is presented to solve task scheduling problem for cloud workflow systems. The novel weight can adjust the particle velocity more correctly so that the algorithm avoids premature convergence by a proper balance between local and global search. Comparing our new adaptive inertia weight with other five traditional inertia weights （viz. constant, index decreasing, linear decreasing, random, and adaptive inertia weight）, the results show that our new adaptive inertia weight-based scheduling algorithm can always achieve stable convergence speed, the optimal fitness and execution cost of the scheduling plan （i. e. roughly 18% reduction of execution cost）.