基于人工鱼群遗传算法的异构多核系统任务调度研究

J4 ›› 2014, Vol. 36 ›› Issue (10): 1866-1871.

基于人工鱼群遗传算法的异构多核系统任务调度研究

姚丽莎1，王占凤2，程家兴1

（1.安徽新华学院信息工程学院，安徽合肥 230088；
2.巢湖学院计算机与信息工程学院，安徽合肥 238000）

收稿日期:2012-12-05 修回日期:2013-04-18 出版日期:2014-10-25 发布日期:2014-10-25
基金资助:
安徽省教育厅自然科学研究项目(KJ2011Z157).

Research of tasks scheduling in heterogeneous multi-core
system based on artificial fish-swarm and genetic algorithm

YAO Lisha1，WANG Zhanfeng2，CHENG Jiaxing1

（1.Faculty of Information Engineering,Anhui Xinhua University,Hefei 230088；
2.Computer and Information Engineering Institute,Chaohu University,Hefei 238000,China）

Received:2012-12-05 Revised:2013-04-18 Online:2014-10-25 Published:2014-10-25

摘要/Abstract

摘要：

异构多核系统的任务调度问题已经被证明是一个NP完全问题。人工鱼群算法在算法初期具有较快的收敛速度，后期收敛较慢，而遗传算法的种群初始化具有较强的鲁棒性，初始化种群的质量直接影响着遗传算法的性能。本文提出了一种将人工鱼群算法与遗传算法相结合的任务调度算法，首先分析了异构多核系统的任务调度问题的本质，使用改进的人工鱼群算法来构建遗传算法的初始化种群，并使用改进的遗传算法进行迭代进化，从而提高了算法的收敛速度。

关键词: 人工鱼群算法, 遗传算法, 任务调度

Abstract:

Tasks scheduling for heterogeneous-multi-core processor system have been proved to be a NP complete problem. Artificial fish-swarm algorithm begins to converge quickly, then has slow convergence. It is robust for genetic algorithm to initialize population; the initialization of the first population affects the performance of genetic algorithm. Based on artificial fish-swarm and genetic algorithm, a task scheduling algorithm is proposed. Firstly, the tasks scheduling of heterogeneous multi-core system is analyzed. Secondly, the improved artificial fish-swarm Algorithm is used to construct the initial population of genetic algorithm. Finally, the improved genetic algorithm is applied to perform iterative optimization and it improves the convergence of algorithm.

Key words: artificial fish-swarm algorithm;genetic algorithm;tasks scheduling

姚丽莎1，王占凤2，程家兴1. 基于人工鱼群遗传算法的异构多核系统任务调度研究[J]. J4, 2014, 36(10): 1866-1871.

YAO Lisha1，WANG Zhanfeng2，CHENG Jiaxing1. Research of tasks scheduling in heterogeneous multi-core
system based on artificial fish-swarm and genetic algorithm [J]. J4, 2014, 36(10): 1866-1871.

参考文献［15］

［1］	Dutot P.Complexity of masterslave tasking on heterogeneoustrees［J］.European Journal on Operational Research, 2005,164(3):690695.
［2］	Ibarra O H, Kim C E. Heuristic algorithms for scheduling independent tasks onnonidentical processor［J］.Journal of the ACM, 1977,24(2):280289.
［3］	Beaumont O, Boudet V, Robert Y. A realistic model and an efficient heuristic for scheduling with heterogeneous processors［C］∥Proc of the 16th International Parallel and Distributed Processing Symposium,2002:37.
［4］	Jiang Zhuocai, Huang Wenming, Lei Linghong. Research on scheduling in grid based on hybrid algorithm of genetic and tabu search ［J］. Computer and Modernization, 2008(5):6972.(in Chinese)
［5］	Liu Juefu,Cai Fulai,Shuai Zhiwei.Research on management scheduling based on simulated annealing and gentic algorithm［J］.Microcomputer Information, 2009,25(93):199200.(in Chinese)
［6］	Wang Jiaping. The research on a scheduling algorithm for realtime tasks in multicore systems［D］.Nanjing:Nanjing University of Posts and Telecommunications, 2012.(in Chinese)
［7］	Wang Xutao. Research of task scheduling based on heterogeneous multiprocessor system［D］.Nanjing:Nanjing University of Posts and Telecommunications, 2011.(in Chinese)
［8］	Li Xiaolei, Lu Fei, Tian Guohui, et al. Applications of artificial fish school algorithm in combinatorial optimization problems［J］.Journal of Shandong University (Engineering Science),2004,34(5):6467.(in Chinese)
［9］	Zhao Haifeng, Yao Lisha, Luo Bin. Registration of multiresolution medical images using a modified artificial fishswarm algorithm combined with Powell’s method ［J］. Journal of Xi’an Jiaotong University,2011,45(4):4652.(in Chinese)
［10］	Xiao Jianmei, Zheng Xiaoming, Wang Xihua. A modified artificial fishswarm algorithm ［C］∥Proc of the 6th World Congress on Intelligent Control and Automation,2006:34563460.
［11］	Yuan Xueli, Zhong Mingyang. Parallel task scheduling algorithm using improved genetic algorithm［J］.Computer Engineering and Applications,2011,47(10):5659.(in Chinese)
［12］	Jiang Jianchun, Wang Tongqing. Task scheduling algorithm for heterogeneous multicore processor［J］.Computer Engineering and Applications,2009,45(33):5256.(in Chinese)
［13］	Zhong Qiuxi, Xie Tao, Chen Huowang. Tasks matching and scheduling of distributed system using genetic algorithm［J］.Journal of Computer Research and Development, 2000, 37(10):11971203.(in Chinese)
［14］	Zhang Cong, Ma Yizhong. Task matching and scheduling by using genetic algorithms in heterogeneous computing system［J］.Microelectronics & Computer,2004,21(6):7478.(in Chinese)
［15］	Cao Daoyou, Cheng Jiaxing. A genetic algorithm based on modified selection operator and crossover operator［J］. Computer Technology and Development, 2010,20(2):4451.(in Chinese)
	附中文参考文献：
［4］	蒋卓材,黄文明，雷领红. 基于混合遗传与禁忌搜索的网格任务调度的研究［J］. 计算机与现代化,2008(5):6972.
［5］	刘觉夫,蔡福来,帅志伟. 基于模拟退火和遗传算法的任务调度研究［J］. 微计算机信息，2009,25(93):199200.
［6］	王嘉平.多核系统中实时任务调度算法的研究［D］. 南京：南京邮电大学，2012.
［7］	王旭涛.基于异构多核处理器系统的任务调度算法研究［D］.南京：南京邮电大学，2011.
［8］	李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法的应用［J］.山东大学学报(工学版),2004,34(5):6467.
［9］	赵海峰,姚丽莎,罗斌.改进的人工鱼群算法和Powell法结合的医学图像配准［J］.西安交通大学学报,2011,45(4):4652.
［11］	袁雪莉,钟明洋.改进遗传算法的并行任务调度［J］.计算机工程与应用，2011,47(10):5659.
［12］	蒋建春,汪同庆. 异构多核处理器的任务调度算法［J］. 计算机工程与应用.2009,45(33):5256.
［13］	钟求喜, 谢涛, 陈火旺. 基于遗传算法的任务分配与调度［J］ .计算机研究与发展, 2000, 37(10):11971203.
［14］	张聪,马义忠.异构计算系统中基于遗传算法的任务分配与调度［J］.微电子学与计算机,2004,21(6):7478.
［15］	曹道友，程家兴.基于改进的选择算子和交叉算子的遗传算法［J］.计算机技术与发展，2010，20(2):4451.

[1]	谢俊标, 江峰, 杜军威, 赵军. 基于改进人工鱼群算法与RBF神经网络的股票价格预测[J]. 计算机工程与科学, 2022, 44(11): 2080-2090.
[2]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[3]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[4]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[5]	毛媛媛, 石恩雅, 蒋从锋, 仇烨亮, 贾刚勇, 万健, 闫龙川. 基于遗传算法的数据中心能效仿真[J]. 计算机工程与科学, 2021, 43(08): 1341-1352.
[6]	胡新荣, 刘嘉文, 刘军平, 彭涛, 何儒汉, . 基于改进GA-BP-MC神经网络的人体三维尺寸预测[J]. 计算机工程与科学, 2021, 43(08): 1443-1453.
[7]	李静, 莫思敏 . 基于改进遗传算法的深度神经网络优化研究[J]. 计算机工程与科学, 2021, 43(08): 1503-1511.
[8]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[9]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[10]	李晶晶, 许少华. 基于组合核函数的径向基过程神经网络及其在示功图诊断中的应用[J]. 计算机工程与科学, 2021, 43(04): 746-752.
[11]	季子豪, 江凌云. 一种基于遗传算法的多站点协同计算卸载算法[J]. 计算机工程与科学, 2021, 43(03): 426-434.
[12]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[13]	贾俊杰, 秦海涛. 基于遗传算法的动态轨迹匿名算法[J]. 计算机工程与科学, 2021, 43(01): 142-150.
[14]	李丹莲, 曹倩, 徐菲. 基于改进遗传算法的连锁便利店配送路径优化[J]. 计算机工程与科学, 2020, 42(11): 2096-2102.
[15]	陈旺虎，田真，张礼智，梁小燕，高雅琼. 基于插值的高维稀疏数据离群点检测方法[J]. 计算机工程与科学, 2020, 42(06): 966-972.