改进的粒子群优化算法在云计算任务调度中的应用  

Improved Particle Swarm Optimization Algorithm for Cloud Computing Task Scheduling

作　　者：汪婷 邵鹏[1] 李光泉[1] 刘珊慧[1] WANG Ting;SHAO Peng;LI Guang-quan;LIU Shan-hui(School of Computer and Information Engineering,Jiangxi Agricultural University,Nanchang 330045,China)

机构地区：[1]江西农业大学计算机与信息工程学院,南昌330045

出　　处：《科学技术与工程》2023年第29期12594-12603,共10页Science Technology and Engineering

基　　金：国家自然科学基金(62041702);教育部人文社会科学规划项目(20YJ870010);江西省社会科学规划项目(19TQ05,21GL12);江西省高校人文社科规划项目(TQ20105);江西省教育厅科技项目(GJJ200424)。

摘　　要：针对粒子群优化算法在求解云计算任务调度问题中存在的收敛速度慢、精度低、易陷入局部极值等缺陷,综合考虑最大完成时间最少、任务执行总时间最优两个优化目标,提出一种多策略融合的粒子群优化(multi-strategy particle swarm optimization,MSPSO)算法,并将其应用于求解云计算任务调度问题。该算法融合模拟退火算法、饥饿游戏搜索和双重变异限制策略。首先,通过模拟退火算法动态更新惯性权重,平衡粒子群优化算法的全局搜索和局部搜索,帮助粒子跳出局部极值。其次,引入饥饿游戏搜索算法优化粒子位置更新策略,在算法后期加快粒子收敛速度,提高结果精度。最后,采用双重变异限制策略,同时限制粒子速度和位置,避免粒子发生越界。与其他3种粒子群优化算法进行对比实验,在适应度平均值、最小值、标准差3个方面,MSPSO都有更好的表现。通过仿真,在求解不同任务量的云计算任务调度问题中,MSPSO在总成本、适应度值最小化两方面均表现出明显优势。尤其当任务量为40时,MSPSO总成本比其他算法分别降低了14.4%、15.3%、11.2%,适应度值分别降低了10.5%、10.6%、7.6%,验证了所提算法在求解云计算任务调度问题中的有效性。A multi-strategy particle swarm optimization(MSPSO) algorithm was proposed to overcome the slow convergence,low accuracy,and easy fall into local extrema of the traditional particle swarm optimization algorithm in solving cloud computing task scheduling,which integrated the two optimization objectives of minimum maximum completion time and optimal total task execution time.The algorithm incorporated the simulated annealing algorithm,the hunger games search,and the dual variance restriction strategy.Firstly,the inertia weights were dynamically updated by the simulated annealing algorithm to balance the global search and local search of the particle swarm optimization algorithm and help the particles jump out of the local extremes.Then,the hunger games search algorithm was introduced to optimize the particle position update strategy to speed up the particle convergence in the later stages of the algorithm.Finally,a dual variational restriction strategy was used to restrict both particle velocity and position to avoid particle transgression.Comparing experiments with the other three particle swarm optimization algorithms,MSPSO has better performance in the three aspects of average,minimum,and standard deviation of fitness.Through the simulation,MSPSO shows significant advantages in solving cloud computing task scheduling problems with different task sizes in terms of both total cost and minimization of fitness values.In particular,when the task size is 40,the total cost of MSPSO is 14.4%,15.3%,and 11.2% lower than other algorithms,and the fitness values are 10.5%,10.6%,and 7.6% lower,respectively,verifying the effectiveness of the proposed algorithm in solving the cloud computing task scheduling problem.

关 键 词：云计算 任务调度 粒子群优化算法 模拟退火算法 饥饿游戏搜索算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]