基于遗传算法的网格任务调度的研究与仿真
|
摘要
网格是一个集成的计算与资源环境,它能充分吸纳各种计算资源,并将它们转化成一种随处可得的、可靠的、标准的同时还是经济的计算能力,实现资源的全面共享。网格任务调度是网格研究的核心内容之一,如何合理地将任务分配给不同资源,使整个网格系统达到最佳的性能,这是任务调度需要解决的问题。由于网格自身的分布性、异构性、动态性和自治性,使得传统的调度算法面临新的挑战。因此,如何在现有调度算法的基础上提出一个好的调度算法,尽可能提高网格系统的吞吐量,是一个重要而现实的问题。
遗传算法是近年兴起的一种用于解决优化问题的启发式算法,被广泛用于解决各类NP问题和任务调度问题。有仿真实验证明:在处理调度问题时,遗传算法与传统调度算法相比更具优越性。由于基本遗传算法SGA(Simple GeneticAlgorithm)本身存在一定的缺陷,比如“早熟”收敛和“欺骗”问题,因此大批学者都致力于改进遗传算法的探索和研究中。
本文深入解析了遗传算法和模拟退火算法SA(Simulated Annealing)的基本原理,针对SGA的不足,提出了一种混合遗传算法HGA(Hybrid Genetic Algorithm)。HGA在SGA的基础上,主要改进了以下几个方面:借鉴了模拟退火的思想,根据SA中的Metropolis准则决定是否接受由交叉和变异操作产生的新个体,使得在接受优质解的同时,也有限度的接受劣质解,保证了种群的多样性;采用了自适应交叉和变异概率;适当地改进了遗传操作。
根据网格任务调度的特点,本文详细设计了混合遗传算法的各个组成部分。在GridSim网格模拟器中,对混合遗传算法进行了仿真实现,并与SGA和SA进行了对比,结果表明本文提出的混合遗传算法具有更好的搜索能力和收敛速度。
Grid is an environment that integrates calculation and resources. It can fully absorb all kinds of computing resources and turns them into a computing capability which is easily available, reliable, standardized and economical. In this way, we can share the resources thoroughly. Task scheduling is one of the most important part in grid research, How allocate tasks to different resources in order to make the grid system obtain the highest performance is the problem which the task scheduling needed to resolve. The features of distribution, heterogeneousness, dynamic and self-ruling of grid challenge the traditional scheduling algorithms. So it is very important and realistic to put forward a better scheduling algorithm based on existing algorithms which can make full use of all kinds of resources and improve the throughput of grid system.
Genetic algorithm is a new kind of modern heuristics algorithm, which is often used to solve different kinds of NP-complete problems and complex job scheduling problems. Some simulation experiments have confirmed that genetic algorithm is better than classical scheduling algorithms. Because the simple genetic algorithm (SGA) has some defects, such as prematurely convergence and deceptive problem, many academicians committed themselves to the research of improving the genetic algorithm.
This thesis analyzes the basic principle of the genetic algorithm and the simulated annealing algorithm (SA) thoroughly. Aiming at the shortage of simple genetic algorithm, this thesis brings forward a kind of hybrid genetic algorithm (HGA). Some improvement is made on the basis of SGA: It learns the Metropolis rule from SA to determine whether to accept a new individual that generated by the crossover or mutation operation. According to the Metropolis rule, the algorithm can accept not only a premium solution, but also a bad solution in a limited probability, so it makes the population having great variety; its crossover probability and the mutation probability are self-adaptive; its genetic operations are also improved properly.
Based on characteristics of task scheduling in Grid, we design all the components of HGA at length. On top of that, we perform an experiment based on GridSim to implement the algorithm, and do comparison with SGA and SA in performance. The experiment results show that the hybrid scheduling algorithm that we put forward has a better ability of search and a higher convergence speed.
遗传算法是近年兴起的一种用于解决优化问题的启发式算法,被广泛用于解决各类NP问题和任务调度问题。有仿真实验证明:在处理调度问题时,遗传算法与传统调度算法相比更具优越性。由于基本遗传算法SGA(Simple GeneticAlgorithm)本身存在一定的缺陷,比如“早熟”收敛和“欺骗”问题,因此大批学者都致力于改进遗传算法的探索和研究中。
本文深入解析了遗传算法和模拟退火算法SA(Simulated Annealing)的基本原理,针对SGA的不足,提出了一种混合遗传算法HGA(Hybrid Genetic Algorithm)。HGA在SGA的基础上,主要改进了以下几个方面:借鉴了模拟退火的思想,根据SA中的Metropolis准则决定是否接受由交叉和变异操作产生的新个体,使得在接受优质解的同时,也有限度的接受劣质解,保证了种群的多样性;采用了自适应交叉和变异概率;适当地改进了遗传操作。
根据网格任务调度的特点,本文详细设计了混合遗传算法的各个组成部分。在GridSim网格模拟器中,对混合遗传算法进行了仿真实现,并与SGA和SA进行了对比,结果表明本文提出的混合遗传算法具有更好的搜索能力和收敛速度。
Grid is an environment that integrates calculation and resources. It can fully absorb all kinds of computing resources and turns them into a computing capability which is easily available, reliable, standardized and economical. In this way, we can share the resources thoroughly. Task scheduling is one of the most important part in grid research, How allocate tasks to different resources in order to make the grid system obtain the highest performance is the problem which the task scheduling needed to resolve. The features of distribution, heterogeneousness, dynamic and self-ruling of grid challenge the traditional scheduling algorithms. So it is very important and realistic to put forward a better scheduling algorithm based on existing algorithms which can make full use of all kinds of resources and improve the throughput of grid system.
Genetic algorithm is a new kind of modern heuristics algorithm, which is often used to solve different kinds of NP-complete problems and complex job scheduling problems. Some simulation experiments have confirmed that genetic algorithm is better than classical scheduling algorithms. Because the simple genetic algorithm (SGA) has some defects, such as prematurely convergence and deceptive problem, many academicians committed themselves to the research of improving the genetic algorithm.
This thesis analyzes the basic principle of the genetic algorithm and the simulated annealing algorithm (SA) thoroughly. Aiming at the shortage of simple genetic algorithm, this thesis brings forward a kind of hybrid genetic algorithm (HGA). Some improvement is made on the basis of SGA: It learns the Metropolis rule from SA to determine whether to accept a new individual that generated by the crossover or mutation operation. According to the Metropolis rule, the algorithm can accept not only a premium solution, but also a bad solution in a limited probability, so it makes the population having great variety; its crossover probability and the mutation probability are self-adaptive; its genetic operations are also improved properly.
Based on characteristics of task scheduling in Grid, we design all the components of HGA at length. On top of that, we perform an experiment based on GridSim to implement the algorithm, and do comparison with SGA and SA in performance. The experiment results show that the hybrid scheduling algorithm that we put forward has a better ability of search and a higher convergence speed.
引文
[1]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002:3-16
[2]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述[J].计算机应用研究,2005,22(5):16-19
[3]Ian Foster,Carl Kesselman.Globus:A Metacomputing Infrastructure Toolkit.Intl J.Supercomputer Applications,1997,11(2):115-128
[4]查礼,李伟,余海燕,蔡季萍.面向服务的织女星网格系统软件设计与评测[J].计算机学报,2005,28(4):495-50
[5]Qiao WG,Zeng GS,Hua A,et al.Scheduling and executing heterogeneous task graph in grid computing environment.In:Zhuge Hai,Fox G,eds.Proc.of the 4~(th)Int'l Workshop on Grid and Cooperative Computing(GCC 2005).LNCS 3795,Beijing:Springer-Verlag,2005:474-479
[6]Buyya R.Economic-Based distributed resource management and scheduling for grid computing[D].Melbourne:School of Computer Science and Software Engineering,Monash University,2002:9-46
[7]Fujimoto N,Hagihara K.A.Comparison among grid scheduling algorithms for independent coarse-grained tasks.In:Proc.of the 2004 Symp.on Applications and the Internet-Workshops.Washington:IEEE Computer Society Press,2004:674-680
[8]Maheswaran M,Ali S,Siegel HJ,et al.Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems.In:Proc.of the 8~(th)Heterogeneous Computing Workshop(HCW'99).Washington:IEEE Computer Society Press,1999:30-44
[9]Maheswaran M,Ali S,Siegel HJ,et al.A comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems.Technical Report,School of ECE,Purdue University,1999
[10]Wu MY,Shu W,Zhang H.Segmented Min-Min:A static mapping algorithm for meta-tasks on heterogeneous computing systems.In:Proc.of the 9~(th)IEEE Heterogeneous Computing Workshop.Washington:IEEE Computer Society Press,2000:375-385
[11]Wei TY,Zeng WH,Huang BB.Scheduling algorithm based on modified Min-Min in grid.Computer Applications,2005,25(5):1190-1192(in Chinese with English abstract)
[12]Casanova H,Legrand A,Zagorodnov D,et al.Heuristics for scheduling parameter sweep applications in grid environments.In:Proc.of the 9~(th)Heterogeneous Computing Workshop.Washington:IEEE Computer Society Press,2000:349-363
[13]Zha L,Xu ZW,Lin GZ,et al.Scheduling algorithm for hybrid data and computation intensive metatask in grid.Computer Engineering and Design,2003,24(10):1-4(in Chinese with English abstract)
[14]中国网格信息中转站.中国国家网格的进展[EB/OL]http://www.jtzx.net.cn/cgi-bin/zwolfl/show.cgi?class=1&id=1139,2004-10-12
[15]Berman and R Wolski.The AppLeS Project:A Status Report.Proceedings of the 8th NEC Research Symposium
[16]High Performance Computing Lab.Application-Level Scheduling[EB/OL]http://miles.cnuce.cnr.it/～lafo/domenico/talks/SSGRR2000/sld040.html,2000-7-31
[17]R Buyya,D Abramson,J Giddy.Nimrod/G:Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C].In Proceedings of the 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region(HPCASIA 2000),2000:283-289
[18]Buyya R,Mershed M,Abramson D.A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global Grids[A].In The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA'02),Las Vegas,Nevada,USA,June 2002
[19]Ian Foster,Carl Kesselman.The Grid:Blueprint for a Future Computing Infrastructure.Morgan Kaufmann:San Francisco,CA,1999:259-27
[20]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005:6-7
[21]冯百明,徐志伟等.网格计算[M].北京:中科院计算所,2002
[22]Ian Foster,Carl Kesselman and S.Tuecke,Grid service for distributed systems integration.IEEE Computer 35(6),2002:37-46
[23]Ian Foster,Carl Kesselman.A distributed resource management architecture that supports advance reservations and co-allocation in International Workshop on Quality of Service,1999:27-36
[24]岑玲.基于简单对象访问协议的分布式计算技术.微型机与应用,2001,12(07):30-31
[25]S.Tuecke,K.Czajkowski,Ian.Foster,J.Frey.Open Grid Services Infrastructure Version 1.0.Globus Grid Forum,Draft draft-ggf-ogsi-gridservice-29,2003.Available at[EB/OL]www.ggf.org/document/Drafts
[26]E.Christensen,F.Curbera,G.Meredith and S.Weerawarana,Web Services Description Language(WSDL)1.1,W3C,Note 15,2001.Available at[EB/OL]www.w3.org/TR/wsdl
[27]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述.计算机应用研究.2005.05
[28]侯小静.基于遗传算法的网格任务调度:[D].新疆:新疆大学计算机学院,2006
[29]Ishohn U S,Yahyapour R,Grid Scheduling Architecture.Global Grid Forum Draft Recommmendation,2002,26(4):21-31
[30]Min-You Wu,Wei shu,and Hong Zhang.Segmented Min-Min:A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems[A].In:proceedings of 9th IEEE Heterogeneous Computing Workshop,2000.(HCW 2000)[C].USA:IEEE Computer Society Press,2000,375-385
[31]Maheswaran M,Siegel H J.A dynamic matching and scheduling algorithm for heterogeneous computing systems[A].In:Proceedings of the 7th IEEE Heterogeneous Computing Workshop(HCW'98)[C].USA:IEEE Computer Society Press,1998:57-65
[32]崔玉宝,贾振华,侯志国,薛桂香.网格任务调度算法研究[J].微计算机信息,2006年15期
[33]Min-You Wu,Wei Shu.Segmented Nin-Min:A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems.Department of Electrical and Computer Engineering University of New Mexico,2000
[34]王翼飞.生物信息学-智能化算法及其应用[M].北京:化学工业出版社.2006:158-161
[35]J.H.Holland,Adaptation in Natural and Artificial Systems,University of Michigan Press.1975
[36]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008:8-13
[37]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999
[38]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004:25-35
[39]李敏强,寇纪淞.遗传算法的基本理论与应用[M].北京:科学出版社,2002:45-46
[40]唐立山等.非数值并行算法(第一册)-模拟退火算法[M].北京:科学出版社,2000
[41]庞峰.模拟退火算法的原理及算法在优化问题上的应用:[D].吉林:吉林大学计算机学院,2006
[42]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002
[43]M.Srinivas,L.M.Patnaik.Adaptive probabilities of crossover and mutation in genetic algorithm.IEEE Transactions on Systems,Man,and Cybemetics,1994,24(4):656-667
[44]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].人民邮电出版社,2001
[45]詹炜,戴光明,龚文引.求解函数优化问题的一种高效混合演化算法[J].计算机工程与应用.2006.2:70-72
[46]周维,罗泽,阎保平.以策略为机制的网格任务调度模型研究[J].计算机工程.2007.7:p89-91
[47]郭茂祖,姜俊峰,李静海.模拟退火算法中冷却调度选取方法的研究[J].计算机工程,2002,26(9):63-64
[48]Buyya R,Murshed M.GridSim:A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing[J].The Journal of Concurrency and Computation:Practice and Experience,Wiley Press,2002,14(13-15):1175-1220
[49]Howell F,McNab R.SimJava:A Discrete Event Simulation Package For Java With Applications In Computer Systems Modelling[A].In:Proceedings of First International Conference on Web-based Modeling and Simulation[C].USA:Society for Computer Simulation,1998,51-56
[50]刘祥瑞,朱建勇,樊孝忠等.基于GridSim的网格调度模拟[J].计算机工,2006,32(2):42-44
[51]D.Abramson,R.Sosic,J.Giddy.Nimrod:A Tool for performing Parametised Simulations using Distributed Workstations,Proceedings of the 4~(th)IEEE International Symposium on High Performance Distributed Computing,Virginia,August 1995,IEEE CS Press,USA,1995
[52]刘一萌.基于GridSim的网格资源调度算法研究[D].四川:四川大学计算机学院,2004
[2]罗红,慕德俊,邓智群等.网格计算中任务调度研究综述[J].计算机应用研究,2005,22(5):16-19
[3]Ian Foster,Carl Kesselman.Globus:A Metacomputing Infrastructure Toolkit.Intl J.Supercomputer Applications,1997,11(2):115-128
[4]查礼,李伟,余海燕,蔡季萍.面向服务的织女星网格系统软件设计与评测[J].计算机学报,2005,28(4):495-50
[5]Qiao WG,Zeng GS,Hua A,et al.Scheduling and executing heterogeneous task graph in grid computing environment.In:Zhuge Hai,Fox G,eds.Proc.of the 4~(th)Int'l Workshop on Grid and Cooperative Computing(GCC 2005).LNCS 3795,Beijing:Springer-Verlag,2005:474-479
[6]Buyya R.Economic-Based distributed resource management and scheduling for grid computing[D].Melbourne:School of Computer Science and Software Engineering,Monash University,2002:9-46
[7]Fujimoto N,Hagihara K.A.Comparison among grid scheduling algorithms for independent coarse-grained tasks.In:Proc.of the 2004 Symp.on Applications and the Internet-Workshops.Washington:IEEE Computer Society Press,2004:674-680
[8]Maheswaran M,Ali S,Siegel HJ,et al.Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems.In:Proc.of the 8~(th)Heterogeneous Computing Workshop(HCW'99).Washington:IEEE Computer Society Press,1999:30-44
[9]Maheswaran M,Ali S,Siegel HJ,et al.A comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems.Technical Report,School of ECE,Purdue University,1999
[10]Wu MY,Shu W,Zhang H.Segmented Min-Min:A static mapping algorithm for meta-tasks on heterogeneous computing systems.In:Proc.of the 9~(th)IEEE Heterogeneous Computing Workshop.Washington:IEEE Computer Society Press,2000:375-385
[11]Wei TY,Zeng WH,Huang BB.Scheduling algorithm based on modified Min-Min in grid.Computer Applications,2005,25(5):1190-1192(in Chinese with English abstract)
[12]Casanova H,Legrand A,Zagorodnov D,et al.Heuristics for scheduling parameter sweep applications in grid environments.In:Proc.of the 9~(th)Heterogeneous Computing Workshop.Washington:IEEE Computer Society Press,2000:349-363
[13]Zha L,Xu ZW,Lin GZ,et al.Scheduling algorithm for hybrid data and computation intensive metatask in grid.Computer Engineering and Design,2003,24(10):1-4(in Chinese with English abstract)
[14]中国网格信息中转站.中国国家网格的进展[EB/OL]http://www.jtzx.net.cn/cgi-bin/zwolfl/show.cgi?class=1&id=1139,2004-10-12
[15]Berman and R Wolski.The AppLeS Project:A Status Report.Proceedings of the 8th NEC Research Symposium
[16]High Performance Computing Lab.Application-Level Scheduling[EB/OL]http://miles.cnuce.cnr.it/～lafo/domenico/talks/SSGRR2000/sld040.html,2000-7-31
[17]R Buyya,D Abramson,J Giddy.Nimrod/G:Architecture for a Resource Management and Scheduling System in a Global Computational Grid[C].In Proceedings of the 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region(HPCASIA 2000),2000:283-289
[18]Buyya R,Mershed M,Abramson D.A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global Grids[A].In The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA'02),Las Vegas,Nevada,USA,June 2002
[19]Ian Foster,Carl Kesselman.The Grid:Blueprint for a Future Computing Infrastructure.Morgan Kaufmann:San Francisco,CA,1999:259-27
[20]桂小林.网格技术导论[M].北京:北京邮电大学出版社,2005:6-7
[21]冯百明,徐志伟等.网格计算[M].北京:中科院计算所,2002
[22]Ian Foster,Carl Kesselman and S.Tuecke,Grid service for distributed systems integration.IEEE Computer 35(6),2002:37-46
[23]Ian Foster,Carl Kesselman.A distributed resource management architecture that supports advance reservations and co-allocation in International Workshop on Quality of Service,1999:27-36
[24]岑玲.基于简单对象访问协议的分布式计算技术.微型机与应用,2001,12(07):30-31
[25]S.Tuecke,K.Czajkowski,Ian.Foster,J.Frey.Open Grid Services Infrastructure Version 1.0.Globus Grid Forum,Draft draft-ggf-ogsi-gridservice-29,2003.Available at[EB/OL]www.ggf.org/document/Drafts
[26]E.Christensen,F.Curbera,G.Meredith and S.Weerawarana,Web Services Description Language(WSDL)1.1,W3C,Note 15,2001.Available at[EB/OL]www.w3.org/TR/wsdl
[27]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述.计算机应用研究.2005.05
[28]侯小静.基于遗传算法的网格任务调度:[D].新疆:新疆大学计算机学院,2006
[29]Ishohn U S,Yahyapour R,Grid Scheduling Architecture.Global Grid Forum Draft Recommmendation,2002,26(4):21-31
[30]Min-You Wu,Wei shu,and Hong Zhang.Segmented Min-Min:A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems[A].In:proceedings of 9th IEEE Heterogeneous Computing Workshop,2000.(HCW 2000)[C].USA:IEEE Computer Society Press,2000,375-385
[31]Maheswaran M,Siegel H J.A dynamic matching and scheduling algorithm for heterogeneous computing systems[A].In:Proceedings of the 7th IEEE Heterogeneous Computing Workshop(HCW'98)[C].USA:IEEE Computer Society Press,1998:57-65
[32]崔玉宝,贾振华,侯志国,薛桂香.网格任务调度算法研究[J].微计算机信息,2006年15期
[33]Min-You Wu,Wei Shu.Segmented Nin-Min:A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems.Department of Electrical and Computer Engineering University of New Mexico,2000
[34]王翼飞.生物信息学-智能化算法及其应用[M].北京:化学工业出版社.2006:158-161
[35]J.H.Holland,Adaptation in Natural and Artificial Systems,University of Michigan Press.1975
[36]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008:8-13
[37]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999
[38]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004:25-35
[39]李敏强,寇纪淞.遗传算法的基本理论与应用[M].北京:科学出版社,2002:45-46
[40]唐立山等.非数值并行算法(第一册)-模拟退火算法[M].北京:科学出版社,2000
[41]庞峰.模拟退火算法的原理及算法在优化问题上的应用:[D].吉林:吉林大学计算机学院,2006
[42]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002
[43]M.Srinivas,L.M.Patnaik.Adaptive probabilities of crossover and mutation in genetic algorithm.IEEE Transactions on Systems,Man,and Cybemetics,1994,24(4):656-667
[44]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].人民邮电出版社,2001
[45]詹炜,戴光明,龚文引.求解函数优化问题的一种高效混合演化算法[J].计算机工程与应用.2006.2:70-72
[46]周维,罗泽,阎保平.以策略为机制的网格任务调度模型研究[J].计算机工程.2007.7:p89-91
[47]郭茂祖,姜俊峰,李静海.模拟退火算法中冷却调度选取方法的研究[J].计算机工程,2002,26(9):63-64
[48]Buyya R,Murshed M.GridSim:A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing[J].The Journal of Concurrency and Computation:Practice and Experience,Wiley Press,2002,14(13-15):1175-1220
[49]Howell F,McNab R.SimJava:A Discrete Event Simulation Package For Java With Applications In Computer Systems Modelling[A].In:Proceedings of First International Conference on Web-based Modeling and Simulation[C].USA:Society for Computer Simulation,1998,51-56
[50]刘祥瑞,朱建勇,樊孝忠等.基于GridSim的网格调度模拟[J].计算机工,2006,32(2):42-44
[51]D.Abramson,R.Sosic,J.Giddy.Nimrod:A Tool for performing Parametised Simulations using Distributed Workstations,Proceedings of the 4~(th)IEEE International Symposium on High Performance Distributed Computing,Virginia,August 1995,IEEE CS Press,USA,1995
[52]刘一萌.基于GridSim的网格资源调度算法研究[D].四川:四川大学计算机学院,2004