一种基于并行遗传算法的机群负载分配调度策略的设计与实现

一种基于并行遗传算法的机群负载分配调度策略的设计与实现TOC\o"1-3"\h\z概述 6§1.1并行处理技术的开展 6§1.2集群技术概述 6§1.3支持软件 7§1.4任务分配负载均衡的重要意义 8并行系统中的任务分配和负载平衡问题 10§2.1任务分配问题的概述 10§任务分配的一般描述及影响因素 10§任务分配问题描述 11§2.2负载均衡问题的概述 12§概述 12§负载平衡问题描述 13§2.3现有任务分配及负载均衡算法及其优缺点评述 14§基于图论的分配策略 14§2.3.20～1程序设计谋略 16§2.3.3“合一阈值〞启发式分配算法 17第三章一种新的基于并行遗传算法的策略提出及可行性分析 19§3.1遗传算法概述 19§3.2遗传算法的结构 20§3.3并行化的目的 21§3.4并行性分析 22§3.5并行算法与并行计算机系统 23§3.6并行搜索与最优化 25§3.7并行遗传算法形式化地定义 29§3.8解决任务的分配与负载均衡问题的优势 30算法建模与设计及针对机群应用环境的具体实现 32§4.1和任务分配及调度相关的概念 32§4.2算法的目标与设计原那么 34§负载均衡算法的目标 34§负载平衡算法的组成 34§4.3算法的描述及数学模型 35§网络应用及其特点 39§4.6以PVM为支撑的PC机群环境的概述 39§4.6.1PVM系统概述 39§4.7针对机群应用环境的具体设计与实现 46§相关问题及解决 46§4.7.2虚拟效劳器技术及其优缺点 46§一种新的网络效劳并行计算模式的提出 48§中连接重定向技术及其实现原理 52§中连接重定向技术及其实现原理 55§在套接口上的实现 59§4.4根本算法的设计 62§4.5算法的分布并行设计 70§简单的主从模型： 71§网络并行模式: 74§4.5.3两级主从模型： 74§负载均衡策略设计 76实验模拟与性能分析 79§5.1性能评价与分析概述 79§5.2实验环境与测试 83结束语 84参考文献 85摘要随着计算机和网络技术的迅速开展，用高速网络连接一组工作站或PC机组成并行计算机系统或利用网络已有资源组成高性能计算环境，来解决许多中、大粒度、十分复杂的计算问题变得越来越普及。采用这种思路建立起来的计算网络是一种可扩展、灵活的、高性价比的分布式并行处理系统，能否充分利用系统的冗余资源和最大限度发挥该系统的潜力，任务的分配和负载的动态调度是主要的影响因素之一，同时也是一个非常困难的问题。十几年间相继提出了许多解决方法，如：基于图论的分配方式及“阈值〞合一法等，这些方法各有其有优缺点，但都不是完美的解决方案。当今，计算机科学各个领域的开展几乎都显示出向并行计算的过渡趋势。人们开始从并行和分布式处理的角度重新探索计算机的各种理论和应用。并行遗传算法的出现，无疑使我们在解决NPC之类问题方面有了新的转机和希望。遗传算法是一种借鉴生物界自然选择和遗传机制得高度并行、随机、自适应得概率搜索算法，主要用于处理最优化问题和机器学习等方面。而并行遗传算法可以利用并行计算机的优势，将一个遗传算法的程序分配给几个处理机并行以提高程序执行速度，缩短算法执行所需的墙钟时间。本文提出了一种基于并行遗传算法的任务分配策略，并且设计了自适应的负载均衡算法，针对PVM系统进行了模拟和实验，同时，还针对PVM在网络应用方面的弱点，采用了底层封装的方法，为PVM系统补充了一个调用库，使得算法能够根据不同的应用类型选择不同的调度方法来实现负载的平衡。并且对算法进行性能分析和应用例如实际测试，到达预期的效果。最后，对这方面的研究作了总结并为进一步的研究工作提出一些看法。关键字：分布式并行处理，并行遗传算法，机群，集群，并行虚拟机，任务分配，负载平衡ABSTRACTWiththerapidprogressofthenetworkandcomputertechnologies，itisbecomingmoreandmorepopulartocombineagroupofworkstationsormicrocomputersintoadistributedparallelComputationsystemwithhighspeednetworkorbuildahighperformancecomputingenviromentWiththeexistingresourceinordertoresovlethesemediagranularitycomplexityapplicationProblems.Thiscomputingnetworkisakindofscalable,flexibleandhighperformandeviapriceratiodistributedparallelprocesssystem.Thattaskallocationandworkloaddispatchmentbecomesthekeyfactorofwhethertheredundanceresourceandpotentialityofthesystemcanbemadethemostofornot.Atthesametime,itisalsoaveryardousissue.Manysolutionswereproposedinthepastfewyears.forexample,allocationbasedongraphicstheoryandsoon.Butthesemethodsarenotperfect.Recently,itindicatesthatallfieldsofcomputerscienceisbeingdevelopedtowardsparallelcomputing.Peoplebegintostudythesetheoryandapplicationproblemswithdistributedandparallelpointofview.ItisnodoubtthattheparallelgeneticalgorithmbringsanewopportunitytousontheNPCProblems.Thegeneticalgorithmisahighparallel,random,adaptivetheorythatintroducesnaturalselectionandgeneticalmechanismfrombiologicalkingdom.Itisusedmainlyinoptimizationandmachinestudyandsoon.Anditcanreachthebestefficiencybyrunningontheparallelsystem.Inthispaper,weproposeataskplacementbasedontheparallelgeneticalgorithm.AndwedesigneansimpleadaptivebalancealgorithmforPVMsystem.Andwealsoenhancealibraryfornetworkapplications.Itisprovedfeasiblethroughourexperiment.Inaddition,wesummarywhatwehavedoneandproposesomeadviceforthemoreresearch.Keyword:distributedparallelcomputing,geneticalgorithm,PVM,task,Workload,adaptive概述1.1并行处理技术的开展最近20多年，并行处理技术一直是计算机科学技术领域的重大研究课题之一，它对提高计算机的性能有着重大作用和广泛的应用前景。并行计算机并不是凭空产生的，而是反映了单处理机向高指标开展的自然趋势。现代使用的单处理机结构是JohnVonNeumann式的，由单个程序计数器控制其执行顺序，在任一时刻，只有一条指令在执行。机器的串行性对于高速处理来说是一个严重障碍。单处理机运算速度的提高是有限的。现在实际中存在的许多大规模和超大规模问题用传统的单处理机是不能解决的。现在进行大规模信息处理采取的主要策略是克服VonNeumann模式的缺点和把工作分散到许多单处理机中，尽可能的高速度、高效率的进行并行处理，即开展并行处理技术。并行处理技术中的几个主要难题：任务的分配非常困难在处理机或节点机数目很多的情况下，要把任何一个问题分解成足够多的并行过程是非常困难的，并且着也不是所有的问题都能做到这一点。在分布式计算机系统中，由于分布式算法具有分散的通信结构和相对独立的模块，在衡量一个算法好坏时，除了考虑时间复杂性、空间复杂性还要计算模块间的通信量IMC，因而一个分布式算法比其他算法更加复杂。在分布式计算中如何充分利用计算的局部性原理和寻找任务最优分配算法以减少过程之间的通信量和活获得高性能，是一个至今仍未很好解决的问题。很难摆脱串行处理方式的约束现有的软件产品绝大多数是按串行算法研制的。为了继承发扬人类的这笔财富，在原有的应用领域内研究并行处理技术时不得不考虑如何利用这笔财富，因此现有的并行算法绝大局部是从串行算法改造过来的。处理机之间的通信开销有可能使并行处理技术得不偿失并行处理技术的主要难题是软件对于含有大量处理机的并行处理结构，软件对系统的影响更大，其性能差距可几个数量级，软件的关键在于如何高效地进行存储管理和机间通信。软件中最难的是并行编译程序。1.2集群技术概述随着电子信息时代的来临，人们把越来越多的工作交给计算机完成。因特网为人类展示出更为宽广的分布式计算模式的天地，随着个人计算机性能的增强、存储设备容量的增加，似乎数据更多的分布在各个微机中。但是对于大型企业和网络提供商来说，他们无限增长的数据必须集中存储和处理，因此企业级的运算对计算机的处理能力提出了更高的要求，计算机系统供给商必须不断完善，改良现有的计算技术，使它们越来越强大。集群技术是使用特定的连接方式，将相对于超级计算机廉价许多的计算机设备结合起来，提供与超级计算机性能相当的并行处理技术。早在七十年代就有人提出可以使用这种集群技术完成并行处理，但是由于受到当时网络交换技术的限制，集群系统在性能上与其他并行处理系统相距甚远，直到ATM技术、千兆位以太网技术逐渐成熟的今天，它才具备了与超级计算机相匹敌的能力。目前最为流行的方式是用高速或超高速网络传输设备将几台效劳器相连，实现并行处理，屏蔽单点失效。目前对集群技术需求最迫切、开展最快的领域主要有：www应用、数据库应用等商业计算领域。集群系统可以通过使用纯硬件的方式或使用软硬件结合的方式来搭建。在日常实践中，天气预报、海洋模型和环流、遗传工程、先进工业制造技术、能源工业、地震分析、化学工业、材料科学、生物科学、环境研究、结构分析、仿真、电子交易和军事等许多领域中都存在着大量的复杂计算问题，被称之为“巨大挑战问题〞，解决这些问题无疑对人类有着重要的意义，这也就是高性能计算所要努力的目标。美国从1992年开始实施高性能计算方面的方案HPCC，并投入巨资研究解决“巨大挑战问题〞的环境、方法和技术。实现高性能计算的核心是并行技术的开展，尽管各类并行结构的超级计算机在高性能计算中发挥了重要作用，但随着网络技术的开展和普及，以网络为根底的分布式并行计算环境以其较高的性价比和大范围、大数量异构机群并行成为新的高性能计算环境，其思想来源于并行结构随网络开展的自然延伸：连接多个日益廉价的独立计算机，如工作站和PC机，形成类似MPP的性能；利用网上日益庞大的空闲处理机资源，形成可扩展的高性能计算能力；连接广域范围内的各种资源，形成巨大的协同计算环境，并使这些昂贵的资源能为尽可能多的用户共享。专用机群一般由一组同构的处理机组成〔有时也有异构情况〕，通常安装在一个机房内，或者将主板等安装在一个机柜的各机箱中〔商业机群常用这种方式〕，或简单地把PC机堆砌在机架上〔PilesofPC〕。在这种机群中，每个处理机都是专用的、无属主的，由系统管理员统一管理，用户可通过前端机进行访问，用户无需知道机群的详情，就像使用MPP机一样，易于配置和管理，不受外界干扰，通信可靠且延迟小，适合于面向加速比的并行任务和面向吞吐量批处理作业。专用机群具有相对结构和管理简单、易于扩展等特点，用途极广。1994年夏，美国的研究人员建成了第一个Beowulf机群，它由16个DX4处理机组成。1997年，又推出了16个基于PⅡ的机群，只需花费5万美元却具有每秒10亿次的浮点运算能力，而购置具有相同能力并行机的投资数却是它的10倍。机群技术已经成了开发本钱有效且可扩展的并行计算机的一大趋势。1.3支持软件随着开放的分布式计算环境的普及，系统软件所扮演的角色日趋重要。为协调各节点机的工作，系统应具备负载管理功能。工作负载管理在支持对完成企业商业目标十分重要的应用程序的同时，工作负载管理必须对所有类型的运行任务进行有效管理，同时最大限度地利用硬件与软件资源。从功能角度来说，工作负载管理软件调度，分析并监测企业应用工作负载的进程。工作负载管理在网络水平上来说具备许多传统操作系统的功能，它动态地通过调度用户作业以充分利用分布式异构计算资源。虽然与数据管理和系统管理联系甚密，工作负载管理在几个主要方面同他们有显著的不同。数据管理为所有应用程序提供＂分布式数据平台＂，而工作负载管理提供“分布式计算平台〞；系统管理侧重于硬，软件资源并由操作人员使用，而工作管理支持企业系统的计算工作负载，并被可信任的最终用户直接或间接地使用。工作负载管理弥补了系统管理的缺乏之处。系统管理确保了分布式计算资源发挥正确的功能，而工作负载管理确保了分布式计算资源有效地满足重要商业处理进程的要求。以前，工作负载管理在系统软件市场中并不是主要的组成局部，由于转向异构式企业计算环境的强烈趋势，工作负载管理日趋重要。正是因为它能够在日益复杂的分布式环境中充分利用异构的硬/软件资源。在分布式计算环境中充分发挥虚拟主机的优势，将数据管理，系统管理和工作负载管理集成起来是十分重要的。工作负载管理的功能与需求:从功能上角度来说，涉及到分布式应用工作负载的调度，分析，监测与操作。下面讨论这三个功能领域。工作负载调度工作负载管理最重要，且是最根本的一个功能就是利用最适宜的可用计算资源进行动态作业调度。根据作业要求，作业调度可以基于以下一或多个方面：资源可用性：一项作业可能要求一种特殊的系统平台，一定的内存或特殊的软件许可证，无须用户指定主机运行该作业，工作负载调度动态地用最正确可用计算资源满足作业要求。如果所需资源不可用，它可将作业延迟，等待下一次批处理来完成。工作负载分析：尽管作业调度优化了工作执行程度并确保了可靠的作业处理，作业分析还支持作业数据综合分析以进入整个系统处理。作业分析使用数据获得计算资源的下载与可用性作业处理与资源利用系统配置；1.4任务分配负载均衡的重要意义为充分利用并行与分布式计算环境中，多处理机的并行处理能力，根据不同的数据约束关系和计算要求。一个任务往往被分解成多个子任务，任务分配与调度就是要将分解好的假设干个子任务指派到处理机群中的各个处理机，并根据给定的子任务的数据约束关系合理安排好每个处理机的执行顺序。遗传算法是于70年代的一种全局优化算法。它模拟和借鉴自然界生物进化的机理，具有简单、通用、稳健的特点。并行遗传算法利用并行计算机的优势，将一个遗传算法的程序分配给几个处理机并行以提高程序执行速度。计算机系统的性能，从静态来看，各个节点机的负载根本平衡是高性能的表现，从动态来看，任务的平均响应时间是性能的尺度。能否做到合理的快速任务分配及负载的动态平衡是能否充分发挥系统资源优势，提高资源利用率的关键所在。也是防止软件并行性和硬件并行性之间失配的前提。分布式并行系统中的任务分配和负载平衡问题2.1任务分配问题的概述一个分布式并行系统由多个处理机或节点机组成，当有任务到达或产生时，要决定运行在哪个处理机或节点机上，这就是任务的分配和调度。静态分配策略是在系统运行的初始时刻，将用户提交的任务集一次性分配给系统中各处理机或节点机，以后直到这些任务执行完毕，各处理机上的任务一般不在变更。动态分配策略〔负载平衡或负载共享〕那么是在运行过程中，将任务分配给各处理机，并对其上的任务数进行动态调整，尽可能使系统中处理机上的负载到达根本平衡，减少系统平均响应时间。我们知道，一般情形下，在处理机或节点机的数目大于3的多机系统或分布式系统中的任务分配问题是一个NP完全问题，人们通常不会去寻求解决问题的最优解，但对于具体的分布式系统，在适当的假设条件下寻找不一定最优但实际可行且效果满意的方法，仍是目前十分热门的研究课题。然而，在实际的应用系统中，对任务动态调度的需求要多于对任务的静态分配，所以，动态任务分配算法〔负载平衡或负载共享〕、自适应分配算法及智能化任务分配算法将是进一步研究的方向。任务分配的一般描述及影响因素任务分配的环境一般的分布式系统的结构示意图如下：MnMnnn…M1M22SP1PNP2图2.1分布式系统的结构图其中，〔M1，M2，…，Mi〕是一组待处理的模块或子任务，〔P1,P2,…,Pn〕是系统的N个处理机或节点机，他们经过互连网络相互通信，分解机制S把m个模块或子任务合理的分配给n个处理机或节点机中某一些。通常m>n,位于不同处理机〔节点机〕上的模块彼此交换数据是通过他们所在处理机〔节点机〕彼此通信来实现的。任何一对模块的IMC〔intermodulecommunication〕的总量将随着模块对的不同而变化。所以，把这些模块分配给处理机〔节点机〕的方式，就可能影响整个系统的处理开销。例如，假设模块Mi和Mj的IMC通信开销很大，通信也较频繁，而且他们又分配在不同的处理机上，那么，相应的IPC〔interprocesscommunication)开销会增大，如果把Mi和Mj分配到同一处理机上就可能减少系统的总处理开销，此外，假设两个模块的IMC较小，且无优先制约关系把他们分配不同的处理机。显然，可能加速整个处理过程。影响系统性能的因素在任务分配中，均衡负载分配策略是把模块比较均匀的分给系统的所有处理机或节点机使得这些处理机或节点机差不多是均匀负载的，这种策略可最大限度的提高系统的吞吐量。如果，只注重减少IPC而不考虑系统的均衡负载，那么可将待处理的模块全局部给同一节点机，任务的处理时间却成倍增加了。显然，均衡负载和减少IPC是相互矛盾的两个因素，左右着任务分配的策略，影响着系统的性能，负载均衡可以提高系统的吞吐量，因为它试图将模块尽可能的均等的分配给各处理机，但由于IPC的开销又迫使分配策略不得不尽可能的把较多的模块分配给尽可能少的处理机或节点机。任务分配策略就是要设法折中这两个因素，将模块分配给处理机或节点机，使整个系统的性能提至最高。任务分配问题描述处理机间的通信开销是由于位于不同处理机〔节点机〕上的模块相互传递数据所引起，所以，IPC是模块间的通信开销和模块分配的函数，显然如果两个模块同驻在一个处理机〔节点机〕上，那么他们不会引起IPC。假设干模块构成一个任务，一个任务是单一的处理实体，任务的分解和分配是用于减少IPC的两个必要步骤。传统的任务分配策略其着眼点都在于设法减少系统中各处理机间的通信开销和运行模块所需的开销，以此来提高整个系统的性能。任务分配的目的是把一个提交任务划分成假设干独立的。具有最小IMC的模块，并且我们假定任务分解已由软件设计者在设计阶段完成，提交给系统的任务已经分解成假设干模块。任务分配是在并行处理系统中针对某个目标，按照一定的策略将规模为N的任务划分和映射P的处理机〔节点机〕上，那么在并行处理系统中一个任务的执行时间T：T=F〔tp,tc,te〕其中：tp子任务的最大执行时间；tc完成任务所需的通信时间；te其他开销一个计算问题划分出的任务越多，tp就越小，但tc和te会增大，而且增大的不仅可能抵消tp减小的作用，甚至可能使并行处理的效益完全丧失。任务分配问题也属于优化问题，即给定N个任务及其相互之间的关系和P个处理机，在各种可能的分配方案中选择最合理的一种，以到达某一最优目标。由于应用要求不同，认为分配的问题的最优目标条件有多种，如：最大吞吐量，最短完成时间，最大资源利用率，最小总费用〔计算时间和通信时间总和〕和最小通信开销等。2.2负载均衡问题的概述概述负载平衡也称负载共享，是指对系统中的负载情况进行动态调整，以尽量消除或减少系统中各场点负载不均匀的现象。具体实现方法是将重载场点上的任务转移到其他轻载场点上，尽可能实现系统中各场点的负载均衡，而且提高系统的吞吐量。负载共享有利于统筹管理分布式系统中的各种资源，便于利用共享信息及其效劳机制扩大局局部布式系统的处理能力。动态负载共享策略是指把系统中各场点上已有的负载作为参考消息，在运行过程中，根据系统中各场点的负载状况，随时调整负载的分配，使各场点尽可能保持负载的均衡。负载：负载共享算法中的关键问题是如何确定负载？根据任务负载可以判断某一任务在特定场点的响应时间。确定在该场点上的执行性能。曾经被研究使用过的负载包括CPU队列长度、某段时间内的平均CPU队列长度、CPU利用率等。Kunz发现负载的选取对系统性能有着重要影响，而最有效的负载计算方式是CPU队列长度。动机：用户将任务提交给系统处理，由于任务到达的随即性导致了某些处理机处于重载而某些处理机处于空闲或轻载状态。负载共享能够通过重载处理机上的任务迁移到轻灾处理机上执行来提高性能。在多处理机或节点机系统中，经常会出现某些处理机负载过重而另外一些处理机负载很轻甚至空闲的情况。为了提高处理机的利用率和系统并行计算的效率，人们试图把负载过重处理机上的一局部负载迁移到空闲或轻载处理机上，而导致了负载平衡问题的研究。负载平衡策略从总的来说，可以分为静态负载平衡和动态负载平衡。静态负载平衡在计算的初始阶段就作好负载的分配工作，由于它只作一次负载分配，不适合那些动态负载的情况，因此适用范围较小，而动态负载平衡根据计算过程中数据项的变化情况动态地分配负载，根据起迁移负载的目的处理机的选择是否随机，可以分为确定型和随机型。确定型方法根据一些预先定义的规那么进行，向哪些处理机迁移超额负载、迁移多少等都由这些规那么的某些参数决定。典型确实定型方法有扩散方法、梯度方法等。而随机型方法那么恰恰相反，负载的重分布是以随机方式进行的，由于没有一些预先定义的规那么，因此随即型方法较确定型方法更简单，但更难于模型化和形式化分析。负载平衡问题描述假设系统由N台处理机组成，顺序标记为P0，P1，…，PN-1，处理机之间通过网络加以连接。为了评测系统的平衡性，用每台处理机所拥有的数据项来表示负载，记为w[I]。整个系统的负载W=∑W(i),0≤i≤N-1，系统的平均负载为W*=W/N。为了便于算法描述，引用了数据发送指令和数据接收指令。发送指令send(desk[k],size[k])将大小为size[]的处理机上的负载发送到由desk[]标记的处理机上接收大小size[]的数据项。负载平衡算法分类负载平衡算法可分为动态算法和自适应算法二大类。动态算法根据系统状态，对可以接受任务的节点进行分析，如果处理机不空闲，可以将任务迁移到空闲节点，甚至可以将正在执行的任务迁移到其他空闲节点。但是，信息的收集、分析及作出决定要造成额外开销，不可小视。自适应算法通过动态改变参数甚至策略来调整自身的行为，以适应正在改变的系统状态，例如，某种负载平衡算法在A情况小的性能优于其他算法，而另一种算法在B情况下更优，自适应算法能够根据系统状态的变化选择适宜的算法。在无法通过任务迁移提高系统性能的情况下，自适应算法是很好的选择。另外，上述算法又可进一步分为抢占式和非抢占式两类。抢占式任务迁移是指可以转移一个已局部执行的任务。这个操作通常是非常昂贵的，因为收集任务的状态信息非常困难。任务状态包括虚拟内存的映像、进程控制块、I/O缓冲区、文件指针等。因此实现抢占式任务迁移开销很大。非抢占式任务迁移只包括未开始执行的任务，所以不涉及任务状态信息的迁移。在这两种方式中，执行任务的一些环境信息将传送给远程节点，这些环境信息包括用户工作目录和任务特权等。其中非强占式任务又称TaskPlacement。动态负载平衡算法可以根据集中的程度加以区分，分为集中、分散、组合三种。但集中式算法隐含着不稳定性，因为当中央控制节点出现故障是会导致系统瘫痪，一种解决方案是保持一个冗余节点，当中央控制节点出现故障是，冗余节点自动激活代行中央节点之责。集中式算法的另外一个缺点是易造成中央节点处的瓶颈。2.3现有主要算法及其优缺点评述基于图论的分配策略基于图论的分配策略的根本思想是把待分配的一组模块作为图中的节点集，连接两个节点的有向连线上的权表示每对模块之间的IMC开销。IMC开销为0意指相应的两模块之间无通信发生，因此它们在图中无连线；IMC开销为∝意指相应的两模块间通信量很大，必须分配给一个处理机。可见，图中节点间连线上的权表示分配在不同处理机上每对模块之间的通信开销。我们假定任何一对同驻模块的IPC开销为0。假设把系统的总的开销定义为系统的处理开销和IPC开销之和，那么，这种分配策略的目的就是实现最小的总开销〔C.C.ShenandW.H.Tsai1985〕。处理开销和IPC开销都是模块到处理机分配的函数，为了表示模块到处理机的分配，我们定义下面的分配矩阵X：x=而处理开销那么由下面的Q矩阵给出：Q={q},I=1,2,……,m;k=1,1,….,n其中qi,k表示mi在处理机Pk上的处理开销，它是该模块处理要求的度量。qi,k=∝隐含模块mi不可能在处理机Pk上执行。令Ci,j表示模块mi和mj之间的IMC开销。于是处理给定任务的总开销T表示为X的函数:T(X)=其中，第一项表示每个模块在它所分配的处理机上的处理开销，第二项那么表示非同驻模块之间的IPC开销。最小开销分配那么是在这种图上执行最小分割算法〔F.Harary1969〕来获得。例如，考虑由两个处理机P1，P2构成的分布式系统，提交的任务由6个模块{A，B，C，D，E，F}组成。相关的IMC开销和处理开销分别给出在图中的〔a〕和(b)中。根据这些信息，利用上述方法可以构造一个模块通信图〔见图2.2〕。为了表示处理开销，我们再给图2.2添加两个节点以表示两个可用的处理机P1和P2。在P1上运行的某个模块的开销〔即处理开销〕标在该模块节点到节点P2的连线上，在处理机P2上运行的某个模块的开销标在该模块节点P1的连线上，于是我们得到图2.2中双线所示，这就是在两个处理机上对给定模块的最小开销分配，容易看出，这种分配策略并没有实现处理机的负载均衡。AABCFED图2.2模块通信图模块模块ABCDEFABCDEF4001281230110500〔A〕模块通信开销表模块模块P1开销P2开销ABCDEF5102∞446352∞4〔B〕处理开销表算法的优点：这种分配策略的最大优点是它的简明性。主要缺点：所用的最小分割算法是一种根本的最小分割算法，它只能用于实现两个或三个处理机间的最小开销分配。假设将它扩充成处理任意个数的处理机，那么需n维〔n个处理机分配〕的最小分割算法，该算法是极其复杂的。这就限制了这种任务分配策略的应用范围；这种方面既未提供表示有关存储空间或处理时间等方面的限制手段，也没有提供负载均衡方面的机制；它没有能力去观察排队延迟效果。当一个以上的模块分配给同一处理机是，就不可防止地出现延迟。因此，基于图论的任务分配策略不是任务分配问题的最好解决方法。2.3.20～1程序设计谋略这种策略的主要思想是把任务分配问题概括成一种“优化问题〞，然后利用数学程序设计去解决它〔J.A.Stankovic1985〕。具体做法是：处理开销Q矩阵来表示，为了表示IPC开销，引进一个卷宗矩阵V和一个距离矩阵D，并用V与D之积替代的单个IMC开销矩阵C，利用卷宗矩阵：V={v},i=1,2,…,m;j=1,2,…,m来定义IMC，其中v表示从模块mi向模块mj发送的数据卷宗，假设v=0。那么表示模块mi和mj之间无数据交换。以图2.1所示的分布式系统为例，在这组处理机上定义的距离矩阵D为：D={d}k=1,2,…,n;h=1,2,…,n其中，n为处理机的个数；距离dk，h是处理机PK和Ph之间通信开销的一种度量。假设P和Ph之间毫无关系，那么令dk,，h=。我们可用距离度量来表示网络中处理机的互连状况。如果允许dk，h之值为非0，那么可用它表示同驻模块之间的通信开销，假定每对处理机间的距离是知道的而且是固定的。这种分配策略的目标函数T现在可定义为：T〔X〕=其中，第一项表示每个模块在它所分配的处理机上的处理开销；第二项那么是对用于表示IPC开销的“卷宗-距离〞元素之积求和；常量w用于调节处理开销和IPC开销，以补偿度量单位上的差异。负载均衡是通过施加假设干限制来实现的。我们主要考虑储存容量、处理机速度以及处理时间的实时要求等方面的限制。由于处理机速度已反映在处理开销矩阵Q中，因此，我们只讨论其他两方面限制。存储容量方面的限制可表示为其中si表示模块mi所需要的存储容量，Rk代表处理机Pk的存储能力。该式说明：分配给某个处理机的全部模块所需要的实际存储量的总和不能超过该处理机的存储能力。时实限制那么由下式表示：其中，ui表示模块mi所需要占用处理机的时间，RT代表位于处理机Pk上全部模块所需要的时间限制〔对于给定任务而言〕。该式说明：处理分配给某一处理机上全部模块所需要的时间的总量不得超过该处理机所规定的实时限制。在条件A和B的限制下，通过对T〔X〕极小化，我们就可以对任何给定的系统执行任务分配。这可以作为一个非线性的0～1整数程序设计问题来求解。这种非线性的0～1方程式可以通过添加进一步的条件而线性化，从而简化整个求解过程。当然，还可以采用其他求解方法，例如：采用近似求解法等。这种分配策略对任务分配环境提供了一种较好的表示方法，它也比较灵活，因为它所能适应地表示出某些限制条件。在基于图论的分配策略中实现这一点是不可能的。但它也存在以下缺点：它难以表示在实时条件限制下当前系统状态的作用；它也难以表示模块间数据流中优先关系的影响。因为这两种因素用一种复杂的方式将排队延迟引入了系统，所以对此需要进一步的研究。基于这方面的考虑，实时限制应变形为≤RT，k=1,2,3,……,n;I,j=1,2,….,m其中pi，,j表示模块mi和mj之间的优先关系，函数fi那么表示处理时间，包括在处理机Pk上处理模块mi是的排队延迟。“合一阈值〞启发式分配算法假定所依赖的分布式系统由多个同构的处理机经互连网络连接而成，其中的每个处理机都具有同等的处理能力。位于不同处理机的模块相互交换信息是通过它们所在的处理机彼此通信实现的。为简化讨论，我们忽略模块间的优化关系。所谓“合一〞是根据一定条件，将两个模块分配到同一处理机。这里的“阈值〞是指处理机所能接收并处理的最大模块数。“合一阈值〞算法是一种分两阶段进行任务分配的算法。第一阶段为“合一〞阶段。即对用户提交的一组模块进行合一处理，具体过程为：先查找其中这样一对模块，即把它们合一后将消除最大的IMC开销，然后检查经过这种合一处理后，相应的处理机是否满足实时和〔或〕存储方面的要求。假设满足，那么认为此次合一成功。否那么，选择下一对具有最大IMC开销的模块，重复前面的过程，直至完成一次成功的何以。再将合一后的模块对全局部配完毕或剩下的模块不能按此方式分配为止。最后将剩下的模块分配到同一处理机上。第二阶段为“调整〞阶段。它在第一阶段工作的根底上，根据各处理机上规定的阈值，对各处理机上的实际负载作必要的调整，即查看各处理机上的模块是否超越预定的阈值。假设均未超过，那么本阶段工作结束，该算法终止。否那么，将那些超过阈值的处理机上的模块迁移到尚未超过阈值的处理机上。评价：下面仅从算法的时空复杂性及算法的输出与最优解的差距等方面来简单地分析该算法。为此，假定有n个模块等待分配给m个同构的处理机。我们可用一个矩阵表示IMC开销，由对称行知，存储这方面的数据只需n〔n-1〕/2个单元。当完成了一次成功的合一后，修改相关模块的IMC开销后的信息用另一个矩阵存放，这也只需n(n-1)/2个单元。不难看出，合一过程采用的是一种局部“贪心〞策略，即每次查找一对这样的模块，它们经合一后不仅消除最大的IMC开销，而且相应的处理机应满足实时和〔或〕存储要求。假设令T〔n〕为合一过程最坏情况下的时间复杂性，那么不能得到下面的递推式：T〔n〕=查找具有最大IMC开销模块对的时间+修改其他模块对的IMC开销时间+T〔n-1〕显然T〔n〕≈O(n3)。假设经合一处理后剩下的模块数大于m，那么认为合一失败〔此时，不必进入“调整〞阶段〕。为此，可假定经合一处理后的模块数小于等于m。“调整〞阶段是“合一〞阶段的继续。在调整过程中，可用数组TV[1..m]存放各处理机的阈值，用load[1..m]存放各处理机上的实际负载。在合一过程中，很难知道别离出哪个模块〔或模块族〕可使得处理开销最小，故此采用“随机策略〞。在此，不妨把调整过程进一步描述为：〔1〕计算各处理机的实际负载与其阈值之差Di，i=1，2，…，m；〔2〕按Di的不增次序排序各处理机，并用j(1，2，…，m)指称经排序后位于序号j处的处理机；〔3〕对于j=1，2，…，m-1执行下面的操作：“向上迁移策略〞假设处理机j的Di大于0，那么用随机方法从处理机j上选定一模块〔或模块族〕并把它迁移到处理机j+1上。重复此过程，直至处理机j的Dj不大于0。必要是，可对模块族进行分裂。假设处理机j的Dj不大于0，那么不做任何迁移工作。〔4〕处理机m的Dm不大于0,那么报告“失败〞，否那么调整成功。以上分析可以看出，由于“合一〞过程采用的是局部“贪心〞策略，因此，不一定能实现最优分配。而“调整〞过程采用随机方法选定迁移的模块，从而带有一定的盲目性。但是成功的合一处理可以减少系统中处理机见的通信开销，而成功的“调整〞过程有尽可能的合一处理机的负载到达根本均衡，有利于提高系统的吞吐量，而且该算法具有较低的时空复杂性，实现过程也比较机械、简单，因此，仍不失为一种可行的方法。第三章一种新的基于并行遗传算法的策略提出及可行性分析3.1遗传算法概述遗传算法最早是由美国Michigan大学的Holland提出的，这种算法模拟达尔文的进化论创立的，它模拟生物遗传进化的过程，引入选择、复制、交叉重组和变异等方法，并将进化论中“物竞天择，适者生存〞的概念，引入到算法中，是一种借鉴生物界自然选择和自然遗传机制的高度并行的、随机的、自适应搜索算法，是一种概率搜索算法，它利用某种编码技术作用于称为染色体的二进制串，其根本思想是模拟由这些串组成的群体的进化过程，遗传算法通过有组织地然而是随机的信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串的结构中适应性好的位和段来生成一个新的串的群体，作为额外添加，偶尔也要在串的结构中尝试用新的位和段来代替原来的局部。遗传算法是一种随机算法，但它不是简单的随机游走，它可以有效利用已有的信息来搜索那些有希望解质量的串。类似于自然进化，遗传算法是通过作用于染色体上的基因寻找好的染色体来寻求解问题，与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应值好的染色体比适应值差的染色体有更多的繁殖时机。在生物界，一个生物群体中个体之间的差异是由包含在生物体内的染色体之间的差异来表达的，这种差异即反映在生物体自身的结构上也反映在它们所处环境的行为上；反过来，结构与行为的不同又表现在它们生存与繁殖率的不同。在环境中，性能好的生物体〔更适应的个体〕具有更高的生存与繁殖率；反之，生存与繁殖率那么较低。经历假设干代之后,就整体而言，生物群体逐渐包含了更多的个体，其染色体的结构在环境中表现出更加优良的性能。这样，随着时间的推移，群体中个体的结构由于自然选择而发生变化。这种由于适应性导致的结构上的差异就是进化的结果。这就是达尔文在?物种起源?一书中描述的适者生存和自然选择的概念。关于进化理论的一般特性已广为人们所接受：进化过程发生在染色体上，而不是发生在它们所编码的生物体上自然选择把染色体以及由他们所译成的结构的表现联系在一起，那些适应性好的个体的染色体经常比差的个体的染色体有更多的繁殖时机。繁殖过程是进化发生的那一刻，变异可以使生物体子代的染色体不同于他们的父代的染色体，通过结合两个父代染色体的物质，重组过程可以在子代中产生很大的差异。生物的进化没有记忆，有关产生个体的信息包含在个体所携带的染色体的集合以及染色体的编码的结构之中，这些个体会很好的适应它们的环境。遗传算法是一种高度并行的数学算法，它使用以遗传操作为模式的数学操作将一组数学对象，通常是以染色体串为模式的定长字符串群体〔每个串都具有一个适应度〔Fitness〕〕，转换为新一代群体。通常，任何抽象的问题都可以认为是求解一个问题，而问题求解又可看成对解空间的搜索。由于我们总是希望寻求“最正确〞的解，因此可把求解过程当作一个优化过程。对于小空间，经典的穷举搜索方法足以解决问题；然而对较大空间，就需要采用自适应的、智能的搜索技术。遗传算法正是这种模拟自然界生物进化过程的自适应寻优技术，它的主要应用领域是复杂的非线性优化问题。尽管遗传算法可归类为概率算法，但它不同于随机算法，它把定向搜索与随机搜索有机地结合起来；正因如此，遗传算法也强于已有的定向搜索算法。遗传算法的另一个重要的特性是使用一个潜在解的群体来搜索解空间。其他方法，一般总是使用单点来搜索空间，这些算法非常依赖于起始点的选择，经常给出局部优化的点，与此相对照，遗传算法保持一个潜在解的群体实现了多个方向上的搜索，同时，在搜索过程中鼓励不同方向上信息的结合和交流。群体经历了一个模拟进化过程：在每一代，较好的解“繁殖〞，较差的解“消亡〞。在这个过程中起关键作用的目标函数〔适应函数〕用于区别解的优劣。3.2遗传算法的结构一般说来，解决一个具体问题的遗传算法由下述五个局部组成：制定问题的潜在解的遗传表示；创立潜在解的初始群体的方法；评估解的适应度的计值函数〔适应函数〕；改变子孙结构的遗传操作；算法适用的各种参数、变量及终止条件等。经典遗传算法的表示模式是将问题搜索空间中的每一个点表示为定长字符串，即字母表K上长度为L的字符串，确定染色体串与空间点之间的映射关系有时是显而易见的，有时那么非常困难，需要对问题有深刻的认识和正确的判断。适应度计算为群体〔种群〕中的每个定长字符串赋予一个适应度的值，赋值方式通常是问题所固有的；改变子孙结构的遗传操作主要有复制〔Reproduction，也称繁殖〕、交叉〔Crossover，也称交配〕和变异〔Mutation〕，而控制遗传算法的参数包括群体的大小〔种群规模〕，进化过程的最大代数以及控制各种遗传操作的概率等。经典遗传算法的执行步骤如下：(1)[开始(Start)]随机创立由N个染色体组成的初始种群(2)[适应度(Fitness)]为种群中的每一个染色体x计算适应度f(x)，其中f(x)为适应函数(3)[产生新的种群(Newpopulation)]循环进行下述各步，直到新的种群创立结束 ①[选择〔selection〕]根据适应度〔适应度越好，被选中的概率就越大〕选择两个父代染色体 ②[交叉〔Crossover〕]根据交叉率，对父代染色体进行交配，从而产生新的子代个体。如果不进行交配，那么子代即为父代的一个拷贝。③[变异〔Mutation〕]根据变异率，对新的子代个体进行变异操作④[接收〔Accepting〕]新的子代成为新的种群中的个体(4)[替换(Replace)]新产生的子代种群成为下一次计算的父代(5)[测试(Test)]如果满足终止条件，那么停止，并返回当前种群中的最好个体(6)[循环(Loop)]转第(2)步上述遗传算法的组成与执行过程，说明了这是一种与问题领域无关的方法，它可以解决大量的不同方面的问题。我们应用遗传算法要考虑如下的问题。首先要考虑的问题是如何创立染色体，选择什么样的编码方式。它与交叉和变异两种遗传算法的根本操作密切相关。其次，是在进行交叉前如何选择父代染色体。这有许多方法，但主要的思想是选择较优的染色体〔寄希望于好的父代产生好的子代〕。但新的种群如果只由新的子代个体组成可能会导致在新的种群中失去最优的染色体。因此，经常用到精英理论〔elitism〕。这意味着，有少数〔至少一个〕当前的最优个体不加改变地被复制到下一代，这样使得最优个体能够存活到算法的运行结束。3.3并行化的目的遗传算法的模仿自然界生物遗传和进化过程中的“物竞天择、适者生存〞的原理而开发出的一种多参数、多个体同时优化方法。经过三十多年的开发研究和应用实践，遗传算法初步显示出了其解决复杂系统优化问题的良好能力，特别是对一些NP组合优化问题的求解，更表现出了优异的性能。如今，遗传算法已经在旅行商问题的求解、生产调度、图形划分、函数优化、机器学习等众多领域中得到了成功的应用，并显示出良好的性能。标准的遗传算法以个体的集合为运算对象，对个体所进行的各种遗传操作都有一定的相互独立性，所以它具有一种天然的并行结构。一方面，虽然遗传算法对一个个体编码串的搜索意味着它同时搜索了多个个体模式，即对个体结构模式的处理具有并行的含义，但这个并行性是一个隐含的并行性，其运行过程及实现方法在本质上仍是串行的。这种串行的遗传算法在结局一些实际问题是，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以到达计算速度上的要求，因而遗传算法的并行计算问题就受到了较大的重现。另一方面，由于遗传算法的天然并行性，人们认识到了对起进行并行处理的可能性，从而基于各种并行计算机或局域网，开发出了多种并行遗传算法〔ParallelGeneticAlgorithm,简称PGA〕。开发并行遗传算法的主要目的是为了提高遗传算法的运行速度，开发和应用实践说明，各种并行遗传算法都能不同程度地到达这个要求。3.4并行性分析Goldberg归纳出了根本遗传算法模型，它是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体〔候选解〕，这个迭代过程直到满足某些结束条件为止。对应于根本遗传算法的运行过程，为实现其并行化的要求，如下图，可以从下面四种并行性方面着手对其进行改良和开展。初始群体循环：个体适应度评价循环：个体选择运算循环：染色体变异运算循环：染色体交叉运算进化结果？算法结果并行性Ⅰ并行性Ⅱ并行性Ⅲ并行性ⅣYESNO图3.遗传算法的并行机制图1．并行性Ⅰ：个体适应度评价的并行性个体适应度的评价或计算在遗传算法的运行过程中所占用的运行时间比较长。通过对个体适应度并行计算方法的开发研究，可找到并行评价个体适应度的算法，从而提高个体适应度评价的计算效率。这种并行性的实现可能性及计算效率取决于个体所有制适应度函数的具体表达形式，依赖于各种数值并行算法的研究进展和开发成果。2．并行性Ⅱ：整个群体中各个个体适应度评价的并行性群体中各个个体的适应度之间无相互依赖关系，这样各个个体适应度的评价或计算过程就可以相互独立、相互并行地进行，即不同个体的适应度评价或计算过程可以在不同的处理机上同时进行。行性Ⅲ：子代群体产生过程的并行性在从父代群体产生下一代群体所需要的遗传运算中，选择操作只与个体的适应度有关，这样，产生子代群体的选择、交叉、变异等遗传操作就可以相互独立地并行进行。并行性Ⅳ：基于群体分组的并行性从总体上来说，遗传算法的操作对象是由多个个体所组成的一个群体。从原理上讲，多个这样的群体应该能共用同一个遗传算法。换一种说法，同一个遗传算法应该可以同时处理多组群体。这些多组群体可看做是由一个大的群体划分而成的，假设把它们及对它们进行进化处理的遗传算法分别置于不同的处理机上，肯定能够提高运行效率。也就是说，可以对群体按一定的方式进行分组，分组后的耽误或一组个体的遗传进化过程可以在不同的处理机上相互独立地进行，在适当的时候，各处理机〔各组个体〕之间再一适当的方式交换一些信息。即不同个体不同组个体的遗传进化过程是并行进行的。在上述四种并行方式中，前三种方式并未从总体上改变简单遗传算法的特点，仍然是从统一的角度出发对群体中的全部个体进行选择、交叉、变异等遗传运算；而第四种方式却对简单遗传算法的结构有较大的改变，并且这种方式也符合自然界中生物群体进化行为，是一种最自然的并行方式，在并行机或局域网环境下实现起来也最简单，所以受到了人们较大的重视。目前已开发出的并行遗传算法根本上都是基于上述四种并行机制或其组合来实现的。3.5并行算法与并行计算机系统1．并行遗传算法执行方案遗传算法的研究从一开始就是基于并行处理，早在六十年代初期，Holland就认识到了遗传算法的自然并行性及其并行处理的内在有效性。目前，人们正不断地致力于把遗传算法应用到各种并行计算机上，下面介绍三种根本的并行实现方案。同步主从式遗传算法的主从式并行执行方案如图所示，一个主过程协调k个从过程，主过程控制选择，杂交和变异的执行，从过程只执行对函数值的计算。这是一种直接并行化方法，实现起来比较容易，然而它有一个缺点：如果函数值计算的时间之间有显著的差异，系统就会有相当长时间的等待；算法不是非常可靠，因为它依赖于主过程的状况，如果主过程不是向前演化，整个系统就会停止不前。GA函数求值函数求值函数求值图遗传算法的主从式并行执行图〔二〕异步同时式遗传算法的异步同时式并行执行方案如图所示，通过存取一个共享存储器，k个同样的处理机彼此无关地执行遗传算子和函数值计算。这种方案不是那么容易实现，但大大提高了系统的可靠性。只要并行进程中有一个以及共享存储器的某局部在继续运行，整个系统就还在执行有用的处理。并行进程并行进程共享存储器并行进程并行进程并行进程并行进程并行进程并行进程并行进程图遗传算法的异步同时式并行执行图网络式网络式遗传算法的并行执行方案如图所示，在这种方案中，k个无关的遗传算法分别在独立的存储器，独立的遗传操作及独立的函数值计算下运行，在运行过程中，各个子群体在每一代中发现的最好的个体通过通讯网络被传送到其他的子群体中去。由于有通讯时的间断，与其他方案相比连接带宽减小了。因为其独立过程的自治性，这种方案的可靠性是很高的。GAGAGAGAGAGAGA图网络式遗传算法的并行执行2．并行遗传算法的硬件支持环境迄今用来实行并行遗传算法的并行机种类很多，既可用粗粒度的并行计算机〔如Transputer网络〕，也可用细粒的并行计算机；既可以在多指令流、多数据流MIMD机器上实现，也可以在单指令流、多数据流SIMD机器上实现；另外，也可在局域网环境中实现并行遗传算法。针对某一具体应用问题，到底选用哪种硬件环境，这取决于所使用的并行化方法。例如，如果要使用统一的全局群体，那么可使用具有共享存储器的多处理机系统作为其实现环境。如果群体被划分得很小，就要使用细粒度的并行机；如果群体被划分的较粗，就要使用粗粒度的并行机。3.6并行搜索与最优化§并行搜索考虑下面的优化问题：给定函数F：XR，其中X是某一度量空间，设S是X的一个子空间，在S中找一点X满足：在S是最优化F或至少产生一个在S上关于F的上确界的可接受近似。解这个问题的最优化方法有许多种，这里只讨论并行最优化算法，它的特征是具体有N条不同的搜索轨道，并且这些搜索是并行执行的，可以描述为：x=G(x,…,x,F(x),…,F(x)),i=1,2,…,N映射G=〔G1，……，GN〕描述了并行搜索之间的相关或信息交换。如果N个搜索是彼此独立的，那么有:x=G(x,F(x)),i=1,2,…,N一个二相关搜索可以描述为x=G(x,x,F(x),F(x)),i=1,2,…,N关于并行搜索算法，存在下面一些根本问题：时间复杂性为t的N并行搜索是否与时间复杂性为的单搜索一样有效；N相关搜索是否比N无关搜索更有效；如何建立这种相关搜索。§并行遗传算法的形式描述通过采用空间群体结构和活动的个体，我们得到了一种完全异步的并行遗传算法，它可以是形式地描述为:PGA=(P,λ,μ,δ,τ,GA,Λ，t)其中：P——初始群体；λ——子群体数目；μ——子群体中的个体数；δ——子群体间的相邻连接数；τ——孤立时间；GA——应用到子群体上的遗传算法；Λ——局部最优化算法；t:{0,1}λ|->{0,1}——停止准那么.下面称遗传算法GA在一个子群体PI0上的应用为一个演化过程GA〔P〕，i∈{1，…，λ}，k=1，2，…。每个子群体被映射到不同的处理机上，下面的定义包括特殊情形μ=1，即每个子群体仅包含1个个体。处理机之间采取的是一个类似与梯形的连接形式。PGA允许各个子群体独立演化一定的时间，这个孤立时间是由代数给出的。相邻群体间的移动发生在代τ，2τ，3τ…，这时把每个子群体中最好的个体传送到相邻的子群体中去。停止准那么τ作用在一组由演化过程GA〔P〕产生的停止信号上，当所有λ个停止信号都出现是，PGA就被停止执行。§遗传算法〔GA〕可以形式地描述为：PGA=(P,μ,Q，г,⊿,Θ,l,Λ，ι)其中：P0为初始群体；μ是群体规模；Q是选择算子；T是交换算子；⊿是变异算子；Θ是重组算子；Λ为局部爬山法；l是判定何时转去爬山的准那么；τ是停止信号；算子Q，T，⊿和Θ都采用概率分布。下面给出对遗传算法更具体的描述，考虑优化问题：min{f(x)|xX}X<b,

这里f不必是凸的、可微的、连续的或单峰的。选择选择算子下面方式进行，在算法的每个阶段，按f(y)增加的顺序对群体P={y,…,y}中的个体进行排序。首先选择具有奇下标的个体y，i=1，3，…，然后相应地选择与之配对的个体，其下标i是通过下面的非线性变换随机产生的：i=(c-)其中c为偏项参数，这里取c=2.5，rnd(0,1)记为〔0，1〕间一致分布的随机变量，每个交配对产生2个子代个体，因此仅需选择μ/2对。上面的选择方法既偏向选择好的个体，又不致破坏群体的多样性。另外，在算法中还采用了最优选择，即把P中最好的个体保存到P中。变异、交换和重组选择完成后，就把遗传算子⊿，T和Θ作用到两个被选择的个体y和yk上，为了说明遗传算子的作用效果，首先来看个体的编码表示，它是由n个二进制串构成的，其中每个二进制传g采用的是计算机的浮点格式SEXPFRACSEXPFRAC串g的值p为:p=(-1)╳1*FRAC╳2在单精度情况下，串g长为32位，其中s为1位，EXP为8位，FRAC为23位，BIAS在使进制小等于127。PGA的变异算子⊿的作用过程如下，对于个体y=〔y1，……，y〕,以概率pm随机地改变每个分量yi的编码表示中FRAC上的每一位，并且，如果搜索空间关于原点的对称的，那么也以概率pm改变编码表示的S位。对于变异后的个体y=〔y，…，y〕和yk=〔y，…，y〕，交换算子T的作用过程如下，首先在每对分量y和y的编码表示上随机地选取一位，然后把y中的这一位以概率pr和y的对应位互换。重组算子Θ以概率pr交换y和y中每个对应的分量。下面以二维向量为例说明遗传算子的作用过程：父代串1父代串2ABab1010011010111100↓1010变异0111101111000101↓交换10100111101101100101↓重组10100111111000110101AbaB局部爬山法应用局部爬山法的主演目的是为了加快算法的搜索速度，在函数最优化问题中，计算一个新的样本点的函数值等价于爬山法中的一步，由于在搜索过程的早期还没有得到关于全局极小值的信息，所以此时应用爬山法是得不偿失的，故在PGA中，通常，我们在算法的后阶段采用爬山法。做出开始采用爬山法的决定是动态运行的，如果下面两个条件中有一个满足，那么就从这个子群体中选择一点作为爬山法的初始点：f-f=0||x-x||≤||b-a||fik是xik点的目标函数值,i{1,…μ}，其中下标i是按目录函数值从小到大排列得到的。停止准那么PGA是一种完全分布式算法，在分布式算法中，停止问题是很难判定的，PGA中的全局终止由主程序来决定。每个过程GA〔Pik〕设置一个停止信号，如果满足下面的判别准那么，就把这个停止信号送到主程序中去：|f-f|≤|f|这个判别准那么每隔△k2代检查一次，当主程序接到所有λ个停止信号，就停止执行PGA。§并行遗传算法形式化地定义并行遗传算法可以形式化地定义一个6元组：PGA=(DMM,X,Z,△,Θ,SGA)式中，DMM——实现并行遗传算法的并行机或局域网中各处理器Pi所组成的集合，即：DMM={p|}X－－各处理器的信息交换对象所组成的集合。假设与处理器Pi可以互相交换信息的处理器的集合为Xi的话，那么有Xi∈X;Z－－信息交换的内容；Δ－－进行信息交换的时间间隔或频率；Θ－－信息交换时的个体替代操作算子；SGA－－各处理机上运行的根本遗传算法。基于群体分组的并行遗传算法的运算过程是：各个处理机运行各自的根本遗传算法，对它自身所带的存储器中的M/p个个体进行遗传进化操作；当到达一个预先指定的信息交换时间T时，每个处理机pi发送需要交换的信息Z到其信息交换对象Xi;同时，它也接受来自于Xi的信息，用该信息来替换本处理机上的某一个或某一些个体。上述过程不断地迭代进行，直到满足某个终止条件为止。假设将处理机pi中的第t代子群体记为集合Pi(t)，那么运行为在处理机pi上的这种并行遗传算法可用下述伪代码来描述。ProcedurePGAProcedurePGAibeginInitializePi(0);t=0while(t<T)dofori=1toM/pdoEvaluatefitnessoflocalPi(t);endforfori=1toM/pdoSelectoperationtolocalPi(t);endforfori=1toM/P/(2p)doCrossoveroperationtolocalPi(t);endforfori=1toM/pdoMutationoperationtolocalPi(t);endforif(△isreached)thenforeachPj∈XidoSendZktopjReceiveZjfrompjendforPi(t+1)=Θ[Z1,Z2,…,Zp]endift=t+1;endwhileend3.7解决任务的分配与负载均衡问题的优势遗传算法是一种更为宏观意义下的仿生算法，它模仿的机制是一切生命与智能产生与进化过程，它通过模拟达尔文进化原理鼓励产生好的结构，通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为一种随机优化和搜索算法具有如下特点：遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码遗传算法的操作对象是一组可行解，而非单个可行解，搜索轨道有多条，而非单条，因而具有良好的并行性，高适应度、定义长度短的模式会按指数增长的方式从一代传播到下一代，且都是并行执行的，这种隐含的并行性使之非常适合于大规模并行处理计算机，也是该算法优于其他算法的主要因素。遗传算法只需利用目标函数的取值信息，而无须梯度等高阶信息，因而适用于大规模、高度非线性的不连续多峰函数优化及无解析表达式的目标函数的优化，具有很强的通用性。遗传算法的择优机制是一种“软〞决策，具有良好的全局优化性能和稳健性。算法利用概率转移规那么，而非确定性规那么遗传算法在搜索过程中不容易陷入局部最优，而即使在定义的适应函数不连续、非规那么、或有噪声的情况下也能以很大的概率找到整体最优解。通常情形下，在处理机或节点机的数目大于3的多机系统或分布式系统中的任务分配问题是一个NPC问题，人们一般不会去寻求解决问题的最优解，但对于具体的分布式系统，由于资源的冗余和分布式的特点，系统存在相当的硬件并行性，为我们开发并行性奠定了物质根底。计算理论告诉我们并行性不可能自然地得到，需要硬件设计者和软件程序员共同努力开发并行性来提高计算机的性能。由以上分析，知道对应于根本遗传算法的运行过程，存在4个不同层次的并行性。使我们可以根据具体应用在不同层次上开发软件的并行性。用遗传算法来解决任务分配问题，就是利用并行计算机系统的优势，将一个遗传程序分布并行执行，来提高程序的执行速度。算法建模与设计及针对机群应用环境的具体实现4.1和任务分配及调度相关的概念为了实现负载的平衡，必须解决两个根本问题：一个是负载的识别，另一个是负载的分布，尤其是动态负载的重分布。负载识别是负载平衡的前提。只有识别出各个计算节点的负载状况，负载平衡的策略才有工作的根底。§处理能力1.节点机的处理能力:DD=F(f,c,m,α,l，O)f:处理器的主频因子或时钟速率c:cachef:处理器的主频因子或时钟速率c:cache大小因子m:存储器容量因子α:系统结构因子l:机器字长因子O：其它因素目前，对计算机的性能评价变得越来越复杂了，人们所熟知的一些方法如：指令混合、PDR指数等，只能反映系统的局部能力，主要是CPU的处理能力，不能反映整个系统的处理能力，不能反映操作系统的水平、数据库的功能、系统的分时处理能力、通信功能等，也不能反映一个系统在不同环境中应用的效率。在此节点机的处理能力主要指CPU的处理能力，上述各个因素对系统的性能均有影响，但没有一个确定的函数关系。上式仅是示意表示。通常，基准程序是性能测试程序，并假设其能刻画某一类应用问题的处理和数据移动的特征，基准程序用来测量和预测计算机的系统的性能，并能提示他们的体系结构的弱点和优点。它可以分为：宏基准程序和微基准程序两类。类型名称类型名称测量微基准测试程序LINPACKLMBENCHSTREAM数值计算UNIX系统调用和数据移动存储带宽宏基准测试程序NASPARKBENCHSPECSPLASHSTAPTPC并行计算并行计算混合基准程序并行计算信号处理商业应用在我