云计算多目标任务调度的优化粒子群算法研究

Research on optimal particle swarm optimization for multi-objective task scheduling in cloud computing

针对传统粒子群算法求解云计算多目标任务调度的收敛速度慢、精度低的缺陷,提出一种优化多目标任务调度粒子群算法(MOTS-PSO)。首先,引入非线性自适应惯性权重,改变粒子的寻优能力,避免算法陷入局部最优;其次引入花朵授粉算法概率更新机制,平衡粒子的全局搜索和局部寻优,并对粒子的全局搜索位置更新公式进行改进;最后引入萤火虫算法,产生"精英解"对局部搜索位置更新公式进行改进;同时利用"精英解"对粒子的位置进行扰动,跳出局部最优状态。实验表明,MOTS-PSO算法在收敛速度和收敛精度上,比PSO算法提高了27.1%、19.9%,比FA算法提高了22.09%、5.2%。进一步实验表明,MOTS-PSO算法在解决不同规模数量的任务调度时,比PSO、FA算法效果更优。

To overcome the slow convergence and low accuracy of traditional particle swarm optimization(PSO) for slow convergence and low accuracy of multi-objective task scheduling in cloud computing, an optimized multi-objective task scheduling particle swarm optimization algorithm(MOTS-PSO) is proposed. Firstly, the nonlinear adaptive inertial weight is introduced to change the particle’s optimization ability to avoid the algorithm from running into local optimum. Secondly, the flower pollination algorithm probability update mechanism is introduced to balance the global search and local optimization of the particles. In addition, we improve the global search position update formula. Finally, the firefly algorithm(FA) is introduced to generate the elite solution to improve the local search position update formula. At the same time, we utilize the elite solution to perturb the particle position and to jump out of the local optimal state. Experiments show that the MOTS-PSO algorithm has 27.1% and 19.9% higher convergence speed and precision than the PSO algorithm, and 22.09% and 5.2% higher than the FA algorithm. Further experiments show that the MOTS-PSO algorithm is more effective than the PSO and FA algorithms in solving tasks of different sizes and numbers.