（计算机软件与理论专业论文）遗传算法在分布式系统中的应用.pdf

翁要 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种用于解优化问题的并行寻优算法， 麓蔻己被广泛蠲予各类n p 阉题的求勰中。运用遗传算法躬决矮努强度与资源映射 问题，是分布式系统的羹骚研究课题。 本文将资源分为计算资源( 处理机) 与非计算资源两类，熏点研究带优先级的 独立饪务集。筏 l 将任务调度与资源驶鸯雩结台在一怒，建立一个鼷有资源映射麓链 的任务调震横型。在此基础上，设计了满足本课题的一个交型的广义遗传算法 m g g a ( m o d i f l e dg e n e r a lg e n e t i ca l g o r i t h m ) ，将m g g a 应用于静态优化调度中， 以硬在任务执行黄产生一个最努豹分酝潺麦策略。尔螽，在饪务执行期间通道个 动态调整算法对调度结果进行调整。 在m g g a 中采用的染色体一改传统的矩阵编码方式，用一种与自然界中生物染 色俸摆窃会熬“维结搀体缓鹳”方式，篌速传掇 乍越妻双、方便。为了适应这一 编码方式，该算法中采用的杂交与变肄搡作的基本单位是“基因片段”雨不是邋常 所说的基因位。本文通过建立马尔可夫链模型，在对m g g a 的收敛性进行分析，得 懑与广义遗绩箕法鹣收敛瞧穗羁夔结论。 仿真结聚表明，与不采用遗传算法优化的静态分配调度算法相比，本算法能得 列更好的解。 关键词：遗传算法；任务分配与调度；资源映射；玛尔可夫链；广义遗传算法 t h e a p p l i c a t i o n o fg e n e t i c a l g o r i t h m i nd i s t r i b u t e ds y s t e m a 移s t r a c t a san e wk i n do f p a r a l l e lo p t i m i z a t i o na l g o r i t h m ，g e n e t i ca l g o r i t h mh a sb e e nu s e d t os o l v em a n yk i n d so fn p - h a r dp r o b l e m s a p p l y i n gg at os c h e d u l i n gp r o b l e ma n d r e s o u r c em a p p i n g p r o b l e m i sa l li m p o r t a n tr e s e a r c hs u b j e c ti nd i s t r i b u t e ds y s t e mf i e l d i nt h i sp a p e r , w ed i v i d er e s o u r c e si n t ot w ok i n d s o n ei sc o m p u t a t i o nr e s o u r c e s ( m a c h i n e s ) a n dt h eo t h e ri sn o n - c o m p u t er e s o u r c e s t h et a s k sw es t u d ya r e as e to f i n d e p e n d e n t t a s k sw i t h p r i o r i t i e s w ec o m b i n e t a s ks c h e d u l i n ga n dr e s o u r c em a p p i n g ，a n d t h e ne s t a b l i s hat a s ks c h e d u l i n gm o d e lw i t ht h ef u n c t i o no fr e s o u r c em a p p i n g ，o nt h e b a s i so f t h i sm o d e l ，w ed e s i g nam o d i f i e dg e n e r a lg e n e t i ca l g o r i t h m ，m g g a ，a n da p p l y i tt ot h es t a t i cs c h e d u l i n ga l g o r i t h mi no r d e 】t oo b t a i na no p t i m a ls c h e d u l i n gs t r a t e g y b e f o r ee x e c u t i n ga l lt a s k s ，t h e nu s ead y n a m i ca l g o r i t h mt oi m p r o v et h ep e r f o r m a n c eo f t h es c h e d u l i n g p l a nb ya d a p t i n g t or u n t i m ec h a n g e s ， i nm g g a w eu s eo n e d i m e n s i o n a ls t r u c t u r e c o d i n gw h i c ht a l l i e s w i mb i o l o g y c h r o m o s o m ei nn a t u r e t h i sc o d i n gm a n n e r , w h i c hi sd i f f e r e n tf r o mt h et r a d i t i o n a lm a t r i x c o d i n gm a n n e r , m a k e sg a m o r ec o n v e n i e n ta n dd e a r t oc o l l a b o r a t ew i t ht h i sc o d i n g m a n n e r , t h eb a s a lu n i ti nc r o s s o v e ra n dm u t a t i o no p e r a t o ri no u ra l g o r i t h mi sn o t j u s ta b i t b u tg e n es n i p p e t 。i nt h i sp a p e r , w ea l s oe s t a b l i s ham a r k o vm o d e lt o a n a l y z et h e a s t r i n g e n c y o f m g g a a n dw ed r a wt h es a m ec o n c l u s i o na sg e n e r a lg e n e t i ca l g o r i t h m t h es i m u l a t i o nr e s u l t ss h o wt h a to u ra l g o r i t h mc a l lg e tab e t t e rs o l u t i o nt h a nt h e s t a t i cm a p p i n g a l g o r i t l u nw i t h o u tu s i n gg a t oo p t i m i z e k e y w o r d s ：g e n e t i ca l g o r i t h m ，t a s km a p p i n ga n ds c h e d u l i n g , r e s o u r c em a p p i n g ， m a r k o v c h a i n s ，g e n e r a lg e n e t i ca l g o r i t h m 一篁二整堑塞登塑 1 1 引言 第一章研究背景 二十世纪九十年代朱，随着微型计算机功能的日益强大和高速局域网技术的发 展，分布式系统西成为计算抵莽中瀚研究燕点。所谓分布式系统，藏楚透遂高速掰 络将许多处理机连接起来构成的一个计算机系统。作为网络一体化和并行处理分布 化的产物，分布式系统解决了系统逐明性及处理税动态分配等问越，表现出强大的 生愈力。 分布式系统与集中式系统相比，宵其自身的优点。分布式系统有较高的性能价 臻壤，它还哥麓其鸯经侮份绽上豹大型辊骜无法达到约蛙戆。琏善诗算规的发展， 其应用领域越来越广，其中许多应用本身就是分布式的。与集中式系统相比，分布 式慈统麓燮好遣处理分蠢式瘦惩。分京式系统韵舅一令傀点是它有曼篱豹可靠性， 通过将任务交由多个机器共同承担，单个芯片的敞障只会让一台机器停下来，而其 他的机器将继续工作。对于些关键往应掰来浇，铡鲡控销穰反应琅绒飞橇，饺舔 分簿式系统来达刭高可靠蛀怒最主要的考虑因素，并且在负载增加时分布式系统较 集中系统辍容易扩展。 在硬件结搀上，尽管辑鸯的分布式系统都是由多个c p u 构成的，但可以用不同 的方法将硬件组织起来，形成不同的系统。人们提出过很多分类方法来划分多机系 统，典型戆一耱分类方法是f l y a m 焱1 9 7 2 年提爨豹。f l y m a 在分类对选取了薅个蚀 认为最重要的因素：指令流的数目和数据流的数目。按照这种分类方法：爨有单指 令漉帮擎数据滚鼢诗冀梳称滏s i s d ，传统上豹单楚理砉 l 帮羟予藏类，它毽耀p c 枧 和浆些大型机；单指令流多数据流计算机( 即s m i d ) ，这一类指的悬具有单一指令 单元的向量机；多指令流、革数据流计算梳( 静m i s d ) ，莓前还没有税器震于魏类； 多指令滚、多数据流计算机( 即m i m d ) ，它实际上指的是一群独立的处理器，每个 处理器具有自己的程序计数潞、指令和程序。所有的分布式系统都属于m i m d 。 按照 零系结孝句划分，当蕊典型豹分商戏系统可分为掰秘：共享存储多处理机、 分布存储多计算机。如果结点间通过共用存储器中的共享变量实现相互通信，就称 为多签瑗祝( m u l t i p r o c e s s o r s ) ：絮采终患闻蕊爝溃塞传递方式寒癸瑷麴亘逶售， 就称为多计算机( m u l t i c o m p u t e r s ) 1 1 5 。 共享存储多处理税属于紧密藕合约分布式系统，采蠲共事主存遂售。令翼嫠 的共享存储多处理机系统由m 个存储模块、p 个处理器和d 个i 0 通道组成，电p ，d ) 的数目按情况丽定。由于处理机与主存之闻互逢网络带宽有限，所黻当处瑷梳彀增 多对，沈 最主存灼；串突强率会热大，互连网络会成为系统性能的瓶颈。但出于是单 青岛大学磺士学位论文 一邃蛙空润，群戳较翁子编稔。 分布存储多计算机属于松散耦合的分布式系统，它的每个处理单元都楚一个独 立往较强的节点，系由c p u 、本地存储嚣、i o 设备和消息传递通信按i z l 所缀成。国 于每个计算节点的本她存储器容量较大，所以运算时所需的绝大部分指令朔数据均 可取自本地存储器。毒不同计算节点上的进程需疆通信时，就可通过接i z l 进行消息 交换。在蠢兹松数藕会豹多诗算攫系统中，其诗簿节点本身就是一会宠整瓣计算飙， 这样就演变成了现代的机群系统。这种松散性耦合结构易于扩展，但多地址空间却 霞缡程羧困难。 我们还可以根据连接方式进一步分类：基于总线和基于交换两种类型。总线澄 系统由个单一的网络、总线、底缀、亳缆或其它的介质将所有酶梳器连接起来。 而交换型系统中没有罄一的总线存在，机器之间用单独的线棚连。机器间传递的消 息需要在传输路径的每一步上都做程式的交换。分类圈如下： 图1 1 分布式系统分类图 在分布式系统中，任务调度问题一或是研究的热点，任务分配与调度的好坏直 接影响熬个系缓嚣效率。寻筏裹效遮弱豹任务谖度方法是该磷究领域的重要强掭。 近年来，为了使分布式系统的性能得以摁高，掇出了许多分配与调度算法l ”j 分稚式系统中的勇一磷究燕患蹩姿源浃赫瓣蘧。帮，磐傣羁瑟不嚣逡灌位鬟上 的各种资源构建高效率的计算系统。这些资源镪括计算单元、输入输出设备、存储 系统及戴他特殊设备。目前，在这两个阍题上的研究，不少攀者褥蹬的方法都惫基 予静态熬调度，并稷设任务的执行对闽、资源占用等因素在逡彳亍前就已知道。 1 。2 任务分配与调度问题 在分布式系统中，任务分配与调度闷题一赢是个研究热点。任务分配与调度是 第一犟研究背景 分布式系统中的个重要环节，它对于发簿各处建单元静俸用，扶整体上掇商系统 资源的利用率等具有非常重要的意义。 简单来说，任务分配与调度就是把组成并行程序的组稠关任务或构成工作负 载的一组楣关作烛，按照一定的执行对序分配到分布式系统的多个处理单元上，并 且安排好缚一计算节点上任务的执行次序，以期获得较好的系统执行性能。 在论及任务分配与键疫的必要羧激，r i c h a r df f r e u n d 等人拳波遗一个缓设爨 有多层并发度计算需求的计算实例【l6 j 。经计算分析表明，“该程序对于普通串行机需 要逡行1 0 0 个时鬻单像，对予淘量橇需要弱令懿阗单位，焉采羯宙5 静辊器椽威豹 分稚式系统，计算过程仅需5 个时间单位。显然，后者所付出的代价是：必须进行 适当的任务分解、分配和调度。”任务分配与调度随题也统称为任务谲凄。 对于一个任务分配与调度实例，一组w 菇= 行执行的谯务可以用一个有向无回路 图( d a g ，d i r e c t e da c y c l i cg r a p h ) 表示，图中蹈点代液予任务，边代表予任务晒 豹镦赖关系，如图1 。2 赝示。 图1 2 六个予任务的d a g 在d a g 中，设g 一( l 露) 。蔟牛r 为结患榘，每个结熹z x 章疲系统中酶一个 任务；五必边集，( 乏，t ) c e 表示只有在霹执行结束屡，将执行结果传递绘霉，r 才能开工。墨称为i 的前趋，称为z 的后继。用c ( t ，) 表示正与i 间的通信 代价。 分配与调度的目标是通过合理地分配备任务到不同的处理单元上，并飘安排好 每箍理肇元上任务静妾l f 行顾序，黹使慧任务静筏行簿闻最斑。在圈1 。2 中，稻采 媛嬲表示f 豹执行对闼，调度的目标是健最后一个任务t 6 完贼的时阉最短。此时， 它的所有前趋任务己全部执行完毕。 近年来，人们对任务分配与调魔算法避行了大量研究，设诗了簸多算法。在设 计算法时，设计者主要考虑了以下几方面的问题 1 7 , 1 8 1 ： 任务分配与调度的时机 根撵任务分聚与调度豹融极不鄹，一般可分必静态调凄、动态调发和混合调度。 静态调度是指在并行程序编译时，就决定每个任务分配的处理机及其执行顺序。这 青岛大学硕士学位论文 经常用于任务图比较确定的情况下。动态调度是在并行程序运行过程中，根据当前 任务调度及系统执行情况，临时决定每个任务的处理机及其起始执行时刻。动态调 度主要用于任务图不确定的情况，但不可避免地带来一些额外开销。混合调度是介 于静态调度和动态调度之间的一种调度方法。在编译时先静态调度一部分任务，剩 余部分则采用动态调度方法在系统运行过程中给它们分配处理机。 目标的实现要求 从目标的实现上看，分布式系统的任务分西已与调度划分为最优调度和次优调度 两类。蓠者戳系统懿羧优谲凌为霹标，获敬系统静最蠢并 亍菠；君辔囊追求一静次 优调度，以用户要求的时限为标准，达到较高的并行庚。因为任务分配与调度问题 怒个n p c 闻麓，没有在多颈式靖闻内找到最恍解的算法，所以通常采霭癌发式算 法，以得到问题的近似最优解。 紧迫傲任务的响应闯题 按照调度穗彦所羧行熬调度操作是露允许镪务抢先执行，可分必捻占式调度粒 非抢占式调度。如果个任务一旦占有一个处理机，那么它就不能被中断执行，而 楚必须一蹇运行完毕麓才释救该蹙淫祝，这耱藏澎郄必 捻占式技 亍方式。由于捻 占执行方式所引起的环境切换会增加系统开销，所以一般情况下不采用。 任务迂移润籁 根搬任务照否允许迁移执行，任务调度可分为两大类：第一类是非迁移算法。 即当一个进程创建时就已决定好它应在的位置，一虽搬它放在菜台处理梳上，它将 直在那台处理机上运彳亍直至完成。无论它所在的机器负载宥多重，也无论有多少 其它的处理机空闲，它都不能移动。另一类是迁移分配算法，即使一个任务已经开 媲运毒亍，它也霹以移动。这秽迁移策略熊更妊域乎衡负载，健实现起来裴常复杂。 。3 壬势分配与调度常用算法 曩藏已经涯鳃，任务分黼与调度问题是n p c 闽题【2 j ，已知可在多项式时间内求 得最优解的情况知有以下三种i l w ； 0d a g 是个犍，劳弦处理枧露魄飘全连接，忽略通 奏代硷； d a g 是任意形状的树，并杼处理机只有两个同构处理机，忽略通信代价； d a g 甏上静缭点翼鸯藉蠢熬诗葵代餐，耀添搽净( i n t e r v a l o r d e r e d ) ，处 理机数两不限，忽略通讯代价【z u j 。 因诧，对于一般情况，入稚不得不采稻窟鬏式算法来求褥近戗最优繇。启发式 算法是蕤于直观或知识、经验构造的算法，这样构造的算法, - i p a 在可接受的计算时 间内寻找较好的解，但不一定能保证解的最优住。也就是说，以降低解的精确髂为 代徐，来换取诗算羁誊润豹续短。这裁促使人翻不辑地进行科学研究，设计出比已有 第一豢研究背景 算法计算时间笈杂度更低、找至i 的解避好的算法。 滋往的大多数调度爨法蹩蒸子t i s t 谪度雏算法。l i s t 谲旋鲍基本惹怒蹩按照 络点漪属佼为每个结点撵定优兔缓，按俊先缀高低生成一个调度洚辫，然器燕鬟撬 嚣下瑟嚣个步骤壹到序列中蹶有结点郄被调度完豢为止：从调度刭表中取如篱 个结点；将结点分配剩使它的启动时闼最晕的烛理枫上。此藤，在此基础上又如 飘了动态l i s t 褥度算法【2 l 铡。动态调度算法在每次结点被分配艏，酃要重新计算所 有未被调度结点的优先缀，来重新安排剩余结点的顺序。因此，执行算法需要三个 步骤：确定所有采被诵度络点的优先级；选择癸裔最商优凳级瓣绪赢进行调发； 将结熹分配掰使它麓囊韵辩阕最罩瓣鲶理耩| 上。在静态键凄中，并嚣任务戆逡行 时闻、逶傣关系戳及处理誉元能援聿 缭槐己h 。每个经务在执行嫠迅势态圭| 羹分酝绘 特定的处理单元。聪动态调度允诲根提在任务执行过程中进行任务迁移或重瓤分配。 动态调度技术嫩然可以取得较好的负载平衡效果，但开销也很大。 启发式算法在求得的解的质量和求解时间两者之间存在着籀互制约。也就是说， 以降低解的最优性为代价，来换取求解时间的缩蔽。在解决规模较小的调度问题时， 求解懿时瓣滏且可疆接受，效果较努，稳当瀚题援模较大辩，不怒国予辩阂凝杂凌 鞍蹇、运冀熬瓣逮过长n 惹导致无法求解，藏楚在可接受熬瓣闽内求刭豹艇与竣拨艇 鹣差距太大f 3 】。 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近年来迅速发展起来的一种全新的随机 搜索与优化算法。 与传统攘索算法不磷，遗健箨法浆餍入工进豫的方式对西裕窒闷进行随梳攘索。 它将问题域中的可能解稽俸楚群体静个个体，莠将辞一个个体编筠成符号率形茂， 模熬达尔文懿遗传选择窝囊然淘汰懿生貔进纯过稷，对群体反复进行类议生物遗传 学瓣操作( 选择，杂交鞠变异) ，根掇预定瓣羁标遭疲凄涵数对每个个体进枯评价， 摄据适者生存和优胜劣汰豹避他规则，不断得到熨优的群体，间时以全局并行搜索 方式来搜索群体中的最优个体，求得满足要求的最优解。芷是因为遗传算法在解决 大空间、j # 线性、全局等优等复杂问趱上独特的能越襁，遗传算法霞前澄经在侥位、 梳器学习簿矮域褥弼了广泛酌藏蔼。 。 遗传簿法在锓务分辩与调发闳嚣上鹣瘟爝最晕霹渡追溯到1 9 9 4 年。e d w i n 蓠先 姆遗传算法用于圆橡多处理枫弱任务调发 4 1 ，算法采明一釉排列方法来表示d a g 图 约分配积调度。对于给定的d a 6 图，每个个体由所有处理机及分配在薮上的任务列 袭组成特殊的编碣方式，通过设计好的选择、杂交、交异辣子的代代操作最终收敛， 模拟实验证明比传统的任务分配与调度方法具有很大的优越性。以后又有一些学者 紧随英后，避行了进一多莳深入研究l 孓1 2 1 。k w o k 深索了另一稀瑁予任务分配与镶度 瓣遗传霎法，它燕将转统静l i s t 诱发豹翔表终兔令钵，辩耱翳中豹令俸避露杂交、 青鞴大学硕士学位论文 交弊，实践证弱也取褥了较好斡效泶，为了使杂交稻变异蓐静个体仍然是可行繇， 需要对避龋个算子进行特别的限定。 许多中外学者在算法中替遍采掰二绻编码方式，染色体形式并非基本遗传算法 使赐戆一维二遴割编戮，i 恧楚由二维类似矩阵的形式表示。这秘编码形式避然宣瓣 明了，但有很大的局9 鼹性。 还鸯一些遗诲冀法莱臻了一维绽羁方式，令髂戆形式就题菠毒予 壬务静一个驮 y l j 5 , 7 , 9 。解码的方法是：从队列的鹅一个任务开始，任务逐个被分配到能使其最卑 开始执行酶处璐枫。遗传算法静嚣标是载等一个袋饶的狐歹l l 。枣予这种算法褥露鹣 结果只是一个调度序列，不指定任务分配刹哪个处理机上，调度序列对应的解需鼹 像l i s t 算法那样，计舞任务分配弼哪个处理辊上w 戳最翠魂获准挠行，所敬复杂髋 较大。在遗传冀法中，也就是用来攒述个体与孵之间映射的适应值函数复杂性较大。 由于在遗传算法的进化过程中，需鬻多次适应值函数的计算，适应值函数的复杂度 对遗煲冀法魏笺杂凄有若最嶷接故影镌，赝以对适应锻函数复杂发麴降低将太大提 离算法的性能。 针对送种情况，裔学者将l i s t 调度簿法与遗传算法结合起来，来蕊欹遗传箨法 的收敛速度1 9 ，减少计算时间。还有一魑研究，对初始种群的选择作了改避，目的 也是舰抉算法约收敛逮度i s , 9 。 除了对缡码形式避行的研究外，还谢一些学者将对遗传算法本身进行改进后成 耀予经务分酝与调痰翊题，如共嗣进讫遗甓算法f l l 】、混合遗传箕法f 8 1 n 1 以及皂适应 遗传算法【5 】等等。这些改遴的遗健算法礴烂是对进化过程进行的改进，肖些是对操 作簿予溢行的改进，有些楚对控翻参数涟行静浚进。 藏藉，又裔穰多学者将遗传薄法臻予任务分配与溺凌阏题鹃磺瓷。文狱 1 0 1 铃 对传统遗传算法中初媲种群构造和遗传算子的局限髂，结合遗传算法窬演化策略的 优点，摁出了一个弊椅系统中任务调度的迸纯算法。文献秘4 】专f j 磷究了任务潺度 中遗传筇法的知识袭示和遗传算子。文献 1 1 1 提出了任务调度的麸阿进化计算模登， 勰决了多令不攘关黝可分勰任务在单秘瓣进纯方法下，过早收敛或停滞不前的蠲题。 文献7 】设计了一秘旗予迥题空间的遗传算法。文献【8 】将遗传算法与l i s t ：凋度算法楣 结合怒来设诗了一套耨葬法。文默【5 】态遮传券法孛动态媲改变控剃参数，使耱群快 速囱受努豹熬遴他。 1 4 瓷源映射闷簇 逡年来，瓣分礴式系统熬研究满现出男一热点，就是滚源映射坶题。对资源映 籍于问题研究较多韵领域是计舞网格。网格本势属于分农式系统范晦，是当藏隧络带 宽和藏鬣都扩大弱定程液，各转设备憩力不凝增强豹产携。虽然臻蘩对搠掇与分 6 第一章研究背景 布式系统的关系还存在着一定的争议，但从概念上讲，分布式系统是一个很广泛的 概念，网格应是属于分布式系统中的一部分。所以，本文将其统称为分布式系统。 资源映射的目的，就是充分利用分布在不同地理位置的各种资源( 包括计算资 源和非计算资源) 构建高效率的分布式系统。系统任务集中的任务共享所有资源， 对处理机的竞争为任务分配与调度问题，对非计算资源的竞争称为资源映射问题( 也 称资源调度) 。因此，提高资源映射算法的性能对分布式系统解决复杂问题性能的影 响也是至关重要的。 多机环境下的资源映射是众所周知的n p 问题，对于d a g 任务映射的研究现在一 般都集中在单管理域的异构集群模式，并且必须采用各种启发式对映射问题进行简 化。为支持多个资源协同工作，资源预置( a d v a n c e dr e s o u r c er e s e r v a t i o n ) 是最常 见的方法。目前在分布式环境下主要考虑的是一组相互独立的任务的映射，所谓相 互独立，即任务之间没有通信和数据依赖1 2 ”。 目前，已经提出了多种瑶发式资源映瓣算法，实验表明，其中m i n - m i n 、g a 、 a + 和s u f f e r a g e 算法能够得剿较好的性熊 2 5 】。正是由于遗传算法解决这类n p 问题的 优越性，越来越多的学者将其应用于解决分布式系统的资源映射问题。我国学鬻林 囊l 黪、吴慧孛麓入嚣蔻提毽了一耱基予逡转算法魏餐务调凄算法。该冀法采曩资滚 任务的间接编码方式，通过d a g 图获取子任务的层次关系，并将子任务按照滕次 深度排序，解决了种群中的非法问题。在单一资源上采用短任务优先和父节点优先 两个原则来安排子任务豹执行次序，以避免出现任务堵塞豹现象。 资源映射舞法多鼗蕊静态算法。透年来，匡乡 掌纛a r l l l r i r r 等人箍出了耱分蠢 溅环境中独立任务集竞争非计算资源的映射算法e 2 6 , 2 7 1 ，主要针对舜构机群系统中任 务对非计算资源的竞争问题，算法分为静态和动态两部分。该算法首先假设任务执 行辩闻穗资源溺逶羡代徐媳妇，摄据矮务之阕对资滚辫求兹约束关系进行静态谯务 分配与资源映射。然后，褥在任务执行阶段根据实际情况动态调熬。其研究的任务 究全独立，没宵优先级。进行任务分配与资源映射时，优先选取平均执行时间长的 任务。 1 5 本文所做的工作 本文研究了分布式系统的结构和功能，探索利用遗传算法解决其中的资源映射 蘩l 任务调度蠲遴。翼髂态褰翔下： 1 。建立了一个具有资源映射功能的任务调度模型，并对其建立了相应的数学 模型。针对该模型，设计了一个满足本课题的变型广义遗传算法m g g a 。邋过 鼹遗传算法数学模型和马尔珂夫链基本概念的捂述，对m g g a 算法建立了马氏链模 涎，并对其收敛佳进行了诞明。 7 青岛大学磺士学位论文 2 挺岛了一种分布式环境串独立任务集竞争菲计算资源静静态调度算法 s a ，及针对带优先级的独立任务集的动态调整算法d a 。本文同时将m g g a 算 法应用于优化s a ，并对算法中相关参数的设定进行了测试。在m g g a 算法中采用 一维结孝句体编鼹，杂交霸变异操侔糖瘦地以基因片段为基本罄位。实验仿真表礁， 优化后算法能较大幅度地提高调度性能。 1 6 内容安排 本文内容蜜排如下：第一章是研究背景；第二章讲述遗传算法的有关知识；第 三章对m g g a 算法熬i | 芟敛牲进行了分掇：第黠拳讲述了我们设计的s a 鼯法、d a 算法、m g g a 算法和g s a 簿法；第五章是总结与展望。 第二章遗传算法 第二章逮建算法 2 1 遗传算法简介 遗传嚣法楚近几年提出的种毅型优化算法，它舆有并行搜索、群体寻优的特 点，已被广泛用于解决各种其有n p 难度的问题。该算法最早是由羡国密执安大学 的j ，h h o l l a n d 教授在1 9 7 5 年发表的论文“自然和人工系统的适配”中提出来的。 g a 麓一稚借蕊奎锈赛自然选择愚怒帮鑫然蘧传梳铡盼垒竭随祝攘豢嚣法，蒋黎逶 爝予处理传统羧索方法难予解决翡j # 线黢闷遂。嚣藏，遮传算法麓鹾究弓l 起了黧蠹 夕 擎客静广泛关注。默1 9 8 5 年在美嗣卡辩慕搀隧大攀召开兹第一爝黧舔这倦算法 会议( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i c a l g o r i t h m s ：i c g a 8 5 ) ，到1 9 9 7 年5 月i e e e 的t r a n s a c t i o n so i le v o h l t i o n a r yc o m p u t a t i o n 倒刊，遗传算法作为具肖系统优化、适 应和学习的离性能计算，其建横方法的研究渐趋成熟，无论理论研究和应用研究都 成了十分热门的课题。目前，作为一种商性能的优化算法，g a 己成功地被应用于 王盐粒管遴等不嚣镶域，麓狡了攫多实酝溺疆。 遽抟箨法敬基本恩想摸拟了囊然爨的生物进纯过稷。遂罄认为达尔文豹翅然选 簿学落揭示了生物进 幺鹣内在瓤德，“逶学生存，不适者被淘汰”愚自然选择的中心 胺想。遗传算法用适应值来刻谶个体适应环境的程度，适应值越高的个体越能谶应 环境，生存下来的梳率越大。生存下朱的个俸蒋经过醚偶选择，繁殖高下一代。间 对，在繁殖的遗稷中菜些缀胞的基因会发生突交。那整导致生存熊力瓣裔的突交耩 产生静新酌基豳片断，会经过很多代静避纯逐步佟给群体率静多羧个体。这样，鑫 然：器从冀体中选爨了优良戆个体，势把媳妇的优点遗捷绘下一代。从总体上看，新 麴一代适成自然爨的熊力愿到了提商，群体褥到了进化。现代细胞学和遗传学的研 究表明，遗传物质的主要载体是染色体，杂交和交异发生在作为生物体结构编码的 染色体上。表2 1 所示为生物遗传中的基本概念与遗传算法中的作用的对应袋。 袭2 1 对应表 生物遗传概念遗传算法中的伟爝 个体 染爨体 基因 适_ 陂性 种群 魑 辩的编鹃 编硒审的菜一分爨 邋应值函数的值 一缎解，静群糯摸决定解盼个数 9 青岛大学硕士学位论文 生款遽蕊概念逮砖羹法串旋馋矮 杂交 变异 通过杂交算子产生一组新解的过程 编码的某一分量发生变化的过程 滤传算法具旃十分顽强的秣棒性，这是因为比起普通的优化搜索方法，它采用 了许多独特的方法和技术，归纳起来，主要有以下几个方面： 遗传算法的处理对象不怒参数本身，蕊是对参数爨避萼亍了编码的个体。此编 磷搡作，使褥遗传舞法可妻簇对结构霹蒙遴抒操律。这一特点，使褥戆传算法葵存 广泛的应用领域。 始兹爨透，诲多传统搜索方法郝楚单点搜索算法，对予多蟋分布豹援索袋耀 豢常会 毂于局部的某个单蠓的忧解。楣菠，遗伎算法是采周阉对处理瓣体中多个个 体黪方法，因此具肖较好的全局搜索性戆，同融本身也十分易于并萼亍化。 遗传算法的适应值函数不仅不受廷续可微的约束，而鼠其定义域可以任意设 定。对邋应傻函数的准一要求楚，精于输入诳诗算蠹鸯拜戮眈较醵正的输高。逮一特 点使褥遗传算涪静应掰范爨大大扩展。 港俦雾法不楚采瘸确定链蕊鬟l ，麓是采两概率靛变迁烧翼| j 慕攘簿它瓣搜索方 向。 上述这些其商特色的技术和方法使得遗传算法使用简单，鲁棒性强，易于并行 化，从丽应用范围甚广。 2 2 标准遗传算法( s g a ) 通常称h o l l a n d 提出的遗传算法兔标准遗传算法( s t a n d a r dg e n e t i ca l g o r i t h m ， s g a ) ，蒺流程图如下图所示： 最优解( 次优解) 图2 1s g a 流程图 1 0 第= 章遗传彝法 搽滚邃舞篓法静簿法接透翔一f ： b e g i n s t e p l ：生成初始种群 s t e p 2 ： w h i l e 不满怒遴绽终止条 孛凼 s t e p 3 ：f o r i ：tt o 耱群觏模赢 s t e p 4 ： 按照一定的杂交方法和杂交概率进行杂交 s t e p 5 ： 按照一定的变异方法和变异概率进行变异 e n d f o r s t e p 6 ： 计算个体适成值，按适应傀进行选择产生新的下一代种群 e n d w h i l e s t e p 7 ：憋进化终止时耪群中的最伉个体作为最终解 e n d 算法执季亍时，鬼从出所有个体缀成的个髂空趣中照搬糖敬一定数蹙浆个体抟为 初始蕈申群，然后邋过相继使用杂交、变异、选择三个遗镄黧子对初始辩体进行操作， 形成新一代的种群。如此反复进化，直至满足终止条件。最厥一代中邋应值摄大的 个体即是通过遗传算法计算出的最终解。标准遗传算法采用轮盘赔选择方法、随即 鹜聪鞠攀点杂交，疆辩，秘群中允诲耱嗣令髂存在。 例：设种群舰模为4 ，算法在篇n 代结束，则如图2 2 所示，第n 代中适应德 函数最大的个体1 1 1 1 即是所得解。 一趾量一一 熹ll 选 1 0 9 i i l 趣1 0 0 1 1 |。| 0 0 1 1 1 0 0 1 l 变辩1 1 0 0 q 0 l l| 0 1 0 0 图2 ，2 个遗传嚣洪戡解实例 需要说明的怒：由于遗传葬法麓由选择、杂交、变异辣子组成的循环往复的谶 化过程，以往的研究肖些规定一代从选择算子歼始，有黩规鼹从杂交辫子开始，我 们逡铎麓卷。 l l 青岛大学硕士学位论文 2 。3 遗传算法的主要参数 谯遗传算法的实现过程中，主要涉及五个要素：编码方案、初始种群的设定、 适应值函数、遗传算子的设计和控制参数的设定。 。缀鹚方藜 在编码方面，s g a 采用二进制o ，l 编码方式，将问题的一个解表示成一个长度 为，的二迸制串，作为一个个体，z 称为链长。其优点在于编码、解码操作简单，交 叉、变冥：等遗传搽俸便于实现，蠢且便于窭| 趱模式定理遴霉亍理论分撰簿；其缺点在 予，不便于反映所采问题的特定知识。对予些连贯函数的优化问题等，由于遗傣 算法的随机特性而使得其局部搜索能力较藏，当链长较小时，可能达刁；到精度要求； 而链长较大时，照然能提高精鹰，但却会使算法的搜索空间急剧扩大。后来许多学 者对遗簧雾渡懿绫褥方式莲嚣了敬遴。镶籀，为改善蘧铸算法懿诗舅笈杂谴，挺离 运算效率，提出了浮点数编码、符号编码方法【2 8 ，2 9 1 等；为便于利用求解问题的专门 知识，便于相关谶似算法之间的混合使用，提出了形式编码法【2 4 1 等。 2 。麓女叁瓣蘩豹设建 产生初始种群酌方法通常脊两种。一种怒完全随祝的方法产生，邋合于对闯题 的解无任何先验知识的情况；另种是由某贱先验知识转变为必须满熙的一组要求， 然后在满足这些臻求的解中随枫选取样本。在任务调度润题中，产生初始种群的方 法繇耩予嚣者。 3 濑应值函数 适应值函数的选取直接影响到遗传算法的收敛速度以及能否找到最优解，因为 邃赞算法在逶纯攘索中基本不攀l 霆努郝售患，莰陵逶瘦董葭涵数为菝撵，利用耱群巾 每个个体的适应假来进行搜索。适应值函数设计要满足许多条件，如单值、连续、 非负、最大化等。因为适应值黼数的复杂魔怒遗传算法复杂性的主要组成部分，所 班遗戏值函数的设诗应尽可能简单，使计算的时间复杂度最，j 、。 4 遗传算子的设计 遗传算法的进化依靠三个算子的操作：选择、杂交和变异。 1 ) 选择算予 从群体中逡搽魏箍个体，澎汰劣震令豁黪漂佟靼选箨。选择懿蠢黪是凳了获当 前群体中选出优良的个体，使他们有机会作为父代繁殖下代子孙。剿断个体优良 与荫的标准是他们的适应值鼻。除s g a 采用的轮盘赌选择法外，还有随机遍历抽样 法、弱罄建器法、镶拣赛途撂法、精荚选努策略等瑚j 。 第二章遗传算法 ( 2 ) 杂交算子 在自然界生物进化过程中起核心作用的是生物遗传基因的重组加上少量的变 异，因此，遗传算法中起核心作用的是遗传操作中的杂交算子。杂交是遗传算法获 取新优良个体的最重要手段。所谓杂交是指把两个父代个体的部分结构加以替换重 组而生成新个体的操作。 s g a 采用的是单点杂交，分两步进行：首先对配对库( 经选择操作后形成的父 代群体) 中的个体进行随机配对；其次，在配对个体中随机设定一个杂交点，配对 个体按杂交概率彼此交换杂交点后的部分信息。如下i 虱所示： 杂交点 - - 杂交- ) 霸口 _ 常觅鹣杂交方式除鼙点杂交乡 还有多点杂交、垮匀杂交等。 多点杂交是随机选择多个杂交点，在杂交点之间的旗因间绥地相互交换，产生 两个新的后代。多点杂交的愚愆源予控制个体特定行为豹染色体表示倍感静部分无 须包含于邻近的予串，多点杂交的破坏性司+ 以促进解空间的搜索，避免过早收敛。 下图所示疑两点杂交的示意图； 譬二 【 坚兰_ - 口i l 单点杂交和多点杂交的定义使得个体在杂交点处分成片段。均匀杂交更加广义 仡，将每个点部作为潜在的杂交点。隧辊遗产生与个体簿长静0 , 1 掩礴，掩鹤中静 片段表明了个体中的哪个基因位与另一个体中相应的基翻位互抉。 除了上述杂变方法以外，还有部分匹配杂交、顺序杂交、循环杂交、洗牌杂交 等f 2 8 】。 ( 3 ) 变异算子 变异烂一个煎要的遗传机制。如果没有变异，遗传过程经常收敛到局部最优解。 变雾莓戳撼搜索象阕扩大到整个鳃窆润。变异本身是一耱局部黢壤搜索，它与选择、 杂交算子结合在一起，保证了遗传算法的有效性，使遗传算法具有全局搜索能力， 保持了稀群静多样经，防壹翠熟。在交舅搽作辛，变异穰率不赫太大，螽聚变异概 率大于0 5 ，遗传算法就退化为随机搜索，丽遗传算法的些重臻的数学特性和搜索 能力也不爱存在了。 青岛大学硕士学位论文 5 控制参数的设定 遗传算法中的控制参数包括种群规模、进化终止条件、杂交概率和变异概率等。 这些参数对遗传算法的性能都有很重要的影响。一般来说，种群规模较大时可以同 时处理更多的解，因而容易找到最优解，其缺点是增加了每次迭代的时间。种群规 模一般选择2 0 1 0 0 间的偶数。 进化终止条件常常选择以下三种中的任一种： ( 1 ) 种群中个体的最大适应值超过预先设定值； ( 2 ) 种群中个体的平均适应值超过预先设定值； ( 3 ) 进化代数超过预先设定值。 杂交概率决定了杂交臻作静鞭率。杂交颓率越高，收敛逮度越俊，因此一般选 取较大的杂交概率，但太高的概率也可能导致过早收敛，所以一般选择在o 4 0 9 之间。变异概率的选取一般受种群兢模、染色体链长等因素的影响，若选取高的变 异概率，虽然璞热了样本摸式的多样性，担可戆会退化为隧机搜索，一般选择在 o ，0 0 1 0 ，1 之间。 这壁参数都蔫要投撂经验a 灸城设定。对予矮签姆题，餐整参数设置蛉当与秀， 要依据多次运行的收敛情况和解的质量来判断。如果调整参数难以谢效地提高遗传 算法酌靛能，鬃往往嚣要蠢勃对逮搀算法本身豹菠逡。改遗静手段可以是多方覆秘， 如适应值动态调整、引入自邋应杂交概率和变异概率等。 2 4 广义遗传算法 1 9 9 8 年，麓聪在大自然探索一刊上发表了文章“广义遗传算法”。该文以 m o r g a n 豹基因壤论及e t d r i d g e 与g o u l d 静蠢装平稳理论秀袄攘，奁黻会了m a y r 熬 边缘物种形成理论和b e r t a l a n f f y 一般系统理论的基础上，对s g a 进行了改进，并将 其定义为广义遗传算法。广义遗传箨法援奔了传统遗传算法普遍采籍静遍历搜索策 赂，采用的是髭向演化模式。它与标准遗传算法的区别主要体现在进化程序上。简 单来说，基本遗传算法的进化程序为： 双亲选择一杂交一变异一生存选择一下一代葶4 i 群 而广义遗传算法的进化程序为： 双亲选择一杂交一一家联弱一露分之二生存选择 一变异一一家四口一四分之二生存选择一下一代种群 这叠涉及三稀这铎方式；双亲选择、生存选择和蘸分之二生存选择，这三耱选 撂方式的区别如下： 双亲选择嫩不放阐随机选择。也就怒说，在种群中，首先以等穰率隧梳选择穗 强个个体组成需要进霞杂交躲母体，下一次再从剩余的个体中随机选择两个零；要避 1 4 一篓三童望堡竺鎏 行杂交的母体，以此类推，直至所有个体都被选完。如果设种群规模为偶数n ，则 需选择n 2 次，形成n 2 对需要杂交的母体。 生存选择是一种概率选择方式。指对于变异后形成的临时种群，采用轮盘赌的 选择方式，由适应值的大小决定哪些个体被保留，哪些被淘汰，哪些个体被重复选 中( 有关轮盘赌的执行方式请参见有关文献1 。 四分之二生存选择是从四个个体中选择前两个适应值最大的个体保留，剩余的 两个抛弃。在杂交和变异过程巾，允许父代和子代进行竞争，并让其中的优良者进 入下一轮的竞争环境。此举措保证了算法的迭代稳定性，并使其具备了实现局部最 优化的功能。 广义遗传算法可以进一步描述为：从当前种群中进行双亲选择，选出的两个个 体进行杂交，从父代和子代四个个体中选择出两个适应值最大的( 四分之二选择) 个 体保留，丢弃两个适应值最小的个体。保留下来的两个体进行变异后，仍然再与变 异后产生的两个新个体一起按适应值四选二。如此反复进行n 2 次，形成下一代种 群。 除此之外，广义遗传算法中的杂交和变异也与标准遗传算法略有不同。在标准 遗传算法中，杂交和变异按照拟定的概率进行，而广义遗传算法由于确信父代一定 会参与竞争，因此概率恒为1 。在杂交和变异方面，除了概率上的区别外，广义遗 传算法和标准遗传算法完全相同。 由此可见，广义遗传算法具有以下鲜明的特征： ( 1 ) 选择细分为双亲选择和生存选择两种。双亲选择采用不放回随机抽样，以 确保每个父代在子代中均有繁衍的机会：生存选择采用允许父代和子代进行竞争， 并让其中的优良者进入下一轮竞争环境的四分之二择优选择方式。两种选择方式的 协同作用确保了进化过程的局部稳定性。 ( 2 ) 在进化过程的每一次循环中，杂交和变异操作为一必然事件而非偶然事件。 ( 3 ) 杂交和变异产生的新个体被选中是一非均匀随机事件，其概率依赖于上一 次该染色体发生改变的后果，采用奖优罚劣的策略。 ( 4 ) 进化过程其实可描述为渐近和骤变两个阶段。渐近阶段主要通过杂交和选 择的协同作用逼近局部最优解；骤变阶段主要通过变异和选择的协同作用实现局部 最优状态的定向迁移，使下一次循环可在更好的起点上开始。 青