基于遗传算法网格任务调度的研究

《基于遗传算法网格任务调度的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文摘要中文摘要网格计算系统实现了不同地理分布的异构资源的共享、选择和聚合，以解决在科研、工程、经济学等领域大规模的计算问题。网格任务调度问题是网格领域的关键问题之一，它是以某一评价指标为依据，针对如何将提交的任务分配到相应的网格资源上运行的问题，提出一个合理有效的调度方案。调度策略的优劣决定了是否能够高效合理地分配和利用网格资源，减少网格任务的总体计算时间和花费，使得网格的性能达到最佳。网格环境下的任务调度问题是网格计算的研究热点之一。论文重点研究了以下几方面的内容：①在综述网格计

2、算的研究背景及意义的基础上，较全面地分析了网格任务调度的特点及其常用的调度算法。②提出了一种改进的基于遗传算法的网格任务调度算法，在算法的初始化种群产生时引入Min-Min算法和Max-Min算法以及采用Hamming距离来控制个体之间的差异，从而在提高初始种群质量的同时保证了种群的多样性；在算法的迭代过程中提出了一种新的局部收敛判定标准以及相应的变异操作来防止算法的局部收敛。③在本文的任务调度算法中采用DAG（DirectedAcyclicGraph）模型来描述并行任务之间的约束依赖关系，DAG模型更能

3、真实地反映并行任务的实际情况，此外本文中的算法设计还考虑了处理器异构等因素。④构建现实当中的网格环境不仅花销昂贵，而且时间上也不允许，且网格资源还具有多样性和动态性等特性，因此利用实际网格系统来测试网格任务调度算法的性能和效率是不现实的，也是很困难的。一般地，我们借助网格模拟工具来进行相应的仿真试验。作者利用GridSim网格模拟器对本文改进的网格任务调度算法进行了仿真实验，从最优跨度的角度对实验结果进行详细的对比和分析。实验结果表明，本文改进后的种群初始化方法不仅能够提高算法的寻优起点，而且能够加快算法

4、的寻优速度；改进后的局部收敛判定标准及相应的局部收敛变异操作在预防早熟局部收敛的同时能够提高算法的全局寻优能力；改进后的基于遗传算法的网格任务调度算法相比于基于自适应遗传算法的调度算法，能够有效地缩短任务的总体执行时间，并且在大规模的网格任务调度环境下具有良好的性能，能够在实际网格环境中加以应用。关键词：网格，任务调度，遗传算法，局部收敛I重庆大学硕士学位论文英文摘要ABSTRACTGridcomputingisbecomingamoreandmoreimportantinthehighperforma

5、ncecomputingduetothefactthatitenablesthesharing,selection,andaggregationofgeographicallydistributedheterogeneousresourcesforsolvinglarge-scaleproblemsinthefieldofscience,engineering,andcommerce.Taskschedulingisanimportantpartofgridcomputing.Gridtaskschedu

6、lingresolveshowtoreasonablyassigngridresourcestotasks,andhowtoscheduleeverytasktotheassignedgridresources.Agoodschedulingpolicycanimprovetherationalallocationandefficientuseofgridresourcesandreducestheoverallgridtaskcomputingtimeandcost,makingthebestperfo

7、rmanceofthegrid.Sotaskschedulingundergridenvironmentsisoneofthekeyresearchfieldsofgridsystems.Themainresearchworksofthispaperarelistedasfollows:①Thefeaturesandcommonschedulingalgorithmsofgridtaskschedulingareanalyzedthroughsummarizingtheresearchbackground

8、andsignificanceofgridcomputing.②Animprovedgridtaskschedulingalgorithmbasedongeneticalgorithmisproposed.Intheprocessofpopulationinitialization,anewmethodwhichcombinestheMin-MinalgorithmandtheMax-Minalgorithmisaddress