基于遗传算法分组竞争的列表调度算法
List Scheduling Algorithm Based on Genetic Algorithm Group Competition
DOI: 10.12677/JSTA.2022.103041, PDF,   
作者: 汪 敏：合肥工业大学微电子学院，安徽 合肥
关键词: 任务调度；遗传算法；分组竞争； Task Scheduling； Genetic Algorithm； Group Competition
摘要: 遗传算法是有效解决任务调度问题的主流算法之一。针对传统遗传算法存在的过早收敛以及搜索空间不够等问题，提出了一种自适应遗传算子，去重机制以及分组竞争策略融合的改进算法GCGA，该算法根据选取个体之间的差异程度决定个体的交叉变异的概率，且对种群中的重复个体采用去重判断，提高种群的多样性；同时采用多子代竞争，提高个体质量与搜索效率。实验表明，与IGA算法相比，平均性能可提升25.84%。
Abstract: Genetic algorithm is one of the mainstream algorithms to effectively solve task scheduling problems. Aiming at the problems of premature convergence and insufficient search space in traditional genetic algorithms, an improved algorithm GCGA, which combines adaptive genetic operator, deduplication mechanism and grouping competition strategy, is proposed. The algorithm is determined according to the degree of difference between selected individuals. The probability of individual crossover variation, and deduplication judgment is used for repeated individuals in the population to improve the diversity of the population; at the same time, multi-offspring competition is used to improve individual quality and search efficiency. Experiments show that the average performance can be improved by 25.84% compared with the IGA algorithm.
文章引用：汪敏. 基于遗传算法分组竞争的列表调度算法[J]. 传感器技术与应用, 2022, 10(3): 342-349. https://doi.org/10.12677/JSTA.2022.103041

参考文献

[1] Topcuoglu, H., Hariri, S. and Wu, M.Y. (2002) Performance-Effective and Low-Complexity Task Scheduling for Het-erogeneous Computing. IEEE Transactions on Parallel and Distributed Systems, 13, 260-274. [Google Scholar] [CrossRef] 
[2] 张多利, 廖金月, 罗乐, 等. 一种多核系统任务扰动迭代算法[J]. 电子测量与仪器学报, 2020, 34(9): 133-139.
[3] 王月恒. 基于任务复制的多核调度算法研究[D]: [硕士学位论文]. 合肥: 合肥工业大学, 2021.
[4] 周超群, 周亦敏. 一种改进的基于复制的异构多核任务调度算法[J]. 电子科技, 2017, 30(6): 57-62.
[5] 谢志强, 韩英杰, 齐永红, 等. 基于关键路径和任务复制的多核调度算法[J]. 国防科技大学学报, 2014(1): 172-177.
[6] 任良育, 赵成萍, 严华. 基于任务复制与冗余消除的多核调度算法[J]. 计算机工程, 2019, 45(5): 59-65.
[7] Kwok, Y.K. and Ahmad, I. (1996) Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors. IEEE Transactions on Parallel Distributed Systems, 7, 506-521. [Google Scholar] [CrossRef] 
[8] 王昱, 左利云. 云计算中基于改进遗传算法的多目标优化调度[J]. 广东石油化工学院学报, 2020, 30(1): 5.
[9] 白楠, 陈正阳. 基于改进模拟退火算法的片上网络任务调度优化研究[J]. 河南科技, 2018(25): 2.
[10] 姚英彪, 王璇. 面向多核任务调度的混合遗传算法[J]. 系统工程与电子技术, 2015(8): 1928-1935.
[11] 张皓, 赵开新, 孙冬. 改进遗传算法在云资源任务调度中的应用[J]. 河南工学院学报, 2020, 28(3): 24-29. [Google Scholar] [CrossRef] 
[12] Hou, E. and Ansari, N. (1994) Genetic Algorithm for Multipro-cessor Scheduling. IEEE Transactions on Parallel and Distributed Systems, 5, 113-120. [Google Scholar] [CrossRef] 
[13] 姚虎. 云计算环境下基于改进遗传算法的任务调度策略研究[Z]. 内蒙古农业大学, 2018.
[14] He, K., Meng, X., Pan, Z., et al. (2019) A Novel Task-Duplication Based Clustering Algorithm for Heterogeneous Computing Environments. IEEE Transactions on Parallel Distributed Systems, 30, 2-14. [Google Scholar] [CrossRef] 
[15] Amoura, A.K., Bampis, E. and Konig, J. (1998) Scheduling Al-gorithms for Parallel Gaussian Elimination with Communication Costs. IEEE Transactions on Parallel and Distributed Systems, 9, 679-686. [Google Scholar] [CrossRef] 

为你推荐