基于GridSim的启发式网格任务调度算法的仿真---毕业论文

本 科 毕 业 论 文基于GridSim的启发式网格任务调度算法的仿真 Simulation of Task scheduling on GridResource with heuristic algorithm based on GridSim姓 名： 学 号：学 院：软件学院系：软件工程专 业：软件工程年 级：校内指导教师： 年 月摘要网格计算是当今计算机科学领域兴起的一项有很高学术价值和应用价值的研究课题。网格是以资源共享为目的，支持对各种资源的远程和并发访问，利用互联网把地理广泛分布的各种资源连成的一个具有单一系统镜像的高性能计算和信息服务环境。任务调度技术是网格核心服务之一。在网格计算环境中，如何协调和分配网格资源，以便使网格计算性能趋于最优，是任务调度算法要解决的基本问题。而网格中的资源具有分布性、动态性、多样性、自治性以及管理的多重性等特征，这就决定了网格环境下的任务调度与资源管理问题的复杂性和网格资源调度策略的重要性。本文对网格任务调度问题进行了初步研究，并且基于GridSim工具，应用遗传算法、蚁群算法和粒子群算法对网格任务调度过程进行了仿真。主要工作包括三个方面：第一，在独立子任务的前提下，设计了基于遗传算法、蚁群算法以及粒子群算法的网格资源调度模型；第二，针对子任务含有优先顺序的情况，改进了遗传算法的网格资源调度模型；第三，采用GridSim搭建资源调度的仿真平台，用Java实现了上述模型，并进行了性能比较。本文从网格计算的基本概念出发，介绍了网格体系结构和网格任务调度问题的定义。然后，概述了遗传算法、蚁群算法和粒子群算法的基本流程及主要思想，详细介绍了三种算法在独立子任务情况下的资源调度策略的设计原理以及遗传算法在子任务含有优先顺序时的调度原理。最后，论文给出了上述模型在GridSim工具中的仿真结果，并以跨度、平均响应时间、吞吐量及算法执行时间作为评价指标对各种算法的性能进行了比较。本文在结论部分对全文所做的工作进行了总结，并指出了下一步的研究方向。关键词：网格任务调度；GridSim；遗传算法；蚁群算法；粒子群算法AbstractGrid Computing is one rising research subject in computer science with high academic and application value. Aimed at resources sharing, it supports remote and distant visit of various resources, using Internet to connect resources in geographical scattered locations into a single computing environment providing information service with high performance. Task scheduling is one of its nuclear services. How to coordinate and distribute grid resources in an effort to realize more optimized performance becomes a very basic problem in grid task scheduling. Moreover, given its distributivity, diversity, dynamics, autonomy and managerial multiplicity, grid task scheduling appears more complicated, and scheduling policy more important.This dissertation has a preliminary research on grid task scheduling. Using GridSim, it simulates the process with three algorithms: Genetic Algorithm, Ant Colony Algorithm and Particle Swarm Optimization. Work has been done mainly in the following areas: Firstly, under the prerequisite of independent gridlets, it designs grid task scheduling models based on Genetic Algorithm, Ant Colony Algorithm and Particle Swarm Optimization. Secondly, it improves the GA model a little adapting to situations where gridlets are in order. Thirdly, applying Java on GridSim platform, it simulates the foregoing models and has their performance compared.Proceeding from concepts of grid, this dissertation introduces definition of grid architecture and grid task scheduling. It then elaborates on basic processes of the three heuristic algorithms, their application in grid resource scheduling models with independent gridlets and scheduling principles of GA with ordered gridlets. Finally, this dissertation shows performance of above models in simulation with GridSim. Performances of these models are compared with indicators like Makespan, average response time, throughput and algorithm execution time. The final part presents the summary of entire dissertation and outlines work to be done in the next stage.Key words: Grid task scheduling ; GridSim ; Genetic Algorithm ; Ant Colony Algorithm ; Particle Swarm Optimization目 录第一章 绪论11.1引言11.2论文组织结构2第二章 网格计算与任务调度32.1 网格计算系统32.1.1 网格的基本概念32.1.2 网格的体系结构32.2 任务调度的基本问题52.2.1 任务调度的定义52.2.2 网格任务调度概述62.2.3 网格任务调度的问题定义62.3 启发式算法与任务调度7第三章 基于遗传算法的网格资源调度策略83.1 遗传算法综述83.2 遗传算法的基本流程83.3 基于遗传算法的网格任务调度的设计93.3.1 染色体的编码与解码93.3.2 种群初始化103.3.3 适应度函数113.3.4 选择操作113.3.5 交叉操作123.3.6 变异操作123.3.7 控制参数133.4 基于任务优先顺序的遗传算法的网格任务调度的设计14第四章 基于蚁群算法的网格资源调度策略164.1 蚁群算法基本原理164.2 基于蚁群算法的网格任务调度的设计174.2.1 资源选择策略184.2.2 资源处理策略214.2.3 调度算法性能评估224.2.4 系统参数调整22第五章 基于粒子群算法的网格资源调度策略245.1 粒子群算法的系统模型245.2 基于粒子群算法的网格任务调度的设计265.2.1 位置与速度的定义265.2.2 更新规则定义265.2.3 算法执行流程27第六章 基于GridSim的仿真实验及结果比较286.1 网格模拟器 GridSim286.1.1 GridSim的体系结构286.1.2 GridSim中的网格资源调度过程296.2 仿真实验及结果分析306.2.1 性能评价指标306.2.2 基于独立子任务的遗传算法、蚁群算法及粒子群算法的调度结果比较316.2.3 基于优先顺序的遗传算法的调度结果38结 论44参考文献46致 谢47ContentsChapter 1 Preface11.1 Introduction11.2 Structure of paper2Chapter 2 Grid architecture and task scheduling32.1 Grid Computing System32.1.1 Basic concept of grid32.1.2 Grid architecture32.2 Fundamentals of task scheduling52.2.1 Definition of task scheduling52.2.2 Overview on grid task scheduling62.2.3 Problem definition of grid task scheduling62.3 Heuristic algorithm and task scheduling7Chapter 3 GridResource scheduling policy with Genetic Algorithm83.1 Overview on Genetic Algorithm83.2 Basic process of Genetic Algorithm83.3 Design of grid task scheduling policy with Genetic Algorithm93.3.1 Coding and decoding of chrosome93.3.2 Colony Initialization103.3.3 Fitness function113.3.4 Seletion operation113.3.5 Cross over operation123.3.6 Mutation operation123.3.7 Control parameter133.4 Design of grid task scheduling policy based on GA with order14Chapter 4 GridResource scheduling policy with Ant Colony Algorithm164.1 Basic principles in Ant Colony Algorithm164.2 Design of grid task scheduling policy with Ant Colony Algorithm174.2.1 Resource selection policy184.2.2 Resource processing policy214.2.3 Performance assessment224.2.4 Ajustment of system parameter22Chapter 5 GridResource scheduling policy with Particle Swarm Optimization245.1 System model of Particle Swarm Optimization245.2 Design of grid task scheduling policy with PSO265.2.1 Definition of position and speed265.2.2 Definition of updating rules265.2.3 Algorithm process27Chapter 6 Simulation with GridSim and performance comparison.286.1 GridSim: Grid Simulator286.1.1 Architecture of GridSim286.1.2 GridResource scheduling process with GridSim296.2 Simulation and performance comparison306.2.1 Performance indicator306.2.2 Performance comparison among GA, ACA and PSO without order316.2.3 Performance of Genetic Algorithm with ordered gridlets38Conclusion44Referential documentation46Acknowledgement47Error! No text of specified style in document.第一章 绪论1.1引言随着信息技术的普及与发展，网格计算作为一种新兴的计算模型得到了人们的广泛关注，成为当前互联网研究的热点问题，也是并行和分布式处理研究的一个发展方向。网格试图实现互联网上所有资源的互通互联，形成对用户相对透明的虚拟的高性能计算环境，最终实现网络虚拟环境上的资源共享和协同工作，有效地提供计算服务、内容服务和存储服务等。清华大学李三立院士将网格与信息高速公路作了比较，他说：“将先进计算基础设施（网格）与信息高速公路相比较，可以说，信息高速公路是信息传输和获取的信息基础设施；而先进计算基础设施则是信息处理的信息基础设施。”中科院计算所李国杰院士认为：“网格不同于国外正在搞的Internet 2或下一代Internet(NGI)，网格可以称作是第三代Internet，其主要特点是不仅仅包括计算机和网页，而且包括各种信息资源，例如数据库、软件以及各种信息获取设备等，它们都连接成一个整体，整个网络如同一台巨大无比的计算机，向每个用户提供一体化的服务。”在网格计算环境中，资源是分散在各个不同地域和管理域中，由不同的组织拥有和操作，并且在使用策略和安全机制上各不相同，即不同站点可能会使用不同的局部资源管理系统。同时，很多应用需要同时使用多个站点上的资源，站点自治性和分配资源时可能出现的故障需要一种特殊机制来同时分配位于多个站点上的资源1。因此，资源管理成为网格计算的核心问题之一。能否以最小的处理时间和最低的资源开销完成资源分配决定了网格系统性能的好坏。高效的调度算法应当可以充分利用网格系统的处理能力，提高整个网格系统的吞吐量。然而，网格任务调度问题已被证明是一个NP完全问题，关于它的研究颇具挑战性。网格资源的广域分布、自主管理、本质上异构和负载动态变化等特性，使得网格环境下的任务调度比传统分布式环境要复杂得多。因此，设计一种网格环境下高效的调度算法对提高网格资源利用率以及网格系统的吞吐量有十分重要的意义。启发式算法是解决NP完全问题的一个有效途径。它是根据问题的性质和特点，基于一些直观的启发，在可行解基础上逐步优化，以便尽可能逼近最优解的近似算法。该技术没有能力去保证可行性或最优性或者甚至在许多情况下没有能力去规定一个特定可行的方法是多么接近最优性。尽管启发式算法在数学上尚不能令人满意，但在实际应用是确实是有效、可行的。因此，本文探索性地采用了三种启发式算法：遗传算法、蚁群算法和粒子群算法对网格任务调度问题进行了研究，并在GridSim工具中进行了仿真。1.2论文组织结构本论文共分为五章，论文首先就网格计算的基本概念及其体系结构予以介绍，并详细探讨了两个比较重要的网格体系结构，引进了网格任务调度问题的定义，提出了仿真实验的一些假设。然后，本文对三种启发式算法：遗传算法、蚁群算法和粒子群算法的基本原理进行了概述，并基于三种算法的原理设计了相应的网格资源调度模型。最后，本文使用GridSim工具，用Java语言实现了上述模型，选取了跨度、平均响应时间、吞吐量和算法执行时间作为评价指标，并进行了性能比较。论文具体安排如下：第一章 简单介绍了网格和网格体系结构的概念，详细描述了五层沙漏结构和基于WebService 的开放式网格体系结构。提出任务调度和网格任务调度问题的定义，介绍启发式算法的基本特征。第二章 对遗传算法的基本流程、五个基本要素及参数选择机制进行了研究，设计了基于遗传算法的网格资源调度模型；另外，对子任务含有优先顺序的情况予以考虑，设计了基于子任务优先顺序的遗传算法调度模型。第三章 对蚁群算法的基本原理、资源的选择和处理策略及算法性能的评估机制进行了研究，设计了基于蚁群算法的网格资源调度模型。第四章 对粒子群算法的系统模型、速度和位置的定义及更新规则等进行了研究，设计了基于粒子群算法的网格资源调度模型。第五章 给出了仿真实验的结果及性能比较，包括在子任务独立情况下遗传算法、蚁群算法和粒子群算法执行情况的比较以及在子任务含有优先顺序情况下三种顺序：横向、纵向、分支顺序对执行结果的影响的比较。第二章 网格计算与任务调度2.1 网格计算系统2.1.1 网格的基本概念网格这一术语于20世纪90年代中期提出，用来表述一种适用于高端科学和工程的分布式计算体系结构。基于充分利用网络化资源达到高效率低成本计算目标的理念，网格技术提供了共享和协调使用各种不同资源的机制。当前的Internet技术实现了计算机硬件的连通，Web技术实现了信息的共享，而网格技术将整个互联网整合成一台巨大的超级计算机，以实现计算资源、存储资源、数据资源、知识资源和专家资源的全面共享与协同。当然，网格并不一定非要如此庞大，人们也可以构造地区性的网格、企事业内部网格、局域网网格，甚至家庭网格和个人网格。网格的根本特征不在于它的规模，而是以下技术特征：资源共享、消除资源孤岛，协同工作；通用开放标准，非集中控制，非平凡服务质量；开放式系统、单一系统映像2。2.1.2 网格的体系结构网格体系结构是划分网格系统基本组件、指定系统组件的目的与功能、说明组件之间如何相互作用的技术。它是网格的骨架和灵魂，是网格最核心的技术。目前比较重要的体系结构包括Lan Foster等提出的五层沙漏体系结构和结合Web Service的开放网格体系结构OGSA。五层沙漏结构五层沙漏结构(如图2-1所示)是影响十分广泛的以协议为中心的层次结构，分为构造层、连接层、资源层、汇集层和应用层。它定义了每一层的运行机制、接口、模式和协议等，支持资源提供者和用户之间通过协商建立资源共享关系。下面简要介绍该体系结构模型。图2-1 网格的五层沙漏模型(右侧为TCP/IP网格协议模型)(1) 构造层(Fabric)：提供一套对局部资源控制的工具和接口；对所控制的共享资源进行局部管辖和调度；实现各种资源本身的一些控制管理机制。(2) 连接层(Connectivity)：是网格中处理通信与授权控制的核心协议层，定义基本的通信和认证协议，这些协议针对专门的网格服务定义。(3) 资源层(Resource)：定义了单个资源的共享操作协议，包括安全协商、初始化、监测、控制、记账和付费等；可以远程统一的访问和共享操作资源。(4) 汇聚层(Collective)：负责全局资源的管理和资源集之间的交互。该层使用部分资源层协议和连接层协议以实现多种不同的资源共享行为。(5) 应用层(Application)：虚拟组织中的所有用户应用构成了网格的应用层，它调用下一层次中的服务来提供网格系统开发和应用开发的工具、环境。基于Web Service的开放式网格体系结构开放网格服务结构OGSA(Open Grid Services Architecture，如图2-2所示)是由GGF(Global Grid Forum)的Open Grid Services Infrastructure(OGSI)工作小组于2002年6月制定的。OGSA是以服务为核心的体系结构，其目标包括使网格应用的所有服务标准化；在多个自治管理域间实现网格自治；定义开放的和公共的接口；充分利用行业标准的集成技术。在层次结构上，OGSA架构从下到上分为4层：资源层、Web服务层、基于OGSA平台的服务层、应用程序层，核心层是Web服务层和OSGA服务层。Web服务层主要指OSGI服务和Web服务资源框架(Web Services Resource Framework，WSRF)。OGSI/WSRF为网格系统提供包括描述和发现服务属性、创建服务实例、管理服务生命周期、管理服务组以及发布和订阅服务同质等标准接口及相关行为，支持创建、管理网格服务，包括策略服务、注册服务、服务级别管理以及其他网格服务，从而在构造网格系统时可以实现代码重用和组件互操作。应用程序层使用底层的平台核心组件可以构建用于共享资源与协同工作的网格应用3。图2-2 OGSA网络体系结构模型2.2 任务调度的基本问题2.2.1 任务调度的定义在分布式计算系统中，一个程序可以看作是一个任务集，这些任务依据一定的优先次序串行或并行地执行。任务调度问题即如何调度应用程序到各种异构资源上，其目标是要在满足一定的性能指标和优先约束关系的前提下，将可并行执行的任务按适当分配策略确定一种执行顺序，合理地分配到各处理机上有序执行，从而减少执行时间，提高处理机效率。调度质量以产生的优化调度的性能为基础来衡量；调度算法的效率以时间复杂度为基础来衡量。也就是说，以优化同一个程序的执行时间来衡量，则完成时间越短越好；以相同执行时间完成的两个调度算法，则算法越简单越好。2.2.2 网格任务调度概述网格任务调度定义为将网格作业映射到多个管理域的资源上的过程。任务调度是网格系统中极其重要的组成部分，需要根据任务信息采用适当的策略把不同的任务分配到相应的资源节点上去运行。由于网格系统的异构性和动态性，以及运行于网格系统中的应用程序对于资源的不同需求，网格任务调度变得十分复杂，不好的任务调度策略，将会增加任务的执行时间，降低整个网格系统的吞吐量。网格任务调度通常由四个部分组成：资源发现、资源匹配、调度产生和任务执行。资源发现即在所有可用的资源中找出满足任务要求的资源；资源匹配是从发现的资源中找出一个最适合的资源分配给任务；调度产生主要是对作业进行选择和产生资源选择方案；任务执行部分按照资源选择方案把任务传送到相应的资源上去执行。由于网格系统具有动态、异构、广域的特点，在网格计算系统下，任务调度需要考虑任务特性、机器特性等，为不同任务匹配不同的资源，从而提高系统资源的利用率和任务的执行效率。2.2.3 网格任务调度的问题定义网格系统中的资源包括处理器、存储器、各种输入输出设备等，且每种类型的资源都有数量的限制。为研究方便，本文在仿真实验的过程中进行了适当假设，其中包括：(1) 已将一个大型的计算程序分解成很多子任务，用户提交任务时可以对子任务关系进行定义。(2) 采用批处理模式。这种模式下的调度算法可以利用充足的资源信息，做出足够合理的任务映射策略。(3) 各个子任务在不同资源上运行所需要的时间已知。(4) 资源是时间共享还是空间共享随机产生，且均为单处理器。(5) 不考虑子任务所占用的存储资源和传输延迟，即只考虑子任务消耗的计算资源。 下面给出网格任务调度的问题定义：(1) n个任务的集合 T=T1,T2,Tn(2) m个资源的集合 R=R1,R2,Rm(3) 一个m*n的矩阵Wm,n，Wj,i为任务Ti在处理机Rj上的运行时间假设用户向网格系统提交了一个大型的计算任务，若A为一个有效的调度策略，设CA(Ri)表示在调度策略A下，资源Ri完成分配到该资源执行的最后一个子任务所需要的总时间。若C(A)表示在调度策略A下花费的总时间，计算C(A)如公式(2-1)所示。CA=max(CARi,i(1im) (2-1)网格任务调度要解决的问题就是找到一个调度策略A，使得C(A)最小4。2.3 启发式算法与任务调度启发式算法是一种基于直观或经验构造的算法，用来在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解，但该可行解与最优解的偏离程度事先不一定可以预计。因此，启发式方法并不总能得到期望的结果，但是它可以使得解决问题的过程尽可能的有意义。好的启发式算法可以通过避免考虑不可能发生的情况或不相关的状态来减少解决问题所需要的时间。尽管启发式算法在数学上尚不能令人满意，但在实际应用中是确实有效、可行的。对于一般的调度问题，由于应用领域的假设和实际情况的复杂性，很多调度问题都是NP-完全的，且非常难以处理，需要使用启发式方法才能在合理时间内完成。但使用了这些启发式方法也不一定能求得最优解，一般只能求得满意解。目前用于求解调度问题的启发式算法有很多，包括人工免疫算法、遗传算法、蚁群算法和模拟退火算法等。本文将基于遗传算法、蚁群算法和粒子群算法展开对网格任务调度的仿真实验。第三章 基于遗传算法的网格资源调度策略3.1 遗传算法综述遗传算法(Genetic Algorithm，简称GA)是一种模拟生物界自然选择思想和遗传机制的自适应启发式全局搜索算法，是由美国密歇根大学的J.H.Holland教授于1975年提出的5。遗传算法在本质上是一种概率搜索算法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则；具有内在的隐并行性和更好的全局寻优能力；通过一定的方式设计遗传算法，可以保证其收敛到全局最优解。近年来，越来越多的国内外学者开始关注和研究遗传算法，使其在组合优化、机器学习、信号处理、自适应控制和人工生命等领域得到了广泛的应用。遗传算法成为现代人工智能和分布式计算中的关键技术之一。3.2 遗传算法的基本流程遗传算法的基本流程是根据问题的目标函数构成一个适应度函数(Fitness Function)，对一个由多个解(每个解对应一个染色体)构成的种群进行评估、遗传运算和选择，经多代繁殖，获得适应值最好的个体作为问题的最优解6。标准遗传算法的算法描述如图3-1所示。算法执行时，首先应对可行域中的点进行编码，然后自可行域中随机挑选一组编码作为进化起点的初始种群，并依据适应度函数计算每个编码的适应度。接着利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本，而适应度较低的解则保留较少的样本，直至被淘汰6。接下去的交叉和变异操作对经过选择的样本进行变换。交叉算子交换随机选择的两个编码的某些位，变异算子对编码中随机挑选的某一位进行变换，如此产生下一代的编码组。将新一代的编码组加入到初始种群中后，即可进行下一次迭代，重复选择、交叉、变异的繁殖过程，直至进化终止条件得到满足为止。进化结束时最后一代种群中适应度值最大的个体即为利用遗传算法解最优化问题所得到的最终结果。Begin 生成初始种群 While 不满足进化终止条件 do For i=1 to 种群规模 do 按照一定的交叉概率进行交叉操作； 按照一定的变异概率进行变异操作； End for 计算个体适应度值，按照一定的选择概率选择产生新的下一代的个体； 将新的个体加入到上一次迭代产生的种群中 End while 将进化终止时种群中的最优个体为最终解End图3-1 标准遗传算法的算法描述3.3 基于遗传算法的网格任务调度的设计网格计算中的任务调度在一般形式下是一个NP问题，而遗传算法原理简单，具有并行性和全局解空间搜索的特征，因此非常适合用来求解任务调度问题。在遗传算法的实现过程中，主要涉及五个基本要素：染色体编码、种群初始化、适应度函数、遗传算子和控制参数。下面针对这5个要素介绍将遗传算法应用于网格任务调度中的详细设计。3.3.1 染色体的编码与解码使用遗传算法时，需要把优化问题的每一个解的参数形式转换为基因码串的表现形式，这一转换操作称作编码。码串中的每一位代表一个基因，一个基因码串代表问题的一个解，每个基因码串称为一个个体，即染色体。目前，人们提出了很多染色体编码方案。总的来说，分为三大类：二进制编码方法、符号编码方法和浮点数编码方法。二进制编码是遗传算法中最常用的一种编码方法，即由二进制符号0和1组成编码符号集，将原问题的解映射为0和1组成的位串，然后在位串空间上进行遗传操作7；符号编码以特定的符号进行编码，将原问题的解映射为特定符号的各种组合，为每种组合赋予一定的意义；浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点数表示，个体的编码长度取决于决策变量的个数。由于遗传算法不能直接作用于问题空间的解，所以必须通过编码过程将问题的解表示成染色体。本文采用资源任务的间接编码方式，即用一维整数表示染色体，其长度等于全部子任务的个数。染色体中每个基因值都是正整数，每个基因座的编号代表子任务的编号，而该基因座的基因值为该子任务分配到的计算资源编号，如图3-2所示。2 3 1 3 2 1 1 2 3 1 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10图3-2 染色体编码实例图假设有10个子任务，3个可用计算资源，则染色体x含有10个基因，每个基因值的范围为1，3，染色体x所代表的意义是子任务T1调度到资源R2、子任务T2调度到资源R3，子任务T10调度到资源R1。染色体的解码过程体现为从基因型到表现型的映射，即将遗传空间映射到问题域的解空间的过程。仍以上面的染色体为例，由上面的基因串可以看出，在资源R1、R2、R3上执行的任务的集合分别为：R1:3 6 7 10 R2: 1 5 8 R3:2 4 9由此得到了在每个资源上执行的任务序列。3.3.2 种群初始化种群初始化的方法通常有两种：一种是完全随机的方法，它适用于对问题的解无任何先验知识的情况；另一种是由某些先验知识转变为必须满足的一组要求，然后在满足这些要求的解中再随机地选取样本8。本文选用后者进行任务调度的仿真。记群体规模为M，资源数为m，子任务的个数为n，则种群的初始化描述如下：由系统随机产生M个染色体，染色体的长度为n，染色体中的每个基因值随机地在1，m中选择。如有5个资源，则基因值在1，2，3，4，5中随机选择。3.3.3 适应度函数适应度用来度量群体中各个个体在优化计算中能达到或接近于最优解的优良程度，用适应度函数f(x)来描述。适应度较高的个体遗传到下一代的概率较大。适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。本文以获得最小调度时间为最优目标，因此得出目标函数如公式(3-1)所示。Fx=maxj=1nEi,j (3-1)其中F(x)表示的是在m个资源上最后一个子任务完成的时间。同时，为保证目标函数的优化方向与种群进化过程中适应值增加的方向一致，将适应度函数设计如公式(3-2)所示。f(x)=1Fx=1/maxj=1nEi,j (3-2)3.3.4 选择操作从群体中选择优胜个体，淘汰劣质个体的过程叫做选择。选择的目的是为了从当前群体中选出优良的个体，使他们有机会作为父代繁殖下一代子孙。标准遗传算法采用的是按比例的适应度分配，利用个体的适应度值fi，考察比例于各个个体适应度的概率以决定其子孙的遗留可能性。即如果某一个体i的适应度为fi，则其被选取的概率如公式(3-3)所示。 Pi=fit=1Mft (3-3)本文的选择操作采用“轮盘赌”策略。具体操作步骤如下：(1) 依据公式(3-2)计算每个染色体的适应度值fi，i=1，2M；(2) 依据公式(3-3)计算每个染色体的选取概率pi，i=1，2，3M-1；(3) 计算每个染色体的累积概率qi，i=1，2，3M-1，如公式(3-4)所示。 qi=j=1ipi (3-4)(4) 在0，1区间内产生一个均匀分布的随机浮点数r，选择满足qir的第一个染色体；(5) 不断的重复第(4)步，直到选择的个体数达到M-1。3.3.5 交叉操作在遗传算法中，交叉操作是产生新个体的主要方法。所谓交叉，是指按交叉概率pc随机选择经过选择操作产生的父代群体中的两个个体，随机地交换部分染色体基因产生两个新个体。它是遗传算法中起核心作用的遗传操作。标准遗传算法中的交叉操作采用单点交叉，即等概率地随机确定一个基因位置作为交叉点；实施交换时，该交叉点后的两个个体的部分结构互换，形成两个新个体，如图3-3所示。 图3-3 单点交叉操作示意图本文采用改进的单点交叉方式，即交叉染色体个体的同时交叉相邻染色体的基因值。取交叉概率Pc为0.6，交叉操作步骤如下：(1) 对于种群中的每个染色体，在0M区间内随机地产生另一个染色体与之交换。(2) 对于交换后的每个染色体，在0，1区间内随机地产生一个浮点数p，若pPc，交换该染色体中的基因值。(3) 对于需要交换基因值的染色体，在0m区间内随机地产生一个正整数，作为交叉位置；交换该染色体和下一个染色体在该交叉位置上的基因值。3.3.6 变异操作变异是一个重要的遗传机制，可以改善遗传算法的局部搜索能力。在使用交叉算子后，遗传算法已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题的最优解。但仅使用交叉算子无法对搜索空间的细节进行局部搜索。这时再使用变异算子对个体编码串中的部分基因值进行调整，就可以从局部的角度出发使个体更加逼近最优解，将搜索空间扩大到整个空间。此外，变异操作还有助于维持种群的多样性，防止早熟现象的出现。变异操作主要包括基本位变异、边界变异、均匀变异等。标准遗传算法采用基本位变异，即先以概率Pm在种群中随机选择参与变异的染色体个体作为父代；然后随机地确定父代发生变异的基因位置，再对基因值进行变换。在变异操作中，变异概率Pm的选取尤为重要。如果Pm大于0.5，遗传算法就退化为随机搜索，遗传算法的一些重要的数学特征和搜索能力也不复存在了。本文中变异概率Pm为0.01，具体操作为：对每个染色体的每一位基因值，在0，1区间内随机地产生一个浮点数p，若p当前累计时间 当前累计时间=前驱任务完成时间； /end for 执行该任务，将任务执行时间累加到该资源的当前累计时间；/end forFor 每一个任务 If 完成标记为false 设置所有任务完成标记为false，跳出循环；/end for图3-4 基于优先顺序的子任务调度模型的执行过程第四章 基于蚁群算法的网格资源调度策略4.1 蚁群算法基本原理蚁群算法(Ant Colony Algorithm，ACA)是一种模拟昆虫王国中蚁群群体智能行为的仿生优化算法9，最早由意大利人M.Dorigo等于1991年提出，是一种分布式、启发式搜索算法，具有正反馈、较强的鲁棒性等特点。该算法模仿蚂蚁觅食的行为，按照启发式思想，通过信息素的诱导作用，逐步收敛到问题的全局最优解，主要用于求解不同的组合优化问题。蚂蚁在寻找食物时，每个走动的蚂蚁都会在其经过的路上释放一些信息素，并且在其运动过程中能够感知信息素。一条路上的信息素踪迹越浓，其他蚂蚁将以越高的概率通过此路径，而该路径上的信息素踪迹又会被加强，因此由大量蚂蚁组成的蚁群的群体行为便表现为一种信息正反馈现象：某一路径上经过的蚂蚁越多，则后来者选择该路径的可能性越大。最优路径上的信息素量越来越大，而其他路径上的信息素量会随着时间的流逝逐渐削减，最终整个蚁群会找出最优路径。蚂蚁个体之间就是通过这种间接的通信机制达到协同搜索食物最优路径的目的。图4-1 基本蚁群算法的逻辑结构蚁群算法的逻辑结构如图4-1所示。先将具体的组合优化问题表述成符合蚁群优化算法的构建性启发式形式，然后利用蚁群优化算法在“探索和“利用”之间根据信息素这一反馈载体进行启发式决策，不断的由蚂蚁个体构建出大量个体解，从中获取较优解，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素根据产生解的质量有区别的进行增量构建，从而通过信息素的正反馈机制积极影响蚁群整体活动朝着可能含有高质量解的搜索空间进行搜索，最终以较小的代价快速获得问题的较优解(甚至最优解)。从整个求解过程可以看出，单个蚂蚁每次都能够找到问题的一个解，解的质量可能较差，但蚁群作为一个内部相互协作的整体，能够始终保证蚁群整体活动向最优解逐步逼近10。4.2 基于蚁群算法的网格任务调度的设计使用蚁群算法解决网格计算中的资源调度问题，实际是在网格系统实际分配和处理作业之前，用蚁群算法模拟作业分配给资源和资源处理作业的过程，然后按照程序模拟中性价比最高的调度方式进行调度。该算法的主要思想如图4-2所示。图4-2 基于蚁群算法的网格计算资源调度策略原理蚁群系统由Gridlet Cluster和 GridResource Cluster两部分组成，其中Gridlet Cluster表示作业群，是网格系统中需要调度的作业实体在调度算法中的抽象表示，其核心是资源选择策略；GridResource Cluster表示资源群，是网格系统中执行作业的资源实体在调度算法中的抽象表示，其核心是资源处理策略。蚁群算法中的作业和资源并不是网格系统中参与最终调度的