基于遗传模拟退火算法的网格任务调度研究.pdf

0年易只b口调度研究学号：作者：专业名称：翰：振江计算机应川技术200702052201
／㈣嬲燃论文题目：基于萼佧幽警冬笋滓的|_何何爹塑f芝矽f窖0年钐月协日内蒙古科技大学硕士学位论文单位：笪：垦：：兰：壁堂堕堂丛生丝丝单位：笪：垦：兰狸堂堕王赴：j：刨邀拯协助指导教师：』作者：阴：振江指导教师：论文提交日期：201学位授予单位：内蒙古科技大学一}
内蒙占科技大学信息学院0，P．R．CHNA研岁芒：l姓名：陈振江指导教帅姓名：谭跃生包头014010，中国Zhen-jiangandSchoolMongoliaCandidate：ChenSupervisor：TanYue—shengofInformationEngineeringInnerUniversityScienceTechnologyBaotou01401
导师签名：互陋F1期：o蛔砬仙签名：佴耻签名：翠§豆及扛独创性说明关于论文使用授权的说明Fj期：扬丞：岳：￡』本人郑重声明：所呈交的论文是我个人在导师指导F进行的研究一I：作及取得研究成果。尽我所知，除了文中特别加以标注和敛谢的地办外，论文中小包含其他人已经发农或撰t拍，J研究成果，也不包含为获得内蒙占科技人学或其他教育机构的学位或证书所使用过的材料。与我一同：[作的同志对本研究所做的任何贡献均已在沦义中做了明确的说明并表示，谢意。本人完全了解内蒙古科技大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵循此规定)内‘蒙古科投人学顺Ij学位论文
摘要感器、远端改箭等融为一体，实现它们的全而共享与协同+I：作。H懈fE务调嫂是网格关键字：网格计算；任务调度：遗传算法(GA)；模拟退火(SA)算法；Gridsim网格计算是近年来的研究热点之一。它可将高速互联网、电脑、大型资料库、传计算研究的骸心内容之一，如何合胖地将仟务分配给不n可资源，使整个阳挤系统达剑最佳的性能，这是任务调度需要解决的问题。由于网格自身的分和性、异构性、动念性和自治性，使得传统的渊度算法tfds临新的挑战。冈此，如何在现有调度算法的基础上改进优化，尽t叮能提高网格系统的吞吐量，是一个重要而现实的问题。遗传算法GA(Genetthm)和模拟退火算法SA(Simulateding)是目自玎解决网格任务凋度比较有效的算法。两种算法都是模拟自然界的某螋现象进行人规模优化问题求解的随机性方法，都不要求目标函数的连续性、可微性和凸性。GA有较强的全局搜索性能，但它的爬山能力弱，在实际应用中容易产生早熟收敛的I、uJ题，在进化后期搜索效率较低。而SA却具有摆脱局部最优解的能力，能抑制遗传算法的早熟现象，fEl它的进化速度慢。针对GA早熟收敛和SA进化速度慢的问题，本文结合两算法的各自特点进行改进并设计了一种遗传模拟退火算法GSAA(OeneticA190tithm)。GSAA基本思想是首先充分利用GA的群体性、全局收敛性、随机性、快速搜索等优势生成初始解，即通过GA的遗传操作产生初始解；随后采用SA，对生成的初始解，利用SA的Metropolis准则跳变特性决定是否接受由交叉和变异操作产生的新个体，使得在接受优质解的同时，也有限度的接受劣质解，保证了种群的多样性；采用了自适应交义和变异概率：适当地改进了遗传操作。通过GSAA来求取网格任务调度的最优解。本文深入研究了GA和SA的壤本原理，根据嗍格任务调度的特点，本文在GA和SA基础上改进并设计了GSAA的各个组成部分。在Gridsim网格模拟器中，对GSAA进行了仿真实现，并与GA和SA进行了对比，结果表明本义提出的GSAA具有更好的搜索能力和收敛速度。内蒙占科技人学f{!i¨j学位论义iAlgoriAnnealSimulated一ngC●
厂二二二=三二二二algorithmAnnealingthe鲥dKEYWORDS：GridWithobjectiveAlgorithm)．ThedesignsAlgorithm(GA)；SimulateddevelopmentcomputerwhichoptimizeGA(GeneticAlgorithm)andsimulatedSA(SimulatedAnnealing)arealgorithm．BothalgorithmsmethodsclimbingefficiencyoptimalcombinedGSAA(GeneticSimulatedGA；thenSAMetropolismutationimprovedsolutionAnnealing)thoroughly．Accordingcomponents，andsimulat