网格环境中一种改进的蚁群任务调度算法

《网格环境中一种改进的蚁群任务调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、网格环境中一种改进的蚁群任务调度算法摘要网格计算环境日益成为一种不受地域限制的廉价的超级计算环境，它试图聚合分布在世界各地的计算、存储、知识、通信和信息等各类资源，以服务大众为目的，实现资源共享与协同工作。但由于网格资源具有异构性、动态性、自治性以及分布性等特点，网格环境下进行任务调度是一个很具挑战性的问题。网格任务调度算法直接关系到任务执行的速度，在网格技术研究中起着重要作用。50年代中期仿生学应运而生，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如遗传算法、神经网络

2、、模拟退火算法等，并成功应用于解决实际问题。近年来，许多学者将蚁群算法应用于网格任务调度技术，并取得了不错的效果。但是目前研究者较少考虑仿生算法初始参数设置对算法收敛性能的影响。在蚁群算法中存在的信息启发因子a、期望因子鼻、信息素强度因子Q、信息素挥发因子P共四个参数中，a反应了蚂蚁受其它蚂蚁经过网格资源节点时留下的信息素影响程度，其值越大，蚂蚁越倾向于选择其他蚂蚁选择过的资源节点，13反应了蚂蚁受资源的固有属性的影响程度，其值越大，蚂蚁越倾向于选择条件好的资源，这两个参数的值越大，蚁群算法极易陷入局部最

3、优。Q能够加强正反馈，使搜索朝有利于寻找最优解的方向进行，P能够避免信息素无限积累，从而扩大搜索范围，以提高求解的效率。本文提出了一种新的改进蚁群算法NACA(newantcolonyalgorithm)，先对蚁群算法中的四个参数进行随机编码，产生染色体，利用蚁群算法得到一组较优解；再利用遗传算法的优点对这组值进行交叉、变异，选择产生更优的解；最后将这组值作为蚁群算法下一轮探索的原始值，进行最大次数的循环迭代直至停止，即求得参数组合的近似最优解。NACA利用遗传算法快速随机的全局搜索能力，以探索出蚁群算法

4、中的四个参数a、鼻、p、Q的优化组合，将它应用于网格系统任务调度中，系统的性能得到了明显的改善。利用网格模拟器GridSim对所提出的算法进行了仿真模拟，结果表明所提出的算法具有更短的调度长度和更宽的适应性，当任务已知时，执行时间约缩短了21．7％，能有效缩短任务的执行时间，且负载变化时对网格中各处理器资源的影响大大减小。然而当任务未知和系统规模很大时，算法需要进一步完善。关键词：网格；任务调度；蚁群算法；GridSimⅡ高校教师硕士学位论文AbstractGridcomputingenvironment

5、hasincreasinglygrownaverycheapsupercomputingenvironmentbeyondarealimit．Itgatherscomputationresources，storageresource，knowledgeresource，communicationresource，andinformationresourceetc．togetherfromallovertheworld，aimsatservingpubfieandrealizingresourcesshar

6、ingandcooperativeworking．However,duetotheheterogeneousdynamic，autonomous，anddistributionandothercharacteristicsingridresources，taskschedulingingridenvironmentisachallengingproblem．TaskschedulingalgorithmforGridschedulingisdirectlyrelatedtothespeed，quality

7、andetc．Itplaysanimportantroleinthegridstudy．Sincebionicswascreatedinmiddleperiodof1950’S，peoplehavebeinginspiredfromthemechanismofthebiologicalevolutionconstantly．Manynewmethodshadbeenappliedtosolvethecomplicatedoptimizationproblemsareproposed．Suchasneura

8、lnetwork，geneticalgorithm，simulatedannealing，andevolutioncomputation．Thesenewmethodshadbeensuccessfullyappliedtosolvethepracticeproblems．Manyscholarsresearchthetaskschedulingalgorithmforthegridtechnology，andhasachie