
科学技术与工程

中国技术经济学会
基于改进粒子群的云计算任务调度算法
Cloud Computing Task Scheduling Algorithm Based on Improved Particle Swarm Optimization
传统粒子群算法(particle swarm optimization, PSO)在云计算任务调度的性能和效率方面仍然存在局部搜索效率较低、搜索精度有限等不足,导致难以找到全局最优解并容易陷入局部最优解,针对此问题提出一种改进的粒子群任务调度算法(improved particle swarm optimization, IPSO)。首先,通过反向学习策略生成分布更加均匀的初始种群,提高算法的收敛速度。其次,在粒子更新过程中引入正弦余弦算法(sine cosine algorithm, SCA)以此提高粒子的寻优能力,平衡全局搜索和局部开发两个过程。最后,添加了基于平均适应度的搜索行为进一步扩大搜索解空间以找到更好的最优解,防止陷入局部最优。在CloudSim仿真平台上进行实验验证。实验结果表明:改进粒子群算法在降低系统任务的成本和最大完工时间上均有着显著的优势。特别是当任务数量达到500时,IPSO在总成本上相较于自适应粒子群算法(adaptive particle swarm optimization, AdPSO)、正弦余弦粒子群算法(sine cosine algorithm-particle swarm optimization, SCA-PSO)、模拟退火粒子群算法(simulated annealing particle swarm optimization, SAPSO)、增强型吞噬遗传算法(enhanced phagocytosis genetic algorithm, EPGA)、竞争交叉机制遗传算法(competitive crossover mechanism genetic algorithm, C2PGA)、反向学习粒子群算法(opposition based learning-particle swarm optimization, OBL-PSO)和PSO分别提升了10%、4.6%、8.6%、9.2%、8.2%、10.4%和11.3%,在最大完工时间上分别提升了34.1%、27%、41.7%、28.5%、21.6%、50.3%和54.8%,验证了IPSO在不同任务规模下解决云计算任务调度问题的可行性和有效性。
The traditional particle swarm optimization (PSO) algorithm still has shortcomings in terms of performance and efficiency of cloud computing task scheduling, such as low local search efficiency and limited search accuracy, which often makes it difficult to find the global optimal solution and easily falls into the local optimal solution. To solve this problem, an improved particle swarm optimization task scheduling algorithm(IPSO) was proposed. Firstly, a opposition-based learning strategy was used to create a more homogeneous initial population and the Rate of convergence of this algorithm was enhanced. Secondly, in the particle update process, the sine cosine algorithm(SCA) was introduced to enhance the optimization ability of the particles and balance the two processes of global search and local development. Finally, a search behavior based on average fitness was added to further expand the search solution space to find better optimal solutions and prevent falling into local optima. Experimental verification was conducted on the CloudSim simulation platform. The experimental results show that the improved particle swarm algorithm has significant advantages in reducing the cost and maximum completion time of system tasks. In particular, when the number of tasks reaches 500, IPSO improves the total cost by 10%, 4.6%, 8.6%, 9.2%, 8.2%, 10.4% and 11.3% respectively compared with adaptive particle swarm optimization (AdPSO), sine cosine algorithm-particle swarm optimization (SCA-PSO), simulated annealing particle swarm optimization (SAPSO), enhanced phagocytosis genetic algorithm (EPGA), competitive crossover mechanism genetic algorithm(C2PGA), opposition based learning-particle swarm optimization (OBL-PSO) and PSO, and improves the maximum completion time by 34.1%, 27%, 41.7%, 28.5%, 21.6%, 50.3% and 54.8% respectively, which verifies the feasibility and effectiveness of IPSO in solving cloud computing task scheduling problems under different task scales.
云计算 / 任务调度 / 粒子群算法(PSO) / 正弦余弦算法(SCA) / CloudSim
cloud computing / task scheduling / particle swarm optimization(PSO) / sine cosine algorithm(SCA) / CloudSim
/
| 〈 |
|
〉 |