基于混合蚁群算法的网格任务调度研究

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

1、哈尔滨T稗人学硕士学位论文立每个资源的初始信息素。每只蚂蚁根据概率公式选取一个资源作为第一个任务分配的资源，并按根据信息素计算出的概率寻找下一个任务的分配节点，直至所有任务分配完毕。然后进行信息素更新，按照新信息素重新构建解，直到满足算法结束条件为止。但是蚁群算法在中后期易陷入局部最优，并且不能很好的兼顾到资源的负载平衡。1．2．2依赖任务调度算法依赖任务调度指的是任务之间存在优先约束关系，即任务的执行要按照一定的顺序进行。目前，最典型的依赖任务调度算法是Carter等人在1999年提出的分代调度算法和优化分代调度

2、算法。(1)分代调度算法分代调度算法【5J(GenerationScheduling，GS)的思想是将依赖任务集合转化成若干内部包含独立任务的任务集合。在算法中，任务按照依赖关系进行过滤，将相对独立的任务构成一个调度子集，在这个子集中使用快速贪吃算法进行任务映射。GS算法按照依赖性不断过滤出互不相干的任务进行调度，直到所有全部任务被指派为止。(2)优化分代算法优化分代算法【5J(OptimizationGenerationScheduling，OGS)是在分代算法的基础上进行优化形成的算法，基本思想是过滤出全部源节

3、点，对这些节点使用Min．Min算法、Max．Min或Max．Int算法，得到每个机器的预测就绪时间，并记录每个源节点所对应的任务的完成时间及其机器，并分别存储到两个局部向量之中。然后，将调度集合中的任务按照优先级数进行调度，直到所有任务分配完毕为止。1．3论文的主要工作和组织结构本文介绍了课题的研究背景、意义和目前网格任务调度研究现状，介绍蚁群算法和禁忌搜索算法的原理，分析这两种算法的优点和局限性；给出了基于禁忌搜索的混合蚁群算法，分析网格任务调度的流程和特点，以此为基础讨论利用混合蚁群算法解决网格任务调度的可行

4、性；建立网格任务调度的4哈尔滨丁稃大学硕十学位论文数学模型，实现基于混合蚁群算法的网格任务调度；最后利用网格仿真工具对算法进行仿真实验并对实验结果进行分析。各章内容安排如下：第1章：介绍课题的研究背景、研究意义，介绍目前网格任务调度算法的国内外研究现状，给出论文的主要工作和论文的组织结构。第2章：重点介绍蚁群算法和禁忌搜索算法的理论知识、基本思想和流程，针对蚁群算法的缺点，提出了蚁群算法的改进措施。第3章：重点内容包括基于禁忌搜索算法的混合蚁群算法研究、对混合蚁群算法中的参数对算法性能的影响进行了分析并介绍了算法中

5、参数的设置。第4章：主要内容包括利用混合蚁群算法进行网格任务调度的可行性分析，给出相应的网格任务调度的数学模型、介绍算法实现的流程、网格任务调度过程中应该考虑的因素和针对这些因素对信息素和信息素更新规则的改进，并给出部分伪代码。第5章：重点内容包括介绍网格仿真工具选择和介绍，实验环境的搭配，进行仿真实验并对实验结果进行分析。哈尔滨T程大学硕十学位论文第2章蚁群算法和禁忌搜索算法2．1蚁群算法20世纪90年代初期，意大利学者DorigoM等从蚂蚁的觅食行为中受到启发提出了蚁群优化(AntColonyOptimizat

6、ion，ACO)算法。蚁群算法具有分布式、正反馈和启发式搜索的特性，是一种基于群体智能的启发式算法，在解组合优化问题方面取得了较好的成果【ll】。2．1．1蚁群行为描述自然界中的蚂蚁在觅食过程中，在经过的路径上留下一种称之为信息素(pheromone)的化学物质，这种物质及其强度能被其他蚂蚁感知，作为一种信息影响后者的行为，具体表现在蚂蚁根据信息素强度按照伪随机概率规则选择路径。蚂蚁个体之间通过这种信息交流寻找到达食物源的最短路径‘12，131，通过下面的例子来了解一下蚁群算法的工作原理，如图2．1所示。HCHC图

7、2．1蚁群算法工作原理蚂蚁要从巢穴A去食物源E。沿途中H、C为障碍物(图2．1(a))，蚂蚁在B点选择经由H或者C到达D，从而到达E。蚂蚁依据其他蚂蚁在路径BHD和BCD上遗留的信息素浓度的大小选择路径。假定距离dBH-dDH=1，dBC=dDc=O．5。假设每个单位时间内有30只新蚂蚁从B至WJD，同时有30只新蚂蚁从D到B。初始时刻，路径上的信息素的量为O。每只蚂蚁释放的信息素的迹为1。f=0时，6哈尔滨]：程大学硕十学位论文各条路径上信息素的迹均为0，30只蚂蚁在点B，30只蚂蚁在点D，每只蚂蚁可随机地选择哪

8、条路径，从统计学的角度可以认为此时选择BC，BH，DC，DH的蚂蚁数均为15(图2．1(b))；f=1时，BH上面的信息素的浓度为15，BC上的浓度为30(15只蚂蚁经由cN达B，并且有15只蚂蚁经由cN达了D)。假设此时在B和D点上又各有30只新蚂蚁选择路径，则B点有20只选择路径BCD，只有10只选择路径BHD，D点有20只选择路径DCB，只有10只选择