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

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

1、·分类号密级UDC编号桂林电子科技大学硕士学位论文题目:基于改进遗传算法的网格任务调度研究(英文)ResearchonGridTaskSchedulingBasedOnImprovedGeneticAlgorithm研究生姓名：张阳指导教师姓名、职务：黄文明副教授申请学科门类：工学硕士学科、专业：计算机应用技术提交论文日期：2009年4月论文答辩时间：2009年6月2009年4月6日···-···独创性（或创新性）声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗

2、列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得桂林电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期：关于论文使用授权的说明本人完全了解桂林电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属桂林电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为桂林电子科技大学。学校有权保留送交论文的复印

3、件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。（保密的论文在解密后遵守此规定）本学位论文属于保密在年解密后适用本授权书。本人签名：日期：导师签名：日期：···-···摘要摘要网格是解决科学计算、工程计算和商业计算等大规模计算的平台。它是下一代互联网技术，把互联网合成一台巨大的超级计算机，从而实现资源的全面共享。在网格计算中，任务管理、任务调度和资源管理是网格必须具备的三个基本功能。网格任务调度的目标是：在复杂的网格动态环境中，同时考虑各网格节点的计算性能、节点之间的通讯性能

4、等参数，把不同的任务以最合理的方式分配到相应的网格结点去完成。网格任务调度是一个NP完全问题。本文分析了网格和网格环境下任务调度的特点，在此基础上给出了网格任务调度问题的有向无环图DAG模型。针对启发式遗传算法早熟收敛的不足，提出了一个改进的具有DNA编码特征的遗传算法。为了保证种群的多样性，提高遗传算法的全局搜索能力，染色体采用DNA编码和解码，这样更符合生物进化规律。然后使用一种基于调度子串合法性判断的初始种群生成方法，并在标准遗传算法的基础上增加新的倒位操作和轮转操作，使网格任务调度取得更优解。另外，本文针对标准遗传算法收敛

5、速度较慢的不足，提出了一种改进的快速收敛的方法，通过调整标准遗传算法结构，增加了对染色体的分割与重组操作，使遗传算法能快速收敛。与标准遗传算法相比，改进的遗传算法更合理地分配了网格资源，从而提高了网格系统的总体性能。本文采用GridSim模拟器构建网格仿真环境，并设计基于图形用户接口的GA模块(GUI-GA)用来设置遗传算法的参数。仿真实验结果表明：改进的DNA遗传算法(DNA-GA)相对标准遗传算法更具有全局解空间搜索的特点，可以有效地缩短网格任务的完成时间，提高网格资源的使用效率。另外，改进的快速收敛方法与标准调度算法相比，提

6、出的算法取得了更好收敛速度。关键词：网格;任务调度;DNA遗传算法;收敛;GridSim···–I–-···摘要AbstractGridisakindofperfectcomputingtechnologyplatform,whichwillbeusedinthefieldsofsciencecomputing,engineeringcomputingandsomeotherlarge-scalecom-puting.GridisthenextgenerationInternet.ItintegratesthewholeIntern

7、etintoagiantsupercomputer,andsharesitsentireresources.InGridcomputing,thetaskmanagement,thetaskschedulingandtheresourcemanagementarethreebasicfunc-tionsthatthegridmusthave.Thepurposeoftaskschedulingistoassigndifferenttaskstocorrespondinggridnoderationally,simultaneousl

8、yconsideringthecomputingperformanceofeachgridnodeandtheparameteramongnodessuchascommunicationperformanceincomplexanddynamicg