（计算机软件与理论专业论文）基于多态蚁群算法计算网格负载均衡的研究.pdf

况旭：基于多态蚁群算法计算网格负载均衡的研究 t h er e s e a r c ho fc o m p u t i n gg r i dl o a db a l a n c i n g p o l i c yb a s e d o n a b s t r a c t p o l y m o r p h i c a n tc o l o n ya l g o r i t h m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：k u a n g x u s u p e r v i s o r ：l i u b o w i t ht h ea d v a n c e m e n ta n dd e v e l o p m e n to fv a r i o u st e c h n o l o g i e s t h ec o m p u t i n g p r o b l e m sw en e e dt os o l v eh a v eb e c o m em o r ec o m p l i c a t e da n dl a r g e rt h a nb e f o r e ， h o w e v e r , d u et ot h eh i g hc o s to fs u p e rc o m p u t e r s ，w ec a nn o tb ee x t e n s i v e l yu t i l i z e t h e m t h u s ，p e o p l eh a v et or e s o r tt od i s t r i b u t e ds y s t e m st or e s o l v et h ep r o b l e mo f l a r g e - s c a l ec o m p u t i n g g r i dc o m p u t i n gu t i l i z e st h en e t w o r ka n dc o m b i n e si d l e r e s o u r c e ss c a t t e r e di ne v e r yr e g i o n sf o rd i s t r i b u t e da p p l i c a t i o n s a sg r i dc o m p u t i n g u s e si n t e r n e t c o n n e c t i o n s ，c o m p a r e dw i t hc o n v e n t i o n a ld i s t r i b u t e ds y s t e m s ，i t p r o v i d e s b e t t e r l a r g e - s c a l es h a r i n gr e s o u r c e ，i m p r o v e sr e s o u r c ea p p l i c a t i o n sa n d s o l v e st h e s es c i e n c ep r o b l e m s l o a db a l a n c i n gi nt h eg r i dc o m p u t i n ge n v i r o n m e n t si s t h ek e yt e c h n o l o g yb yw a yo fc o m b i n i n gt h eb r o a d f i e l di n t e m e tr e s o u r c e t h ep a p e r p r e s e n t st h a tp o l y m o r p h i ca n tc o l o n ya l g o r i t h m ，t h a ti sa p p l i e dt ot h ec o m p u t i n gg r i d l o a db a l a n c i n g ，o p e n su pan e w p a t hf o r t h er e a l i z a t i o no fg r i dc o m p u t i n g b a s e do nt h ep r i n c i p l ea n dp e r f o r m a n c eo fc o m p u t a t i o ng r i dl o a db a l a n c e - p o l y m o r p h i ca n tc o l o n ya l g o r i t h m ，t h i sp a p e rp u t sf o r w a r dt h em o d e lo fc o m p u t i n g g r i dl o a db a l a n c i n gp o l i c y t l l i sp a p e rm a k e st h ef o l l o w i n gw o r k s ： 1 ，n a r r o wy o u rs e a r c h ，s p e e du pt h ec o n v e r g e n c e d u et ot h ec o m p l e x i t yo f c o m p u t i n gg r i ds i z ea n dt h eh u g e ，t or e a c hg l o b a ls e a r c ha n df i n dt h eo p t i m a l a l l o c a t i o no fr e s o u r c e sa n dc a l c u l a t i o ni sd i f f i c u l t i nr e s p o n s et ot h i s t h ea r t i c l el i m i t s t h es c o p eo ft h es e a r c h , t h ef a s t e s tt of i n das u i t a b l ec o m p u t i n gr e s o u r c e s 2 ，o p t i m a l s e a r c h p r o b a b i l i t y , t o m a k es e a r c ha n ts e a r c ht o a p p r o p r i a t e c o m p u t a t i o n a lr e s o u r c e sn o d e 3 ，r e d u c et h es e a r c hp a t h t h r o u g ht h et h r e s h o l do fs e t t i n g ，s e v e r a lp o s s i b l e s e a r c hp a t hc a r lb ed e t e r m i n e d a l s or e d u c en e t w o r kt r a f f i c ，a c c e l e r a t es e a r c hs p e e do f a p p r o p r i a t ec o m p u t a t i o n a lr e s o u r c e sn o d e t h ep r a c t i c a b i l i t ya n dv a l i d i t yo fl o a db a l a n c i n gp o l i c yb a s e do np o l y m o r p h i c a n t c o l o n ya l g o r i t h mh a sb e e na p p r o v e dw i t hl a b o r a t o r i a ls i m u l a t i o n i n g r i d c o m p u t i n ge n v i r o n m e n tb yt h i st h e s i s k e yw o r d s ：c o m p u t i n gg r i d ；l o a db a l a n c i n g ；a n tc o l o n ya l g o r i t h m ；p o l y m o r p h i c a n tc o l o n ya l g o r i t h m ；g r i ds i m u l a t i o n i i 华南师范大学硕士毕业论文 目录 删 y 1 7 6 8 芝斟百 摘要i a b s t r a c t i i 目录i i i 第一章绪论1 1 1 网格计算研究背景和意义1 1 1 1 网格计算概述1 1 1 2 网格研究现状及其发展趋势2 1 1 2 网格计算研究目的和意义一3 1 2 计算网格负载均衡研究现状及其意义4 1 2 1 计算网格负载均衡研究现状4 1 2 2 计算网格负载均衡研究意义。6 1 3 本文研究的内容及其意义一7 1 3 1 基于多态蚁群算法计算网格负载均衡模型的提出7 1 3 2 本文研究的意义9 1 4 本文的组织结构9 第二章蚁群算法及其研究现状1 0 2 1 仿生算法概述j l0 2 2 蚁群算法的基本原理1 0 2 2 1 蚁群算法概述lo 2 2 2 旅行商问题1 1 2 2 3 基本蚂蚁算法的数学模型1 1 2 2 4 基本蚁群算法的实现步骤及其流程图13 2 3 多态蚁群算法模型及其实现1 5 2 3 1 蚁群系统的多态性1 5 2 3 2 多态蚁群算法模型。1 6 2 3 3 多态蚁群算法( p a c a ) 的实现步骤及其流程图1 8 2 4 蚁群算法研究现状19 i i i 况旭：基于多态蚁群算法计算网格负载均衡的研究 2 4 1 蚁群算法理论研究现状1 9 2 4 2 蚁群算法应用研究现状2 0 2 5 本章小结2 l 第三章基于p a c a 的网格负载均衡模型设计及其分析2 2 3 1p a c a 用于计算网格负载均衡问题的可行性分析。2 2 3 2 系统结构概述2 3 3 3 系统结构设计2 4 3 3 1 节点资源管理器的结构。2 4 3 3 2 蚂蚁种群结构2 6 3 3 3 算法设计。2 6 3 3 4 算法结构流程图。3 0 3 4 基于p a c a 网格负载均衡模型的参数分析3 1 3 4 1 最大生存周期z 7 z 一分析3 l 3 4 2 信息启发因子口，t 分析3 3 3 4 3 参数p 、w 、c 。耐、c 。赫分析3 4 3 5 本章小结3 5 第四章模型参数确定及其实现3 6 4 1g r i d s i m 3 6 4 1 1g r i d s i m 模拟器简介3 6 4 1 2g r i d s i m 体系结构3 6 4 2 仿真实验环境搭建3 8 4 2 1 实验环境的设置3 8 4 2 2 实验任务以及资源的创建3 8 4 3 模型参数确定3 9 4 3 1 参数a ，卢值的确定4 0 4 3 2 参数p 值的确定4 1 4 3 - 3 参数c 。瞄，c 。值的确定4 2 i v 华南师范大学硕十毕业论文 4 4 实验结果及其分析4 4 4 4 1 基于p a c a 计算网格负载均衡算法的实验数据4 4 4 4 2 动态调度算法o l b 实验数据及对比分析4 5 4 5 本章小结4 7 第五章总结与展望4 8 参考文献4 9 攻读硕士学位期间发表的学术论文5 2 致谢5 3 v 华南师范大学硕士毕业论文 第一章绪论 1 1 网格计算研究背景和意义 网格是把互联网上的众多计算资源整合成一台虚拟的超级计算机，将以c p u 为主的各种资源“拧成一股绳”，实现各种资源的全面共享。当今，随着高性能应 用需求的迅猛发展，单台高性能计算机已经不能胜任数据密集型和计算密集型等 超大规模应用问题的解决。另一方面，分布在世界各地的大型计算资源、存储资 源、数据资源和价格昂贵的高精密仪器等资源也存在着使用效率不高的问题。因 此，迫切需要将地理上分布、系统异构的各种相关资源通过高速网络连接起来， 协同解决大型应用问题。 1 1 1 网格计算概述 在开始阶段，网格计算更多地被称为“元计算 ( m e t a c o m p u t i n g ) n 1 ，过去 对元计算的研究可以认为是网格计算的初级阶段。直到2 0 世纪9 0 年代中期，网 格( g r i d ) 一词才出现，在1 9 9 5 年的i w a y 项目中明确提出了网格计算的概念他1 。 网格计算( g r i dc o m p u t i n g ) 是一种特殊的具有重要创新思想和巨大发展 潜力的分支网络计算1 。最初，网格计算研究的目标是希望能够将超级计算机连 接成为一个可远程控制的元计算机系统，这一目标已深化为建立大规模计算和数 据处理的通用基础支撑结构，将网络上的各种高性能计算机、服务器、p c 、信息 系统、海量数据存储和处理系统、应用模拟系统、虚拟现实系统、仪器设备和信 息获取设备( 例如传感器) 集成在一起，为各种应用开发提供底层技术支撑，将 i n t e r n e t 变为一个功能强大，无处不在的计算设施。 网格作为一种新的计算基础设施，有它自己一些特殊的特点，这些特点对于 网络构建、网格研究和网格应用有着重要的影响。将从以下几个方面来论述： ( 1 ) 分布与共享共存 分布性是网格的一个最主要的特点，首先网格涉及的资源是分布的，它们一 般类型复杂，规模较大，跨越的地理范围较广。由于这个原因，基于网格的计算 况旭：基于多态蚁群算法计算网格负载均衡的研究 也是分布式的，这就产生了资源与任务的分配和调度、安全传输与通信、人与系 统以及人与人之间的交互和协同等一系列需要解决的问题h 3 。 ( 2 ) 自相似性 网格的局部和整体之间存在着一定的自相似性，局部往往在许多地方具有全 局的某些特征，而全局的特征在局部也有一定的体现。 ( 3 ) 动态性 对于网格来说，决不能假设它是一成不变的，原来拥有的资源或者功能，在 下一时刻可能会出现故障或者不可用；而原来没有的资源，可能随着时间的推移 会不断地加入进来。这就对网格系统的容错性以及可扩展性提出了更高的要求。 ( 4 ) 异构性 网格资源是异构和多样的。在网格系统中可以有不同体系结构的计算机系统 和类别不同的资源，因此网格系统必须能够解决这些不同结构、不同类别资源之 间的通信和互操作问题。 ( 5 ) 自治性与管理的多重性 网格上的资源首先是属于某一个组织或者个人，因此网格资源的拥有者对该 资源有最高级别的管理权限，网格在统一管理这些资源的同时，也应该允许资源 拥有者对他的资源有自主的管理能力。因此网格的管理具有多重性，一方面允许 网格资源的拥有者具有自主性的管理，另一方面又要求网格资源必须接受网格的 统一管理。 以上就是网格的一些特性，也提出了网格需要解决的问题。为解决不同领域 中的不同问题，人们以网络互连为基础构造了不同的网格，如计算网格( c o m p u t e r g r i d ) 、数据网格( d a t ag r i d ) 、科学网格( s c i e n c eg r i d ) 、访问网格( a c c e s s g r i d ) 、知识网格( k n o w l e d g eg r i d ) 、集群网格( c l u s t e rg r i d ) 、大地网格( t e r r a g r i d ) 以及商品网格( c o m m o d i t yg r i d ) 等。 i i 2 网格研究现状及其发展趋势 1 、我国网格研究现状： 在我国，网格研究已列入“8 6 3 计划 ，中国科学院计算技术研究所从1 9 9 6 年便开始了网格技术的研究开发工作。2 0 0 0 年，开发了连接国内八个曙光计算 2 华南师范大学硕士毕业论文 中心的网络。中国科学院计算技术研究所把网格研究当作一个长期、重要、具有 发展潜力的研究方向。目前国内正在进行的网格研究项目n 2 1 还有：( 1 ) 8 6 3 计划 支持的国家高性能计算环境一计算网格的建设，有多家单位参加。它主要研制网 格系统软件和开发网格应用，开发一套具有自主知识产权的网格软件。( 2 ) “中 国教育科研网格 由中国教育部2 0 0 3 年1 0 月份启动，将连接国内上百所高等院 校，主要研究基于网格核心中间件的网格服务支撑平台。( 3 ) “仿真网格 的研 究由航天二院和清华大学共同开展。( 4 ) “织女星网格 由中科院计算所开发， 侧重于计算网格和信息网格。另外，全国还有几十所大学和研究机构已经开展各 种网格研究。可以看出，网格研究在国内得到高度重视并迅速展开。 2 、国外网格研究现状： 欧洲数据网格，其目标是以欧洲粒子中心从t e r a b y t e 到p e t a b y t e 规模数 据为中心，为世界范围内分布的科研团体提供的数据分布存储、传输和计算密集 型分析处理的能力，实现卫星数据地理数据在全球范围内共享的系统原型研究。 研究内容主要包括：数据访问、数据副本管理、元数据管理、数据安全、查询优 化、资源调度和管理等。另外，国外较有代表性的网格计算项目包括晗1 ： 实验床( h t t p ：w w w d i s t r i b u t e d n e t ；h t t p ：w w w s e t i a t h o m e s s l b e r k e l e y e d u ) 、g l o b u s 项目( h t t p ：w w w g l o b u s o r g ) 、l e g i o n 项目( h t t p ：l e g i o n v i r g i n i a e d u ) 、g l o b e 项 目( h a p ：c s n l s t e e n g l o b e ) 、n e t s o l v e 项目( h t t p ：w w w c s u t k e d u n e t s o l v e ) 、 j a v a l i n 项目( h t t p ：w w w c s u c s b e d u r e s e a r c h j a v a l i n ) 等。 3 、网格发展趋势： 一方面，为了实现网格资源间的相互操作，从而实现广泛的资源共享，要 求资源之间具有统一的访问接口。另一方面，为了方便用户使用，屏蔽资源细节， 必须提供给用户一个统一的界面。因此，标准化将是网格的一个发展趋势。标准 化有利于规范和统一目前大量的网格技术研究。 1 1 2 网格计算研究目的和意义 网格计算实际上是利用互联网将分散与不同地域的计算机组织起来，成为一 个虚拟的“超级计算机1 。每台参与的计算机就是一个“节点 ，成千上万的 节点组合起来，成为一张“网格”。因此网格计算具有独特的优势：一是数据处 况旭：基于多态蚁群算法计算网格负载均衡的研究 理能力超强，另一个是能够充分地利用网络中的空闲计算能力，从而实现计算资 源、存储资源、数据资源、信息资源、知识资源、专家资源等全面的共享。网格 的这些优势证实了它有很大的生命力，能够满足今后在各个领域不断要求复杂计 算的需求。网格计算对信息化进程具有相当重要的作用，凭借其固有的资源共享 和协同工作能力，网格不仅可以实现计算资源的最大化共享和应用，避免资源浪 费，更能够降低应用人才的门槛、应用开发难度和应用运行成本，促使信息化实 现本质上的飞跃。 1 2 计算网格负载均衡研究现状及其意义 1 2 1 计算网格负载均衡研究现状 随着i n t e r n e t 的发展，如何提供高质量、高效率的服务已成为企业和网站 运营商迫在眉睫的问题，常用的方法就是提高服务器的性能和网络带宽，而随着 网络通信技术的发展，服务器性能越来越成为技术发展的瓶颈。为了满足提高服 务器性能的需求，许多商业机构和非盈利组织进行了大量的研究工作，提出了许 多负载均衡技术嘲吲m 。 ( 1 ) 基于网络的负载均衡 常见的基于网络的负载均衡技术有两类，即域名调度( d n s ) 技术和负载均 衡器( 1 0 a db a l a n c e r ，或称为分发器) 技术哺1 。 基于d n s 的集群技术是最早的负载均衡技术。在d n s 中为多个地址配置同一 个名字，每个地址对应一个服务节点，因而查询这个名字的客户机将按某种映射 算法( 如轮转) 得到其中一个地址，使得不同的客户通过同样的名字访问不同的 服务节点，从而达到负载均衡的目的。例如，当一个客户程序请求d n s 解析主机 名时，d n s 可为每一个请求随机地选择一台服务器以指派不同的i p 地址，从而 将客户请求分散到不同的后台服务器去处理。又如，路由器也可以基于当前的负 载情况，将一个t c p 流绑定到任意的后台服务器，并在整个流的传输过程中都使 用该绑定。d n s 负载均衡技术过于简单，它不能区分服务节点的差异，也不能反 映服务节点的当前运行状态。d n s 负载均衡的另一个问题是，一旦某个服务器出 现故障，即使及时修改了d n s 设置，还是要等待足够的时间( 刷新时间) 才能发 4 华南师范大学硕十毕业论文 挥作用。在此期间，保存故障服务器地址的客户计算机将不能正常访问服务器。 基于负载均衡器技术，通过专用的负载均衡器来接受用户请求，然后根据所 有服务节点的处理能力和现状，为了提供最短的响应时间，选择剩余服务能力最 强的服务节点。它克服了d n s 技术不能区分服务节点的差异和运行状况的缺点， 但是由于它承担了太多的计算任务，在高负载时，容易成为整个系统的瓶颈，从 而活锁服务节点( 服务节点实质上并不忙，而负载均衡器忙于计算由哪个节点来 处理却迟迟不把客户请求转发给服务节点) 。 支持大量访问的w e b 站点经常使用基于网络的负载均衡。路由器在i s o o s i 参考模型的网络层( 第三层) 执行负载均衡，通过i p 地址主机名确定如何转发 数据包，又称第三层交换技术。d n s 在i s o o s i 参考模型的传输层( 第四层) 执 行负载均衡，使用通信端口等信息确定如何转发数据包，又称第四层交换技术。 目前市面上的许多第三层或第四层交换机都提供负载均衡功能。然而，基于网络 的负载均衡未能考虑每个用户请求的内容，而且也未能获得服务器反馈的当前负 载值，因此执行负载均衡任务时有较大的局限性。例如，d n s 一般采用循环策略 ( r o u n dr o b i n ) 依次分派不同的i p 地址，未能考虑不同服务器之间的差异，故 此这种技术实现的负载分配未必合理。采用循环策略的d n s 还可能将一个请求分 配给一个无法正常提供服务的服务器，导致系统的可靠性降低。 ( 2 ) 基于操作系统的负载均衡 分布式操作系统通过集群机制实现这一层次的负载均衡，集群是提高系统可 用性与整体性能的有效手段。集群负载均衡即将多台服务器用局域网联结成一个 局域集群( 也有称其为“并行服务器集群 ) ，或由多个局域集群在地理上广域分 布形成的广域集群。服务器集群方案相对成本更低、灵活性更大、可靠性也更高。 一个分布式应用系统通过采用服务器集群集，可将多个服务器组合在一起来提高 整个系统的处理能力。分布式操作系统保证了进程可在集群中的不同的计算机之 间透明地分布，从而将负载较重的计算机上的任务调度到负载较轻的计算机上执 行，使系统的整体处于均衡，增加了系统的可靠性。集群系统通常支持进程迁移 ( p r o c e s sm ig r a ti o n ) 。进程迁移机制允许将一个正在运行的进程从集群中的一 个服务器透明地转移到另一个服务器上，迁移后的进程仍能从原中断出继续执 行。采用进程迁移不仅可实现集群的负载均衡，而且还可将故障服务器上的进程 况旭：基于多态蚁群算法计算网格负载均衡的研究 迁移到其它的服务器中，从而实现故障恢复并提高系统的可用性。 与基于网络的负载均衡类似，由于负载均衡的策略未考虑应用层的不同特 征，基于操作系统的负载均衡提供的服务质量( q o s ) 也受到很大限制。例如， 负责执行负载均衡功能的负载均衡器无法确定某一个对象副本是否应该接受更 多的请求，因为这些对象副本并不会将负责相关的信息反馈给负责均衡器。另外， 基于操作系统的负载均衡过于依赖特定的操作系统平台，难以集群不同的软件、 硬件平台的服务器，降低了分布式应用系统的可移植性。 ( 3 ) 基于中间件的负载均衡 基于网络和基于操作系统的负载均衡机制都具有不同程度的限制。相比之 下，基于中间件的负载均衡策略不仅可以结合以上两种机制同时使用，而且还可 建立在不同的商品化的网络与操作系统上。由于中间件在执行负载均衡时可参考 更多的应用程序特征，执行效果相对较好。在c o r b a 体系结构中，o r b 中间件允 许客户在分布式对象上引用操作，却无需关心对象的位置、编码种类、操作系统 平台、传输协议、互动连接以及硬件设施。c o r b a 体系结构中的基于中间件的负 载均衡机制是作业对象可以不直接与系统底层接触，降低了耦合性，使开发人员 不必关系系统结构而直接实现业务逻辑也能够很好的控制作业的执行状态，从而 提高了系统的稳定性和可靠性。基于中间件的负载均衡结构如图1 - 1 所示呻1 。 图1 - 1 基于中间件的负载均衡结构 1 2 2 计算网格负载均衡研究意义 网格计算是人们正在研究的利用网络并联合分散在网络中各个区域的空闲 资源来为网格系统应用软件服务，从而解决大量复杂计算的科学问题。它从世界 6 华南师范火学硕士毕业论文 各地集合了丰富的计算资源从而形成强大的计算能力来协助科学领域大量复杂 任务的计算隋埘。因此，相对于传统的分布式计算系统来说，网格计算提供了更 大范围的资源共享，改善了资源的利用和广域互联网的访问环境。在网格环境中， 有许多节点经常空闲并可以提供计算资源共享，但是有些不行。当选择节点来执 行任务时，如果一个不能胜任的节点被选中，就要重新去分配和执行任务，有时 经常发生这种情况，这样就大大降低了系统的执行性能阳1 。在这种的情况下，使 用负载均衡技术来增强系统的伸缩性、可靠性、有效性就成为迫切需要解决的重 要技术问题。 负载均衡建立在现有网络中，它提供了一种廉价有效的方法扩展服务器带 宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。它主要 完成以下任务： ( 1 ) 解决网络拥塞问题，就近提供服务，从而实现地理位置无关性； ( 2 ) 为用户提供更好的访问质量； ( 3 ) 提高服务响应速度； ( 4 ) 提高资源的可利用效率； ( 5 ) 避免了网络关键部位出现单点失效。 然而，在传统的分布式集群计算机网络中的负载均衡策略和算法在一些方面 不能满足庞大的网格环境的需求乜1 ，具体有： ( 1 ) 服务单一性，只能从一个或者有限的几个点获得服务，而在网格中任何节 点都能够提供服务( 有些有时不能提供服务) ； ( 2 ) 缺乏负载均衡服务的透明性，难以提供跨网络、跨区域、异构系统透明性 的服务和交互功能： ( 3 ) 部分服务器一旦出错或者崩溃，影响整个服务，降低了系统可靠性； 1 3 本文研究的内容及其意义 1 3 1 基于多态蚁群算法计算网格负载均衡模型的提出 蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化 算法，该算法采用了正反馈自催化机制，具有较强的鲁棒性、优良的分布式计算 7 况旭：基于多态蚁群算法计算网格负载均衡的研究 机制，而网格计算也是分布式计算的一种。但是蚁群算法收敛速度慢、容易陷入 局部最优等缺点。本文通过查阅国内外文献，对多种改进蚁群算法进行比较，发 现多态蚁群算法n 们( p o l y m o r p h i ca n tc o l o n ya l g o r i t h m ，p a c a ) 更能体现蚁群 社会的真实状况，对实现网格负载均衡具有借鉴意义。 多态蚁群算法是在针对蚁群算法的基础之上，通过对蚁群社会的仔细研究发 现，真实蚁群社会中的所有蚂蚁不仅各司其职，而且相互依赖、相互协作，相互 之间形成一个有机的整体n 。在执行某项任务时，个体之间会通过各自分泌的信 息素相互联系、相互协作。这里的“多态性 是指蚁群社会所具有多种状态的蚂 蚁群体及信息素。根据分工的不同将蚂蚁分为：侦察蚁、搜索蚁和工蚁，各种蚂 蚁各司其职。其中，侦察蚁群负责局部侦察，搜索蚁群负责全局搜索。这种改进 大大提高了蚂蚁群体之间的合作效果，增强了算法的有效性。本文在广泛查阅国 内外相关文献的基础上，采用模拟仿真的方式对网格任务调度的策略和蚁群算法 进行了分析研究，提出一种基于多态蚁群算法的计算网格负载均衡模型。 根据对p a c a ( p o l y m o r p h i ca n tc o l o n ya l g o r i t h m ，p a c a ) 算法以及计算网格 负载均衡的研究，本文设计出基于p a c a 的计算网格负载均衡模型。将本模型中 蚁群社会从事劳动的蚂蚁定义为三类：侦查蚂蚁、搜索蚂蚁、和工蚁。侦查蚂蚁 群的任务是以每个资源为中心做局部侦查，并以侦查素来标记侦查结果，以便为 搜索蚂蚁到达下一资源提供辅助信息；搜索蚂蚁的任务是进行全局搜索，每到一 个资源点，根据侦查素和各出口的信息素等信息来选择下一个资源点直到找到含 有计算资源能里强的一条路径为止，并将其标记，以便工蚁群取食回巢，并将作 业下载到计算资源强的节点中，该节点将作业放到自身作业队列中，并在处理完 这个作业后将计算结果返回源节点，源节点再将结果返回给用户；工蚁群的任务 是根据作业执行的情况对资源进行奖惩。本模型中所定义的工蚁群与搜索资源无 关，所以只需针对侦查蚂蚁群和搜索蚂蚁群设计各自的信息素调控机制。其中， 侦查蚂蚁负责局部搜索，搜索蚂蚁负责全局搜索。 本模型的基本原理和基本蚁群算法搜索最佳路径相似。每个节点对应一种类 型的信息素，搜索蚂蚁根据信息素的指引搜索计算资源能力强的节点，并留下新 的信息素，一段时间后，通往强计算能力节点的信息素轨迹就变得明显，而通往 弱计算能力节点的信息素轨迹则较淡。因此，强计算能力的节点比弱计算能力节 8 华南师范大学硕士毕业论文 点有更多的机会获得新的作业，从而实现负载。 1 3 2 本文研究的意义 本文通过对多态蚁群算法的研究，并结合计算网格负载均衡的特点，提出了 一种基于多态蚁群算法的网格负载均衡模型。最后，通过模拟仿真实验验证其有 效性，通过实验分析，本算法模型是适合计算网格负载均衡的。应此本文实现了 计算网格负载均衡的另一途径。 1 4 本文的组织结构 本文介绍了课题的研究背景，意义和目前计算网格负载均衡研究的现状，并 介绍了基本蚁群算法和多态蚁群算法的基本原理；通过对计算网格负载均衡和多 态蚁群算法的研究，本文给出了基于多态蚁群算法的计算网格负载均衡模型，并 对模型参数进行理论分析；最后通过仿真实验对模型参数进行最后确认并通过模 拟实验检验模型的有效性。 本文的组织结构： 第一章：主要介绍网格和计算网格负载均衡研究的背景和意义、本文研究的内容 和意义，及本文的组织方式。 第二章：阐述了基本蚁群算法和多态蚁群算法的基本原理以及蚁群算法研究的现 状。 第三章：通过对计算网格负载均衡和多态蚁群算法的研究，本章设计出一种基于 多态蚁群算法的计算网格负载均衡模型，并对相关参数进行理论分析。 第四章：本章为实验部分，本模拟实验首先对算法参数进行最后确定，在此基础 上对模型进行评估、分析和对比，得出结论。 第五章：总结全文，指出自己工作的成果、本文需要完善改进的地方和研究方向。 9 况旭：基于多态蚁群算法计算网格负载均衡的研究 第二章蚁群算法及其研究现状 2 1 仿生算法概述 在计算机科学，自动化，管理和工程技术等领域里人们经常会碰到组合优化 问题，其中的很多问题如旅行商问题( t s p ) ，指派问题( q a p ) ，车间作业调度( j s p ) 等都已被证明是n p 完全问题。用传统的单纯形法或非线性规划这些基于数学的 优化方法解决此类问题时，计算时间随着问题规模的增大呈指数级延长，且要求 目标函数有较严格的数学特性，这大大限制了其应用的范围。为了克服这些困难， 科学家们从生物系统的进化和自适应性现象得到灵感，提出了一些以搜索近优解 为目标的仿生优化算法n 刳。 仿生优化算法是一类模拟自然生物进化或者群体社会行为的随机搜索方法 的统称。自从2 0 世纪7 0 年代产生第一个仿生优化算法一遗传算法以来，越来越 多的研究者投身其中，又先后提出了蚁群算法，微粒群算法，捕食搜索算法，人 工鱼群算法，混合蛙跳算法等一系列仿生算法。由于这些算法求解时不依赖于梯 度信息，其应用范围较广，在许多传统方法难以解决的大规模复杂问题中都已体 现出了优异的性能。因此，它们的出现为n p 完全的组合优化问题求解提供了一 条全新的途径，并作为新兴的演化计算方法已越来越受到国内外研究者的关注 n 羽。本章将对仿生算法中蚁群算法的原理和研究现状着重分析。 2 2 蚁群算法的基本原理 2 2 1 蚁群算法概述 蚂蚁是社会性昆虫，觅食行为是蚁群一个重要而有趣的行为。虽然单只蚂蚁 的行为极其简单，但由大量的蚂蚁个体组成的蚂蚁群体却表现出极其复杂的行 为，能够完成复杂的任务。据科学家的观察和研究发现，蚂蚁在没有任何可见提 示下有能力找出从蚁穴到食物源的最短路径，并且能随环境变化适应性地搜索新 的路径，产生新的选择n 羽。根据蚁群的这一智能行为，科学家们提出了智能型的 优化算法一蚁群系统。蚁群系统的第一个应用是旅行商问题，之所以选择旅行商 1 0 华南师范大学硕士毕业论文 问题，原因有二：一是因为旅行商问题为大家所熟悉、易懂，是n p 问题；二是 旅行商问题较容易阐明蚁群优化算法n 钔的原理。下面就以旅行商问题为例来说明 其原理。 2 2 2 旅行商问题 旅行商问题n 引，就是指旅行商按一定的顺序访问n 个城市的每个城市，使 得每个城市都被访问且仅能被访问一次而使花费的代价最小，用图论的观点来 看，就是找出一个最短的封闭路线。假设有n 个城市，l ( i ，j ) 表示城市i 与城市 j 之间的连接( 在对称t s p 的情况下，l ( j ，i ) 与其含义相同。否则，表示城市j 到城市i 之间的连接) ，吐，表示城市i 与城市j 之间的距离，那么我们可以将 其描述成图g = ( c ，l ) ( 其中c 表示城市的集合，l 表示城市间连接的集合) 。那 么，t s p 问题用图论的观点来说，就是从图g 中找出一条可行的优化路径，这个 路径也叫做该问题的一个解。当然，所有的可行的解必须满足其限定条件，在 t s p 问题中就是每个城市都必须被访问一次且仅被访问一次。 2 2 3 基本蚂蚁算法的数学模型 假设b , ( t x i = 1 ，2 ，刀) 为蚂蚁在时间t 在城市i 的数目，m = 包( f ) 为蚂蚁的 i = l 总数目，每只蚂蚁具有如下特征： ( 1 ) 选择下一个待访问的城市要以连接这两个城市间的距离和留在该边上 的信息素强度构成的概率函数作为依据； ( 2 ) 禁止蚂蚁访问已被访问过的城市，从而使蚂蚁走过的路径形成一个可 行的解； ( 3 ) 当它访问了所有的城市后，才在每条已被访问的边l ( i ，j ) 上释放信息 素；f ，o ) 为边在t 时刻的信息素强度，在每一时刻每只蚂蚁都要选择下一个合 法的城市，当时刻t + n 完成后，所有的蚂蚁都走遍了所有的城市，此时系统信息 素强度的修改公式由式( 2 一1 ) 所示： i i o + 1 1 ) = ( 1 一p ) f o ) + a z 矿 公式( 2 1 ) 况旭：基于多态蚁群算法计算网格负载均衡的研究 其中，p 为信息素的挥发速率，p 为小于1 的正数，之所以这样做，一方 面是为了防止信息素的无穷积累，另一方面是为了提高系统搜索到更好的可行解 的能力，防止较早地失去探索新路径的能力。a v 打表示蚂蚁在本次运行中留在路 径l ( i ，j ) 上的信息素强度由公式( 2 - 2 ) 所示： a r 扩= f 参公式( 2 2 ) 其中，f ：表示蚂蚁k 放置在边l ( i ，j ) 上的信息素强度公式由公式( 2 - 3 ) 所示： 瞄：层若蚂瓣嗽啦秕“加经逝( f ，_ ，) 公北- 3 ) i o ，否则 其中，q 为常量，k 为第k 只蚂蚁访问所有城市的总长度。 为了让所有的蚂蚁访问所有的城市，而不致重复，建立了禁忌列表t a b u 。， 在禁忌列表中保存了每只蚂蚁已经访问过的城市。当一个新的城市要加入到这个 表时，必须先搜索这个禁忌列表，检查这个城市是否在禁忌列表中，若在，就必 须重新选择另外的城市，以保证解的合法性。 概率函数式( 2 - 4 ) 表示信息素强度和城市间距离对蚂蚁选择路径的影响，定 义如下： p ：器 1 7 ，如果歹七p ；： 孕f 驴】a 矿】_ 卜卜几 i ，七 10 ，否则 公式( 2 4 ) 其中，以= n t a b u 。) a 、卢是系统参数，分别表示信息素、距离对蚂蚁 选择路径概率的影响程度( 当a = 0 时，距离当前城市最近的那个城市将最有可能 被选中，这个性质相当于经典的贪婪算法；当卢= 0 时，这相当于只有信息素起 作用，但这会导致系统均依赖路径上的信息素，更早的收敛，出现所谓“早熟” 的现象，所以必须选择适当的纵卢的参数值) 。叩 ，表示由城市i 到城市j 的期望 1 2 华南师范大学硕士毕业论文 程度，可根据某种启发算法具体确定，一般用场表示。 ” ， 根据具体算法的不同，毛o ) ，a t 盯o 工露( f ) 的表达形式可不同，根据具体 问题而定。d o r i g om 曾给出三种不同模型，分别称之为a n t - c y c l es y s t e m 、 a n t - q u a n t i t ys y s t e m 、a n t d e n s i t ys y s t e m 。它们的差别在于边上的信息素强 度的表达式不同。前面表达式( 2 3 ) 表示的是a n t - c y c l es y s t e m 模型。在 a n t - q u a n tit ys y s t e m 模型中： 叫：侈若蚂黼嗽如秕“加经引“) i o ，否则 瞄搿赃嗽啦秕“拥纰。 公式( 2 5 ) 公式( 2 6 ) 它们的区别在于：后两种模型中，利用的是局部信息；而前者利用的是全局、 整体信息。在求解t s p 问题时，a n t - c y c l es y s t e m 性能较好，因而通常采用其 作为基本模型。 2 2 4 基本蚁群算法的实现步骤及其流程图 l 、实现步骤 下面以t s p 为例，用伪码来说明蚂蚁系统的实现步骤： ( 1 ) 参数初始化。令时间t = o 和循环次数c = o ，设置最大循环次数c 嘣，将 m 蚂蚁置于n 个元素( 城市) 上，令有向图上每条边( i ，j ) 的初始化信息量 f 盯( ，) = c o n s t ，其中c o n s t 表示常数，且初始时刻f ! ，( o ) = 0 。 ( 2 ) 循环次数c 卜c + l 。 ( 3 ) 蚂蚁的禁忌表索引号k = l 。 ( 4 ) 蚂蚁数目k 卜k + 1